🤖 machine learning

SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums

यह शोध पत्र SILAGE का प्रस्ताव करता है, जो नेस्टेड फाइनाइट सम्स (nested finite sums) पर नॉनकॉन्वेक्स ऑप्टिमाइज़ेशन के लिए एक मेमोरी-कुशल, फुल-ग्रेडिएंट-फ्री वेरियंस-रिड्यूस्ड एल्गोरिदम है, जो ग्लोबल फुल-ग्रेडिएंट रिफ्रेशेस को समाप्त करके $\mathcal{O}(n)$ मेमोरी उपयोग प्राप्त करता है और नेस्टेड फंक्शनल सिमिलरिटीज के माध्यम से अपनी कन्वर्जेंस कॉम्प्लेक्सिटी को डेटा ज्योमेट्री के अनुरूप ढालता है।

मूल लेखक: Igor Sokolov, Laurent Condat, Peter Richtárik

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

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

CC BY 4.0

मूल लेखक: Igor Sokolov, Laurent Condat, Peter Richtárik

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

कल्पना कीजिए कि आप एक विशाल, धुंधली घाटी में सबसे निचले बिंदु को खोजने की कोशिश कर रहे हैं (यह एक "ऑप्टिमाइज़ेशन" समस्या है)। इसे करने के लिए, आपको यह जानने की आवश्यकता है कि "नीचे" की दिशा कौन सी है। इस "नीचे" की दिशा की गणना लाखों डेटा पॉइंट्स (सैंपल्स) को देखकर की जाती है।

आमतौर पर, एक सटीक दिशा प्राप्त करने के लिए, आपको एक ही समय में प्रत्येक डेटा पॉइंट को देखना होगा। लेकिन अरबों वस्तुओं वाले आधुनिक डेटासेट्स के साथ, यह समुद्र तट पर रेत के हर एक कण को गिनने जैसा है ताकि यह तय किया जा सके कि किस दिशा में चलना है—इसमें बहुत अधिक समय लगता है और इसके लिए बहुत अधिक मेमोरी की आवश्यकता होती है।

समस्या: "दो-मंजिला" डेटा (The "Double-Decker" Data)

यह शोध पत्र एक विशिष्ट तरीके पर ध्यान केंद्रित करता है जिससे डेटा व्यवस्थित किया गया है। डेटा का एक साधारण ढेर होने के बजाय, कल्पना कीजिए कि डेटा $n$ बड़े गोदामों में संग्रहीत है, और प्रत्येक गोदाम में $m$ बक्से हैं।

पुराना तरीका (PAGE): एक अच्छी दिशा प्राप्त करने के लिए, आपको कभी-कभी हर एक गोदाम तक दौड़ना पड़ता है और उसके अंदर के हर एक बक्से को गिनना पड़ता है। यह धीमा और महंगा है।
दूसरा पुराना तरीका (SILVER): हर गोदाम तक दौड़ने से बचने के लिए, आप अपने दिमाग में हर एक बक्से की दिशा याद रखने की कोशिश करते हैं। लेकिन यदि आपके पास अरबों बक्से हैं, तो आपका मस्तिष्क (मेमोरी) फट जाएगा। आप उन सभी को याद नहीं रख सकते।

समाधान: SILAGE (एक स्मार्ट नेविगेटर)

लेखक एक नई विधि प्रस्तावित करते हैं जिसे SILAGE (सिंगल लूप एवरेज ग्रेडिएंट एस्टिमेटर) कहा जाता है। SILAGE को एक स्मार्ट नेविगेटर के रूप में समझें जो कुशलतापूर्वक घाटी के निचले हिस्से तक पहुँचने के लिए "दो-स्तरीय" रणनीति का उपयोग करता है।

