📊 statistics

Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation

यह शोध पत्र स्पष्ट संचार-गणना व्यापार-संबंधों (communication-computation trade-offs) और विषमता-जागरूक त्रुटि सीमाओं (heterogeneity-aware error bounds) के साथ रैखिक स्टोकेस्टिक सन्निकटन (linear stochastic approximation) के लिए पहले फेडरेटेड गॉसियन सन्निकटन स्थापित करता है, और अंतिम इटरेशन (last iterate) पर अनुमान के लिए एक गैर-अनंतकालीन रूप से वैध (non-asymptotically valid) ऑनलाइन मल्टीप्लायर बूटस्ट्रैप प्रक्रिया विकसित करने के लिए इन परिणामों का लाभ उठाता है।

मूल लेखक: Ilya Levin, Maksim Shuklin, Eric Moulines, Paul Mangold, Sergey Samsonov

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

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

CC BY 4.0

मूल लेखक: Ilya Levin, Maksim Shuklin, Eric Moulines, Paul Mangold, Sergey Samsonov

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

कल्पना कीजिए कि दोस्तों का एक समूह मिलकर एक विशाल, जटिल पहेली को हल करने की कोशिश कर रहा है। वे अलग-अलग कमरों में हैं (अलग-अलग कंप्यूटर या "एजेंट्स") और वे एक साथ पूरी तस्वीर नहीं देख सकते। उनके पास पहेली का अपना-अपना हिस्सा है, लेकिन उनके हिस्से थोड़े अलग हैं क्योंकि उन्हें काटने का तरीका अलग था (इसे विषमता या heterogeneity कहा जाता है)।

पहेली को हल करने के लिए, वे फेडरेटेड लर्निंग (Federated Learning) नामक विधि का उपयोग करते हैं। सभी पहेली के टुकड़ों को हर सेकंड एक केंद्रीय मेज पर भेजने के बजाय (जो धीमा होगा और इंटरनेट को जाम कर देगा), वे कुछ समय के लिए अपने टुकड़ों पर काम करते हैं, कुछ प्रगति करते हैं, और फिर अपनी वर्तमान प्रगति को एक केंद्रीय केंद्र (hub) को भेजते हैं। वह केंद्र सबकी प्रगति का औसत निकालता है और एक नया "बेहतर अनुमान" वापस सभी को भेज देता है। वे इस चक्र को दोहराते हैं।

यह शोध पत्र मुख्य रूप से दो चीजों के बारे में है: वे वास्तव में कितनी तेजी से पहेली हल करते हैं और वे कितने आश्वस्त हो सकते हैं कि उनका समाधान सही है।

यहाँ सरल उपमाओं का उपयोग करके शोध पत्र की खोजों का विवरण दिया गया है:

1. "गति बनाम सटीकता" का संतुलन (The "Speed vs. Accuracy" Trade-off)

अतीत में, शोधकर्ताओं ने मुख्य रूप से इस बात पर ध्यान दिया कि यह समूह कितनी तेजी से पहेली हल करता है। यह शोध पत्र एक अलग प्रश्न पूछता है: "उनका अंतिम उत्तर एक आदर्श, बेल-कर्व (घंटी के आकार के वक्र) वितरण के कितना करीब है?"

सोचिए कि अंतिम उत्तर एक बोर्ड पर फेंका गया डार्ट है। यदि आप पर्याप्त डार्ट फेंकते हैं, तो वे आमतौर पर एक सुंदर, गोल क्लस्टर (समूह) बनाते हैं (एक गॉसियन वितरण)। लेखक यह जानना चाहते थे कि: इस क्लस्टर को पूरी तरह से गोल दिखने में कितने थ्रो (इटरेशन) लगते हैं?

उन्होंने पाया कि इस क्लस्टर का आकार दो विकल्पों पर बहुत अधिक निर्भर करता है जो समूह द्वारा किए जाते हैं:

स्टेप साइज (Step Size): अपने अनुमान को अपडेट करते समय वे कितना बड़ा कदम उठाते हैं।
लोकल अपडेट्स (Local Updates): समूह के साथ चेक-इन करने से पहले वे अकेले कितनी देर तक काम करते हैं।

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

2. "जादुई दर्पण" (The "Magic Mirror" - Multiplier Bootstrap)

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

