🔢 mathematics

Decentralized Online Riemannian Optimization Beyond Hadamard Manifolds

यह शोध पत्र एक विकेंद्रीकृत ऑनलाइन रीमानियन अनुकूलन (Riemannian optimization) ढांचे का प्रस्ताव करता है जो एक वक्रता-जागरूक (curvature-aware) आम सहमति चरण को पेश करके हैडामार्ड मैनिफोल्ड्स (Hadamard manifolds) की सीमाओं को दूर करता है, जिससे संभवतः धनात्मक वक्रता वाले मैनिफोल्ड्स पर पूर्ण-सूचना और टू-पॉइंट बैंडिट फीडबैक सेटिंग्स के लिए $O(\sqrt{T})$ रिग्रेट बाउंड प्राप्त होता है।

मूल लेखक: Emre Sahinoglu, Shahin Shahrampour

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

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

CC BY 4.0

मूल लेखक: Emre Sahinoglu, Shahin Shahrampour

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

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

लेकिन क्या होगा यदि दुनिया सपाट नहीं है? क्या होगा यदि ज़मीन घुमावदार है, जैसे कि एक गोले या सैडल (saddle) की सतह? यह रीमानियन मैनिफोल्ड्स (Riemannian manifolds) की दुनिया है। इस शोध पत्र में, लेखक एक बहुत कठिन समस्या का समाधान करते हैं: कैसे एजेंटों (जैसे हाइकर्स या कंप्यूटर) का एक समूह एक समाधान पर सहमत हो सकता है और अपने पथ को अनुकूलित (optimize) कर सकता है जब जिस ज़मीन पर वे चल रहे हैं वह घुमावदार है, संभावित रूप से बाहर की ओर उभरी हुई (धनात्मक वक्रता/positive curvature) है, और वे केवल अपने निकटतम पड़ोसियों से ही बात कर सकते हैं?

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

1. समस्या: "घुमावदार ज़मीन" की चुनौती

पिछले अधिकांश शोधों ने माना था कि ज़मीन या तो पूरी तरह से सपाट थी या अंदर की ओर मुड़ी हुई थी (जैसे एक कटोरा)। इससे हाइकर्स के लिए मिलने के स्थान पर सहमत होना आसान था। हालाँकि, लेखकों ने धनात्मक रूप से घुमावदार सतहों (जैसे एक गेंद की सतह) पर इस समस्या को हल करने का प्रयास किया।

एक गेंद पर, ज्यामिति (geometry) के नियम बदल जाते हैं। यदि दो हाइकर सीधी रेखाओं (geodesics) में चलते हैं जो समानांतर शुरू होती हैं, तो वे अंततः एक-दूसरे से टकरा सकते हैं। यह उनके स्थानों का औसत निकालने को कठिन बना देता है। यदि आप पुराने, सपाट दुनिया के गणित का उपयोग यह बताने के लिए करते हैं कि उन्हें कहाँ मिलना चाहिए, तो वे गलत जगह पहुँच सकते हैं या फंस सकते हैं।

2. समाधान: "मिलने" का एक नया तरीका (Consensus)

इस शोध का मुख्य भाग नया "कंसेंसस स्टेप" (consensus step) है—वह क्षण जब हाइकर तय करते हैं कि उन्हें कहाँ इकट्ठा होना है।

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

3. लक्ष्य: चलते-चलते सीखना (Online Optimization)

हाइकर केवल मिलने की कोशिश नहीं कर रहे हैं; वे यह भी खोजने की कोशिश कर रहे हैं कि सबसे अच्छा स्थान कहाँ है जबकि भूभाग हर सेकंड बदल रहा है (यह "ऑनलाइन" ऑप्टिमाइज़ेशन है)।

