📊 statistics

High-probability zeroth-order online convex optimisation beyond Euclidean geometry

यह शोध पत्र कोन-मेज़र सैंपलिंग (cone-measure sampling) का उपयोग करते हुए $\ell_q$ -लिप्सचिट्ज़ लॉस और $\ell_p$ -नियमितीकृत FTRL के साथ ज़ीरोथ-ऑर्डर ऑनलाइन कॉनवेक्स ऑप्टिमाइज़ेशन के लिए एकीकृत उच्च-प्रायिकता रिग्रेट बाउंड्स स्थापित करता है, जो $q \in [1,2]$ के लिए इष्टतमता सिद्ध करता है और $q > 2$ के लिए एक अंतर्निहित अंतराल की पहचान करता है।

मूल लेखक: David Janz, El-Mahdi El-Mhamdi, Arya Akhavan

प्रकाशित 2026-05-12

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

CC BY 4.0

मूल लेखक: David Janz, El-Mahdi El-Mhamdi, Arya Akhavan

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

कल्पना कीजिए कि आप एक विशाल, धुंधली घाटी (एक फलन का "न्यूनतम" या "minimum") में सबसे निचले बिंदु को खोजने की कोशिश कर रहे हैं। एक आदर्श दुनिया में, आपके पास एक मानचित्र या दिशा-सूचक यंत्र (कम्पास) होगा जो आपको ठीक-ठीक बताएगा कि कौन सी दिशा "नीचे" की ओर है (एक ग्रेडिएंट)। लेकिन इस शोध पत्र में, लेखक एक ऐसी स्थिति से निपट रहे हैं जहाँ आपके पास न तो मानचित्र है और न ही दिशा-सूचक यंत्र। आप केवल एक कदम उठा सकते हैं, जमीन को महसूस कर सकते हैं, और पूछ सकते हैं, "क्या यह यहाँ पहले से ऊँचा है या नीचा?" इसे जीरोथ-ऑर्डर ऑप्टिमाइज़ेशन (zeroth-order optimization) कहा जाता है।

यह शोध पत्र इस समस्या के एक विशिष्ट, कठिन संस्करण को संबोधित करता है: ऑनलाइन कॉनवेक्स ऑप्टिमाइज़ेशन (Online Convex Optimization)।

"ऑनलाइन" का अर्थ है कि आप एक-एक करके निर्णय ले रहे हैं, जैसे कि एक खेल खेलना जहाँ आप अगले कदम के बारे में पहले से नहीं जानते।
"कॉनवेक्स" का अर्थ है कि घाटी का आकार एक सुंदर, चिकने कटोरे जैसा है (कोई छिपी हुई पहाड़ियाँ या अजीब उभार नहीं), जो इसे सैद्धांतिक रूप से खोजने योग्य बनाता है।
"जीरोथ-ऑर्डर" का अर्थ है कि आपको ढलान का अनुमान लगाने के लिए केवल दो विशिष्ट स्थानों पर जमीन को छूकर देखना होता है।

यहाँ उनके कार्य का सरल उपमाओं (analogies) का उपयोग करके विवरण दिया गया है:

1. समस्या: अंधेरे में ढलान का अनुमान लगाना

आमतौर पर, घाटी के निचले हिस्से को खोजने के लिए आपको ढलान जानने की आवश्यकता होती है। चूंकि आप ढलान देख नहीं सकते, इसलिए आपको इसका अनुमान लगाना होगा। मानक तरीका यह है कि आप दो बिंदुओं के पास जमीन को टटोलते हैं (एक कदम आगे, एक कदम पीछे) और ऊंचाई के अंतर को देखते हैं। इसे टू-पॉइंट फाइनाइट-डिफरेंस एस्टिमेटर (two-point finite-difference estimator) कहा जाता है।

लेखक पूछते हैं: यदि जमीन का आकार अलग हो, तो हम ढलान का सबसे अच्छा अनुमान कैसे लगा सकते हैं?

क्या घाटी का आकार एक वृत्त (यूक्लिडियन) की तरह है?
क्या यह एक हीरे (L1 norm) की तरह है?
क्या यह एक वर्ग (L infinity norm) की तरह है?

वे यह अध्ययन करते हैं कि ढलान का अनुमान कैसे लगाया जाए जब "जमीन" (लॉस फंक्शन) और "खेल के नियम" (ज्यामिति) इनमें से कोई भी आकार ले सकते हैं।

