📊 statistics

Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory

यह शोध पत्र समय-परिवर्ती संचलन लागत (time-varying movement costs) वाले अनकन्स्ट्रेंड ऑनलाइन कॉनवेक्स ऑप्टिमाइज़ेशन के लिए एक नवीन पैरामीटर-मुक्त एल्गोरिदम प्रस्तावित करता है जो पहला कंपैरेटर-एडेप्टिव डायनेमिक रिग्रेट बाउंड प्राप्त करता है, जिसे फिर विलंबित फीडबैक और समय-परिवर्ती मेमोरी से जुड़ी समस्याओं के लिए इष्टतम गारंटी स्थापित करने के लिए लागू किया जाता है।

मूल लेखक: Hao Qiu, Andrew Jacobsen, Emmanuel Esposito, Mengxiao Zhang

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

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

CC BY 4.0

मूल लेखक: Hao Qiu, Andrew Jacobsen, Emmanuel Esposito, Mengxiao Zhang

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

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

यह शोध पत्र उस जहाज को चलाने का एक नया, स्मार्ट तरीका पेश करता है, जो विशेष रूप से दो पेचीदा समस्याओं से निपटता है: बदलती लागत (changing costs) और देरी से मिलने वाली जानकारी (delayed information)।

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

1. समस्या: "बदलता लक्ष्य" और "भारी बैकपैक"

मानक नेविगेशन में, आप बस यह चाहते हैं कि आप सबसे अच्छे मार्ग से कितना भटक गए हैं उसे कम करें। लेकिन वास्तविक दुनिया में, अपना रास्ता बदलना मुफ्त नहीं होता।

मूवमेंट कॉस्ट (गति की लागत): कल्पना कीजिए कि आपके जहाज पर एक भारी बैकपैक है। हर बार जब आप दिशा बदलने के लिए पहिया घुमाते हैं, तो बैकपैक और भारी हो जाता है, जिससे अधिक ईंधन जलता है। अतीत में, शोधकर्ताओं ने माना था कि यह "ईंधन की लागत" हमेशा एक समान रहती है।
समय-परिवर्तित लागत (Time-Varying Costs): लेखकों ने महसूस किया कि वास्तविक जीवन में, मुड़ने की लागत बदलती रहती है। कभी पानी शांत होता है (मुड़ने की लागत कम), और कभी तूफान आता है (मुड़ने की लागत अधिक)। वे एक ऐसा एल्गोरिदम चाहते थे जो मौसम के पूर्वानुमान को पहले से जाने बिना इन बदलते ईंधन खर्चों को संभाल सके।
"बदलता लक्ष्य" (The Moving Target): वे एक ऐसे लक्ष्य का भी पीछा करना चाहते थे जो इधर-उधर घूमता रहता है (डायनामिक रिग्रेट), न कि केवल एक निश्चित बिंदु पर रुकने की कोशिश करते हैं।

2. समाधान: एक "स्मार्ट, स्वयं-समायोजित कप्तान"

लेखकों ने एक नया एल्गोरिदम (एक "कप्तान") बनाया है जो पैरामीटर-मुक्त (parameter-free) है।

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

3. "बैचिंग" (Batching) की तरकीब: सिग्नल का इंतज़ार करना

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

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

4. दो वास्तविक दुनिया के अनुप्रयोग

लेखकों ने दिखाया कि उनका "स्मार्ट कप्तान" अन्य दो कठिन नेविगेशन समस्याओं को "बदलती मूवमेंट कॉस्ट" की समस्या में बदलकर हल कर सकता है:

A. "देर से आने वाली डाक" की समस्या (Delayed Feedback)

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

B. "कम समय की याददाश्त" की समस्या (Time-Varying Memory)

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

सारांश

संक्षेप में, यह शोध पत्र निर्णय लेने के लिए एक यूनिवर्सल नेविगेशन टूल प्रदान करता है।