पूर्ण सूचना (Full Information): पहले परिदृश्य में, प्रत्येक हाइकर अपने पैरों के नीचे ढलान को देख सकता है (उनके पास "ग्रेडिएंट" है)। लेखकों ने दिखाया कि इस घुमावदार ज़मीन और सीमित संचार के साथ भी, समूह एक सपाट दुनिया की तरह ही लगभग उतनी ही तेज़ी से सर्वोत्तम स्थान पा सकता है। उन्होंने सिद्ध किया कि उनका "रिग्रेट" (उनके प्रदर्शन और आदर्श प्रदर्शन के बीच का अंतर) समय के वर्गमूल ( $\sqrt{T}$ ) की दर से बहुत धीरे बढ़ता है।
"अंधा" परिदृश्य (Bandit Feedback): दूसरे, अधिक कठिन परिदृश्य में, हाइकर आंखों पर पट्टी बांधे हुए हैं। वे ढलान को देख नहीं सकते। वे केवल दो नजदीकी बिंदुओं पर ज़मीन को छूकर महसूस कर सकते हैं कि वह ऊँची है या नीची। यह एक छड़ी के दो बार प्रहार से घाटी के निचले हिस्से को खोजने जैसा है।
- लेखों ने एक चतुर "स्मूथिंग" (smoothing) तकनीक का आविष्कार किया। केवल एक प्रहार से ढलान का अनुमान लगाने के बजाय, वे भूभाग के एक "स्मूथ" संस्करण का अनुकरण करते हैं।
- इस अंधेपन और घुमावदार ज़मीन के बावजूद, उन्होंने सिद्ध किया कि समूह अभी भी उसी धीमी गति से बढ़ने वाले रिग्रेट दर ( $\sqrt{T}$ ) के साथ इष्टतम स्थान पा सकता है।

4. प्रमाण: ज्यामितीय उपकरण (Geometry Tools)

इसे काम करने के लिए, लेखकों को नए गणितीय "रूलर" और "कंपास" (ज्यामितीय उपकरण) बनाने पड़े जो किसी भी घुमावदार सतह पर काम कर सकें, चाहे वह ऊपर की ओर मुड़ी हो या नीचे की ओर। उन्होंने दिखाया कि भले ही ज़मीन अजीब हो, फिर भी आप दूरी और कोणों को इतनी सटीकता से माप सकते हैं कि यह गारंटी दी जा सके कि हाइकर अंततः सफल होंगे।

सारांश

इस शोध पत्र को एक विशाल, उछलने वाली ट्रैम्पोलिन (trampoline) पर खेले जाने वाले एक समूह खेल के नए नियम पुस्तिका के रूप में समझें, न कि एक सपाट फर्श के रूप में।

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

यह कार्य महत्वपूर्ण है क्योंकि यह "आसान" सपाट या कटोरे के आकार की दुनिया से आगे बढ़ता है और दिखाता है कि जटिल, घुमावदार ज्यामिति पर भी विकेंद्रीकृत शिक्षण (decentralized learning) प्रभावी ढंग से काम कर सकता है।

तकनीकी सारांश: हैडामार्ड मैनिफोल्ड्स से परे विकेंद्रीकृत ऑनलाइन रीमानियन अनुकूलन

समस्या का निरूपण
यह शोध पत्र धनात्मक वक्रता (positive curvature) वाले मैनिफोल्ड्स पर विकेंद्रीकृत ऑनलाइन रीमानियन अनुकूलन की समस्या को संबोधित करता है, जो हैडामार्ड मैनिफोल्ड्स (जिनमें गैर-धनात्मक वक्रता होती है) के प्रतिबंधात्मक परिवेश से आगे बढ़कर है। लक्ष्य यह है कि $n$ एजेंटों का एक नेटवर्क प्रत्येक समय चरण $t$ पर एक वैश्विक उद्देश्य फलन $f_t(\cdot) = \frac{1}{n}\sum_{i=1}^n f_{i,t}(\cdot)$ को सहयोगात्मक रूप से न्यूनतम करे, जहाँ प्रत्येक एजेंट $i$ केवल अपने स्थानीय लॉस फलन $f_{i,t}$ को देखता है। एजेंट दो फीडबैक व्यवस्थाओं के तहत कार्य करते हैं:

पूर्ण ग्रेडिएंट फीडबैक (Full Gradient Feedback): एजेंटों के पास अपने स्थानीय फलनों के सटीक रीमानियन ग्रेडिएंट तक पहुँच होती है।
टू-पॉइंट बैंडिट फीडबैक (Two-Point Bandit Feedback): एजेंटों को केवल दो निकटवर्ती बिंदुओं पर फलन मूल्यांकन प्राप्त होता है, जिसके लिए ग्रेडिएंट अनुमानकों (gradient estimators) के निर्माण की आवश्यकता होती है।

निर्णय चर (decision variables) और तुलना बिंदु $x^*$ एक रीमानियन मैनिफोल्ड $\mathcal{M}$ के एक जियोडेसिक रूप से उत्तल (geodesically convex) उपसमुच्चय $\mathcal{X}$ के भीतर सीमित हैं। प्राथमिक तकनीकी चुनौतियाँ धनात्मक वक्रता वाले स्थानों में वैश्विक उत्तलता (global convexity) के अभाव और मैनिफोल्ड की गैर-रैखिकता से उत्पन्न होती हैं, जो विकेंद्रीकृत यूक्लिडियन अनुकूलन में उपयोग किए जाने वाले मानक सहमति (consensus) चरणों को जटिल बनाती है।

कार्यप्रणाली
लेखक एक एकीकृत ढांचा प्रस्तावित करते हैं जो तीन मुख्य पद्धतिगत घटकों पर आधारित है:

वक्रता-जागरूक सहमति चरण (Curvature-Aware Consensus Step):
यह शोध पत्र टेंजेंट स्पेस में परिभाषित एक विशिष्ट सहमति अपडेट नियम का उपयोग करता है:
$x_{i,t+1} = \text{Exp}_{y_{i,t+1}}\left(s \sum_{j=1}^n w_{ij} \text{Log}_{y_{i,t+1}}(y_{j,t+1})\right)$
जहाँ $y_{i,t+1}$ स्थानीय ग्रेडिएंट अपडेट और प्रोजेक्शन का परिणाम है, $W$ एक डबली स्टोकेस्टिक संचार मैट्रिक्स है, और $s$ एक सहमति स्टेप-साइज है। पिछले कार्यों के विपरीत जो एम्बिएंट स्पेस की रैखिकता या हैडामार्ड मैनिफोल्ड की वैश्विक उत्तलता पर निर्भर करते हैं, यह कार्य सामान्य मैनिफोल्ड्स पर इस चरण के रैखिक विचरण न्यूनीकरण (linear variance reduction) का विश्लेषण करता है जिसका बाउंडेड सेक्शनल कर्वेचर $K \in [K_{\min}, K_{\max}]$ है। विश्लेषण वक्रता द्वारा विकृत होने वाले उत्तलता और स्मूथनेस गुणों के बीच संतुलन बनाने के लिए स्टेप-साइज $s$ को अनुकूलित करता है।
पूर्ण सूचना एल्गोरिदम (एल्गोरिदम 1):
पूर्ण ग्रेडिएंट सेटिंग में, एजेंट एक रीमानियन ग्रेडिएंट डिसेंट चरण करते हैं, उसके बाद एक सुलभ सेट $\mathcal{X}$ पर प्रोजेक्शन करते हैं, और फिर ऊपर वर्णित सहमति चरण को निष्पादित करते हैं। रिग्रेट विश्लेषण कुल त्रुटि को एक नेटवर्क त्रुटि (स्थानीय चरों और वैश्विक फ्रेट माध्य के बीच विसंगति) और एक स्थानीय अनुकूलन त्रुटि में विभाजित करता है। नेटवर्क त्रुटि को सहमति विश्लेषण में स्थापित रैखिक विचरण न्यूनीकरण गुण का उपयोग करके सीमित किया जाता है।
बैंडिट फीडबैक एल्गोरिदम (एल्गोरिदम 2) और स्मूथिंग:
टू-पॉइंट बैंडिट सेटिंग के लिए, लेखक एक यादृच्छिक स्मूथिंग (randomized smoothing) तकनीक का उपयोग करते हैं। एजेंट टेंजेंट स्पेस स्फीयर से समान रूप से दिशाएँ चुनते हैं और एक स्मूथिंग पैरामीटर $\delta$ द्वारा अलग किए गए दो बिंदुओं पर फलन का मूल्यांकन करते हैं। यह एक ग्रेडिएंट अनुमानक $g^\delta_{i,t}$ उत्पन्न करता है।
- उप-उत्तलता विश्लेषण (Subconvexity Analysis): चूंकि स्मूथिंग सख्त जियोडेसिक उत्तलता को नष्ट कर देती है, इसलिए लेखक यह स्थापित करते हैं कि स्मूदन किया गया उद्देश्य $\delta$ -जियोडेसिक रूप से उप-उत्तल (subconvex) है। वे सिद्ध करते हैं कि पूर्ण उत्तलता से विचलन $\delta$ द्वारा रैखिक रूप से नियंत्रित होता है।
- डोमेन संकुचन (Domain Shrinkage): सीमा के पास बिंदुओं का मूल्यांकन करते समय व्यवहार्यता सुनिश्चित करने के लिए, एल्गोरिदम मूल डोमेन के एक संकुचित उपसमुच्चय $(1-\tau)\mathcal{X}$ पर कार्य करता है।