1. "गोदाम प्रबंधक" रणनीति (मेमोरी दक्षता)
हर एक बक्से की दिशा को याद रखने के बजाय (जिसके लिए भारी मेमोरी की आवश्यकता होगी), SILAGE केवल प्रत्येक गोदाम के लिए एक सारांश दिशा (summary direction) याद रखता है।

यदि आपके पास 1,000 गोदाम हैं, तो आपको केवल 1,000 दिशाओं को याद रखने की आवश्यकता है, न कि अरबों बक्से-स्तर की दिशाओं को।
उपमा: किराने की दुकान में हर सेब के स्थान को याद करने के बजाय, आप बस प्रत्येक गलियारे (aisle) में सेबों के औसत स्थान को याद रखते हैं। यह आपके मस्तिष्क पर बहुत हल्का है।

2. "नो फुल-रिसेट" रणनीति (गति)
पुराने तरीके अक्सर यह सुनिश्चित करने के लिए कि आप अपने रास्ते से भटक नहीं रहे हैं, आपको हर कुछ चरणों के बाद पूरे डेटासेट का "पूर्ण ऑडिट" करने के लिए मजबूर करते हैं। SILAGE कहता है, "इसकी कोई आवश्यकता नहीं है!"

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

यह क्यों विशेष है: डेटा के "आकार" को समझना

शोध पत्र का दावा है कि SILAGE अधिक स्मार्ट है क्योंकि यह डेटा की संरचना को समझता है।

परिदृश्य A (समरूप गोदाम - Homogeneous Warehouses): यदि सभी गोदाम मूल रूप से एक जैसे हैं (जैसे, वे सभी एक ही प्रकार के फल बेचते हैं), तो गोदामों के बीच का "अंतर" कम होता है। SILAGE बहुत तेज़ी से चलता है क्योंकि उसे उनके बीच के अंतर की चिंता करने की आवश्यकता नहीं होती।
परिदृश्य B (विभिन्न गोदाम): यदि गोदाम बहुत अलग हैं (जैसे, एक फल बेचता है, दूसरा इलेक्ट्रॉनिक्स), तो SILAGE अनुकूलित हो जाता है। यह समझ जाता है कि "शोर" (noise) गोदामों के बीच के अंतर से आता है और उसके अनुसार अपनी गति को समायोजित करता है।

यह शोध पत्र गणितीय रूप से सिद्ध करता है कि डेटा को केवल एक "बड़ा ढेर" मानने के बजाय "बक्सों के गोदामों" के रूप में मानकर, SILAGE पिछले तरीकों की तुलना में तेज़ और कम मेमोरी का उपयोग कर सकता है, विशेष रूप से जब डेटा बहुत बड़ा हो।

मुख्य निष्कर्ष (The Bottom Line)

SILAGE विशाल डेटासेट्स पर AI मॉडल को प्रशिक्षित करने का एक नया तरीका है जो:

मेमोरी बचाता है: यह प्रत्येक एकल डेटा पॉइंट को याद करने की कोशिश नहीं करता, बल्कि प्रत्येक समूह के सारांश को याद रखता है।
समय बचाता है: यह कभी भी एक साथ पूरे डेटासेट को स्कैन करने के लिए नहीं रुकता; यह केवल छोटे हिस्सों या एक समय में एक समूह को स्कैन करता है।
अनुकूलित होता है: यह स्वचालित रूप से पता लगा लेता है कि डेटा समूह समान हैं या भिन्न, और उसके आधार पर अपने पथ को अनुकूलित करता है।

यह एक ऐसी विधि से स्विच करने जैसा है जिसमें आपको अपने बैकपैक में मानचित्रों का एक पुस्तकालय ले जाने की आवश्यकता होती है, और एक ऐसी विधि में जहाँ आपके पास बस एक स्मार्ट कंपास है जो चलते समय इलाके को पढ़ने में सक्षम है।

तकनीकी सारांश: SILAGE

समस्या विवरण (Problem Statement)

