🤖 machine learning

Beyond Bounded Variance: Variance-Reduced Normalized Methods for Nonconvex Optimization under Blum-Gladyshev Noise

यह शोध पत्र ब्लम-ग्लाडिशेव शोर मॉडल (Blum-Gladyshev noise model) के तहत मोमेंटम के साथ और बिना, सामान्यीकृत स्टोकेस्टिक ग्रेडिएंट विधियों के लिए पहले अभिसरण गारंटी (convergence guarantees) स्थापित करता है, जो यह सिद्ध करता है कि वेरिएंस-रिड्यूस्ड नॉर्मलाइज्ड STORM मानक स्मूथनेस (standard smoothness) के तहत मिनिमैक्स ऑप्टिमल $O(\varepsilon^{-4})$ जटिलता प्राप्त करता है, जबकि बिना सीमित डोमेन, बढ़ते बैच आकार, या स्पष्ट एंकरिंग की आवश्यकता के सामान्यीकृत स्मूथनेस (generalized smoothness) के लिए विशिष्ट दरों को अभिलक्षणित करता है।

मूल लेखक: Antesh Upadhyay, Arda Fazla, Abolfazl Hashemi

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

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

CC BY 4.0

मूल लेखक: Antesh Upadhyay, Arda Fazla, Abolfazl Hashemi

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

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

आमतौर पर, गणित की समस्याओं में, हम यह मान लेते हैं कि यह दिशा-सूचक यंत्र काफी भरोसेमंद है। यदि आप एक कदम उठाते हैं, तो दिशा-सूचक में होने वाला शोर (त्रुटि/नॉइज़) समान रहता है, चाहे आप कितनी भी दूर चले गए हों।

समस्या: "चलते-फिरते लक्ष्य" वाला शोर (The "Moving Target" Noise)
यह शोध पत्र एक अधिक जटिल वास्तविकता को संबोधित करता है जिसे ब्लम-ग्लाडेशेव (BG-0) शोर कहा जाता है। कल्पना कीजिए कि आप अपने शुरुआती बिंदु से जितना दूर भटकते हैं, दिशा-सूचक उतना ही अधिक पागलों की तरह घूमने लगता है। "शोर" बढ़ता जाता है क्योंकि आप दूर जा रहे हैं।

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

नया समाधान: "नॉर्मलाइजेशन" (The "Normalized" Approach)
लेखक एक चतुर तरकीब प्रस्तावित करते हैं: नॉर्मलाइजेशन (Normalization)।
दिशा-सूचक यह तय करने के बजाय कि आपका कदम कितना बड़ा होगा, वे कहते हैं: "चाहे दिशा-सूचक कितना भी पागल क्यों न हो जाए, आप केवल एक निश्चित आकार (fixed size) का कदम ही उठाएंगे।"

रूपक (Metaphor): कल्पना कीजिए कि आप एक तूफान में चल रहे हैं। एक सामान्य यात्री एक झोंके में 100 फीट दूर जा सकता है। हमारा नया यात्री कहता है, "मैं केवल एक कदम आगे बढ़ाऊंगा, चाहे हवा कितनी भी तेज चले।"
परिणाम: कदम के आकार को सीमित करके, आप यह गारंटी देते हैं कि आप अपने शुरुआती बिंदु से बहुत दूर नहीं भटकेंगे। चूंकि आप घर के करीब रहते हैं, इसलिए दिशा-सूचक कभी भी बहुत अधिक पागल नहीं होता। आपके आंदोलन को सीमित करके "शोर" को नियंत्रण में रखा जाता है।

परीक्षण किए गए दो तरीके
शोध पत्र इस "निश्चित-कदम" विचार का उपयोग करने के दो विशिष्ट तरीकों का परीक्षण करता है:

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

"सुचारूता" का मोड़ (The "Smoothness" Twist)
शोध पत्र एक विशेष प्रकार के भूभाग को भी देखता है जिसे सामान्यीकृत सुचारूता (Generalized Smoothness) कहा जाता है।

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

मुख्य निष्कर्ष (The Bottom Line)
यह शोध पत्र सिद्ध करता है कि शोर भरे, गैर-कॉन्वेक्स परिदृश्य में नेविगेट करने के लिए आपको तूफान के सटीक नियमों को जानने या मापों के विशाल समूहों की आवश्यकता नहीं है। केवल अपने कदम के आकार को सीमित करके (नॉर्मलाइजेशन) और मोमेंटम या स्मार्ट तुलनाओं का उपयोग करके, आप यह गारंटी दे सकते हैं कि आप अंततः सबसे निचले बिंदु को खोज लेंगे, भले ही शोर बढ़ता जाए।

