🤖 machine learning

Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization

यह शोध पत्र दृढ़ रूप से उत्तल नुकसान (strongly convex losses) के साथ ऑनलाइन उत्तल अनुकूलन (online convex optimization) के लिए शोर-अनुकूलित उच्च-संभाव्यता रिग्रेट बाउंड्स (noise-adaptive high-probability regret bounds) स्थापित करता है, जो पूर्ण-सूचना गारंटियों (full-information guarantees) में सुधार करने के लिए एक एक्सपोनेंशियल सुपरमार्टिंगेल तकनीक (exponential supermartingale technique) पेश करता है, बैंडिट फीडबैक (bandit feedback) के लिए एक रैखिक $\log(1/\delta)$ कॉन्फिडेंस कॉस्ट सेपरेशन (confidence cost separation) सिद्ध करता है, और बाधित सेटिंग्स (constrained settings) के लिए एक साथ उच्च-संभाव्यता बाउंड्स प्रदान करता है।

मूल लेखक: Wentao Zhang, Yutong Zhang, Wentao Mo

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

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

CC BY 4.0

मूल लेखक: Wentao Zhang, Yutong Zhang, Wentao Mo

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

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

गणित और कंप्यूटर विज्ञान की दुनिया में, इसे ऑनलाइन कॉनवेक्स ऑप्टिमाइज़ेशन (Online Convex Optimization - OCO) कहा जाता है। आमतौर पर, गणितज्ञ यह सिद्ध कर सकते हैं कि आपकी "पछतावा" (regret) (वह अतिरिक्त नुकसान जो आपने सबसे अच्छे संभावित विकल्प की तुलना में सहा है) औसतन छोटा होगा। लेकिन वास्तविक जीवन में, "औसत पर" निर्भर रहना हमेशा पर्याप्त नहीं होता। आप जानना चाहते हैं: "इस बात की क्या संभावना है कि मेरा एक दिन बहुत बुरा न जाए?"

झांग, झांग और मो का यह शोध पत्र इन गारंटियों को बहुत अधिक मजबूत और यथार्थवादी बनाने के लिए तीन विशिष्ट समस्याओं पर काम करता है। यहाँ सरल उपमाओं का उपयोग करके इसका विवरण दिया गया है:

1. "शोर-अनुकूली" (Noise-Adaptive) सफलता (पूर्ण जानकारी)

समस्या:
कल्पना कीजिए कि आप एक छिपे हुए खजाने की ओर बढ़ने की कोशिश कर रहे हैं। आपके पास एक दिशा-सूचक यंत्र (कम्पास/ग्रेडिएंट) है जो सही दिशा दिखाता है, लेकिन यह थोड़ा डगमगा रहा है।

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

2. "बैंडिट" वास्तविकता परीक्षण (सीमित जानकारी)

समस्या:
अब, एक कठिन संस्करण की कल्पना करें। इसके बजाय कि आपके पास दिशा दिखाने वाला कम्पास हो, आप केवल अपनी चाल का अंतिम स्कोर देखते हैं। आपको यह नहीं पता कि आप क्यों जीते या हारे, बस संख्या पता है। इसे "बैंडिट फीडबैक" (Bandit Feedback) कहा जाता है।

प्रश्न: क्या जानकारी की कमी यह बदल देती है कि यह सुनिश्चित करने के लिए "आत्मविश्वास" की कितनी कीमत चुकानी पड़ती है कि आप विफल नहीं होंगे?
खोज: लेखकों ने एक कड़वा सच साबित किया है: हाँ, इसकी कीमत बहुत अधिक है।
- पूर्ण जानकारी के साथ (कम्पास के साथ), विफल न होने के प्रति आश्वस्त होने की लागत धीरे-धीरे बढ़ती है (जैसे किसी संख्या का वर्गमूल)।
- सीमित जानकारी के साथ (केवल स्कोर देखना), विफल न होने के प्रति आश्वस्त होने की लागत रैखिक (linearly) रूप से बढ़ती है (बहुत तेजी से)।
उपमा: यह एक गुप्त कोड का अनुमान लगाने जैसा है। यदि कोई आपको "गरम" या "ठंडा" बताता है (पूर्ण जानकारी), तो आप जल्दी से संकुचित हो सकते हैं। यदि वे अंत में केवल यह बताते हैं कि "आपने सही अनुमान लगाया" या "आप गलत थे" (बैंडित), तो समान रूप से आश्वस्त होने के लिए आपको कई अधिक प्रयास करने होंगे। यह शोध पत्र सिद्ध करता है कि यह केवल गणित की खामी नहीं है; यह सूचना का एक मौलिक नियम है।