यह शोध पत्र विशाल डेटासेट पर नॉनकॉन्वेक्स एम्पिरिकल रिस्क मिनिमाइजेशन (ERM) को संबोधित करता है जो एक नेस्टेड डबल फाइनाइट-सम स्ट्रक्चर (nested double finite-sum structure) प्रदर्शित करते हैं। ऑब्जेक्टिव फंक्शन को इस प्रकार तैयार किया गया है:
$\min_{x \in \mathbb{R}^d} f(x) := \frac{1}{n} \sum_{i=1}^n f_i(x), \quad \text{जहाँ} \quad f_i(x) := \frac{1}{m} \sum_{j=1}^m f_{i,j}(x)$
यहाँ, $N = nm$ कुल नमूनों (samples) की संख्या है, जिसे $n$ ब्लॉक्स (या सिलोस) में विभाजित किया गया है, जिनमें से प्रत्येक का आकार $m$ है। यह संरचना केंद्रीकृत सेटिंग्स में स्वाभाविक रूप से उत्पन्न होती है, जैसे कि पूल्ड डेटा लेक्स (जैसे कई अस्पतालों के स्वास्थ्य रिकॉर्ड), आउट-ऑफ-कोर लर्निंग जहाँ डेटा मेमोरी से अधिक होता है, या क्लस्टरिंग के माध्यम से जानबूझकर किया गया स्ट्रैटिफिकेशन।

मौजूदा वेरिएंस-रिड्यूस्ड (VR) विधियाँ इस शासन (regime) में एक महत्वपूर्ण ट्रेड-ऑफ का सामना करती हैं:

रिकर्सिव एस्टिमेटर्स (जैसे PAGE, SARAH): ये इष्टतम ओरकल कॉम्प्लेक्सिटी प्राप्त करते हैं लेकिन इनके लिए सभी $nm$ नमूनों पर आवधिक ग्लोबल फुल-ग्रेडिएंट रिफ्रेश (global full-gradient refreshes) की आवश्यकता होती है। ये रिफ्रेश अत्यधिक महंगे होते हैं और स्केलिंग बाधाएं (bottlenecks) उत्पन्न करते हैं।
मेमोरी-आधारित एस्टिमेटर्स (जैसे SILVER, SAGA): ये ग्लोबल रिफ्रेश से बचते हैं लेकिन प्रत्येक व्यक्तिगत नमूने के लिए एक कंट्रोल वेरिएट (control variate) संग्रहीत करने की आवश्यकता होती है, जिसके परिणामस्वरूप विशाल डेटासेट के लिए एक अव्यवहारिक $\mathcal{O}(nm)$ मेमोरी फुटप्रिंट होता है।

लक्ष्य एक ऐसा एल्गोरिदम डिजाइन करना है जो आवधिक ग्लोबल रिफ्रेश को समाप्त करे और साथ ही मेमोरी फुटप्रिंट को केवल ब्लॉक्स की संख्या ( $\mathcal{O}(n)$ ) के समान बनाए रखे, न कि कुल नमूनों के समान।

कार्यप्रणाली: SILAGE

लेखक SILAGE (SIngle Loop Average Gradient Estimator) प्रस्तावित करते हैं, जो नेस्टेड स्ट्रक्चर के लिए अनुकूलित एक सिंगल-लूप वेरिएंस-रिड्यूस्ड एल्गोरिदम है। SILAGE दो वेरिएंस-रिडक्शन दर्शनों को जोड़ता है:

SILVER-शैली की मेमोरी संरचना: प्रत्येक ब्लॉक के लिए एक कंट्रोल वेरिएट (ग्रेडिएंट एस्टिमेटर) बनाए रखता है ( $n$ प्रविष्टियाँ कुल), न कि प्रत्येक नमूने के लिए।
PAGE-शैली का रिकर्सिव ट्रैकिंग: इन एस्टिमेटर्स को स्टोकेस्टिक ग्रेडिएंट्स का उपयोग करके रिकर्सिव रूप से अपडेट करता है।