2. नवाचार: "कोन" सैंपलिंग रणनीति

ढलान का अनुमान लगाने के लिए, आपको एक दिशा चुननी होगी जिसमें आप जमीन को टटोल सकें।

पुराना तरीका: अधिकांश लोग एक दिशा यादृच्छिक (randomly) रूप से चुनते हैं, जैसे कि एक पूर्ण गोले (जैसे बास्केटबॉल) पर एक पासा फेंककर दिशा चुनना।
इस शोध पत्र का तरीका: लेखक सुझाव देते हैं कि विभिन्न आकारों (जैसे हीरा या घन) पर एक "कोन मेजर" (cone measure) के आधार पर दिशा चुनें।

उपमा: कल्पना कीजिए कि आप एक कमरे में आँखों पर पट्टी बांधकर खड़े हैं।

यदि कमरा एक गोला (sphere) है, तो आप घूम सकते हैं और एक यादृच्छिक दिशा में इशारा कर सकते हैं।
यदि कमरा एक घन (cube) है, तो एक गोले की तुलना में घन के कोनों (corners) की ओर इशारा करना बेहतर हो सकता है, यह इस पर निर्भर करता है कि आप क्या खोजने की कोशिश कर रहे हैं।
लेखकों ने पता लगाया कि कुछ प्रकार की "घाटियों" के लिए, घन या हीरे के कोनों (या विशिष्ट किनारों) की ओर इशारा करना, गोले पर यादृच्छिक रूप से इशारा करने की तुलना में ढलान का बहुत बेहतर अनुमान देता है।

3. बड़ा दावा: "उच्च-संभाव्यता" गारंटी

अधिकांश पिछले अध्ययन कहते थे, "औसतन, कई प्रयासों के बाद, यह तरीका अच्छा काम करता है।"
लेखक कहते हैं: "नहीं, हम यह सिद्ध कर सकते हैं कि लगभग हर बार जब आप इसे चलाएंगे, तो यह अच्छी तरह से काम करेगा।"

रूपक (Metaphor): एक मौसम भविष्यवक्ता की कल्पना करें।
- पुराना तरीका: "औसतन, 50% समय बारिश होती है।" (यह आपकी मदद नहीं करता यदि आपको जानना है कि आज बारिश होगी या नहीं)।
- नया तरीका: "हम 99% निश्चितता के साथ गारंटी दे सकते हैं कि आज बारिश नहीं होगी।"
शोध पत्र यह सिद्ध करता है कि उनका एल्गोरिदम विश्वसनीय है। यह केवल "औसतन" काम नहीं करता; यह लगातार काम करता है, यहाँ तक कि सबसे खराब स्थितियों में भी, बशर्ते कि "धुंध" (डेटा में शोर/noise) बहुत अधिक न हो।

4. "एनीटाइम" (Anytime) विशेषता

यह एल्गोरिदम डेटा-संचालित और एनीटाइम है।

उपमा: एक वीडियो गेम खेलने की कल्पना करें जहाँ आपको नहीं पता कि कितने स्तर (levels) हैं। कुछ एल्गोरिदम को आपको यह बताने की आवश्यकता होती है कि "खेल 100 स्तरों में समाप्त होता है," ताकि वे अपने कदम की योजना बना सकें।
यह एल्गोरिदम इसकी परवाह नहीं करता। यह खेलना शुरू कर सकता है, और यदि खेल 10 स्तरों में या 10,000 स्तरों में समाप्त होता है, तो यह मौके पर ही खुद को ढाल लेता है। इसे इष्टतम रूप से खेलने के लिए "क्षितिज" (खेल के अंत) को जानने की आवश्यकता नहीं है।

5. परिणामों में "अंतराल" (Gap)

लेखकों ने एक दिलचस्प सीमा पाई।