यह तब काम करता है जब विचार बदलने की लागत बेतहाशा बदलती रहती है।
इसे आपको पहले से पैरामीटर्स का अनुमान लगाने की आवश्यकता नहीं होती।
यह ऊर्जा बर्बाद करने से बचने के लिए एक स्मार्ट वेटिंग स्ट्रैटेजी का उपयोग करता है।
यह देरी से मिलने वाले फीडबैक और बदलती मेमोरी की समस्याओं को "लागत वाली मूवमेंट" की समस्याओं के रूप में हल करता है।

लेखक दावा करते हैं कि इन विशिष्ट, जटिल परिदृश्यों के लिए ऐसा लचीला, "पैरामीटर-मुक्त" समाधान मिलना पहली बार हुआ है।

तकनीकी सारांश: समय-परिवर्तनीय संचलन लागत के साथ पैरामीटर-मुक्त डायनेमिक रिग्रेट (Parameter-free Dynamic Regret with Time-varying Movement Costs)

1. समस्या सेटिंग (Problem Setting)

यह शोध पत्र गैर-स्थिर वातावरण (non-stationary environments) में अनकन्स्ट्रेंड ऑनलाइन कॉन्वेक्स ऑप्टिमाइज़ेशन (Unconstrained Online Convex Optimization - OCO) को संबोधित करता है जहाँ शिक्षार्थी (learner) को समय-परिवर्तनीय संचलन लागत (time-varying movement costs) का सामना करना पड़ता है।

मानक OCO सेटिंग में, एक शिक्षार्थी एक उत्तल स्थान (convex space) $\mathcal{W}$ (विशेष रूप से इस कार्य में $\mathbb{R}^n$ ) से एक निर्णय $w_t$ चुनता है और एक उत्तल हानि (convex loss) $f_t(w_t)$ का सामना करता है। लक्ष्य तुलनाकर्ताओं (comparators) के अनुक्रम $(u_1, \dots, u_T)$ के विरुद्ध डायनेमिक रिग्रेट (dynamic regret) को कम करना है:
$R_T(u_{1:T}) = \sum_{t=1}^T f_t(w_t) - \sum_{t=1}^T f_t(u_t)$

यह कार्य इस समस्या को एक संचलन लागत (movement cost) दंड जोड़कर विस्तारित करता है जो क्रमिक निर्णयों के बीच की दूरी के समानुपाती है। महत्वपूर्ण रूप से, इस लागत को नियंत्रित करने वाला गुणांक $\lambda_t$ समय-परिवर्तनीय (time-varying) और अनिश्चित है। शिक्षार्थी का उद्देश्य असममित डायनेमिक रिग्रेट (asymmetric dynamic regret) को कम करना है:
$R_T(u_{1:T}, \lambda_{1:T}) = \sum_{t=1}^T \left( f_t(w_t) - f_t(u_t) + \lambda_t \|w_t - w_{t-1}\| \right)$
ध्यान दें कि इस असममित सूत्रीकरण में तुलनाकर्ता अनुक्रम $(u_t)$ संचलन लागत दंड का सामना नहीं करता है, जिससे यह समस्या सममित संस्करण (symmetric variant) की तुलना में अधिक कठिन हो जाती है।

प्राथमिक चुनौती ऐसे पैरामीटर-मुक्त (parameter-free) (तुलनाकर्ता-अनुकूल) एल्गोरिदम डिजाइन करना है जिन्हें निम्नलिखित की पूर्व जानकारी की आवश्यकता नहीं होती:

तुलनाकर्ता नॉर्म बाउंड $M = \max_t \|u_t\|$ ।
तुलनाकर्ता पथ लंबाई (path length) $P_T = \sum_{t=2}^T \|u_t - u_{t-1}\|$ ।
ग्रेडिएंट नॉर्म्स (gradient norms) $\|g_t\|$ का अनुक्रम।
संचलन लागत गुणांकों $\lambda_t$ का अनुक्रम।