3. "दोधारी तलवार" (प्रतिबंध)

समस्या:
कल्पना कीजिए कि आप अपने गंतव्य तक जितनी जल्दी हो सके (पछतावा कम करने के लिए) पहुँचने के लिए एक कार चला रहे हैं, लेकिन आपको गति सीमा के भीतर रहना है और ईंधन खत्म होने से भी बचना है (प्रतिबंध)।

पुराना तरीका: पिछला गणित यह वादा कर सकता था कि आप एक लंबी यात्रा के दौरान औसतन गति सीमा के भीतर रहेंगे। लेकिन यह गारंटी नहीं दे सकता था कि आप कुछ मिनटों के लिए बहुत तेज गति से गाड़ी नहीं चलाएंगे और फिर उसकी भरपाई के लिए धीमे नहीं हो जाएंगे।
नया तरीका: लेखकों ने एक ऐसी प्रणाली बनाई है जो गारंटी देती है कि दोनों चीजें उच्च संभावना के साथ होंगी:
1. आप बहुत धीरे नहीं चलेंगे (कम पछतावा/low regret)।
2. आप गति सीमा नहीं तोड़ेंगे या ईंधन खत्म नहीं होने देंगे (कम प्रतिबंध उल्लंघन/low constraint violation)।
कैच (Catch): गणित यह दर्शाता है कि यदि आपका "सुरक्षा मार्जिन" (सीमा से आपकी दूरी) छोटा है, तो उल्लंघन का जोखिम बढ़ जाता है। लेकिन यदि आपके पास एक अच्छा सुरक्षा मार्जिन (एक "स्लेटर पॉइंट", जो एक आरामदायक बफर ज़ोन की तरह है) है, तो सिस्टम उच्च विश्वास के साथ आपको सुरक्षित रख सकता है।

तीन जीतों का सारांश

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

यह शोध पत्र कृत्रिम कंप्यूटर प्रयोगों (सिम्युलेटेड गेम्स) का उपयोग करके यह दिखाता है कि ये गणितीय वादे व्यवहार में भी सही साबित होते हैं, जिससे पुष्टि होती है कि नया "शोर-अनुकूली" गणित पुराने तरीकों की तुलना में बेहतर काम करता है जब डेटा साफ होता है।

तकनीकी सारांश: ऑनलाइन कॉनवेक्स ऑप्टिमाइज़ेशन के लिए नॉइज़-एडेप्टिव हाई-प्रोबेबिलिटी रिग्रेट बाउंड्स

समस्या विवरण
यह कार्य ऑनलाइन कॉनवेक्स ऑप्टिमाइज़ेशन (OCO) को तीन विशिष्ट लेकिन परस्पर जुड़े हुए चुनौतियों के तहत संबोधित करता है: (1) फुल-इंफॉर्मेशन सेटिंग में स्ट्रॉन्गली कॉनवेक्स लॉस के लिए नॉइज़-एडेप्टिव हाई-प्रोबेबिलिटी रिग्रेट बाउंड्स प्राप्त करना; (2) फुल-इंफॉर्मेशन से बैंडिट फीडबैक की ओर बढ़ने पर मौलिक कॉन्फिडेंस कॉस्ट (विफलता की संभावना $\delta$ पर निर्भरता) का निर्धारण करना; और (3) स्टोकेस्टिक कंस्ट्रेंट्स वाले कंस्ट्रेंड OCO में संचयी रिग्रेट (cumulative regret) और लॉन्ग-रन कंस्ट्रेंट वायलेशन (long-run constraint violation) दोनों के लिए एक साथ हाई-प्रोबेबिलिटी गारंटी स्थापित करना।