"चिकनी" घाटियों के लिए (q ≤ 2): उनका तरीका ढलान का अनुमान लगाने का सबसे अच्छा संभव तरीका है। उन्होंने सिद्ध किया है कि आप इससे बेहतर नहीं कर सकते।
"नुकीली" घाटियों के लिए (q > 2): यहाँ एक अंतराल है। उनका तरीका काम तो करता है, लेकिन यह सैद्धांतिक सीमा के अनुसार उतना सटीक नहीं है जितना होना चाहिए।
रूपक: कल्पना कीजिए कि आप घास के ढेर में सुई खोजने की कोशिश कर रहे हैं।
- यदि घास का ढेर नरम और गोल है (q ≤ 2), तो उनका उपकरण सुई को पूरी तरह से ढूंढ लेता है।
- यदि घास का ढेर नुकीले, टेढ़े-मेढ़े स्पाइक्स (q > 2) से बना है, तो उनका उपकरण अभी भी सुई को ढूंढ लेता है, लेकिन ऐसा लगता है कि उपकरण स्वयं (जिस तरह से वे जमीन को टटोलते हैं) ही समस्या है, न कि उनका गणित। उन्हें संदेह है कि इन "नुकीले" आकारों के लिए, हमें भविष्य में पूरी तरह से अलग तरह के "टटोलने" (poke) के तरीके की आवश्यकता हो सकती है।

सारांश: उन्होंने क्या किया

ढलान का अनुमान लगाने का एक नया तरीका बनाया—विभिन्न ज्यामितीय आकारों (गोले, हीरे, घन) के आधार पर जमीन को टटोलकर।
सिद्ध किया कि यह लगभग हर बार काम करता है (उच्च संभाव्यता), न कि केवल औसतन।
इसे लचीला बनाया ताकि यह बिना यह जाने काम कर सके कि कार्य कितने समय तक चलेगा।
एक सीमा पाई: यह कुछ आकारों के लिए एकदम सही है, लेकिन बहुत "नुकीले" आकारों के लिए, ढलान का अनुमान लगाने का वर्तमान तरीका स्वाभाविक रूप से त्रुटिपूर्ण हो सकता है, जो भविष्य के शोधकर्ताओं के लिए एक पहेली छोड़ देता है।

संक्षेप में, उन्होंने जटिल, बहु-आकार वाली घाटियों के निचले हिस्से को खोजने के लिए एक अधिक विश्वसनीय, अनुकूलन योग्य और गणितीय रूप से सिद्ध "आँखों पर पट्टी बांधकर चलने वाले खोजकर्ता" का निर्माण किया है।

तकनीकी सारांश: यूक्लिडियन ज्यामिति से परे उच्च-संभाव्यता वाले ज़ीरोथ-ऑर्डर ऑनलाइन कॉनवेक्स ऑप्टिमाइज़ेशन

समस्या सेटिंग (Problem Setting)
यह कार्य ज़ीरोथ-ऑर्डर सेटिंग में ऑनलाइन कॉनवेक्स ऑप्टिमाइज़ेशन (OCO) की समस्या को संबोधित करता है जहाँ शिक्षार्थी (learner) के पास केवल फलन मूल्यांकन (function evaluations) तक पहुँच होती है, न कि ग्रेडिएंट्स तक। विशिष्ट सेटिंग में रैंडम लिप्सचिट्ज़ लॉस (Lipschitz losses) $f_t$ का एक अनुक्रम शामिल है जो एक वितरण $\mu$ से लिया गया है। जबकि $f_t$ के वास्तविक रूप (realizations) को-वेक्स (convex) होना आवश्यक नहीं है, उनका माध्य फलन (mean function) $F_\mu(x) = \mathbb{E}_{f \sim \mu}[f(x)]$ को-वेक्स माना जाता है। शिक्षार्थी एक कॉम्पैक्ट, को-वेक्स सेट $\Theta \subset \mathbb{R}^d$ पर कार्य करता है और उसका लक्ष्य स्यूडो-रिग्रेट (pseudo-regret) को न्यूनतम करना है:
$R_n^\mu = \sup_{u \in \Theta} \sum_{t=1}^n \left( F_\mu(x_t) - F_\mu(u) \right)$
फीडबैक मॉडल शिक्षार्थी को प्रति राउंड दो बिंदुओं पर फलन क्वेरी करने की अनुमति देता है, $x_t \pm h_t \zeta_t$ , जहाँ दिशा $\zeta_t$ को कोन मेजर (cone measure) के अनुसार $\ell_r$ -बॉल की सीमा से सैंपल किया जाता है। लॉस को $\ell_q$ नॉर्म के सापेक्ष $L$ -लिप्सचिट्ज़ माना गया है, और एल्गोरिदम एक फॉलो-द-रेगुलराइज्ड-लीडर (FTRL) फ्रेमवर्क के भीतर $\ell_p$ -स्ट्रॉन्गली को-वेक्स रेगुलराइज़र का उपयोग करता है।