उन्होंने दिखाया कि यह काम करता है—मानक परिदृश्यों और इन "अजीब तरह से खड़ी" भूमियों दोनों के लिए—और यह बिना किसी जटिल "एंकरिंग" युक्तियों के, इस विशिष्ट प्रकार के शोर वाले, अनबाउंडेड वातावरण के लिए पहला गणितीय आश्वासन प्रदान करता है।

तकनीकी सारांश: ब्लम-ग्लेडीशेव (Blum–Gladyshev) शोर के तहत नॉनकॉन्वेक्स ऑप्टिमाइज़ेशन के लिए वेरिएंस-रिड्यूस्ड नॉर्मलाइज्ड मेथड्स

समस्या का स्वरूप (Problem Formulation)

यह शोध पत्र नॉनकॉन्वेक्स स्टोकेस्टिक ऑप्टिमाइज़ेशन समस्याओं को संबोधित करता है जो $\min_{x \in \mathbb{R}^d} f(x) = \mathbb{E}_\xi[f(x; \xi)]$ के रूप में होती हैं, जहाँ ऑब्जेक्टिव $f$ सामान्यतः नॉनकॉन्वेक्स है। मुख्य चुनौती ब्लम-ग्लेडीशेव (BG-0) शोर मॉडल है, जो कि मानक बाउंडेड वेरिएंस धारणा का एक रिलैक्सेशन (relaxation) है। BG-0 के तहत, स्टोकेस्टिक ग्रेडिएंट का वेरिएंस समान रूप से बाउंडेड नहीं होता है, बल्कि इनिशियलाइजेशन पॉइंट $x_0$ से दूरी के साथ द्विघात (quadratically) रूप से बढ़ता है:
$\mathbb{E}_\xi \|\nabla f(x; \xi) - \nabla f(x)\|^2 \leq B^2 \|x - x_0\|^2 + G^2$
जहाँ $B, G \geq 0$ हैं। यह मॉडल उन परिदृश्यों को कैप्चर करता है जहाँ डीप लर्निंग और अनकन्स्ट्रेंड ऑप्टिमाइज़ेशन में ग्रेडिएंट शोर, इटरेट्स (iterates) के शुरुआती बिंदु से दूर जाने पर बढ़ जाता है। लेखक नोट करते हैं कि इस शोर मॉडल के तहत, अंतर्निहित फीडबैक मैकेनिज्म (जहाँ बड़े इटरेट्स अधिक शोर उत्पन्न करते हैं, जो बदले में इटरेट्स को और दूर धकेलता है) एक स्वाभाविक कठिनाई पैदा करता है, जिससे स्मूथ नॉनकॉन्वेक्स ऑप्टिमाइज़ेशन के लिए सैद्धांतिक लोअर बाउंड $\Omega(\epsilon^{-4})$ से बदलकर $\Omega(\epsilon^{-6})$ हो जाता है [13]।

यह अध्ययन दो स्मूथनेस रिजीम्स (regimes) पर विचार करता है:

स्टैंडर्ड स्मूथनेस ( $L_0$ ): ग्रेडिएंट ग्लोबली लिप्सचिट्ज कंटीन्यूअस (Lipschitz continuous) है।
जनरलाइज्ड स्मूथनेस ( $L^*_{sym}(\alpha)$ और $EL^*_{sym}(\alpha)$ ): लोकल स्मूथनेस कांस्टेंट ग्रेडिएंट नॉर्म के साथ स्केल करता है, विशेष रूप से $\|\nabla f(y) - \nabla f(x)\| \leq (L_0 + L_1 \max_{\theta} \|\nabla f(x_\theta)\|^\alpha) \|y-x\|$ । यह फ्रेमवर्क उच्च-क्रम के पॉलिनॉमियल या एक्सपोनेंशियल कर्वेचर वाले ऑब्जेक्टिव्स को कैप्चर करता है।

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

यह शोध पत्र नॉर्मलाइज्ड स्टोकेस्टिक मेथड्स का प्रस्ताव और विश्लेषण करता है जो बाउंडेड डोमेन, डायनेमिक बैचिंग, या स्पष्ट एंकरिंग (जैसे PASTA [13] जैसे पिछले कार्यों में उपयोग की जाने वाली हलpern-शैली की रेगुलेराइजेशन) पर निर्भर नहीं करते हैं। मुख्य तंत्र नॉर्मलाइजेशन है, जो अपडेट स्टेप साइज को स्टोकेस्टिक ग्रेडिएंट एस्टिमेटर के मैग्नीट्यूड से अलग (decouple) करता है:
$x_{k+1} = x_k - \gamma \frac{v_k}{\|v_k\|}$
यह सुनिश्चित करता है कि ट्राजेक्टरी ग्रोथ नियंत्रित रहे ( $\|x_k - x_0\| \leq k\gamma$ ), जिससे डिस्टेंस-डिपेंडेंट वेरिएंस टर्म $B^2\|x_k - x_0\|^2$ सीमित रहता है।