प्रमुख योगदान
यह शोध पत्र निम्नलिखित विशिष्ट तकनीकी योगदान देता है:

सामान्य मैनिफोल्ड्स पर रैखिक विचरण न्यूनीकरण: लेखक सामान्य मैनिफोल्ड्स (धनात्मक और ऋणात्मक दोनों वक्रता वाले) पर सहमति चरण के रैखिक अभिसरण को स्थापित करते हैं (थ्योरम III.2)। यह वक्रता द्वारा प्रभावित होने वाले उत्तलता और स्मूथनेस के बीच के ट्रेड-ऑफ को प्रबंधित करने के लिए सहमति स्टेप-साइज को अनुकूलित करके प्राप्त किया गया है, जो हैडामार्ड सेटिंग में एक चुनौती नहीं थी जहाँ ऋणात्मक वक्रता स्वाभाविक रूप से उत्तलता को सुदृढ़ करती है।
पूर्ण सूचना के लिए $O(\sqrt{T})$ रिग्रेट: सामान्य मैनिफोल्ड्स (संभावित रूप से धनात्मक वक्रता वाले) के लिए, यह शोध पत्र विकेंद्रीकृत ग्रेडिएंट डिसेंट एल्गोरिदम के लिए एक स्टैटिक रिग्रेट बाउंड $O(\sqrt{T})$ सिद्ध करता है (थ्योरम IV.2)। यह यूक्लिडियन सेटिंग्स में ज्ञात इष्टतम दर से मेल खाता है, जो यह दर्शाता है कि विकेंद्रीकरण और धनात्मक वक्रता स्पर्शोन्मुखी रूप से रिग्रेट दर को कम नहीं करते हैं।
बैंडिट फीडबैक के लिए प्रथम $O(\sqrt{T})$ रिग्रेट: यह शोध पत्र टू-पॉइंट बैंडिट फीडबैक के तहत विकेंद्रीकृत ऑनलाइन रीमानियन अनुकूलन के लिए पहला स्टैटिक रिग्रेट बाउंड $O(\sqrt{T})$ प्रदान करता है (थ्योरम V.2)। यह एक गणनात्मक रूप से कुशल ग्रेडिएंट अनुमानक और स्मूदन किए गए उद्देश्यों की उप-उत्तलता के कठोर विश्लेषण का उपयोग करके प्राप्त किया गया है।
सामान्यीकृत ज्यामितीय उपकरण: लेखक ज्यामितीय तुलना असमानताओं (लेम्मा VII.3–VII.4) को विकसित और विस्तारित करते हैं जो $K_{\min}$ और $K_{\max}$ के संदर्भ में स्पष्ट रूप से परिभाषित स्थिरांकों वाले, वक्रता के किसी भी चिह्न वाले मैनिफोल्ड्स के लिए मान्य हैं।