कार्यप्रणाली (Methodology)
यह शोध एक एडेप्टिव, एनीटाइम (anytime) एल्गोरिदम (SOLO FTRL) प्रस्तावित करता है जो रैंडमाइज्ड टू-पॉइंट फाइनाइट-डिफरेंस ग्रेडिएंट एस्टिमेटर्स का उपयोग करता है। मुख्य पद्धतिगत नवाचार ज्यामितीय सामान्यीकरण और संभावabilistic विश्लेषण में निहित हैं:

सामान्यीकृत ग्रेडिएंट एस्टिमेशन (Generalised Gradient Estimation): ग्रेडिएंट एस्टिमेटर का निर्माण $\ell_r$ बॉल की सीमा पर कोन मेजर ( $\zeta \sim \partial B_d^r$ ) से लिए गए दिशाओं का उपयोग करके किया जाता है। एस्टिमेटर को इस प्रकार परिभाषित किया गया है:
$g_t = \frac{d}{2h_t} \left( f_t(x_t + h_t \zeta_t) - f_t(x_t - h_t \zeta_t) \right) n_r(\zeta_t)$
जहाँ $n_r(\zeta)$ $\zeta$ पर $\ell_r$ स्फीयर का यूनिट नॉर्मल है। यह क्लासिकल स्फेरिकल एस्टिमेटर्स ( $r=2$ ) का सामान्यीकरण करता है और $\ell_1$ या $\ell_\infty$ सैंपलिंग ज्योमेट्री की अनुमति देता है।
मोमेंट एनालिसिस और कंसन्ट्रेशन (Moment Analysis and Concentration): पिछले कार्यों के विपरीत जो इन-एक्सपेक्टेशन बाउंड्स (आमतौर पर सेकंड मोमेंट्स) पर निर्भर करते हैं, यह विश्लेषण ड्यूल नॉर्म $\ell_{p^*}$ में ग्रेडिएंट एस्टिमेटर के लिए सभी-मोमेंट बाउंड्स (all-moment bounds) स्थापित करता है। यह सिद्ध करके कि ड्यूल नॉर्म स्क्वेर्ड एरर्स का अनुक्रम एक सीक्वेंशियल बर्नस्टीन मोमेंट कंडीशन (SBM) को संतुष्ट करता है, लेखक समय-यूनिफॉर्म हाई-प्रोबेबिलिटी कंसन्ट्रेशन इनइक्वेलिटीज (concentration inequalities) प्राप्त करते हैं। इसमें $\ell_r$ स्फीयर्स पर लिप्सचिट्ज़ फंक्शन्स के लिए कंसन्ट्रेशन ऑफ मेजर परिणामों का उपयोग करके ग्रेडिएंट एस्टिमेटर के टेल बिहेवियर (tail behavior) को नियंत्रित करना शामिल है।
एडेप्टिव एल्गोरिदम (Adaptive Algorithm): एल्गोरिदम पूरी तरह से डेटा-ड्रिवन है और इसे समय क्षितिज (time horizon) $n$ या मोमेंट एनालिसिस से प्राप्त वर्स्ट-केस कांस्टेंट्स के ज्ञान की आवश्यकता नहीं है। इसे केवल ज्योमेट्री पैरामीटर्स ( $p, r$ ), रेगुलराइज़र, और डोमेन साइज के ऊपरी बाउंड की आवश्यकता होती है।

प्रमुख योगदान (Key Contributions)