दो विशिष्ट एल्गोरिदम का विश्लेषण किया गया है:

NSGDM (Normalized Stochastic Gradient Descent with Momentum): दिशा को स्थिर करने के लिए मोमेंटम अपडेट के साथ प्रति इटरेशन एक फ्रेश स्टोकेस्टिक ग्रेडिएंट का उपयोग करता है।
NSTORM (Normalized STORM): एक रिकर्सिव एस्टिमेटर का उपयोग करने वाला वेरिएंस-रिडक्शन मेथड, जो वर्तमान और अगले इटरेट्स पर मूल्यांकित दो स्टोकेस्टिक ग्रेडिएंट्स के अंतर पर आधारित है। यह प्रारंभिक त्रुटि को नियंत्रित करने के लिए एक "शार्प इनिशियलाइजेशन" (एक सिंगल बैच $x_0$ पर) का उपयोग करता है।

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

1. नॉर्मलाइज्ड मोमेंटम का अभिसरण (Convergence of Normalized Momentum - NSGDM)

लेखक सिद्ध करते हैं कि NSGDM, बिना बाउंडेड डोमेन या डायनेमिक बैचिंग के, केवल एक स्टोकेस्टिक ग्रेडिएंट का उपयोग करके BG-0 शोर के तहत अभिसरण करता है।

कॉम्प्लेक्सिटी: यह विधि $O(\epsilon^{-6})$ की ओरैकल कॉम्प्लेक्सिटी प्राप्त करती है।
जनरलाइज्ड स्मूथनेस: यह रेट स्टैंडर्ड स्मूथनेस, $\alpha$ -सिमेट्रिक जनरलाइज्ड स्मूथनेस ( $\alpha \in (0, 1)$ ), और एंडपॉइंट $\alpha=1$ के लिए भी मान्य है। लेखक प्रदर्शित करते हैं कि NSGDM के लिए जनरलाइज्ड स्मूथनेस रेट-न्यूट्रल है; $\epsilon$ -एक्सपोनेंट $-6$ ही रहता है, जबकि जनरलाइज्ड स्मूथनेस पैरामीटर्स केवल लीडिंग कांस्टेंट्स को प्रभावित करते हैं।
महत्व: यह बिना किसी स्पष्ट स्टेबिलाइजेशन मैकेनिज्म के BG-0 शोर के तहत नॉर्मलाइज्ड मोमेंटम के लिए पहला अभिसरण गारंटी प्रदान करता है, जो इस सेटिंग के ज्ञात लोअर बाउंड [13] से मेल खाता है।

2. नॉर्मलाइज्ड वेरिएंस रिडक्शन का अभिसरण (Convergence of Normalized Variance Reduction - NSTORM)

शोध पत्र जांचता है कि क्या वेरिएंस रिडक्शन BG-0 शोर के तहत इष्टतम दरों (optimal rates) को पुनः प्राप्त कर सकता है।

मीन-स्क्वायर स्मूथनेस (MSS): MSS और शार्प इनिशियलाइजेशन के तहत, NSTORM $O(\epsilon^{-4})$ की मिनिमैक्स ऑप्टिमल कॉम्प्लेक्सिटी प्राप्त करता है। यह MSS के तहत BG-0 शोर के लिए लोअर बाउंड [13] से मेल खाता है और जब $B=0$ (बाउंडेड वेरिएंस) हो, तो मानक $O(\epsilon^{-3})$ रेट को पुनः प्राप्त करता है।
एक्सपेक्टेड जनरलाइज्ड स्मूथनेस ( $EL^*_{sym}(\alpha)$ ): एक्सपेक्टेड $\alpha$ $α$ -सिमेट्रिक जनरलाइज्ड स्मूथनेस के तहत, ग्रेडिएंट-डिपेंडेंट स्मूथनेस और डिस्टेंस-डिपेंडेंट शोर के बीच की अंतःक्रिया एक $\alpha$ $α$ -डिपेंडेंट कीमत पेश करती है:
- $\alpha \in (0, 1)$ के लिए, कॉम्प्लेक्सिटी $O(\epsilon^{-(4+\alpha)})$ है।
- $\alpha = 1$ के लिए, कॉम्प्लेक्सिटी $O(\epsilon^{-5})$ है।
महत्व: लेखक पहचानते हैं कि जबकि जनरलाइज्ड स्मूथनेस मोमेंटम-आधारित तरीकों (NSGDM) के लिए "फ्री" है, यह BG-0 शोर के तहत वेरिएंस-रिड्यूस्ड तरीकों (NSTORM) के लिए ग्रेडिएंट मोमेंट्स और ट्राजेक्टरी-डिपेंडेंट वेरिएंस के कपलिंग के कारण एक मापने योग्य दंड (penalty) पेश करती है।

