🔢 mathematics

Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe

यह शोध पत्र हाइब्रिड मोमेंटम स्टोकेस्टिक फ्रैंक-वोल्के (Hybrid Momentum Stochastic Frank–Wolfe) एल्गोरिदम का प्रस्ताव करता है, जो नॉन-स्मूथ आउटर फंक्शन्स वाले नॉन-कॉन्वेक्स स्टोकेस्टिक कंपोजिशनल ऑप्टिमाइज़ेशन के लिए एक जनरल लाइज़्ड लीनियर मिनिमाइजेशन ऑरेकल में स्टोकेस्टिक लीनियरइज़ेशन्स का उपयोग करने हेतु टेलर-करेक्टेड फंक्शन ट्रैकिंग के साथ मोमेंटम-आधारित जैकोबियन ट्रैकिंग को जोड़कर एक इष्टतम $\mathcal{O}(K^{-1/4})$ अभिसरण दर (convergence rate) प्राप्त करता है।

मूल लेखक: El Mahdi Chayti

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

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

CC BY 4.0

मूल लेखक: El Mahdi Chayti

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

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

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

यह पेपर एक नए प्रकार के पदयात्री को पेश करता है: हाइब्रिड मोमेंटम स्टोकेस्टिक फ्रैंक-वोल्फ (Hybrid Momentum Stochastic Frank–Wolfe) एल्गोरिदम। यह कैसे काम करता है, यहाँ सरल अवधारणाओं में दिया गया है:

1. समस्या: "ऊबड़-खाबड़ चट्टान" (The Jagged Cliff)

कई वास्तविक दुनिया के परिदृश्यों में, लक्ष्य केवल एक चिकने ढलान को खोजना नहीं होता है। कभी-कभी लक्ष्य सबसे खराब स्थिति को कम करना होता है (जैसे, "अधिकतम नुकसान जो मैं झेल सकता हूँ?") या जोखिम को इस तरह प्रबंधित करना होता है जो गणित में तीखे कोने बनाता है (जैसे वित्त में कंडीशनल वैल्यू-एट-रिस्क - CVaR)।

पुराना तरीका: पिछले तरीकों ने इन ऊबड़-खाबड़ चट्टानों को चलने योग्य बनाने के लिए उन्हें चिकना करने की कोशिश की। लेकिन इससे समस्या बदल जाती है, जिससे वास्तविक दुनिया के लक्ष्य के लिए समाधान कम सटीक हो जाता है।
नया तरीका: यह पेपर कहता है, "आइए हम इन ऊबड़-खाबड़ चट्टानों पर बिना उन्हें चिकना किए चलें।" यह तीखे कोनों को सीधे तौर पर संभालता है।

2. समाधान: दो सहायकों के साथ "अंधे व्यक्ति का मार्गदर्शक" (The Blindfolded Guide)

चूंकि पदयात्री (एल्गोरिदम) पूरे मानचित्र को नहीं देख सकता, इसलिए वे दो "ट्रैकर्स" (सहायकों) पर भरोसा करते हैं जो इलाके का अनुमान लगाने के लिए आगे दौड़ते हैं।

सहायक A (जैकबियन ट्रैकर): यह सहायक ढलान की दिशा का अनुमान लगाता है।
सहायक B (फंक्शन ट्रैकर): यह सहायक ज़मीन की ऊंचाई का अनुमान लगाता है।

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

इस टीम के दो संस्करण हैं:

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

3. "सामान्यीकृत दिशा-सूचक यंत्र" (The Generalized Compass - GLMO)

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

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

4. कोहरे को संभालना (Heavy-Tailed Noise)

वास्तविक दुनिया में, "शोर" (कोहरा) हमेशा सौम्य नहीं होता। कभी-कभी, हवा का एक अचानक झोंका आपको रास्ते से बुरी तरह भटका सकता है (इसे हैवी-टेल्ड नॉइज़/भारी-पूंछ वाला शोर कहा जाता है)।

कई एल्गोरिदम टूट जाते हैं जब हवा बहुत तेज़ होती है।
यह नया एल्गोरिदम इन हिंसक झोंकों को संभालने के लिए बनाया गया है। यह अपने कदम के आकार और मोमेंटम को इस आधार पर समायोजित करता है कि हवा कितनी जंगली है। भले ही शोर भारी हो, फिर भी यह घाटी के निचले हिस्से तक पहुँच जाता है।

5. परिणाम: यह कितनी तेज़ी से जाता है?

यह पेपर गणितीय रूप से सिद्ध करता है कि यह नया पदयात्री बहुत कुशल है:

जटिल, नॉन-स्मूथ समस्याओं के लिए: यह लगभग $1/\sqrt[4]{K}$ (जहाँ $K$ कदमों की संख्या है) की दर से एक अच्छा समाधान पाता है। यह इस प्रकार की समस्याओं के लिए बिना अतिरिक्त मेमोरी या धारणाओं के सैद्धांतिक रूप से संभव सबसे तेज़ गति है।
स्मूथ, कॉनवेक्स समस्याओं के लिए: यह $1/\sqrt[3]{K}$ की गति तक बढ़ जाता है।
"परफेक्ट वर्ल्ड" चेक: यदि कोहरा गायब हो जाता है (कोई शोर नहीं), तो यह एल्गोरिदम सहजता से सबसे अच्छे ज्ञात नियतात्मक (deterministic) तरीके में बदल जाता है, जो यह सिद्ध करता है कि यह आदर्श स्थितियों में भी पूरी तरह से काम करता है।

वास्तविक दुनिया के परीक्षण

लेखकों ने तीन वास्तविक दुनिया की "घाटियों" पर इसका परीक्षण किया:

रोबस्ट रिग्रेशन (Robust Regression): एक ऐसी रेखा खोजना जो डेटा में चरम आउटलेर्स (outliers) होने पर भी डेटा में फिट बैठती है।
पोर्टफोलियो ऑप्टिमाइज़ेशन (Portfolio Optimization): सबसे खराब संभावित नुकसान के जोखिम को कम करने के लिए स्टॉक पोर्टफोलियो का प्रबंधन करना (CVaR)।
मैट्रिक्स कंप्लीशन (Matrix Completion): उपयोगकर्ता रेटिंग को संभालते हुए मूवी रेटिंग टेबल (जैसे नेटफ्लिक्स) में गायब डेटा को भरना।

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

संक्षेप में: यह पेपर हमें मशीन लर्निंग में जटिल, "ऊबड़-खाबड़" अनुकूलन समस्याओं को हल करने के लिए एक नया उपकरण देता है। यह स्मार्ट मेमोरी (मोमेंटम) को एक विशेष दिशा-सूचक यंत्र (GLMO) के साथ जोड़ता है ताकि उन ऊबड़-खाबड़, शोर भरे परिदृश्यों में नेविगेट किया जा सके जिन्हें पिछले उपकरण नहीं संभाल सके।

तकनीकी सारांश: हाइब्रिड मोमेंटम फ्रैंक-वोल्के के माध्यम से स्टोकेस्टिक कंपोजिशनल ऑप्टिमाइजेशन

समस्या का निरूपण
यह कार्य स्टोकेस्टिक कंपोजिशनल ऑप्टिमाइजेशन समस्या को संबोधित करता है, जिसका उद्देश्य इस प्रकार के ऑब्जेक्टिव्स को न्यूनतम करना है:
$\min_{x \in X} \phi(x) := F(f(x), x)$
जहाँ $X \subset \mathbb{R}^d$ एक कॉनवेक्स (convex) और कॉम्पैक्ट (compact) सेट है, $f: X \to \mathbb{R}^n$ एक इनर मैपिंग (inner mapping) है जो केवल शोर वाले स्टोकेस्टिक क्वेरीज़ ( $f(x) = \mathbb{E}_\xi[\tilde{f}(x; \xi)]$ ) के माध्यम से सुलभ है, और $F: \mathbb{R}^n \times X \to \mathbb{R}$ एक डिटरमिनिस्टिक (deterministic) आउटर फंक्शन (outer function) है।

