🤖 machine learning

Online Convex Optimization with Sublinear Noisy Probes

यह शोध पत्र ऑनलाइन कॉनवेक्स ऑप्टिमाइज़ेशन (Online Convex Optimization) के लिए एक एकीकृत ढांचे को प्रस्तुत करता है जो $O\left(\min\left\{\sqrt{dT\ln T},\; \frac{dT\ln T}{k|1-2\delta|}\right)$ का एक सटीक रिग्रेट बाउंड प्राप्त करने के लिए शोर युक्त पेयरवाइज प्रोब्स (noisy pairwise probes) के सबलीनियर बजट का लाभ उठाता है, यह प्रदर्शित करते हुए कि कैसे ऐसे प्रोब्स कंटीन्यूअस एक्सपोनेंशियल वेट्स (Continuous Exponential Weights) के सेकंड-ऑर्डर विश्लेषण के भीतर एक वेरिएंस रिडक्शन प्रभाव उत्पन्न करते हैं।

मूल लेखक: Simone Di Gregorio, Anupam Gupta, Stefano Leonardi, Matteo Russo

प्रकाशित 2026-06-15

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

CC BY 4.0

मूल लेखक: Simone Di Gregorio, Anupam Gupta, Stefano Leonardi, Matteo Russo

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

कल्पना कीजिए कि आप हर दिन एक साल तक एक विशाल, धुंध भरे शहर में सबसे अच्छा रास्ता खोजने की कोशिश कर रहे हैं। आपको पहले से ट्रैफिक के पैटर्न का पता नहीं है, और "ट्रैफिक" (नुकसान) एक चालाक प्रतिद्वंद्वी द्वारा चुना जाता है जो आपकी यात्रा को यथासंभव धीमा करना चाहता है। यह ऑनलाइन कॉनवेक्स ऑप्टिमाइज़ेशन (OCO) की दुनिया है।

मानक संस्करण में, आप एक रास्ता चुनते हैं, गाड़ी चलाते हैं, और फिर—पफ़—आपको उस दिन के ट्रैफिक का पूरा नक्शा दिख जाता है। आप अपनी गलतियों से सीखते हैं और अगले दिन बेहतर करने की कोशिश करते हैं। समय के साथ, आप काफी अच्छे हो जाते हैं, लेकिन फिर भी आप कुछ गलत मोड़ ले लेते हैं। यह शोध पत्र पूछता है: क्या होगा अगर आप गाड़ी चलाने से पहले नक्शे पर एक झलक देख सकें, लेकिन केवल कुछ ही बार?

"झलक" (प्रोबिंग)

लेखक एक नया नियम पेश करते हैं: आपके पास अपने पूरे $T$ दिनों के वर्ष में "प्रोब्स" (मान लीजिए $k$ झलक) का एक सीमित बजट है।

पुराना तरीका: आपको अंधे होकर अंदाज़ा लगाना पड़ता था या फिर गाड़ी चलाने के बाद ट्रैफिक देखने के लिए इंतज़ार करना पड़ता था।
नया तरीका: अपना रास्ता चुनने से पहले, आप एक "जादुई ओरेकल" (oracle) से एक विशिष्ट प्रश्न पूछ सकते हैं: "यदि मैं रूट A या रूट B चुनता हूँ, तो इस समय किसमें कम ट्रैफिक होगा?"
कैच (Catch): ओरेकल परफेक्ट नहीं है। कभी-कभी (संभावना $\delta$ के साथ), वह आपसे झूठ बोलता है और आपको बताता है कि खराब रूट वास्तव में बेहतर है। यही "नॉइज़ी" (Noisy) वाला हिस्सा है।

यह शोध पत्र की बड़ी खोज है कि यदि आप केवल बहुत कम समय के लिए यह प्रश्न पूछ पाते हैं (सबलीनियर बजट) और ओरेकल कभी-कभी गलत होता है, तो भी आप बिना देखे खेलने की तुलना में अपने प्रदर्शन में नाटकीय रूप से सुधार कर सकते हैं।

"स्मार्ट डिटेक्टिव" रणनीति

आप इन कुछ, संभावित रूप से झूठ बोलने वाली झलकों का उपयोग कैसे करते हैं? लेखकों ने एक एल्गोरिदम डिज़ाइन किया है जो एक चतुर जासूस की तरह काम करता है जिसके पास दो तरकीबें हैं:

वैरिएंस ट्रिक (विचलन की तकनीक - "फैलाव" मीटर):
कल्पना कीजिए कि आपकी वर्तमान योजना एक संभाव्यता मानचित्र (probability map) के आधार पर शहर में यादृच्छिक (randomly) रूप से गाड़ी चलाने की है। यदि ट्रैफिक पैटर्न बहुत अराजक (chaotic) हैं (उच्च "वैरिएंस"), तो दो रैंडम रास्तों में से बेहतर को चुनना आपको एक बड़ा लाभ देता है। एल्गोरिदम महसूस करता है: "हे, आज ट्रैफिक बहुत बिखरा हुआ है। अगर मैं दो रैंडम जगहों की तुलना करता हूँ, तो मैं अंधे होकर चुनने की तुलना में एक बेहतर रास्ता खोजने की लगभग गारंटी के साथ सक्षम हूँ।" यह एल्गोरिदम अराजकता का उपयोग अपनी गलतियों को कम करने के लिए करने की अनुमति देता है।
"ट्रस्ट मी" मेटा-लर्नर:
चूंकि ओरेकल झूठ बोल सकता है, इसलिए एल्गोरिदम एक छोटा साइड-गेम चलाता है। इसके दो मोड हैं: "ओरेकल पर भरोसा करें" और "ओरेकल को अनदेखा करें।"

यदि ओरेकल कहता है "रूट A बेहतर है," तो एल्गोरिदम जाँचता है: अतीत में ओरेकल पर भरोसा करना कितना सफल रहा है?
यदि ओरेकल बहुत अधिक झूठ बोल रहा है, तो एल्गोरिदम स्वचालित रूप से "ओरेकल को अनदेखा करें" (या यहाँ तक कि इसके विपरीत) मोड में स्विच हो जाता है।
यह अपने आप होता है। एल्गोरिदम यह सीख लेता है कि कब नॉइज़ी संकेत पर भरोसा करना है और कब उसे अनदेखा करना है, और इसके लिए उसे यह जानने की आवश्यकता नहीं है कि ओरेकल कितना नॉइज़ी है।

परिणाम: कम प्रयास में बड़ी जीत

यह शोध पत्र गणितीय रूप से सिद्ध करता है कि यह रणनीति अविश्वसनीय रूप से अच्छी तरह से काम करती है।

प्रोब्स के बिना: आपका "रिग्रेट" (वह अतिरिक्त समय जो आपने परफेक्ट रूट की तुलना में बर्बाद किया) समय के वर्गमूल ( $\sqrt{T}$ ) के साथ बढ़ता है।
प्रोब्स के साथ: यदि आपके पास $k$ $k$ प्रोब्स हैं, तो आपका रिग्रेट काफी कम हो जाता है। सूत्र दिखाता है कि आपका प्रदर्शन अनुमानित रूप से आपके पास मौजूद प्रोब्स के अनुपात में सुधरता है।
- यदि आपके पास शून्य प्रोब्स हैं, तो आपको मानक परिणाम मिलता है।
- यदि आपके पास कई प्रोब्स हैं, तो आप परफेक्ट रूट के बहुत करीब पहुँच जाते हैं।
- भले ही ओरेकल नॉइज़ी हो (आधे समय झूठ बोलता हो), एल्गोरिदम अनुकूलित होता है और बिना प्रोब्स के खेलने की तुलना में बेहतर प्रदर्शन करता है।

"एक्सपर्ट्स" का विशेष मामला

शोध पत्र एक सरल संस्करण को भी देखता है: $d$ निश्चित विशेषज्ञों (experts) की एक सूची के बीच चयन करना (जैसे 100 लोगों की सूची में से सबसे अच्छा स्टॉक टिप चुनना)।

इस विशिष्ट मामले में, गणित और भी सटीक हो जाता है। एल्गोरिदम सर्वोत्तम संभव प्रदर्शन प्राप्त करता है, जो उन अधिक शक्तिशाली (लेकिन अवास्तविक) तरीकों के परिणामों से मेल खाता है जो पहले से ही जानते हैं कि सबसे अच्छा विशेषज्ञ कौन है।
संक्षेप में, कुछ बार यह पूछना कि "क्या विशेषज्ञ A, विशेषज्ञ B से बेहतर है?" लगभग उतना ही प्रभावी है जितना यह जानना कि "विशेषज्ञ A सबसे अच्छा है!"

निचोड़

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

संक्षेप में: थोड़ी सी नॉइज़ी जानकारी, यदि समझदारी से उपयोग की जाए, तो बहुत मूल्यवान होती है।

तकनीकी सारांश: उप-रैखिक शोरयुक्त जांच (Sublinear Noisy Probes) के साथ ऑनलाइन कॉनवेक्स ऑप्टिमाइज़ेशन

समस्या का निरूपण (Problem Formulation)
यह शोध पत्र एक उत्तल समुच्चय (convex set) $K \subseteq \mathbb{R}^d$ पर ऑनलाइन कॉनवेक्स ऑप्टिमाइज़ेशन (OCO) की जांच करता है। मानक सेटिंग में, एक शिक्षार्थी (learner) प्रत्येक दौर $t$ में एक निर्णय $x_t \in K$ चुनता है, एक प्रतिकूल रूप से चुने गए उत्तल नुकसान (convex loss) $f_t(x_t)$ को सहता है, और पूर्ण फीडबैक (फलन $f_t$ या उसके सबग्रेड्स) प्राप्त करता है। इसका उद्देश्य पिछले अनुभव के आधार पर सर्वोत्तम स्थिर निर्णय के विरुद्ध पछतावा (regret) को कम करना है।

लेखक एक एकीकृत प्रोबिंग मॉडल (probing model) पेश करते हैं जो दो हालिया कार्यों का सामान्यीकरण करता है: विशेषज्ञों के सेटिंग में उप-रैखिक सर्वश्रेष्ठ-विशेषज्ञ प्रश्न [Russo et al., 2024] और OCO में युग्मवार तुलना (pairwise comparison) फीडबैक [Bhaskara et al., 2023b]। इस ढांचे में, शिक्षार्थी को $k \le T$ युग्मवार जांच (pairwise probes) का बजट दिया जाता है। एक प्रोब किए गए दौर में, $x_t$ चुनने से पहले, शिक्षार्थी दो बिंदुओं $\{y_{t,1}, y_{t,2}\} \subseteq K$ को क्वेरी कर सकता है और यह संकेत प्राप्त कर सकता है कि किस बिंदु में कम नुकसान है। महत्वपूर्ण रूप से, ये प्रोब्स शोरयुक्त (noisy) हैं: प्रायिकता $\delta$ के साथ, ओरेकल (oracle) उस बिंदु को लौटाता है जिसमें अधिक नुकसान है (गलत उत्तर), और प्रायिकता $1-\delta$ के साथ, यह सही न्यूनीकरणकर्ता (minimizer) को लौटाता है। शोर पैरामीटर $\delta \in [0, 1]$ शिक्षार्थी के लिए अज्ञात है।

प्रोटोकॉल एक ओब्लिवियस एडवर्सरी (oblivious adversary) मानता है जो शिक्षार्थी द्वारा किसी विशिष्ट दौर में प्रोब करने का निर्णय लेने से पहले नुकसान के फलनों $\{f_t\}_{t=1}^T$ के अनुक्रम के लिए प्रतिबद्ध हो जाता है। यह बाधा अत्यंत महत्वपूर्ण है; यदि एडवर्सरी प्रोबिंग निर्णय के अनुकूल हो सकता है, तो प्रोब को बेकार किया जा सकता है (उदाहरण के लिए, प्रोब दौरों पर नुकसान को 0 निर्धारित करके), जिससे पछतावा (regret) बाउंड $\Theta(\sqrt{T-k})$ तक गिर सकता है।

कार्यप्रणाली (Methodology)
प्रस्तावित एल्गोरिदम कंटीन्यूअस एक्सपोनेंशियल वेट्स (CEW) का एक अनुकूलित (adaptive), प्रोब-संवर्धित संस्करण है। मुख्य तकनीकी अंतर्दृष्टि विचरण न्यूनीकरण प्रभाव (variance reduction effect) और CEW एल्गोरिदम के द्वितीय-क्रम (विचरण-आधारित) विश्लेषण पर निर्भर करती है।

प्रोबिंग के माध्यम से विचरण न्यूनीकरण:
एक प्रोबिंग दौर में, एल्गोरिदम वर्तमान घनत्व वितरण $p_t$ से स्वतंत्र रूप से दो बिंदुओं को नमूना (sample) लेता है। देखे गए कम नुकसान वाले बिंदु (या प्रोब द्वारा सुझाए गए बिंदु) को खेलकर, अपेक्षित नुकसान $p_t$ के तहत नुकसान फलन के विचरण $v_t = \text{Var}_{x \sim p_t}[f_t(x)]$ के समानुपाती मात्रा से कम हो जाता है। विशेष रूप से, शोर रहित प्रोब्स के लिए, अपेक्षित नुकसान $v_t$ से कम हो जाता है।
शोरयुक्त प्रोब्स को संभालना (Meta-Learner):
चूंकि $\delta$ अज्ञात है, इसलिए एल्गोरिदम यह तय करने के लिए कि प्रोब के सुझाव का "अनुसरण" (follow) करना है या उसे "उल्टा" (invert) करना है, एक हल्का मेटा-लर्नर (Meta-Learner) (विशेष रूप से AdaHedge) नियोजित करता है। मेटा-लर्नर दो क्रियाओं पर कार्य करता है: $F$ (अनुसरण) और $I$ (उल्टा)। यह प्रोब किए गए दौरों पर इन दो काल्पनिक क्रियाओं द्वारा होने वाले नुकसान के आधार पर अपने भार (weights) को अपडेट करता है। यह एल्गोरिदम को प्रोब पर तब भरोसा करने की अनुमति देता है जब वह सूचनात्मक हो ( $\delta$ का $1/2$ से दूर होना) और इसे तब अनदेखा करने की अनुमति देता है जब वह अनौपचारिक हो।
पछतावा अपघटन (Regret Decomposition):
पछतावा विश्लेषण कुल नुकसान को दो घटकों में विभाजित करता है:

गैर-प्रोबिंग दौर: एल्गोरिदम मानक CEW अपडेट का पालन करता है। पछतावे को एक द्वितीय-क्रम विश्लेषण का उपयोग करके सीमित किया जाता है (de Rooij et al., 2014 का अनुसरण करते हुए) जो बेसलाइन पछतावे को संचयी विचरण $V_T = \sum v_t$ से जोड़ता है।
प्रोबिंग दौर: नुकसान को मेटा-लर्नर की बेहतर क्रिया ( $F$ या $I$ ) के नुकसान, प्लस मेटा-लर्नर के स्वयं के पछतावा पद द्वारा सीमित किया जाता है। विश्लेषण दिखाता है कि "बेहतर" क्रिया $|1-2\delta|v_t$ के समानुपाती नुकसान न्यूनीकरण प्राप्त करती है।

मुख्य परिणाम (Key Results)
यह शोध पत्र स्थापित करता है कि उप-रैखिक शोरयुक्त युग्मवार प्रोब्स का बजट पूर्ण-फीडबैक OCO शासन में वर्स्ट-केस पछतावे में प्रमाणिक रूप से सुधार कर सकता है।

सामान्य उत्तल नुकसान (General Convex Losses): सामान्य उत्तल नुकसानों के लिए जो $K \subseteq \mathbb{R}^d$ पर $[0, 1]$ में सीमित हैं, अपेक्षित पछतावा है:
$\text{Reg}_T \le O\left( \min\left\{ \sqrt{dT \ln T}, \frac{dT \ln T}{k |1 - 2\delta|} \right\} \right)$
यह बाउंड क्षितिज $T$ , प्रोब बजट $k$ , और शोर पैरामीटर $\delta$ के संबंध में $T$ के संदर्भ में (लॉग-कारक को छोड़कर) टाइट (tight) है। जैसे-जैसे $\delta \to 1/2$ (सिक्का उछाल) होता है, पछतावा सुचारू रूप से घटता है।
विशेषज्ञों के साथ भविष्यवाणी (Prediction with Experts): विशेषज्ञों के सेटिंग (सिम्प्लेक्स $\Delta^{d-1}$ के शीर्षों पर रैखिक नुकसान) के विशेष मामले में, बाउंड सुधरकर निम्न हो जाता है:
$\text{Reg}_T \le O\left( \min\left\{ \sqrt{T \ln d}, \frac{T \ln d}{k |1 - 2\delta|} \right\} \right)$
ये दरें $T, k, \delta$ सहित सभी मापदंडों में पूरी तरह से टाइट हैं, जिसमें आयाम $d$ भी शामिल है।

महत्व और योगदान (Significance and Contributions)
लेखक कई महत्वपूर्ण योगदानों का दावा करते हैं:

एकीकरण (Unification): यह कार्य विविक्त "सर्वश्रेष्ठ-विशेषज्ञ" प्रोबिंग मॉडल और निरंतर "युग्मवार तुलना" मॉडल को एक एकल ढांचे में एकीकृत करता है, यह प्रदर्शित करते हुए कि युग्मवार प्रोब इष्टतम पछतावा दर प्राप्त करने के लिए सर्वश्रेष्ठ-विशेषज्ञ प्रोब्स के समान ही सूचनात्मक हैं।
शोर के प्रति मजबूती (Robustness to Noise): पिछले कार्यों के विपरीत जो अक्सर शोर रहित या विशिष्ट शोर मॉडल मानते हैं, यह ढांचा अज्ञात शोर स्तरों $\delta$ को संभालता है और $|1-2\delta|$ पर इष्टतम निर्भरता प्राप्त करता है।
तकनीकी नवीनता (Technical Novelty): विश्लेषण डिफरेंशियल प्राइवेसी मशीनरी और ग्रेडिएंट नॉर्म्स या कर्वेचर (curvature) के संबंध में धारणाओं (जो पिछले कार्यों जैसे Bhaskara et al., 2023b में आवश्यक थे) से बचता है। इसके बजाय, यह विचरण-आधारित न्यूनीकरण तर्क का लाभ उठाता है।
इष्टतमता (Optimality): शोध पत्र मिलान करने वाले लोअर बाउंड्स (परिशिष्ट A में) प्रदान करता है जो दिखाते हैं कि प्राप्त दरें विशेषज्ञों के सेटिंग के लिए टाइट हैं और सामान्य उत्तल सेटों के लिए $T, k, \delta$ में टाइट हैं।

लेखक नोट करते हैं कि हालांकि सैद्धांतिक गारंटी मजबूत है, मुख्य एल्गोरिदम के लिए उत्तल समुच्चयों पर समाकलन (integrals) की गणना करना आवश्यक है, जो सामान्य रूप से कम्प्यूटेशनल रूप से कठिन हो सकता है। वे तुलनीय गारंटी प्राप्त करने वाले कुशल एल्गोरिदम के विकास को एक खुला दिशा (open direction) के रूप में पहचानते हैं।

"झलक" (प्रोबिंग)

"स्मार्ट डिटेक्टिव" रणनीति

परिणाम: कम प्रयास में बड़ी जीत

"एक्सपर्ट्स" का विशेष मामला

निचोड़

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