3. मानक दरों की रिकवरी (Recovery of Standard Rates)

विश्लेषण दर्शाता है कि जब डिस्टेंस-ग्रोथ पैरामीटर $B$ शून्य हो जाता है (बाउंडेड वेरिएंस को रिकवर करता है) या जब $B$ और $G$ दोनों शून्य हो जाते हैं (डिटरमिनिस्टिक केस), तो प्रस्तावित विधियाँ मानक इष्टतम दरें प्राप्त करती हैं:

बाउंडेड वेरिएंस: मोमेंटम के लिए $O(\epsilon^{-4})$ , वेरिएंस रिडक्शन के लिए $O(\epsilon^{-3})$ ।
डिटरमिनिस्टिक: नॉर्मलाइज्ड ग्रेडिएंट डिसेंट के लिए $O(\epsilon^{-2})$ ।

प्रयोगात्मक सत्यापन (Experimental Validation)

शोध पत्र में BG-0 ओरैकल के साथ लिप्सचिट्ज जनरलाइज्ड स्मूथ ऑब्जेक्टिव्स (फेज रिट्रीवल और क्यूबिक पॉलिनॉमियल्स) पर सिंथेटिक प्रयोग शामिल हैं।

निष्कर्ष: नॉर्मलाइज्ड मेथड्स (NSGDM और NSTORM) ट्राजेक्टरी ग्रोथ को सफलतापूर्वक नियंत्रित करते हैं और सिंगल-सैंपल SGD की तुलना में कम ग्रेडिएंट नॉर्म प्राप्त करते हैं।
तुलना: डायनेमिक बैचिंग बेसलाइन्स (जैसे PASTA [13]) के विपरीत, जिन्हें शोर की भरपाई के लिए $\sim 10^3$ तक बैच साइज बढ़ाने की आवश्यकता होती है, प्रस्तावित नॉर्मलाइज्ड मेथड्स पूरे ऑप्टिमाइज़ेशन के दौरान बैच साइज एक बनाए रखते हैं, जो यह दर्शाता है कि नॉर्मलाइजेशन बिना वेरिएंस-ग्रोथ कांस्टेंट्स $B$ और $G$ के ज्ञान के प्रभावी रूप से वेरिएंस स्केल को नियंत्रित करता है।

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

शोध पत्र का दावा है कि यह नॉनकॉन्वेक्स स्टोकेस्टिक ऑप्टिमाइज़ेशन के तहत BG-0 शोर में नॉर्मलाइज्ड मेथड्स के लिए पहले अभिसरण गारंटी प्रदान करता है जो निम्नलिखित के बिना काम करते हैं:

बाउंडेड डोमेन।
बढ़ते बैच साइज (डायनेमिक बैचिंग)।
स्पष्ट एंकरिंग या रेगुलेराइजेशन।

यह कार्य इस सिद्धांत को (जो स्थापित करता है कि "जनरलाइज्ड स्मूथ ऑप्टिमाइज़ेशन, स्टैंडर्ड स्मूथ ऑप्टिमाइज़ेशन जितना ही कुशल है" [7]) अधिक चुनौतीपूर्ण BG-0 सेटिंग में विस्तारित करता है। हालांकि, यह इस सिद्धांत की सीमाओं को भी स्पष्ट करता है: जबकि जनरलाइज्ड स्मूथनेस मोमेंटम-आधारित तरीकों के लिए दर को खराब नहीं करती है, यह डिस्टेंस-डिपेंडेंट शोर के तहत वेरिएंस-रिड्यूस्ड तरीकों के लिए एक $\alpha$ -डिपेंडेंट गिरावट पेश करती है। लेखक अनुमान लगाते हैं कि यह गिरावट ग्रेडिएंट-डिपेंडेंट कर्वेचर और डिस्टेंस-डिपेंडेंट वेरिएंस के कपलिंग के कारण स्वाभाविक है, और यह एक खुला प्रश्न बना हुआ है कि क्या कोई मैचिंग लोअर बाउंड या वैकल्पिक विधि इस सेटिंग में इष्टतम $O(\epsilon^{-4})$ दर प्राप्त कर सकती है।