एल्गोरिदम ब्लॉक्स की संख्या ( $n$ ) और ब्लॉक आकार ( $m$ ) के बीच संबंध के आधार पर अलग-अलग कार्य करता है:

1. $m \ge n$ वाला शासन (एल्गोरिदम 1)

इस शासन में, ब्लॉक का आकार ब्लॉक्स की संख्या के बराबर या उससे बड़ा होता है।

तंत्र (Mechanism): एक एकल ग्लोबल कॉइन फ्लिप यह निर्धारित करता है कि इटरेशन का प्रकार क्या होगा। प्रायिकता $p$ के साथ, एक एकल ब्लॉक $i_t$ को यूनिफॉर्मली रैंडम तरीके से चुना जाता है और उसका पूर्ण स्थानीय ग्रेडिएंट $\nabla f_{i_t}(x_{t+1})$ कंप्यूट किया जाता है (एक "एंकर रिसेट")। प्रायिकता $1-p$ के साथ, किसी भी ब्लॉक को रिसेट नहीं किया जाता है; इसके बजाय, प्रत्येक ब्लॉक से एक एकल सैंपल्ड कंपोनेंट ग्रेडिएंट का उपयोग करके सभी $n$ ब्लॉक्स को रिकर्सिव रूप से अपडेट किया जाता है।
कपलिंग (Coupling): प्रायिकता $p$ को $n/m$ के रूप में सेट किया गया है। यह सुनिश्चित करता है कि किसी विशिष्ट ब्लॉक के रिफ्रेश होने की मार्जिनल प्रायिकता $1/m$ है, जो एक फ्लैट डेटासेट पर मानक PAGE के रिफ्रेश रेट से मेल खाती है, जबकि यह गारंटी देता है कि प्रति इटरेशन अधिकतम एक ब्लॉक ही रिफ्रेश होगा।
लागत (Cost): प्रति-इटरेशन लागत $\mathcal{O}(m)$ है (जो एकल स्थानीय पूर्ण ग्रेडिएंट या $n$ कंपोनेंट ग्रेडिएंट्स द्वारा डोमिनेटेड है)।

2. $n > m$ वाला शासन (एल्गोरिदम 2)

इस शासन में, ब्लॉक्स की संख्या ब्लॉक आकार से अधिक होती है।

तंत्र (Mechanism): एक पूर्ण रिसेट के लिए एक एंकर ब्लॉक $i_t$ चुनना और रिकर्सिव अपडेट के लिए $b_{grp}-1$ आकार का एक छोटा सक्रिय उपसमुच्चय (active subset) $\Omega_t$ चुनना महंगा है।
साझा ड्रिफ्ट (Shared Drift): शेष $n - b_{grp}$ अन-सैंपल किए गए ब्लॉक्स के लिए, एल्गोरिदम फ्रेश ग्रेडिएंट्स नहीं निकालता है। इसके बजाय, यह उनके एस्टिमेटर्स को अपडेट करने के लिए सक्रिय उपसमुच्चय से प्राप्त स्टोकेस्टिक अंतर के औसत के रूप में गणना किए गए एक साझा ड्रिफ्ट (shared drift) $d_t$ को लागू करता है।
कार्यान्वयन दक्षता (Implementation Efficiency): सभी $n$ एस्टिमेटर्स को ड्रिफ्ट के साथ स्पष्ट रूप से अपडेट करने की $\mathcal{O}(n)$ लागत से बचने के लिए, लेखक एक साझा संचयक (accumulator) $q_t$ का उपयोग करके एक कार्यान्वयन-कुशल रूप (एल्गोरिदम 3) प्रस्तावित करते हैं, जिससे बुककीपिंग लागत घटकर $\mathcal{O}(b_{grp})$ हो जाती है।

मुख्य योगदान

