Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration

तकनीकी सारांश: गैर-विस्तारजनक दो-समय-पैमाने का स्टोकेस्टिक सन्निकटन (Non-Expansive Two-Time-Scale Stochastic Approximation)

समस्या विवरण
यह शोध पत्र उस क्षेत्र में दो-समय-पैमाने के स्टोकेस्टिक सन्निकटन (TTSA) की अभिसरण दरों (convergence rates) की जांच करता है जहाँ 'फास्ट मैप' संकुचित (contractive) है, लेकिन 'रिड्यूस्ड स्लो मैप' केवल गैर-विस्तारजनक (non-expansive) है। यह सेटिंग मिनिमैक्स ऑप्टिमाइज़ेशन, वेरिएशनल इनइक्वेलिटीज़ और कन्सट्रेंड स्टोकेस्टिक अप्रोक्सिमेशन में उत्पन्न होती है। संकुचित TTSA के विपरीत, जहाँ स्लो वेरिएबल एक अद्वितीय संतुलन (equilibrium) की ओर अभिसरित होता है, गैर-विस्तारजनक मामले में एक संभावित गैर-एकल (non-singleton) फिक्स्ड-पॉइंट सेट होता है। फलस्वरूप, स्वाभाविक प्रदर्शन मीट्रिक विशिष्ट बिंदु से दूरी के बजाय फिक्स्ड-पॉइंट रेसिडुअल $p(y) = h(y) - y$ है।

पूर्व कार्य ने इस क्षेत्र के लिए लास्ट-इटरेट मीन-स्क्वायर रेसिडुअल दर $O(k^{-1/4+\epsilon})$ स्थापित की थी। यह शोध पत्र इस $1/4$ एक्सपोनेंट (exponent) के सैद्धांतिक मूल को समझाने और यह निर्धारित करने का लक्ष्य रखता है कि क्या एल्गोरिद्मिक संशोधनों से इसमें सुधार किया जा सकता है।

कार्यप्रणाली और सैद्धांतिक ढांचा
लेखक त्रुटि गतिकी (error dynamics) को दो अलग-अलग घटकों में विभाजित करते हैं: गैर-विस्तारजनक स्लो रिकर्सन का आंतरिक अभिसरण और फास्ट-ट्रैकिंग त्रुटियों का स्लो ऑरेकल में रिसाव (leakage)।

1. शार्पनेस ऑफ द फिक्स्ड-शेड्यूल KM बैरियर:
   शोध पत्र पहले शास्त्रीय क्रास्नोसेल्स्की-मैन (KM) रेसिडुअल स्केल को स्थापित करता है, जो किसी भी निश्चित स्लो स्टेपसाइज़ शेड्यूल $(\beta_k)$ के लिए $\sum \beta_i(1-\beta_i)$ के व्युत्क्रम द्वारा परिभाषित होता है। एक प्लेनर रोटेशन उदाहरण का उपयोग करते हुए, लेखक एक फाइनाइट-होराइजन लोअर बाउंड सिद्ध करते हैं कि कोई भी अन-रेगुलराइज्ड KM अपडेट दिए गए शेड्यूल के लिए इस स्केल से तेज़ वर्स्ट-केस रेसिडुअल डिके (decay) प्राप्त नहीं कर सकता है। यह निहित करता है कि दर में सुधार करने के लिए एल्गोरिद्मिक रिजीम या ऑरेकल संरचना को बदलने की आवश्यकता है, न कि केवल मानक KM अपडेट के विश्लेषण को परिष्कृत करने की।