लेखकों ने एक नया टूल विकसित किया जिसे मल्टीप्लायर बूटस्ट्रैप (Multiplier Bootstrap) कहा जाता है।

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

बड़ी दावा: लेखकों ने सिद्ध किया कि यह "हिलता हुआ साया" समाधान की वास्तविक अनिश्चितता की सटीक नकल करता है।

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

3. "विषमता" की समस्या (The "Heterogeneity" Problem)

वास्तविक जीवन में, हर कोई एक जैसा नहीं होता। कुछ दोस्त तेज़ हैं, कुछ के पास बेहतर टुकड़े हैं, कुछ विचलित हैं। इसे विषमता (heterogeneity) कहा जाता है।

शोध पत्र दिखाता है कि यह "दोस्तों के बीच का अंतर" एक विशिष्ट प्रकार का शोर (noise) पैदा करता है। यदि सभी समान होते, तो समाधान की भविष्यवाणी करना आसान होता। लेकिन क्योंकि वे अलग हैं, इसलिए "क्लस्टर" के उत्तर खिंच जाते या दब जाते हैं। लेखकों के सूत्र स्पष्ट रूप से इस खिंचाव को मापते हैं। वे दिखाते हैं कि आप अभी भी एक विश्वसनीय उत्तर प्राप्त कर सकते हैं, लेकिन आपको यह ध्यान में रखना होगा कि समूह के सदस्य कितने अलग हैं।

"मुख्य निष्कर्ष" का सारांश (Summary of the "Takeaway")

समस्या: वितरित शिक्षण (distributed learning) में, यह जानना कठिन है कि आप अपने उत्तर के प्रति कितने आश्वस्त हैं, खासकर जब डेटा अव्यवस्थित और उपयोगकर्ताओं के बीच भिन्न होता है।
समाधान: लेखकों ने एक नया गणितीय ढांचा बनाया जो:
1. "गोलता" को मापता है: उन्होंने गणना की कि समूह के उत्तरों को एक अनुमानित, बेल-कर्व आकार में स्थिर होने में कितने चरण लगते हैं, भले ही डेटा अव्यवस्थित और अलग हो।
2. "छाया वाला ट्रिक" (The Shadow Trick): उन्होंने सिद्ध किया कि आप जटिल गणितीय समस्या को सीधे हल करने के बजाय एक "छाया सिमुलेशन" (बूटस्ट्रैप) का उपयोग करके कॉन्फिडेंस इंटरवल बना सकते हैं।

संक्षेप में: उन्होंने दोस्तों के समूह को एक नया नियम पुस्तिका दी जो उन्हें न केवल पहेली को तेज़ी से हल करने के लिए बल्कि यह जानने के लिए भी कि वे गणितीय निश्चितता के साथ काम कर रहे हैं कि वे केवल भाग्यशाली नहीं हुए हैं।

तकनीकी सारांश: फेडरेटेड लीनियर स्टोकेस्टिक एप्रोक्सिमेशन के लिए गॉसियन एप्रोक्सिमेशन और मल्टीप्लायर बूटस्ट्रैप

समस्या विवरण

यह शोध पत्र फेडरेटेड लीनियर स्टोकेस्टिक एप्रोक्सिमेशन (FedLSA) में सांख्यिकीय अनुमान (statistical inference) की चुनौती को संबोधित करता है। जबकि फेडरेटेड एवरेजिंग (FedAvg) वितरित एजेंटों के बीच सहयोगात्मक मॉडल प्रशिक्षण के लिए एक मानक एल्गोरिदम है, मौजूदा सैद्धांतिक साहित्य मुख्य रूप से अनुकूलन अभिसरण दरों (optimization convergence rates) पर ध्यान केंद्रित करता है। सांख्यिकीय अनुमान के लिए गैर-अनंत गारंटी (non-asymptotic guarantees) प्रदान करने में एक महत्वपूर्ण अंतराल है, विशेष रूप से मॉडल मापदंडों के लिए कॉन्फिडेंस इंटरवल (confidence intervals) बनाने के संदर्भ में।