1. नेस्टेड स्ट्रक्चर के माध्यम से मेमोरी दक्षता

SILAGE को केवल $\mathcal{O}(n)$ मेमोरी की आवश्यकता होती है (प्रत्येक ब्लॉक के लिए एक $d$ -आयामी वेक्टर और कुछ सहायक वेक्टरों को संग्रहीत करना)। यह फ्लैटनड विधियों (जैसे SILVER) की तुलना में एक महत्वपूर्ण कमी है, जिन्हें $\mathcal{O}(nm)$ मेमोरी की आवश्यकता होती है।

2. आवधिक ग्लोबल रिफ्रेश का उन्मूलन

PAGE और इसके वेरिएंट्स के विपरीत, SILAGE कभी भी सभी $nm $कंपोनेंट्स पर **ग्लोबल फुल-ग्रेडिएंट पास** नहीं करता है। यह प्रति इटरेशन केवल एक स्थानीय ग्रुप ग्रेडिएंट$ \nabla f_i $को ही इवैल्यूएट करता है (एक$ \mathcal{O}(m)$ लागत पर)। इनिशियलाइजेशन (Initialization) मनमाना हो सकता है (जैसे शून्य), जिससे प्रारंभिक ग्लोबल ग्रेडिएंट गणना की आवश्यकता नहीं होती है।

3. नेस्टेड समानता का लाभ उठाना

इसका कन्वर्जेंस विश्लेषण डेटा ज्योमेट्री पर एक नवीन दो-स्तरीय निर्भरता पेश करता है, जो निराशाजनक वर्स्ट-केस लिप्सचिट्ज़ कांस्टेंट्स ( $L_{\max}$ ) से बचता है:

एक्रॉस-ग्रुप समानता ( $\delta_1$ ): यह मापता है कि ग्रुप ग्रेडिएंट्स ग्लोबल ग्रेडिएंट से कितना विचलित होते हैं।
विदिन-ग्रुप समानता ( $\delta_2$ ): यह मापता है कि सैंपल ग्रेडिएंट्स उनके स्थानीय ग्रुप एवरेज से कितना विचलित होते हैं।
कन्वर्जेंस रेट इन कांस्टेंट्स के प्रति स्पष्ट रूप से अनुकूलित होते हैं। $m \ge n$ शासन में, दर मुख्य रूप से $\delta_2$ पर निर्भर करती। $n > m$ शासन में, $\delta_1$ और $\delta_2$ दोनों ही जटिलता को प्रभावित करते हैं, लेकिन एल्गोरिदम उन्हें ऑपरेशनल शासन के आधार पर अलग करता है।

4. मौजूदा विधियों का एकीकरण

SILAGE मौजूदा दृष्टिकोणों को सीमित मामलों (limiting cases) के रूप में एकीकृत करता है:

जब $n=1$ (सिंगल ब्लॉक), तो SILAGE PAGE बन जाता है।
जब $m=1$ (प्रति ब्लॉक एकल सैंपल), तो SILAGE SILVER बन जाता है।

परिणाम और कन्वर्जेंस

शोध पत्र $\epsilon$ -अनुमानित स्टेशनरी पॉइंट ( $\mathbb{E}[\|\nabla f(\tilde{x})\|^2] \le \epsilon$ ) खोजने के लिए टाइट नॉनकॉन्वेक्स कन्वर्जेंस गारंटी प्रदान करता है।