जबकि शास्त्रीय परिणाम यह स्थापित करते हैं कि ऑनलाइन ग्रेडिएंट डिसेंट (OGD) $\alpha$ -स्ट्रॉन्गली कॉनवेक्स लॉस के लिए $O(\frac{G^2}{\alpha} \log T)$ एक्सपेक्टेड रिग्रेट प्राप्त करता है (जहाँ $G$ ग्रेडिएंट नॉर्म्स को बाउंड करता है), हाई-प्रोबेबिलिटी गारंटी अक्सर सुरक्षा-महत्वपूर्ण अनुप्रयोगों के लिए अपर्याप्त रूप से टाइट होती हैं। मानक दृष्टिकोण अज़ुमा-होफ़िंग (Azuma-Hoeffding) असमानता पर निर्भर करते हैं, जो एक मार्टिंगेल डेविएशन टर्म प्रदान करता है जो वर्स्ट-केस ग्रेडिएंट बाउंड $G$ और डोमेन डायमीटर $D$ (विशेष रूप से $GD\sqrt{2T \log(1/\delta)}$ ) के साथ स्केल करता है। यह बाउंड तब ढीला (loose) हो जाता है जब वास्तविक स्टोकेस्टिक नॉइज़ स्तर $\sigma$ , $G$ की तुलना में काफी छोटा होता है, जो कि रेगुलराइज्ड एम्पिरिकल रिस्क मिनिमाइजेशन में एक सामान्य परिदृश्य है। इसके अतिरिक्त, मौजूदा साहित्य में नॉइज़ एडेप्टिविटी, फीडबैक संरचना के अंतर और हाई-प्रोबेबिलिटी कंस्ट्रेंट सेटिस्फैक्शन के एकीकृत उपचार का अभाव है।

कार्यप्रणाली और मुख्य योगदान

यह शोध पत्र नवीन कंसंट्रेशन आर्गुमेंट्स और लोअर-बाउंड कंस्ट्रक्शन के माध्यम से तीन खुले प्रश्नों को हल करता है:

नॉइज़-एडेप्टिव हाई-प्रोबेबिलिटी बाउंड्स (फुल इंफॉर्मेशन):
लेखक सिद्ध करते हैं कि स्टेप साइज़ $\eta_t = 1/(\alpha t)$ के साथ प्रोजेक्टेड OGD एक ऐसा हाई-प्रोबेबिलिटी रिग्रेट बाउंड प्राप्त करता है जहाँ मार्टिंगेल डेविएशन टर्म ग्रेडिएंट बाउंड $G$ के बजाय नॉइज़ लेवल $\sigma$ के साथ स्केल करता है।