फेडरेटेड सेटिंग्स में अनुमान के लिए वर्तमान दृष्टिकोण अक्सर एक सीमित गॉसियन वितरण तक अनंत अभिसरण (asymptotic convergence) पर निर्भर करते हैं या स्पष्ट रूप से एसिम्प्टोटिक कोवेरिएंस मैट्रिक्स ( $\Sigma_\infty$ ) के अनुमान की आवश्यकता रखते हैं, जो गणनात्मक रूप से महंगा है और सीमित-नमूना व्यवस्था (finite-sample regimes) में सटीक रूप से अनुमानित करना कठिन है। इसके अलावा, स्टोकेस्टिक एप्रोक्सिमेशन (SA) और स्टोकेस्टिक ग्रेडिएंट डिसेंट (SGD) के लिए मौजूदा गैर-अनंत गॉसियन एप्रोक्सिमेशन परिणाम विषमता (heterogeneity) (स्थानीय डेटा वितरणों में अंतर) और फेडरेटेड लर्निंग में निहित विशिष्ट कम्युनिकेशन-कंप्यूटेशन ट्रेड-ऑफ को पूरी तरह से नहीं पकड़ पाते हैं, विशेष रूप से जब स्थानीय पुनरावृत्तियों (local iterations) की संख्या समय के साथ बदलती रहती है।

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

लेखक घटते हुए स्टेप साइज़ (decreasing step sizes) और बढ़ते हुए स्थानीय पुनरावृत्तियों (increasing local iterations) के शासन के तहत FedLSA के अंतिम इटरेट (last iterate) का विश्लेषण करने के लिए एक कठोर सैद्धांतिक ढांचा विकसित करते हैं। कार्यप्रणाली तीन मुख्य चरणों के माध्यम से आगे बढ़ती है:

उच्च-क्रम मोमेंट बाउंड्स और एरर डिकंपोजिशन (High-Order Moment Bounds and Error Decomposition):
लेखक गैर-स्थिर स्टेप साइज़ और परिवर्तनशील स्थानीय अपडेट काउंट को समायोजित करने के लिए एरर डिकंपोजिशन फ्रेमवर्क का विस्तार करते हैं। वे अनुमान त्रुटि $\theta_t - \theta^\star$ को चार घटकों में विभाजित करते हैं:
- एक क्षणिक पद (transient term) जो इनिशियलाइजेशन से घटता है।
- सांख्यिकीय विषमता से उत्पन्न होने वाला एक बायस (bias) पद।
- विषमता के कारण होने वाला एक फ्लक्चुएशन (fluctuation) पद।
- स्टोकेस्टिक शोर (stochastic noise) के कारण होने वाला एक फ्लक्चुएशन पद।
  महत्वपूर्ण रूप से, वे इन त्रुटि घटकों के लिए उच्च-क्रम मोमेंट बाउंड्स ( $p \ge 2$ के लिए) स्थापित करते हैं। यह एक अभिनव योगदान है, क्योंकि पिछला साहित्य मुख्य रूप से दूसरे क्रम के मोमेंट्स पर केंद्रित था। ये बाउंड्स स्थानीय स्टेप साइज़, स्थानीय अपडेट की संख्या और डेटा विषमता के प्रभावों को स्पष्ट रूप से मात्रात्मक रूप से दर्शाते हैं।