परिणाम

सैद्धांतिक सीमाएँ: प्राप्त स्टैटिक रिग्रेट बाउंड पूर्ण ग्रेडिएंट और टू-पॉइंट बैंडिट फीडबैक दोनों सेटिंग्स के लिए $O(\sqrt{T})$ हैं। इन बाउंड्स में स्थिरांक मैनिफोल्ड के वक्रता, नेटवर्क कनेक्टिविटी (W के दूसरे सबसे बड़े सिंगुलर मान के माध्यम से), और डोमेन के व्यास पर निर्भर करते हैं, लेकिन समय क्षितिज $T$ के संबंध में इनका स्पर्शोन्मुखी दर इष्टतम रहता है।
संख्यात्मक प्रयोग: प्रयोग 50 एजेंटों के साथ एक 16-आयामी यूनिट स्फीयर (एक धनात्मक वक्रता वाला मैनिफोल्ड) पर किए गए। परिणाम पुष्टि करते हैं कि एल्गोरिदम अभिसरित होते हैं, जिसमें संचयी रिग्रेट अपेक्षित रूप से बढ़ता है। प्रयोग दिखाते हैं कि बड़े सहमति स्टेप-साइज आम तौर पर कम रिग्रेट की ओर ले जाते हैं क्योंकि वे तेज़ सहमति दरों के कारण होते हैं, और बैंडिट सेटिंग पूर्ण-सूचना सेटिंग की तुलना में धीमा अभिसरण प्रदर्शित करती है क्योंकि इसमें ग्रेडिएंट अनुमान की भिन्नता (variance) अधिक होती है।

महत्व
यह शोध पत्र वक्रीय स्थानों पर विकेंद्रीकृत अनुकूलन की सैद्धांतिक समझ में एक महत्वपूर्ण अंतर को पाटने का दावा करता है।

हैडामार्ड से परे: विकेंद्रीकृत रीमानियन अनुकूलन के लिए पूर्व सैद्धांतिक गारंटी काफी हद तक हैडामार्ड मैनिफोल्ड्स तक सीमित थी। यह कार्य उन गारंटियों को धनात्मक वक्रता वाले मैनिफोल्ड्स तक विस्तारित करता है, जहाँ जियोडेसिक दूरियाँ वैश्विक उत्तल संरचनाओं को प्रेरित नहीं करती हैं।
बैंडिट सेटिंग: यह बैंडिट फीडबैक के तहत विकेंद्रीकृत रीमानियन अनुकूलन के पहले अनछुए क्षेत्र को संबोधित करता है, जो इस सेटिंग के लिए पहले सबलीनियर रिग्रेट बाउंड प्रदान करता है।
इष्टतमता: परिणाम यह प्रदर्शित करते हैं कि यूक्लिडियन विकेंद्रीकृत ऑनलाइन अनुकूलन में प्राप्त होने वाली मौलिक $O(\sqrt{T})$ रिग्रेट दर धनात्मक वश्विक और सीमित फीडबैक की उपस्थिति में भी संरक्षित रहती है, बशर्ते कि वक्रता-जागरूक सहमति और स्मूथिंग तकनीकों का उपयोग किया जाए।

लेखक उल्लेख करते हैं कि जबकि बाउंड $T$ के संदर्भ में इष्टतम हैं, भविष्य के कार्य इन बाउंड्स की नेटवर्क कनेक्टिविटी और वक्रता मापदंडों पर विशिष्ट निर्भरता की जांच कर सकते हैं, और उन विशिष्ट मापदंडों के संबंध में प्रमाणित रूप से इष्टतम एल्गोरिदम डिजाइन कर सकते हैं।

1. समस्या: "घुमावदार ज़मीन" की चुनौती

2. समाधान: "मिलने" का एक नया तरीका (Consensus)

3. लक्ष्य: चलते-चलते सीखना (Online Optimization)

4. प्रमाण: ज्यामितीय उपकरण (Geometry Tools)

सारांश

इसी तरह के और पेपर