🤖 machine learning

Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)

यह शोध पत्र संकुचित ऑनलाइन उत्तल अनुकूलन (constrained online convex optimization) में OGD+प्रोजेक्शन एल्गोरिदम के लिए संचयी बाधा उल्लंघन (cumulative constraint violation) पर $\Omega(T^{\frac{d-1}{2d}})$ का पहला निचला स्तर (lower bound) स्थापित करता है, जो यह प्रदर्शित करता है कि इसका प्रदर्शन समस्या की आयामीता (dimensionality) द्वारा मौलिक रूप से सीमित है।

मूल लेखक: Haricharan Balasundaram, Karthick Krishna Mahendran, Rahul Vaze

प्रकाशित 2026-07-14

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Haricharan Balasundaram, Karthick Krishna Mahendran, Rahul Vaze

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप "कॉन्स्ट्रेंड ऑनलाइन कॉनवेक्स ऑप्टिमाइज़ेशन" (Constrained Online Convex Optimization) नामक एक उच्च-दांव वाला वीडियो गेम खेल रहे हैं। इस खेल में, आप एक बहादुर खोजकर्ता (सीखने वाला/learner) हैं जो एक अंधेरे, बदलते हुए भूलभुलैया (maze) में रास्ता खोजने की कोशिश कर रहा है। हर मोड़ पर, आपको खड़े होने के लिए एक जगह चुननी होती है (आपका "एक्शन")। जैसे ही आप अपनी जगह चुनते हैं, खेल दो चीजें प्रकट करता है: एक "लॉस" (कितना स्कोर आप वहां खड़े होने के लिए खो देते हैं) और एक "कन्स्ट्रेंट" (एक नया अदृश्य दीवार जो कहती है, "आपको इस रेखा के गलत तरफ नहीं होना चाहिए")।

आपका लक्ष्य दोहरा है:

रिग्रेट (Regret) को कम करना: बहुत अधिक अंक न खोएं यदि तुलना एक सुपर-स्मार्ट चीट-शीट खिलाड़ी से की जाए जिसे खेल शुरू होने से पहले ही सभी दीवारों और स्कोर ट्रैप्स का पता था।
कन्स्ट्रेंट उल्लंघन (Constraint Violation - CCV) को कम करना: आप दीवारों के गलत तरफ कितनी देर खड़े रहते हैं, इसमें बहुत अधिक समय न बिताएं। यदि आप ऐसा करते हैं, तो आप "उल्लंघन अंक" (violation points) जमा कर सकते हैं।

लंबे समय तक, सबसे अच्छी रणनीति जिसे हर कोई जानता था, वह थी OGD+Projection। यह एक रोबोट की तरह है जो पिछले स्कोर के आधार पर एक कदम आगे बढ़ता है, फिर तुरंत खुद को सुरक्षित क्षेत्र के अंदर वापस "प्रोजेक्ट" (बाउंस) करता है यदि वह गलती से बाहर निकल जाता है।

बड़ा सवाल: रोबोट कितना बुरा हो सकता है?

वैज्ञानिकों ने यह पता लगाने की कोशिश की है कि इस रोबोट का सबसे खराब परिदृश्य (worst-case scenario) क्या है। वे पहले से जानते थे कि रोबोट अपना स्कोर लॉस कम रख सकता है (लगभग $\sqrt{T}$ , जहाँ $T$ कुल टर्न की संख्या है)। लेकिन उसके उल्लंघन अंक (violation points) के बारे में क्या?

पिछले शोध ने दिखाया कि 2D भूलभुलैया के लिए, रोबोट के उल्लंघन अंक धीरे-धीरे बढ़ते हैं, जैसे $T^{1/3}$ । किसी भी आयाम (dimension $d$ ) वाली भूलभुलैया के लिए, अनुमानित सबसे खराब उल्लंघन $\sqrt{T}$ के आसपास था।

इस पेपर की मुख्य खोज: लेखकों ने सिद्ध किया कि OGD+Projection रोबोट वास्तव में एक विशिष्ट मात्रा में उल्लंघन अंक जोड़ने के लिए मजबूर है, चाहे आप भूलभुलैया को कितनी भी चतुराई से डिज़ाइन करें। उन्होंने दिखाया कि $d$ आयामों वाली भूलभुलैया में, उल्लंघन अंक कम से कम $T^{\frac{d-1}{2d}}$ की दर से बढ़ेंगे।

द "इम्पॉसिबल मेज़" कंस्ट्रक्शन (असंभव भूलभुलैया का निर्माण)