कार्यप्रणाली: विश्लेषण एक एक्सपोनेंशियल सुपरमार्टिंगेल तर्क पेश करता है जो कंडिशनली सब-गॉसियन अनुक्रमों (sequences) के लिए अनुकूलित है। यह तकनीक फ्रीडमैन की असमानता (Freedman's inequality) की आवश्यक 'बाउंडेड-डिफरेंस' आवश्यकता को दरकिनार करती है, जिसके लिए आमतौर पर अनबाउंडेड सब-गॉसियन नॉइज़ को ट्रंकेट करने की आवश्यकता होती है। ट्रंकेशन से बचकर, लेखक मार्टिंगेल प्रॉपर्टी को बनाए रखते हैं और एक ऐसा बाउंड प्राप्त करते हैं जहाँ डेविएशन टर्म $O(\sigma D \sqrt{T \log(1/\delta)})$ होता है।
परिणाम: रिग्रेट बाउंड $O(\frac{G^2}{\alpha} \log T + \sigma D \sqrt{T \log(1/\delta)})$ है। यह शास्त्रीय अज़ुमा-होफ़िंग बेसलाइन की तुलना में $G/\sigma$ का मल्टीप्लिकेटिव सुधार प्रदान करता है जब $\sigma \ll G$ हो। प्रमाण ग्रेडिएंट नॉर्म्स के ट्रंकेशन को मार्टिंगेल टेल कंसंट्रेशन से अलग करने के लिए स्वतंत्र प्रोबेबिलिटी बजट का उपयोग करता है।

कॉन्फिडेंस कॉस्ट सेपरेशन (बैंडिट बनाम फुल इंफॉर्मेशन):
यह शोध पत्र एक मिनिमैक्स लोअर बाउंड स्थापित करता है जो स्ट्रॉन्गली कॉनवेक्स OCO के लिए फुल-इंफॉर्मेशन और बैंडिट फीडबैक सेटिंग्स के बीच कॉन्फिडेंस कॉस्ट में एक मौलिक सेपरेशन प्रदर्शित करता है।

कार्यप्रणाली: एडिटिव गॉसियन नॉइज़ के साथ एक एपोक-आधारित टेस्टिंग कंस्ट्रक्शन का उपयोग करते हुए, लेखक एक हार्ड इंस्टेंस बनाने के लिए ब्रेटैग्नोलो-हुबर लेम्मा (Bretagnolle-Huber lemma) और कंडिशनल कपलिंग आर्गुमेंट्स लागू करते हैं।
परिणाम: फुल-इंफॉर्मेशन सेटिंग में, हाई-प्रोबेबिलिटी रिग्रेट $\sqrt{\log(1/\delta)}$ के रूप में स्केल होता है। इसके विपरीत, बैंडिट फीडबैक (जहाँ केवल स्केलर लॉस वैल्यू देखी जाती है) के तहत, रिग्रेट $\log(1/\delta)$ के रूप में लीनियरली स्केल होता है। यह औपचारिक प्रमाण है कि स्ट्रॉन्गली कॉनवेक्स समस्याओं के लिए कॉन्फिडेंस की सूचना-सैद्धांतिक लागत (information-theoretic cost) बैंडिट सेटिंग में स्पष्ट रूप से अधिक है।

सिमल्टेनियस हाई-प्रोबेबिलिटी गारंटी (कंस्ट्रेंड OCO):
लेखक स्लेटर कंडीशन (Slater condition) को संतुष्ट करने वाले स्टोकेस्टिक कंस्ट्रेंट्स के तहत संचयी रिग्रेट और लॉन्ग-रन कंस्ट्रेंट वायलेशन के लिए एक साथ हाई-प्रोबेबिलिटी नियंत्रण प्राप्त करने वाला पहला एल्गोरिदम प्रदान करते हैं।

कार्यप्रणाली: विश्लेषण एक प्राइमल-डुअल OGD फ्रेमवर्क का उपयोग करता है। रिग्रेट बाउंड फ्रीडमैन की असमानता का लाभ उठाता है (जो कंस्ट्रेंट नॉइज़ की लगभग-निश्चित सीमाबद्धता के कारण लागू है)। कंस्ट्रेंट वायलेशन विश्लेषण संचयी वायलेशन को एक अपेक्षित घटक और एक स्टोकेस्टिक मार्टिंगेल घटक में विभाजित करता है। अपेक्षित घटक को सैडल-पॉइंट तर्क और मार्कोव की असमानता के माध्यम से बाउंड किया जाता है, जबकि स्टोकेस्टिक घटक को फ्रीडमैन की असमानता के माध्यम से नियंत्रित किया जाता है।
परिणाम: एल्गोरिदम $O(\sqrt{T \log(m/\delta)})$ रिग्रेट और $O(\frac{\sqrt{T}}{\zeta \delta_1} + m\sqrt{T \log(m/\delta_2)})$ लॉन्ग-रन कंस्ट्रेंट वायलेशन प्राप्त करता है। उल्लेखनीय रूप से, वायलेशन बाउंड अपेक्षित घटक के लिए मार्कोव की असमानता के माध्यम से $1/\delta$ कारक को बनाए रखता है, जबकि स्टोकेस्टिक डेविएशन $\sqrt{\log(1/\delta)}$ के साथ स्केल होता है।

प्रायोगिक सत्यापन
सिंथेटिक प्रयोगों ने सैद्धांतिक भविष्यवाणियों की पुष्टि की है:

नॉइज़ एडेप्टिविटी: एम्पिरिकल टेल स्टैटिस्टिक्स पुष्टि करते हैं कि रिग्रेट क्वांटाइल्स नॉइज़-एडेप्टिव बाउंड ( $\sigma$ -डिपेंडेंट) का अनुसरण करते हैं और जब $\sigma \ll G$ हो, तो वे अज़ुमा-होफ़िंग बेसलाइन ( $G$ -डिपेंडेंट) से काफी नीचे रहते हैं।
कॉन्फिडेंस कॉस्ट: 1D स्ट्रॉन्गली कॉनवेक्स समस्याओं पर प्रयोगों से पता चलता है कि फुल-इंफॉर्मेशन रिग्रेट $\sqrt{\log(1/\delta)}$ के रूप में बढ़ता है, जबकि बैंडिट रिग्रेट $\log(1/\delta)$ के रूप में लीनियरली बढ़ता है, जो सूचना-सैद्धांतिक सेपरेशन को प्रमाणित करता है।
कंस्ट्रेंड OCO: रिग्रेट और वायलेशन के संयुक्त वितरण यह पुष्टि करते हैं कि स्वतंत्र प्रोबेबिलिटी बजटिंग और स्लेटर गैप $\zeta$ के साथ इन्वर्स-लीनियर स्केलिंग प्रभावी है।

महत्ता और दावे
यह शोध पत्र दावा करता है कि यह स्ट्रॉन्गली कॉनवेक्स OCO में नॉइज़ एडेप्टिविटी, फीडबैक संरचना और कंस्ट्रेंट सेटिस्फैक्शन के संगम पर तीन विशिष्ट खुले प्रश्नों को हल करता है।

यह एक नॉइज़-एडेप्टिव रिफाइनमेंट प्रदान करता है, जो दिखाता है कि "प्राइस ऑफ कॉन्फिडेंस" को वर्स्ट-केस ग्रेडिएंट मैग्नीट्यूड से अलग किया जा सकता है और इसके बजाय वास्तविक नॉइज़ स्तर से जोड़ा जा सकता है।
यह कॉन्फिडेंस कॉस्ट में एक औपचारिक सेपरेशन स्थापित करता है, यह सिद्ध करता है कि बैंडिट फीडबैक, फुल-इंफॉर्मेशन के $\sqrt{\log(1/\delta)}$ दंड की तुलना में लीनियर $\log(1/\delta)$ दंड वहन करता है।
यह स्टोकेस्टिक कंस्ट्रेंड सेटिंग में रिग्रेट और कंस्ट्रेंट वायलेशन दोनों के लिए पहली सिमल्टेनियस हाई-प्रोबेबिलिटी गारंटी प्रदान करता है, जिससे उन सांख्यिकीय तंत्रों (मार्कोव बनाम फ्रीडमैन) को स्पष्ट किया जाता है जो प्रत्येक घटक को नियंत्रित करते हैं।

लेखक नोट करते हैं कि कंस्ट्रेंट वायलेशन बाउंड में $1/\delta$ की निर्भरता वर्तमान प्रूफ तकनीक (जो अपेक्षित घटक के लिए मार्कोव की असमानता पर निर्भर है) के लिए टाइट है, इसे $\log(1/\delta)$ में सुधारना एक खुला प्रश्न बना हुआ है जिसके लिए प्राइमल-डुअल सैडल-पॉइंट असमानता के पाथवाइज कंट्रोल की आवश्यकता है। इसी तरह, नॉन-ट्रिवियल बायस-सुपरमार्टिंगेल इंटरैक्शन के साथ बैंडिट सेटिंग्स में नॉइज़ एडेप्टिविटी का विस्तार भविष्य के कार्य के लिए एक दिशा के रूप में पहचाना गया है।

1. "शोर-अनुकूली" (Noise-Adaptive) सफलता (पूर्ण जानकारी)

2. "बैंडिट" वास्तविकता परीक्षण (सीमित जानकारी)

3. "दोधारी तलवार" (प्रतिबंध)

तीन जीतों का सारांश

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