एकीकृत हाई-प्रोबेबिलिटी बाउंड्स (Unified High-Probability Bounds): यह पेपर सभी ज्योमेट्री कॉम्बिनेशन $p, q, r \in [1, \infty]$ के लिए ज़ीरोथ-ऑर्डर OCO के लिए पहले एकीकृत हाई-प्रोबेबिलिटी रिग्रेट बाउंड्स प्रदान करता है। ये बाउंड्स रैंडम लिप्सचिट्ज़ लॉस के लिए मान्य हैं जिनका एक को-वेक्स मीन है, जो पिछले इन-एक्सपेक्टेशन गारंटियों को टाइम-यूनिफॉर्म हाई-प्रोबेबिलिटी स्टेटमेंट्स में मजबूत बनाता है।
ग्रेडिएंट एस्टिमेटर मोमेंट बाउंड्स (Gradient Estimator Moment Bounds): लेखक ड्यूल नॉर्म $\ell_{p^*}$ में $\ell_r$ -रैंडमाइज्ड टू-पॉइंट ग्रेडिएंट एस्टिमेटर्स के लिए नवीन मोमेंट बाउंड्स सिद्ध करते हैं। ये परिणाम सैंपलिंग ज्योमेट्री ( $r$ ) और लिप्सचिट्ज़ नॉर्म ( $q$ ) पर निर्भरता को ट्रैक करते हैं, यह स्थापित करते हुए कि संचयी (cumulative) स्क्वेर्ड ड्यूल नॉर्म्स एक सब-गामा प्रोसेस (subgamma process) की तरह व्यवहार करते हैं।
एल्गोरिदम-स्वतंत्र लोअर बाउंड्स (Algorithm-Independent Lower Bounds): यह पेपर समान समस्या वर्ग के लिए कॉन्स्टेंट-प्रोबेबिलिटी लोअर बाउंड्स स्थापित करता है। ये बाउंड्स पिछले इन-एक्सपेक्टेशन परिणामों (विशेष रूप से $p=q=1$ के लिए $\sqrt{\log d}$ फैक्टर को हटाकर) में सुधार करते हैं और एक ही कंस्ट्रक्शन के साथ $p, q \in [1, \infty]$ की पूरी रेंज को कवर करते हैं।
$q > 2$ के लिए एक गैप की पहचान (Identification of a Gap for $q > 2$ ): विश्लेषण $q > 2$ के लिए ऊपरी और निचले बाउंड्स के बीच एक विसंगति को प्रकट करता है। लेखक तर्क देते हैं कि यह प्रमाण की त्रुटि नहीं है, बल्कि रैंडमाइज्ड टू-पॉइंट ग्रेडिएंट एस्टिमेटर्स की इस क्षेत्र में अंतर्निहित उप-इष्टतमता (suboptimality) का संकेत है, क्योंकि वे हाई- $q$ लिप्सचिट्ज़ फंक्शन्स में निहित स्पैरसिटी (sparsity) का लाभ उठाने में विफल रहते हैं।

मुख्य परिणाम (Main Results)
प्राथमिक सैद्धांतिक परिणाम (Theorem 2.3) बताता है कि कम से कम $1-\delta$ प्रायिकता के साथ, रिग्रेट इस प्रकार संतुष्ट होता है:
$R_n^\mu \leq 22R\sqrt{\nu_r} \left( \sqrt{n \Lambda_n^*(\delta)} + 11 d^{\gamma_r} \log(32n/\delta)^{3/2} \right)$
जहाँ $\nu_r$ एक प्रॉक्सी वेरिएंस है जो $L, d, p, q, r$ पर निर्भर करता है, और $\gamma_r = (1/p - 1/r)_+$ है। $\sqrt{\log \log n}$ टर्म बाउंड की एनीटाइम प्रकृति से उत्पन्न होती है।

लोअर बाउंड (Theorem 2.4) दिखाता है कि किसी भी टू-पॉइंट एल्गोरिदम के लिए, एक ऐसी समस्या इंस्टेंस मौजूद है जहाँ रिग्रेट कॉन्स्टेंट प्रोबेबिलिटी के साथ कम से कम $d^{(1/2 + 1/q - 1/p)_+} LR\sqrt{n}$ के ऑर्डर का होता है।

महत्व और दावे (Significance and Claims)
यह पेपर दावा करता है कि यह यूक्लिडियन सेटिंग ( $p=q=r=2$ ) से परे ज़ीरोथ-ऑर्डर कॉनवेक्स ऑप्टिमाइज़ेशन के लिए पहला एकीकृत उपचार प्रदान करता है। इन-एक्सपेक्टेशन से हाई-प्रोबेबिलिटी विश्लेषण की ओर बढ़कर, परिणाम मजबूत, टाइम-यूनिफॉर्म गारंटियाँ प्रदान करते हैं जो एडेप्टिव और एनीटाइम सेटिंग्स के लिए उपयुक्त हैं।

यह कार्य एक विशिष्ट सीमा को उजागर करता है: $q > 2$ के लिए, मानक रैंडमाइज्ड टू-पॉइंट ग्रेडिएंट एस्टिमेटर्स सैद्धांतिक लोअर बाउंड की तुलना में उप-इष्टतम प्रतीत होते हैं। लेखक सुझाव देते हैं कि यह अंतर मौजूदा फाइनाइट-डिफरेंस मेथड्स के विश्लेषण को और अधिक परिष्कृत करने के बजाय, मौलिक रूप से भिन्न एस्टिमेटर स्ट्रक्चर की आवश्यकता की ओर संकेत करता है।