इसे सिद्ध करने के लिए, लेखकों ने केवल अनुमान नहीं लगाया; उन्होंने एक विशेष, कष्टदायक भूलभुलैया बनाई जो रोबोट को धोखा देने के लिए डिज़ाइन की गई थी। कल्पना कीजिए कि भूलभुलैया संकेंद्रित गोलों (concentric spheres - जैसे प्याज की परतें) से बनी है जो गहराई में जाने पर थोड़ी छोटी होती जाती हैं।

परतें (Layers): भूलभुलैया में $M$ परतें हैं। प्रत्येक परत में, एक घेरे (या उच्च-आयामी गोले) में व्यवस्थित कई "सुरक्षित स्थान" (safe spots) हैं।
जाल (The Trap): खेल एक नई दीवार (कन्स्ट्रेंट) प्रकट करता है जो ठीक एक सुरक्षित स्थान को काट देती है।
रोबोट का धर्मसंकट: रोबोट सुरक्षित स्थान पर खड़ा है। दीवार दिखाई देती है। रोबोट को सुरक्षित रहने के लिए अगले सुरक्षित स्थान पर जाना चाहिए। लेकिन क्योंकि दीवारें एक विशिष्ट, घूमते हुए पैटर्न में दिखाई देती रहती हैं, रोबोट को छोटे, अक्षम कदम उठाने के लिए मजबूर किया जाता है।
घूर्णन (Rotation): लेखकों ने एक चालाक गणितीय ट्रिक (रोटेटिंग वेक्टर्स का उपयोग करके) का उपयोग किया ताकि यह सुनिश्चित हो सके कि रोबोट का पथ गोले के चारों ओर घूमे, और हर बार एक नए "कट" (cut) से टकराए।

लेखकों ने सिद्ध किया कि इस विशिष्ट सेटअप में, रोबोट सीमाओं से बाहर जाने से बच नहीं सकता है। हर बार जब एक नई दीवार आती है, तो रोबोट को एक सूक्ष्म मात्रा में बाधा का उल्लंघन करने के लिए मजबूर किया जाता है। जब आप पूरे खेल में इन सूक्ष्म उल्लंघनों को जोड़ते हैं, तो कुल योग ठीक उसी दर से बढ़ता है: $T^{\frac{d-1}{2d}}$ ।

यह "सर्वश्रेष्ठ" एल्गोरिदम के बारे में क्या बताता है

यह परिणाम एक "लोअर बाउंड" (lower bound) है। इसे एक स्पीड लिमिट साइन की तरह समझें जो कहता है, "आप 50 मील प्रति घंटे से धीमी गति से नहीं जा सकते।" यह पेपर सिद्ध करता है कि OGD+Projection एल्गोरिदम इस विशिष्ट उल्लंघन दर से बेहतर नहीं कर सकता (जैसे $O(1)$ या कुछ बहुत छोटा)।

यह क्या खारिज करता है: यह इस उम्मीद को खारिज करता है कि OGD+Projection एक "परफेक्ट" एल्गोरिदम है जो किसी भी प्रकार की भूलभुलैया के लिए बहुत कम उल्लंघन दर (जैसे $O(1)$ ) प्राप्त कर सकता है। यह पेपर दिखाता है कि कुछ पेचीदा भूलभलैयाओं के लिए, रोबोट मौलिक रूप से सीमित है।
यह क्या पुष्टि करता है: यह पुष्टि करता है कि पिछले अपर-बाउंड अनुमान (सबसे अच्छे मामले के परिदृश्य) केवल ढीले अनुमान नहीं थे; वे वास्तव में सच के करीब थे। एल्गोरिदम उतना ही अच्छा कर रहा है जितना कि वह संभव है, समस्या की ज्यामिति (geometry) को देखते हुए।

वे कितने आश्वस्त हैं?

लेखकों ने केवल कंप्यूटर सिमुलेशन नहीं चलाया या यह सुझाव नहीं दिया कि यह सच हो सकता है। उन्होंने एक कठोर गणितीय प्रमाण (rigorous mathematical proof) प्रदान किया। उन्होंने सटीक भूलभुलैया का निर्माण किया, रोबोट के सटीक कदमों को परिभाषित किया, और उल्लंघन बिंदुओं की सटीक गणना की।