गैर-अनंत गॉसियन एप्रोक्सिमेशन (GAR):
प्राप्त मोमेंट बाउंड्स का उपयोग करते हुए, शोध पत्र FedLSA के अंतिम इटरेट के लिए एक बेरी-एस्मीन-टाइप बाउंड (Berry-Esseen-type bound) स्थापित करता है। विश्लेषण एक रैखिक सांख्यिकी $W_t$ और एक शेष पद (remainder term) $D_t$ के डिकंपोजिशन का उपयोग करता है। नॉन-लीनियर स्टैटिस्टिक्स के सिद्धांत (विशेष रूप से Shao और Zhang [2022]) के सांद्रता असमानताओं (concentration inequalities) और उपकरणों को लागू करके, लेखक सामान्यीकृत अंतिम इटरेट के वितरण और एक गॉसियन वितरण के बीच कॉन्वेक्स डिस्टेंस (convex distance) को सीमित करते हैं।
- विश्लेषण स्टेप साइज़ डिके रेट ( $\gamma_\eta$ ) और स्थानीय पुनरावृत्तियों की वृद्धि दर ( $\gamma_H$ ) के बीच परस्पर क्रिया को ट्रैक करता है।
- यह एम्पिरिकल कोवेरिएंस मैट्रिक्स $\Sigma_t$ के एसिम्प्टोटिक कोवेरिएंस $\Sigma_\infty$ में अभिसरण की दर को स्पष्ट रूप से ध्यान में रखता है, यह दिखाते हुए कि $\Sigma_\infty$ को सीधे अनुमानित करने से अभिसरण की दर धीमी हो सकती है।
ऑनलाइन मल्टीप्लायर बूटस्ट्रैप (Online Multiplier Bootstrap):
$\Sigma_\infty$ के अनुमान के बिना व्यावहारिक अनुमान की सुविधा के लिए, लेखक एक ऑनलाइन मल्टीप्लायर बूटस्ट्रैप प्रक्रिया प्रस्तावित करते हैं। यह विधि स्थानीय अपडेट्स में रैंडम मल्टीप्लिकेटिव वेट्स पेश करके बूटस्ट्रैप इटरेट्स उत्पन्न करती है।
- यह प्रक्रिया पूरी तरह से ऑनलाइन और डेटा-संचालित है।
- इसकी सैद्धांतिक वैधता यह दिखाकर सिद्ध की जाती है कि बूटस्ट्रैप सांख्यिकी का कंडीशनल डिस्ट्रीब्यूशन, सामान्यीकृत अनुमान त्रुटि के सैंपलिंग डिस्ट्रीब्यूशन को गॉसियन एप्रोक्सिमेशन दर के समान दर से अनुमानित करता है, जिससे $\Sigma_\infty$ के अनुमान की आवश्यकता प्रभावी रूप से समाप्त हो जाती है।

मुख्य योगदान

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

FedLSA के लिए प्रथम उच्च-क्रम मोमेंट बाउंड्स: लेखक घटते स्टेप साइज़ और बढ़ती स्थानीय पुनरावृत्तियों के साथ FedLSA के लिए $p \ge 2$ क्रम के पहले मोमेंट बाउंड्स प्रदान करते हैं। ये बाउंड्स विषमता बायस और शोर वाले अपडेट को कैप्चर करते हैं, जो पिछले कार्यों का विस्तार करते हैं जो स्थिर स्टेप साइज़ या दूसरे क्रम के मोमेंट्स तक सीमित थे।
अंतिम इटरेट के लिए गैर-अनंत गॉसियन एप्रोक्सिमेशन: शोध पत्र बढ़ती स्थानीय पुनरावृत्तियों वाले फेडरेटेड सेटिंग में FedLSA के अंतिम इटरेट के लिए पहला गॉसियन एप्रोक्सिमेशन बाउंड प्रस्तुत करता है। यह बाउंड कॉन्वेक्स डिस्टेंस के संदर्भ में व्यक्त किया गया है और $N^{-1/2}t^{-\gamma_\eta/2}$ तक स्केल होता है (लॉगारिदमिक कारकों और विषमता पदों तक), जो संचार आवृत्ति और स्थानीय गणना के बीच ट्रेड-ऑफ को स्पष्ट रूप से कैप्चर करता है।
फेडरेटेड इंफरेंस के लिए वैध मल्टीप्लायर बूटस्ट्रैप: लेखक अंतिम इटरेट के लिए एक ऑनलाइन मल्टीप्लायर बूटस्ट्रैप प्रक्रिया विकसित करते हैं और उसकी वैधता सिद्ध करते हैं। यह विधि एसिम्प्टोटिक कोवेरिएंस मैट्रिक्स $\Sigma_\infty$ के स्पष्ट अनुमान के बिना, जो फेडरेटेड इंफरेंस में एक बाधा है, काम करती है।
लोअर बाउंड विश्लेषण: शोध पत्र एक सरलीकृत 1-डायमेंशनल सेटिंग में कॉन्वेक्स डिस्टेंस के लिए एक गैर-अनंत लोअर बाउंड प्रदान करता है, यह प्रदर्शित करते हुए कि प्राप्त दरें सटीक (tight) हैं और कोवेरिएंस मैट्रिक्स का अभिसरण एक सीमित कारक है।

परिणाम

सैद्धांतिक परिणामों को निम्नानुसार संक्षेपित किया गया है:

अभिसरण दरें (Convergence Rates): घटते स्टेप साइज़ ( $\eta_t \propto t^{-\gamma_\eta}$ ) और बढ़ती स्थानीय पुनरावृत्तियों ( $H_t \propto t^{\gamma_H}$ ) के योजना के तहत, अंतिम इटरेट के लिए गॉसियन एप्रोक्सिमेशन एरर उन पदों द्वारा सीमित है जो $N^{-1/2}t^{-\gamma_\eta/2}$ , $N^{1/2}t^{-\gamma}$ , और $t^{-(3\gamma-\gamma_\eta)/2}$ के रूप में स्केल होते हैं, जहाँ $\gamma = \gamma_\eta - \gamma_H$ है।
बूटस्ट्रैप वैधता: मल्टीप्लायर बूटस्ट्रैप प्रक्रिया गॉसियन एप्रोक्सिमेशन के समान ही क्रम ( $O(t^{-1/2})$ ) की अभिसरण दर प्राप्त करती है। यह पुष्टि करता है कि बूटस्ट्रैप डिस्ट्रीब्यूशन, $\Sigma_\infty$ के ज्ञान के बिना, वास्तविक सैंपलिंग डिस्ट्रीब्यूशन का सटीक रूप से अनुमान लगाता है।
संख्यात्मक सत्यापन: विषम एजेंटों के साथ एक Garnet एनवायरनमेंट पर प्रयोगों से पता चलता है कि प्रस्तावित बूटस्ट्रैप-आधारित कॉन्फिडेंस इंटरवल (एम्पिरिकल क्वांटाइल्स और स्टैंडर्ड डेविएशन का उपयोग करके) प्लग-इन गॉसियन बेसलाइन्स की तुलना में बेहतर कवरेज प्राप्त करते हैं, विशेष रूप से शुरुआती इटरेशन्स और बढ़ती स्थानीय अपडेट्स वाले रेजिम में। प्लग-इन विधि सैंपल साइज बढ़ने के साथ बेहतर होती है लेकिन सीमित-नमूना प्रदर्शन में पीछे रह जाती है।

महत्व और दावे

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

विषमता-जागरूक (Heterogeneity-Aware): होमोजेनियस एजेंटों या स्थिर स्थानीय स्टेप्स को मानने वाले पिछले कार्यों के विपरीत, यह विश्लेषण डेटा विषमता और स्थानीय अपडेट के डायनेमिक शेड्यूल के प्रभाव को स्पष्ट रूप से मॉडल करता है।
व्यावहारिक अनुमान: मल्टीप्लायर बूटस्ट्रैप को मान्य करके, शोध पत्र फेडरेटेड सेटिंग्स में एसिम्प्टोटिक कोवेरिएंस मैट्रिक्स के अनुमान की गणनात्मक लागत के बिना कॉन्फिडेंस इंटरवल बनाने के लिए एक व्यावहारिक उपकरण प्रदान करता है।
परिकल्पनाओं की पुष्टि: परिणाम उस परिकल्पना की पुष्टि करते हैं (जो Bonnerjee et al. [2025] द्वारा बिना प्रमाण के अनुमानित की गई थी) कि मल्टीप्लायर बूटस्ट्रैप प्रक्रियाएं फेडरेटेड एस्टिमेटर्स के लिए वैध अनुमान प्रदान कर सकती हैं, भले ही वे परिवर्तनशील स्थानीय पुनरावृत्तियों वाले जटिल रेजिम में हों।
ट्रेड-ऑफ अंतर्दृष्टि: विश्लेषण एक मौलिक ट्रेड-ऑफ को उजागर करता है: जबकि स्थानीय पुनरावृत्तियों की संख्या बढ़ाना अनुकूलन दक्षता और संचार लागत में सुधार करता है, यह वितरण अभिसरण (गॉसियन एप्रोक्सिमेशन) की दर को प्रतिकूल रूप से प्रभावित कर सकता है, जो यह सुझाव देता है कि सांख्यिकीय अनुमान के लिए एक स्थिर संख्या में स्थानीय अपडेट अधिक उपयुक्त हो सकती है, हालांकि संचार बाधाओं के कारण यह हमेशा लागू करने योग्य नहीं होता है।

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