2. $1/4$ एक्सपोनेंट का निदान:
   पेपर "फर्स्ट-ऑर्डर फास्ट-मैनिफोल्ड लीकेज" को प्राथमिक बाधा के रूप में पहचानता है। रॉ (raw) TTSA में, स्लो ऑरेकल वास्तविक संतुलन $x^*(Y_k)$ के बजाय वर्तमान फास्ट इटरेट $X_k$ पर मैप का मूल्यांकन करता है। फास्ट कोऑर्डिनेट में स्लो मैप की लिप्सचिट्ज़ निरंतरता (Lipschitz continuity) के कारण, त्रुटि $g(X_k, Y_k) - h(Y_k)$ फास्ट ट्रैकिंग त्रुटि $\|X_k - x^*(Y_k)\|$ के प्रथम-क्रम (first-order) में होती है। ट्रैकिंग त्रुटि स्वयं फास्ट स्टोकेस्टिक वेरिएंस ($\alpha_k$) और मूविंग टारगेट के पीछे के डिटर्मिनिस्टिक लैग ($(\beta_k/\alpha_k)^2$) के बीच संतुलन द्वारा नियंत्रित होती है। मानक सेपरेशन कंडीशन $\beta_k^2/\alpha_k^3 \lesssim 1$ के तहत भी, शार्प KM स्केल और इस फर्स्ट-ऑर्डर लीकेज का संयोजन कुल सैंपल कॉम्प्लेक्सिटी $T^{-1/4+o(1)}$ प्रदान करता है। सेपरेशन कंडीशन का उल्लंघन करना दर में सुधार नहीं करता है; यह केवल बॉटलनेक को सांख्यिकीय वेरिएंस से मूविंग-टार्गेट लैग की ओर स्थानांतरित करता है, जो अभी भी एक फर्स्ट-ऑर्डर परटर्बेशन के रूप में प्रवेश करता है।

3. रेसिडुअल प्रीकंडीशनिंग के माध्यम से बायस करेक्शन:
   फर्स्ट-ऑर्डर लीकेज से पार पाने के लिए, लेखक एक रेसिडुअल-प्रीकंडिश्न्ड स्लो ऑरेकल पेश करते हैं। फास्ट और स्लो मैप्स के डेरिवेटिव्स का उपयोग करते हुए, वे एक करेक्शन टर्म का निर्माण करते हैं जो फास्ट ट्रैकिंग त्रुटि पर रैखिक निर्भरता को रद्द करता है।
   विशेष रूप से, यदि $A(y) = I - \nabla_x f(x^*(y), y)$ और $C(y) = \nabla_x g(x^*(y), y)$ है, तो प्रीकंडीशनर $P^*(y) = C(y)A(y)^{-1}$ है। सुधारा गया ऑरेकल इस प्रकार परिभाषित है:
   $$H_{corr}(x, y) = g(x, y) + P^*(y)(f(x, y) - x)$$
   टेलर एक्सपेंशन से पता चलता है कि यह करेक्शन स्लो ऑरेकल बायस को फर्स्ट-ऑर्डर ($O(\|e\|)$) से घटाकर सेकंड-ऑर्डर ($O(\|e\|^2)$) कर देता है, जहाँ $e$ फास्ट ट्रैकिंग त्रुटि है।

मुख्य योगदान और परिणाम

शोध पत्र तीन मुख्य सैद्धांतिक परिणाम प्रस्तुत करता है, जो रॉ मेथड के निदान से लेकर संरचित ऑरेकल धारणाओं के तहत अनुकूलित एल्गोरिदम तक प्रगति करते हैं।

1. फिक्स्ड-शेड्यूल लोअर बाउंड:
   लेखक सिद्ध करते हैं कि किसी भी फिक्स्ड स्लो स्टेपसाइज़ शेड्यूल के लिए, अन-रेगुलराइज्ड KM इटरेशन का मीन-स्क्वेयर रेसिडुअल $(\sum \beta_i(1-\beta_i))^{-1}$ के स्केल से समान रूप से बेहतर नहीं हो सकता है। यह पुष्टि करता है कि $1/4$ एक्सपोनेंट रॉ TTSA में ढीले विश्लेषण का आर्टिफैक्ट नहीं है, बल्कि शार्प KM स्केल और फर्स्ट-ऑर्डर लीकेज का परिणाम है।

2. नेस्टेड बायस-करेक्टेड एल्गोरिदम ($T^{-1/3}$):
   एक नेस्टेड टिखोनोव-KM फ्रेमवर्क में, लेखक रेसिडुअल प्रीकंडीशनिंग लागू करते हैं।