2. कार्यप्रणाली (Methodology)

लेखक एक पदानुक्रमित एल्गोरिद्मिक ढांचे (hierarchical algorithmic framework) का प्रस्ताव करते हैं जिसमें तीन मुख्य घटक शामिल हैं:

A. समय-परिवर्तनीय रेगुलराइजेशन के साथ कंपोजिट मिरर डिसेंट (Algorithm 1)

आधार एल्गोरिदम एक कंपोजिट मिरर डिसेंट (Composite Mirror Descent) अपडेट का उपयोग करता है। प्रत्येक दौर $t$ में, ग्रेडिएंट $g_t$ और अगले संचलन लागत $\lambda_{t+1}$ को देखने के बाद, शिक्षार्थी $w_{t+1}$ को निम्न को मिनिमाइज करके अपडेट करता है:
$w_{t+1} = \arg\min_{w} \left( \langle g_t, w \rangle + D_\psi(w | w_t) + \phi_t(w) \right)$

रेगुलराइज़र $\psi(w)$ : एक लॉग-लीनियर फंक्शन जिसे अनबाउंडेड डोमेन को संभालने के लिए डिज़ाइन किया गया है।
करेक्शन टर्म $\phi_t(w)$ : एक समय-परिवर्तनीय क्वाड्रेटिक टर्म जिसे $\beta_t^2 = (\|g_t\| + \lambda_{t+1})^2$ द्वारा स्केल किया गया है। यह टर्म एक "डायनेमिक फ्रिक्शन" (गतिशील घर्षण) के रूप में कार्य करता है, जो इटरेट्स (iterates) को स्थिर करता है। जब संचलन लागत या ग्रेडिएंट अधिक होते हैं, तो दंड बढ़ जाता है, जिससे अपडेट सीमित हो जाते हैं; जब वे कम होते हैं, तो दंड शिथिल हो जाता है।

B. पैरामीटर-मुक्त मेटा-एल्गोरिदम (Algorithm 2)

$M$ , $P_T$ , और ग्रेडिएंट/मूवमेंट स्केल्स की पूर्व जानकारी की आवश्यकता को समाप्त करने के लिए, लेखक एक मेटा-एल्गोरिदम का उपयोग करते हैं जो अलग-अलग लर्निंग रेट $\eta_i$ वाले समानांतर इंस्टेंस के ग्रिड को बनाए रखता है।

शिक्षार्थी सभी इंस्टेंस के निर्णयों का योग खेलता है।
कुल रिग्रेट को "सर्वश्रेष्ठ" इंस्टेंस (जो इष्टतम $\eta$ का अनुमान लगाता है) के रिग्रेट और अन्य इंस्टेंस से होने वाली एक छोटी योज्य लागत (additive cost) में विभाजित किया जाता है।
परिणाम: इससे $\tilde{O}\left( \sqrt{(M + P_T) \sum_{t} (\|g_t\|^2 + \lambda_{t+1}^2) \|u_t\|} \right)$ का रिग्रेट बाउंड प्राप्त होता है।
सीमा (Limitation): यह बाउंड संचलन लागतों पर द्विघात (quadratically) निर्भर करता ( $\lambda_{t+1}^2$ ), जो कि तब उप-इष्टतम (suboptimal) है जब ग्रेडिएंट्स छोटे हों लेकिन संचलन लागत अधिक हो।

C. एडेप्टिव फर्स्ट-ऑर्डर रिडक्शन (Algorithm 3)

संचलन लागतओं पर निर्भरता को द्विघात (quadratic) से रैखिक (linear) में सुधारने के लिए, लेखक एक एडेप्टिव बैचिंग (adaptive batching) तंत्र पेश करते हैं।