शासन $m \ge n$ :
ग्रेडिएंट कॉम्प्लेक्सिटी $\mathcal{O}\left(nm + \frac{(nL + \sqrt{nm}\delta_2)\Delta_0}{\epsilon}\right)$ है (यह मानते हुए कि इनिशियलाइजेशन सटीक है)। महत्वपूर्ण रूप से, लीडिंग टर्म $\delta_2$ (विदिन-ग्रुप वेरिएंस) पर निर्भर करता है, न कि ग्लोबल फ्लैट समानता या $L_{\max}$ पर।
शासन $n > m$ :
जटिलता $\mathcal{O}\left(nm + \frac{(mL + m\sqrt{n-m}\delta_1 + \sqrt{nm}\delta_2)\Delta_0}{\epsilon}\right)$ है।
यहाँ, एल्गोरिदम एक्रॉस-ग्रुप हेटेरोजेनिटी ( $\delta_1$ ) और विदिन-ग्रुप हेटेरोजेनिटी ( $\delta_2$ ) की लागत के बीच संतुलन बनाता है।

बेसलाइन्स की तुलना में:

ZeroSARAH के विरुद्ध: SILAGE $L_{\max}$ के स्थान पर स्ट्रक्चर्ड $L, \delta_1, \delta_2$ का उपयोग करता है, जो हेटेरोजेनियस शासन में महत्वपूर्ण सुधार प्रदान करता है।
SILVER के विरुद्ध: SILAGE समान या बेहतर ग्रेडिएंट कॉम्प्लेक्सिटी प्राप्त करता है जबकि मेमोरी को $\mathcal{O}(nm)$ से घटाकर $\mathcal{O}(n)$ कर देता है।
D-PAGE के विरुद्ध: जबकि D-PAGE प्रतिस्पर्धी कॉम्प्लेक्सिटी प्रदान करता है, इसे आवधिक ग्लोबल रिफ्रेश की आवश्यकता होती है। SILAGE इन रिफ्रेश को पूरी तरह से हटा देता है, जो $\mathcal{O}(1)$ से $\mathcal{O}(n)$ तक मेमोरी में मामूली वृद्धि के बदले में, सेंट्रलाइज्ड लार्ज-स्केल ट्रेनिंग के सबसे महंगे ऑपरेशन को समाप्त करता है।

महत्व और दावे

लेखक दावा करते हैं कि SILAGE केंद्रीकृत लार्ज-स्केल ऑप्टिमाइजेशन में एक मौलिक स्केलिंग बॉटलनेक को संबोधित करता है। नेस्टेड डबल-सम स्ट्रक्चर का सक्रिय रूप से लाभ उठाकर, SILAGE "दोनों दुनियाओं का सर्वश्रेष्ठ" (best of both worlds) परिदृश्य प्राप्त करता है:

यह रिकर्सिव एस्टिमेटर्स द्वारा आवश्यक आवधिक ग्लोबल फुल-ग्रेडिएंट रिफ्रेश के कंप्यूटेशनल बॉटलनेक से बचता है।
यह प्रत्येक नमूने के लिए कंट्रोल वेरिएट स्टोर करने के लिए आवश्यक मेमोरी बॉटलनेक से बचता है।

शोध पत्र इस बात पर जोर देता है कि मौजूदा बाउंड्स की तुलना में इनके थ्योरिटिकल रेट्स स्ट्रक्चरली टाइट हैं क्योंकि वे नेस्टेड सिमिलरिटी कांस्टेंट्स ( $\delta_1, \delta_2$ ) पर निर्भर करते हैं, जो कि फ्लैटनड सिमिलरिटी कांस्टेंट्स या वर्स्ट-केस स्मूथनेस पैरामीटर्स की तुलना में काफी छोटे हो सकते हैं, विशेष रूप से उन शासन में जहाँ ब्लॉक्स रेडंडेंट या होमोजेनियस होते हैं। सिंथेटिक नॉनकॉन्वेक्स लॉजिस्टिक रिग्रेशन कार्यों पर प्रयोगात्मक परिणाम पुष्टि करते हैं कि SILAGE का प्रदर्शन इसके थ्योरिटिकल प्रेडिक्शंस को ट्रैक करता है, और जब नेस्टेड सिमिलरिटी स्ट्रक्चर अनुकूल होता है, तो यह बेसलाइन्स की तुलना में तेजी से कन्वर्ज होता है।