स्टोकेस्टिक सेटिंग में प्राथमिक चुनौती यह है कि जेन्सन के इनइक्वलिटी (Jensen's inequality) के कारण नेइव प्लग-इन एस्टिमेटर्स बायस्ड (biased) होते हैं ( $\mathbb{E}[F(\tilde{f}(x; \xi), x)] \neq F(\mathbb{E}[\tilde{f}(x; \xi)], x)$ )। जबकि मौजूदा स्टोकेस्टिक विधियाँ (जैसे SCGD, NASA, SCSC) इस बायस को मोमेंटम-आधारित ट्रैकर्स और चेन रूल का उपयोग करके संबोधित करती हैं, वे मौलिक रूप से यह आवश्यकता रखती हैं कि आउटर फंक्शन $F$ निरंतर अवकलनीय (continuously differentiable) हो। यह धारणा कई महत्वपूर्ण अनुप्रयोगों को बाहर कर देती है जिनमें नॉन-स्मूथ (non-smooth) आउटर फंक्शन्स शामिल हैं, जैसे कि रोबस्ट मैक्स-ऑफ-लॉस (robust max-of-losses), कंडीशनल वैल्यू-एट-रिस्क (CVaR), और नॉर्म रेगुलराइज़र (norm regularizers)। इसके अतिरिक्त, मौजूदा प्रोजेक्शन-फ्री (projection-free) स्टोकेस्टिक विधियाँ (जैसे LiNASA+ICG) भी $F$ की स्मूथनेस पर निर्भर करती हैं।

कार्यप्रणाली (Methodology)
लेखक हाइब्रिड मोमेंटम स्टोकेस्टिक फ्रैंक-वोल्के एल्गोरिदम प्रस्तावित करते हैं, जो पूरी तरह से कंपोजिट समस्याओं के लिए पहला प्रोजेक्शन-फ्री मेथड है जो नॉन-स्मूथ आउटर फंक्शन्स को हैंडल करता है। मुख्य नवाचार एक जनरल लाइनियर मिनिमाइजेशन ऑरेकल (Generalized Linear Minimization Oracle - GLMO) द्वारा स्टैंडर्ड ग्रेडिएंट-आधारित अपडेट को बदलने में निहित है, जो एक स्टोकेस्टिक एफाइन सरोगेट (stochastic affine surrogate) पर कार्य करता है।

एल्गोरिदम प्रत्येक इटरेशन $k$ पर दो स्टोकेस्टिक ट्रैकर्स बनाए रखता है:

जैकोबियन ट्रैकर ( $V_k$ ): जैकोबियन $\nabla f(y_k)$ के लिए एक पोलियाक-शैली (Polyak-style) का मोमेंटम एस्टिमेटर।
फंक्शन ट्रैकर ( $z_k$ ): फंक्शन वैल्यू $f(y_k)$ के लिए एक एस्टिमेटर।

एल्गोरिदम मेमोरी उपयोग और धारणाओं के बीच संतुलन बनाने के लिए फंक्शन ट्रैकर के दो वेरिएंट प्रदान करता है:

वेरिएंट I (पोलियाक): मेमोरीलेस है लेकिन इसके लिए इनर फंक्शन $f$ का लिप्सचिट्ज़ कंटीन्यूअस (Lipschitz continuous) होना आवश्यक है।
वेरिएंट II (टेलर-करेक्टेड): इसके लिए पिछले इटरेट को स्टोर करना आवश्यक है लेकिन यह फर्स्ट-ऑर्डर टेलर एक्सट्रपलेशन ( $V_k(y_k - y_{k-1})$ ) का उपयोग करके फंक्शन वैल्यू की भविष्यवाणी करता है, जिससे फंक्शन $f$ पर लिप्सचिट्ज़ धारणा की आवश्यकता समाप्त हो जाती है और ट्रैकिंग एरर को क्वाड्रेटिक रिमाइंडर (quadratic remainder) तक कम कर दिया जाता है।

प्रत्येक स्टेप पर, एल्गोरिदम एक एफाइन सरोगेट $\tilde{l}_k(x) = z_k + V_k(x - y_k)$ बनाता है और इसे GLMO में फीड करता है:
$x_{k+1} \in \arg\min_{x \in X} F(\tilde{l}_k(x), x)$
महत्वपूर्ण रूप से, GLMO $F$ को एक ब्लैक बॉक्स की तरह मानता है, और रैखिककृत इनर फंक्शन (linearized inner function) पर इसे सीधे मिनिमाइज करता है, जिसके लिए $F$ के सबग्रेडिएंट की आवश्यकता नहीं होती है। यह विधि को नॉन-स्मूथ $F$ (जैसे $\ell_p$ -norms, max-functions) को कुशलतापूर्वक संभालने की अनुमति देता है, जो अक्सर ऑरेकल कॉल को लीनियर प्रोग्राम (LP) या सेकंड-ऑर्डर कोन प्रोग्राम (SOCP) में कम कर देता है।

मुख्य योगदान

एल्गोरिद्मिक नवीनता: नॉन-स्मूथ आउटर फंक्शन्स के साथ पूरी तरह से कंपोजिट ऑप्टिमाइजेशन के लिए पहले स्टोकेस्टिक प्रोजेक्शन-फ्री एल्गोरिदम का परिचय।
हैवी-टेल्ड नॉइज़ (Heavy-Tailed Noise) के तहत सैद्धांतिक गारंटी: विश्लेषण यह मानता है कि स्टोकेस्टिक ऑरेकल में बाउंडेड $r$ $r$ -थ मोमेंट्स ( $r \in (1, 2]$ $r \in (1, 2]$ ) हैं, जो हैवी-टेल्ड नॉइज़ परिदृश्यों को कवर करता है।
- नॉन-कॉन्वेक्स केस: एल्गोरिदम जेनराइज्ड फ्रैंक-वोल्के गैप में $O(K^{-(r-1)/(3r-2)})$ की कन्वर्जेंस रेट प्राप्त करता है। $r=2$ (फाइनाइट वेरिएंस) के लिए, यह $O(K^{-1/4})$ देता है, जो एक्सपेक्टेड स्मूथनेस के तहत सिंगल-सैंपल प्रोजेक्शन-फ्री स्टोकेस्टिक मेथड्स के मिनिमैक्स-ऑप्टिमल लोअर बाउंड से मेल खाता है।
- कॉन्वेक्स केस: जॉइंट कॉनवेक्सिटी धारणाओं के तहत, प्राइमल रेट $O(K^{-(r-1)/(2r-1)})$ है, जो $r=2$ के लिए $O(K^{-1/3})$ प्राप्त करता है।
डिटरमिनिस्टिक इंटरपोलेशन: एल्गोरिदम डिटरमिनिस्टिक रिजीम के साथ सहजता से इंटरपोलेट करता है। जब ऑरेकल सटीक (जीरो नॉइज़) होता है, तो मोमेंटम पैरामीटर्स को 1 पर सेट करने से व्लाडेरियन एट अल. [2023] का डिटरमिनिस्टिक बेसिक मेथड रिकवर होता है, जो अपने ऑप्टिमल रेट्स ( $O(1/K)$ कॉन्वेक्स के लिए, $\tilde{O}(1/\sqrt{K})$ नॉन-कॉन्वेक्स के लिए) के साथ आता है।
एक्सेलरेशन: स्ट्रॉन्गर $r$ -एवरेज स्मूथनेस धारणाओं (या बाउंडेड हेसियन नॉइज़ मोमेंट्स) के तहत, फ्रेमवर्क नॉन-कॉन्वेक्स रेट को $O(K^{-1/3})$ (at $r=2$ ) तक एक्सेलेरेट करने के लिए STORM वेरिएंस रिडक्शन या हेसियन-करेक्टेड मोमेंटम के साथ एकीकृत होता है।

परिणाम और प्रयोग
पेपर तीन वास्तविक दुनिया की समस्याओं पर संख्यात्मक प्रयोगों के माध्यम से सैद्धांतिक निष्कर्षों को मान्य करता है जिसमें नॉन-स्मूथ $F$ और हैवी-टेल्ड नॉइज़ है:

रोबस्ट मिनिमैक्स स्पार्स रिग्रेशन: डेटा सबसेट्स पर वर्स्ट-केस लॉस को मिनिमाइज करना।
CVaR पोर्टफोलियो ऑप्टिमाइजेशन: S&P 500 रिटर्न्स पर रिस्क-अवर्स ऑप्टिमाइजेशन।
रोबस्ट मैट्रिक्स कंप्लीशन: MovieLens-100K डेटासेट पर $\ell_1$ लॉस का उपयोग करना।

प्रायोगिक परिणाम दर्शाते हैं कि स्टैंडर्ड स्टोकेस्टिक कंपोजिशनल फ्रैंक-वोल्के (वैनिला SCFW) बायस के कारण कन्वर्ज होने में विफल रहता है, और क्लिप्ड वेरिएंट्स प्लेटो (plateau) कर जाते हैं। इसके विपरीत, दोनों प्रस्तावित वेरिएंट (पोलियाक और टेलर) अनुमानित $O(K^{-1/4})$ कन्वर्जेंस रेट प्राप्त करते हैं। टेलर वेरिएंट (वेरिएंट II) को सैद्धांतिक रूप से तब भी रोबस्ट दिखाया गया है जब लिप्सचिट्ज़ धारणा को सत्यापित नहीं किया जा सकता, हालांकि जहाँ यह धारणा लागू होती है वहाँ पोलियाक वेरिएंट थोड़ा बेहतर प्रदर्शन करता है।

महत्व
पेपर व्लाडेरियन एट अल. [2023] द्वारा पहचाने गए एक ओपन प्रॉब्लम को हल करने का दावा करता है, जो पूरी तरह से कंपोजिट ऑप्टिमाइजेशन के लिए नॉन-स्मूथ आउटर फंक्शन के साथ स्टोकेस्टिक एक्सटेंशन के संबंध में था। $F$ की स्मूथनेस आवश्यकता को हटाकर, यह कार्य प्रोजेक्शन-फ्री ऑप्टिमाइजेशन को रिस्क-अवर्स, रोबस्ट और फेयरनेस-कंस्ट्रेंड लर्निंग समस्याओं के एक व्यापक वर्ग में लागू करने में सक्षम बनाता है। यह विधि प्रोजेक्शन-फ्री स्टोकेस्टिक मेथड्स के लिए ऑप्टिमल कॉम्प्लेक्सिटी रेट्स प्राप्त करती है और अपनी कम्प्यूटेशनल दक्षता बनाए रखती है (पिछले तरीकों के विपरीत जिनमें महंगे इनर लूप्स की आवश्यकता होती थी, इसमें प्रति इटरेशन केवल एक GLMO कॉल की आवश्यकता होती है)।