तंत्र: एल्गोरिदम एक एपोक (epoch) के दौरान बफर $H_\tau$ में ग्रेडिएंट्स को संचित करता है। यह केवल तभी बेस लर्नर को अपडेट ट्रिगर करता है जब संचित ग्रेडिएंट नॉर्म $\|H_\tau\|$ , वर्तमान संचलन लागत $\lambda_{t+1}$ से अधिक हो जाता है।
तर्क: यदि संचलन लागत अधिक है, तो एल्गोरिदम तब तक प्रतीक्षा करता है जब तक कि "सिग्नल" (ग्रेडिएंट) इतना मजबूत न हो जाए कि वह "लागत" (मूवमेंट कॉस्ट) को उचित ठहरा सके।
परिणाम: यह संचलन लागतओं पर रिग्रेट की निर्भरता को $\lambda^2$ से घटाकर $\lambda \|g\|$ कर देता है।

3. मुख्य योगदान (Key Contributions)

समय-परिवर्तनीय लागतों के साथ प्रथम पैरामीटर-मुक्त डायनेमिक रिग्रेट: यह शोध पत्र अनिश्चित (arbitrary), समय-परिवर्तनीय संचलन लागतों के साथ अनकन्स्ट्रेंड OCO के लिए पहले तुलनाकर्ता-अनुकूल (comparator-adaptive) डायनेमिक रिग्रेट बाउंड स्थापित करता है।
इष्टतम अनुकूलन क्षमता (Optimal Adaptivity): प्रस्तावित एल्गोरिदम एक साथ अनुकूलित होते हैं:
- तुलनाकर्ता जटिलता ( $M$ और $P_T$ )।
- वास्तविक ग्रेडिएंट अनुक्रम ( $\|g_t\|$ )।
- समय-परिवर्तनीय संचलन गुणांक ( $\lambda_t$ )।
सुधारित संचलन लागत निर्भरता: एडेप्टिव बैचिंग रणनीति (Algorithm 3) पेश करके, लेखक $\sum (\|g_t\|^2 + \lambda_t \|g_t\|) \|u_t\|$ के साथ स्केल होने वाला रिग्रेट बाउंड प्राप्त करते हैं। यह $\lambda_t^2$ वाले पिछले सेकंड-ऑर्डर बाउंड की तुलना में एक महत्वपूर्ण सुधार है, विशेष रूप से उन स्थितियों में जहाँ ग्रेडिएंट्स छोटे होते हैं।
अन्य समस्याओं में नवीन रिडक्शन (Reductions to Other Problems): इस ढांचे को अन्य ऑनलाइन लर्निंग समस्याओं को समय-परिवर्तनीय संचलन लागत सेटिंग्स में अनुवादित करके उन्हें हल करने के लिए एक प्रिमिटिव (primitive) के रूप में दिखाया गया है:
- विलंबित फीडबैक (Delayed Feedback) के साथ OCO: गायब ग्रेडिएंट्स की संख्या को संचलन लागत स्केल के रूप में माना जाता है।
- समय-परिवर्तनीय मेमोरी (Time-Varying Memory) के साथ OCO: मेमोरी लंबाई के उतार-चढ़ाव को समय-परिवर्तनीय संचलन लागतों में मैप किया जाता है।

4. मुख्य परिणाम (Main Results)

सैद्धांतिक गारंटी (Theoretical Guarantees)

Algorithm 3 (सुधारित संस्करण) के लिए, शोध पत्र एक डायनेमिक रिग्रेट की गारंटी देता है:
$\tilde{O}\left( (M + P_T)L + \sqrt{(M + P_T) \sum_{t=1}^T (\|g_t\|^2 + \lambda_t \|g_t\|) \|u_t\|} \right)$
जहाँ $L$ एक लिप्सचिट्ज़-समान स्थिरांक (Lipschitz-like constant) है जो $G + \lambda_{\max}$ से संबंधित है।

अनुप्रयोग 1: विलंबित फीडबैक (Delayed Feedback)