• अन-करेक्टेड: रॉ ऑरेकल के साथ नेस्टेड मेथड कुल सैंपल रेट $T^{-1/4+o(1)}$ प्राप्त करता है।
• करेक्टेड: प्रीकंडिश्न्ड ऑरेकल का उपयोग करके, स्लो ऑरेकल का स्क्वेर्ड बायस $O(n^{-1})$ के बजाय $O(n^{-2})$ ($n$ इनर सैंपल्स की संख्या है) हो जाता है। यह संरचनात्मक परिवर्तन कुल सैंपल कॉम्प्लेक्सिटी को $T^{-1/3+o(1)}$ तक सुधार देता है।
• नोट: यह परिणाम यह मानता है कि सटीक प्रीकंडीशनर $P^*(y)$ या एक विशिष्ट प्रोडक्ट-एक्यूरेसी कंडीशंस को संतुष्ट करने वाला एस्टिमेटर उपलब्ध है।

3. सिंगल-लूप लर्नड प्रीकंडीशनर ($T^{-1/2}$):
   नेस्टेड मेथड में बार-बार इनर-लूप सॉल्व्स की लागत से बचने के लिए, लेखक एक सिंगल-लूप एल्गोरिदम प्रस्तावित करते हैं जो फास्ट इक्विलिब्रियम, स्लो वेरिएबल और प्रीकंडीशनर मैट्रिक्स को ऑनलाइन ट्रैक करता है।

• यह विधि स्टोकेस्टिक डेरिवेटिव ऑब्जर्वेशन्स का उपयोग करके $X_k$, $Y_k$, और $P_k$ के रनिंग एस्टिमेट बनाए रखती है।
• स्मूथनेस धारणाओं (मैप्स की डिफरेंशिएबिलिटी और डेरिवेटिव ऑरेकल तक पहुंच) के तहत, यह दृष्टिकोण प्रति इटरेशन $O(1)$ प्रिमिटिव सैंपल्स के साथ कुल सैंपल रेट $T^{-1/2+o(1)}$ प्राप्त करता है।
• यह सुधार लीकेज प्रीकंडीशनर को ऑनलाइन सीखने की क्षमता पर निर्भर करता है, जो प्रभावी रूप से इनर सॉल्व की लागत को एमोर्टाइज (amortize) करता है।

महत्व और दावे
शोध पत्र का दावा है कि यह नॉन-एक्सपेंसिव TTSA में $1/4$ एक्सपोनेंट के लिए पूर्ण सैद्धांतिक स्पष्टीकरण प्रदान करता है, जिसका श्रेय शार्प KM रेसिडुअल स्केल और फर्स्ट-ऑर्डर फास्ट-मैनिफोल्ड लीकेज के बीच परस्पर क्रिया को दिया जाता है। प्राथमिक योगदान यह प्रदर्शित करना है कि यह बैरियर मौलिक नहीं है, बल्कि "रॉ" ऑरेकल संरचना के लिए विशिष्ट है।

एक रेसिडुअल-प्रीकंडिश्न्ड ऑरेकल पेश करके, लेखक दिखाते हैं कि लीकेज को सेकंड-ऑर्डर तक कम किया जा सकता है, जिससे अभिसरण दरों में सुधार होता है। $T^{-1/3}$ का परिणाम एक प्रमाण के रूप में कार्य करता है कि बायस करेक्शन प्रभावी है, जबकि $T^{-1/2}$ का परिणाम यह दर्शाता है कि यदि डेरिवेटिव जानकारी उपलब्ध है, तो इन लाभों को सिंगल-लूप सेटिंग में प्राप्त किया जा सकता है। लेखक स्पष्ट रूप से इन परिणामों को "स्ट्रक्चर्ड-ऑरेकल" उपलब्धियों के रूप में फ्रेम करते हैं, यह नोट करते हुए कि वे डिफरेंशिएबिलिटी और जैकोबियन-संबंधित जानकारी तक पहुंच पर निर्भर करते हैं, जो उन्हें ब्लैक-बॉक्स नॉन-एक्सपेंसिव फिक्स्ड-पॉइंट मेथड्स से अलग करता है। यह कार्य यह दावा नहीं करता है कि यह सामान्य ब्लैक-बॉक्स ऑरेकल के लिए समस्या को हल करता है, बल्कि यह पहचानता है कि स्मूथनेस की उपस्थिति में अभिसरण को तेज करने के लिए विशिष्ट संरचनात्मक संशोधन (बायस कैंसिलेशन) की आवश्यकता है।