उन्होंने दिखाया कि किसी भी आयाम $d \ge 2$ के लिए, एक ऐसी स्थिति मौजूद है जहाँ उल्लंघन $\Omega(T^{\frac{d-1}{2d}})$ है। $\Omega$ का प्रतीक अर्थ है "कम से कम इतना"।

इसलिए, यदि आप 2D दुनिया ( $d=2$ ) में खेल रहे हैं, तो उल्लंघन कम से कम $T^{1/4}$ है। यदि आप 3D दुनिया ( $d=3$ ) में हैं, तो यह कम से कम $T^{2/6}$ (जो $T^{1/3}$ में सरल होता है) है। जैसे-जैसे आयाम बढ़ते हैं, घातांक (exponent) $1/2$ के करीब पहुँच जाता है, जिसका अर्थ है कि रोबोट को नियमों के भीतर रहने के लिए अधिक मेहनत करनी पड़ती है।

निष्कर्ष (The Takeaway)

यह पेपर एक छिपे हुए स्पीड बंप को खोजने जैसा है जिसे हर कोई एक चिकना हाईवे समझ रहा था। यह हमें बताता है कि "OGD+Projection" रोबोट, जो बहुत अच्छा है, उसकी एक कठिन सीमा है कि वह सबसे खराब मामलों वाले कन्स्ट्रेंट्स को कितनी अच्छी तरह संभाल सकता है। यह परफेक्ट नहीं हो सकता। लेखकों ने गणितीय रूप से सिद्ध किया है कि $d$ आयामों वाली दुनिया में, संचयी कन्स्ट्रेंट उल्लंघन (cumulative constraint violation) हमेशा कम से कम $T^{\frac{d-1}{2d}}$ की दर से बढ़ेगा। यह पहली बार है जब ऐसा एक सीमा (limit) सिद्ध किया गया है, जो उस अंतर को पाटता है जो हम उम्मीद कर रहे थे और जो गणितीय रूप से अनिवार्य है।

तकनीकी सारांश: OGD+प्रोजेक्शन एल्गोरिदम के लिए संचयी बाधा उल्लंघन (Cumulative Constraint Violation) पर निचली सीमा (Lower Bound)

समस्या विवरण
यह शोध पत्र कंस्ट्रेंड ऑनलाइन कॉन्वेक्स ऑप्टिमाइज़ेशन (COCO) की समस्या को संबोधित करता है। इस सेटिंग में, एक ऑनलाइन लर्नर $T$ राउंड के दौरान कार्य करता है। प्रत्येक राउंड $t$ पर, लर्नर एक उत्तल फिक्स्ड सेट (convex feasible set) $X \subset \mathbb{R}^d$ से एक एक्शन $x_t$ चुनता है। तत्पश्चात, एक एडवर्सरी (adversary) एक उत्तल लॉस फंक्शन $f_t$ और एक उत्तल कंस्ट्रेंट फंक्शन $g_t$ प्रकट करता है। लर्नर $f_t(x_t)$ का लॉस और यदि $g_t(x_t) > 0$ हो, तो कंस्ट्रेंट उल्लंघन (constraint violation) का सामना करता है। इसका उद्देश्य एक स्टैटिक बेंचमार्क $x^\star$ (जो भविष्य के सभी फंक्शन्स को जानता है और एक व्यवहार्य एक्शन $g_t(x^\star) \le 0$ चुनता है) की तुलना में दो मेट्रिक्स को एक साथ कम करना है:

स्टैटिक रिग्रेट (Static Regret): लर्नर के संचयी लॉस और बेंचमार्क के बीच का अंतर।
संचयी कंस्ट्रेंट उल्लंघन (Cumulative Constraint Violation - CCV): कंस्ट्रेंट उल्लंघनों के धनात्मक भागों का योग, $\sum_{t=1}^T \max(g_t(x_t), 0)$ ।

यह शोध पत्र विशेष रूप से OGD+Projection एल्गोरिदम (वाज़ और सिन्हा, 2025 द्वारा प्रस्तावित) पर केंद्रित है, जो एक ऑनलाइन ग्रेडिएंट डिसेंट (OGD) स्टेप के बाद अब तक प्रकट किए गए सभी कंस्ट्रेंट सेट्स के इंटरसेक्शन पर प्रोजेक्शन करता है। जबकि इस एल्गोरिदम के लिए अपर बाउंड्स (upper bounds) ज्ञात हैं, इसके CCV के संबंध में लोअर बाउंड (lower bound) स्थापित नहीं किया गया था।