लेखक $\lambda_t = G |m_t|$ सेट करके विलंबित फीडबैक वाले OCO को अपने सेटिंग में रिड्यूस करते हैं, जहाँ $|m_t|$ समय $t$ पर गायब ग्रेडिएंट्स की संख्या है।

परिणाम: वे $\tilde{O}\left( (M + P_T)L + G\sqrt{(M^2 + MP_T)(T + d_{\text{tot}})} \right)$ का पैरामीटर-मुक्त डायनेमिक रिग्रेट प्राप्त करते हैं।
लाभ: यह अनबाउंडेड डोमेन को संभालकर और "इन-ऑर्डर" फीडबैक की प्रतिबंधात्मक धारणा के बिना, अधिकतम विलंब $d_{\max}$ के बजाय कुल विलंब $d_{\text{tot}}$ पर टighter निर्भरता प्राप्त करके पूर्व कार्य (जैसे, Wan et al., 2024) में सुधार करता है।

अनुप्रयोग 2: समय-परिवर्तनीय मेमोरी (Time-Varying Memory)

लेखक समय-परिवर्तनीय मेमोरी (जहाँ लॉस पिछले $b_t$ निर्णयों पर निर्भर करता है) वाले OCO को अपने सेटिंग में रिड्यूस करते हैं।

परिणाम: वे $\tilde{O}\left( (M + P_T)L + \sqrt{M(M + P_T)(H^2 T + GH \sum b_t^2)} \right)$ का रिग्रेट बाउंड प्राप्त करते हैं।
लाभ: यह अनबाउंडेड डोमेन धारणा को हटाकर और मेमोरी लंबाई अनुक्रम पर निर्भरता को परिष्कृत करके, समय-परिवर्तनीय मेमोरी लंबाई के साथ अनकन्स्ट्रेंड OCO के लिए पहला डायनेमिक रिग्रेट गारंटी है। यह Zhao et al. (2023) की तुलना में सुधार करता है।

5. महत्व और दावे (Significance and Claims)

शोध पत्र का दावा है कि इसके परिणाम ऑनलाइन लर्निंग की कई चुनौतीपूर्ण दिशाओं के एकीकरण का प्रतिनिधित्व करते हैं:

एकीकरण (Unification): यह अनकन्स्ट्रेंड ऑप्टिमाइज़ेशन, डायनेमिक रिग्रेट और संचलन लागत के बीच के अंतर को पाटता है, जो एक ऐसा संयोजन है जिसे पहले अनएक्सप्लोर्ड (unexplored) रखा गया था।
बहुमुखी प्रतिभा (Versatility): ढांचा यह प्रदर्शित करता है कि संचलन लागतों के साथ OCO एक शक्तिशाली प्रिमिटिव है। केवल "गायब जानकारी" (विलंबित फीडबैक में) या "मेमोरी डिपेंडेंसी" को संचलन दंड के रूप में व्याख्या करके, इन जटिल सेटिंग्स के लिए इष्टतम डायनेमिक रिग्रेट बाउंड प्राप्त किए जा सकते हैं।
इष्टतमता (Optimality): लेखक दावा करते हैं कि पथ लंबाई $P_T$ और तुलनाकर्ता नॉर्म्स पर उनकी निर्भरता (लॉग फैक्टर को छोड़कर) मिनिमैक्स इष्टतम (minimax optimal) है, और संचलन लागतों पर प्रथम-क्रम (first-order) निर्भरता उतार-चढ़ाव वाले दंडों वाले सेटिंग्स में इष्टतमता प्राप्त करने के लिए एक आवश्यक परिशोधन है।
व्यावहारिकता (Practicality): एल्गोरिदम कुशल हैं, जिन्हें प्रति दौर $O(d \log T)$ गणना की आवश्यकता होती है, जो मानक पैरामीटर-मुक्त OCO एल्गोरिदम की जटिलता से मेल खाती है।

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