कार्यप्रणाली और निर्माण (Methodology and Construction)
लोअर बाउंड प्राप्त करने के लिए, लेखक COCO समस्या का एक विशिष्ट "कठिन" उदाहरण (hard instance) निर्मित करते हैं। यह निर्माण $d$ -आयामी स्थान में बिंदुओं और बाधाओं (constraints) की एक ज्यामितीय व्यवस्था पर आधारित है।

वेक्टर निर्माण (थ्योरम 2): प्रमाण का मुख्य भाग $S^d$ पर यूनिट स्फीयर पर यूनिट वेक्टर्स के एक व्यवस्थित संग्रह $U_d(\rho)$ का निर्माण करना है। इन वेक्टर्स को दो गुणों को संतुष्ट करने के लिए डिज़ाइन किया गया है:
- सेपरेशन (Separation): कोई भी दो अलग-अलग वेक्टर्स कम से कम $\rho$ के कोणीय अंतर (angular distance) से अलग हैं।
- लोकल कनेक्टिविटी (Local Connectivity): क्रमबद्ध अनुक्रम में क्रमिक वेक्टर्स अधिकतम $A_d \rho$ के कोणीय अंतर से अलग हैं।
- कार्डिनैलिटी (Cardinality): ऐसे वेक्टर्स की संख्या $\Omega(\rho^{-(d-1)})$ के रूप में स्केल करती है।
  यह निर्माण एक इंडक्टिव प्रोसेस (inductive process) के माध्यम से किया गया है, जिसमें स्फेरिक कैप्स (spherical caps) और देशांतर/अक्षांश ट्रैवर्सल का उपयोग करके यह सुनिश्चित किया गया है कि ऑर्डरिंग और सेपरेशन गुण बने रहें।
कंस्ट्रेंट और एक्शन ट्राजेक्टरी:
- एक्शन स्पेस $X$ को एक बॉल $B(0, D)$ के रूप में परिभाषित किया गया है।
- टाइम होराइजन $T$ को $M = T^{1/d}$ "लेयर्स" में विभाजित किया गया है, जिनमें से प्रत्येक घटते रेडियस वाली एक संकेंद्रित स्फीयर $C_m$ के अनुरूप है।
- प्रत्येक लेयर $m$ के भीतर, एल्गोरिदम को $n$ बिंदुओं $z^{(m)}_i$ की एक अनुक्रम को पार करने के लिए मजबूर किया जाता है जो स्फीयर $C_m$ पर स्थित हैं। ये बिंदु ऊपर दिए गए निर्माण से प्राप्त यूनिट वेक्टर्स को स्केल करके बनाए गए हैं।
- कंस्ट्रेंट डिज़ाइन: प्रत्येक बिंदु $z^{(m)}_i$ के लिए, एक नया कंस्ट्रेंट पेश किया जाता है जो $z^{(m)}_i$ के प्रोजेक्शन पर अगली छोटी स्फीयर $C_{m+1}$ के स्पर्शरेखीय (tangent) एक हाफ-स्पेस (half-space) है। यह कंस्ट्रेंट प्रभावी रूप से $z^{(m)}_i$ पर केंद्रित एक स्फेरिक कैप को "कट ऑफ" कर देता है।
- फिजिबिलिटी लॉजिक: कोणीय सेपरेशन $\rho$ और सावधानीपूर्वक चुने गए कट एंगल के कारण, $z^{(m)}_i$ से जुड़ा कंस्ट्रेंट वर्तमान लेयर के उम्मीदवारों के सेट में से केवल उस विशिष्ट बिंदु को हटाता है, जिससे अन्य सभी बिंदु व्यवहार्य (feasible) रहते हैं। हालांकि, बिंदु $z^{(m)}_i$ स्वयं कंस्ट्रेंट प्रकट होने के तुरंत बाद इनफीजबल (infeasible) हो जाता है।
कॉस्ट फंक्शन डिज़ाइन:
- लॉस फंक्शन्स को OGD+Projection एल्गोरिदम को पूर्व-निर्धारित ट्राजेक्टरी $z_1, z_2, \dots, z_P$ (जहाँ $P$ कुल बिंदुओं की संख्या है) का पालन करने के लिए निर्देशित करने हेतु डिज़ाइन किया गया है।
- प्रत्येक चरण की शुरुआत में (जब नया कंस्ट्रेंट प्रकट होता है), एल्गोरिदम एक प्रोजेक्शन डिस्टेंस का सामना करता है क्योंकि वर्तमान एक्शन नए कंस्ट्रेंट के सापेक्ष इनफीजबल है।
- चरण के दौरान अगले टाइम स्टेप्स के भीतर, लॉस फंक्शन्स लीनियर होते हैं और एल्गोरिदम को अगले लक्ष्य बिंदु की ओर वापस ले जाने के लिए ओरिएंटेड होते हैं, जिससे यह सुनिश्चित होता है कि एल्गोरिदम इच्छित पथ पर बना रहे।

मुख्य परिणाम
यह शोध पत्र OGD+Projection एल्गोरिदम के CCV के लिए पहला लोअर बाउंड स्थापित करता है।

थ्योरम 1: एक COCO इंस्टेंस मौजूद है जिसका व्यास $2D$ और लिप्सचिट्ज़ कांस्टेंट $G$ है, ताकि OGD+Projection एल्गोरिदम का CCV $\Omega(T^{\frac{d-1}{2d}})$ हो।
डेरिवेशन: कुल CCV "फेज हेड्स" (जब नए कंस्ट्रेंट्स पेश किए जाते हैं) पर होने वाले उल्लंघनों का योग है। ऐसे $P \approx T^{\frac{d+1}{2d}}$ फेज हैं। प्रत्येक फेज हेड पर, एल्गोरिदम $T^{-1/d}$ के क्रम का उल्लंघन करता है। इन्हें गुणा करने पर प्राप्त होता है:
$\text{CCV} \approx T^{\frac{d+1}{2d}} \times T^{-\frac{1}{d}} = T^{\frac{d-1}{2d}}$
डायमेंशनल डिपेंडेंस (Dimensional Dependence): परिणाम यह उजागर करता है कि लोअर बाउंड आयाम $d$ पर निर्भर करता है। $d=2$ के लिए, बाउंड $\Omega(T^{1/3})$ है, जो $d=2$ के लिए ज्ञात अपर बाउंड (Balasundaram et al., 2026) से मेल खाता है। सामान्य $d$ के लिए, बाउंड $\Omega(T^{\frac{d-1}{2d}})$ है।

महत्व और दावे
लेखक दावा करते हैं कि यह कार्य OGD+Projection एल्गोरिदम के CCV के लिए पहला लोअर बाउंड परिणाम प्रदान करता है। इस परिणाम का प्राथमिक महत्व यह है कि यह दर्शाता है कि इस एल्गोरिदम के लिए मौजूदा अपर बाउंड विश्लेषण मौलिक रूप से ढीला (not fundamentally loose) नहीं है।

विशेष रूप से, शोध पत्र नोट करता है कि जबकि OGD+Projection एल्गोरिदम $d=2$ के लिए $O(T^{1/3})$ और सार्वभौमिक रूप से $O(\sqrt{T})$ का CCV प्राप्त करता है, प्राप्त लोअर बाउंड $\Omega(T^{\frac{d-1}{2d}})$ यह दिखाता है कि एल्गोरिदम का प्रदर्शन आयाम $d$ के संबंध में 'टाइट' (tight) है। $d=2$ के लिए, लोअर बाउंड $\Omega(T^{1/3})$ अपर बाउंड से मेल खाता है, जो उस आयाम के लिए इष्टतमता (optimality) की पुष्टि करता है। उच्च आयामों के लिए, लोअर बाउंड और सार्वभौमिक $O(\sqrt{T})$ अपर बाउंड के बीच का अंतर यह सुझाव देता है कि हालांकि एल्गोरिदम मजबूत है, कंस्ट्रेंट्स की विशिष्ट ज्यामितीय संरचना उल्लंघन दर को आयाम के साथ स्केल करने के लिए मजबूर कर सकती है।

यह शोध पत्र नए एल्गोरिदम या अनुप्रयोगों का प्रस्ताव नहीं करता है बल्कि कंस्ट्रेंड ऑनलाइन ऑप्टिमाइज़ेशन में वर्तमान स्टेट-ऑफ-द-आर्ट OGD+Projection दृष्टिकोण की सैद्धांतिक सीमाओं को परिभाषित करने का कार्य करता है।

बड़ा सवाल: रोबोट कितना बुरा हो सकता है?

द "इम्पॉसिबल मेज़" कंस्ट्रक्शन (असंभव भूलभुलैया का निर्माण)

यह "सर्वश्रेष्ठ" एल्गोरिदम के बारे में क्या बताता है

वे कितने आश्वस्त हैं?

निष्कर्ष (The Takeaway)

इसी तरह के और पेपर