Self-Creating Random Walks for Decentralized Learning under Pac-Man Attacks

तकनीकी सारांश: पैकमैन हमलों के तहत विकेंद्रीकृत शिक्षण के लिए स्व-निर्मित रैंडम वॉक (Random Walks)

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

मूल समस्या यह है कि भले ही एक एकल पैकमैन नोड, एक सकारात्मक प्रायिकता $\zeta \in (0, 1]$ के साथ RW को समाप्त कर दे, तो वह अंततः एक निश्चित प्रायिकता के साथ नेटवर्क में सभी सक्रिय RWs के विलुप्त होने का कारण बन सकता है। यह स्पष्ट विफलता अलार्म बजाए बिना सीखने की प्रक्रिया को पूरी तरह से रोक देता है। मौजूदा रेडंडेंसी-आधारित दृष्टिकोण (जैसे, कई RWs के साथ शुरू करना) विफल हो जाते हैं क्योंकि स्थिर रेडंडेंसी एक निरंतर समाप्ति विरोधी (persistent termination adversary) की उपस्थिति में पूर्ण विलुप्ति को नहीं रोक सकती है। इसके अलावा, मौजूदा स्व-नियमन तंत्र जैसे DECAFORK और AC, जो जनसंख्या आकार या विज़िट अंतराल का अनुमान लगाने के लिए डुप्लिकेशन को ट्रिगर करते हैं, इस हमले के मॉडल के तहत पैरामीटर चयन के प्रति संवेदनशील पाए गए हैं और स्थायी विलुप्ति का शिकार हो सकते हैं।

कार्यप्रणाली: CREATE-IF-LATE (CIL) एल्गोरिदम
पैकमैन हमले का मुकाबला करने के लिए, लेखक CREATE-IF-LATE (CIL) का प्रस्ताव करते हैं, जो एक पूर्णतः विकेंद्रीकृत तंत्र है जो वैश्विक समन्वय या सिस्टम पैरामीटर अनुमान की आवश्यकता के बिना RW जनसंख्या के दीर्घकालिक अस्तित्व को सुनिश्चित करता है।

• तंत्र: प्रत्येक बेनेफिशल (benign) नोड $u$ एक स्थानीय टाइमर $L_t^{(u)}$ बनाए रखता है जो किसी भी RW द्वारा अपनी अंतिम विज़िट के समय को रिकॉर्ड करता है। यदि बीता हुआ समय $t - L_t^{(u)}$ एक पूर्व-निर्धारित थ्रेशोल्ड $A_u$ से अधिक हो जाता है, तो नोड संभावित RW समाप्ति का अनुमान लगाता है। एक निर्माण प्रायिकता $q$ के साथ, नोड अपने स्थानीय कैश में संग्रहीत सबसे हाल ही में देखी गई RW को पुनरुत्पादित करके संभाव्यता के साथ एक नई RW बनाता है।
• स्व-नियमन: जनसंख्या संख्या बनाए रखने के उद्देश्य वाले डुप्लिकेशन-आधारित तरीकों के विपरीत, CIL निष्क्रियता द्वारा ट्रिगर की गई "निर्माण" (creation) पर निर्भर करता है। यदि RW जनसंख्या समाप्त हो जाती है, तो बेनेफिशल नोड्स विज़िट की अनुपस्थिति (जो $A_u$ से अधिक है) का पता लगा लेंगे और नई RW को पुनर्जीवित करेंगे, जिससे यह सुनिश्चित होगा कि जनसंख्या कभी स्थायी रूप से विलुप्त न रहे।
• सैद्धांतिक ढांचा: लेखक RW जनसंख्या प्रक्रिया $\{Z_t\}$ का अध्ययन करने के लिए एक नया विश्लेषणात्मक ढांचा विकसित करते हैं। वे नोट करते हैं कि मानक ब्रांचिंग प्रोसेस सिद्धांत (जैसे, गैल्टन-वाल्सन) सीधे लागू नहीं होते हैं क्योंकि RW निर्माण दर घनत्व-निर्भर (density-dependent) है और विज़िट इतिहास और सभी RW के स्थानों के संयुक्त सिस्टम स्टेट पर निर्भर करती है। विश्लेषण इन जटिल निर्भरताओं को ध्यान में रखते हुए स्थिरता और अभिसरण (convergence) को सिद्ध करता है।

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

1. पैकमैन हमलों के प्रति लचीलापन: यह शोध पत्र प्रदर्शित करता है कि CIL, समाप्ति प्रायिकता $\zeta$ के बावजूद, RW जनसंख्या के गैर-विलुप्त होने की गारंटी देता है। यह सुनिश्चित करता है कि प्रतिकूल वातावरण में भी कम्प्यूटेशनल कार्य जारी रहें, जो DECAFORK जैसे पूर्ववर्ती डुप्लिकेशन-आधारित तरीकों द्वारा गारंटीकृत नहीं है।
2. जनसंख्या गतिशीलता पर सैद्धांतिक गारंटी:
   • कोई स्थायी विलुप्ति नहीं: RW जनसंख्या अस्थायी विलुप्ति की घटनाओं से उबरने की गारंटी देती है।
     क लेखक यह सिद्ध करते हैं कि RW जनसंख्या का आकार लगभग निश्चित रूप से (almost surely) सीमित रहता है। वे निर्माण प्रायिकता $q$ चुनने के लिए एक सैद्धांतिक शासन प्रदान करते हैं ताकि अपेक्षित पीक जनसंख्या एक निर्धारित स्तर से नीचे रहे, जो नेटवर्क आकार $N$ से स्वतंत्र है (विशेष रूप से पूर्ण ग्राफों के लिए, सामान्य जुड़े हुए ग्राफों के विस्तार के साथ)।
3. विकेंद्रीकृत शिक्षण का अभिसरण (Convergence): यह शोध पत्र सिद्ध करता है कि CIL के साथ एकीकृत RW-SGD अभिसरित होता है।
   • अभिसरण बिंदु: एल्गोरिदम एक सरोगेट ऑब्जेक्टिव फंक्शन के मिनिमाइज़र की ओर अभिसरित होता है, जो एक क्वासी-स्टेशनरी डिस्ट्रीब्यूशन $\pi^{(\zeta)}_{chain}$ द्वारा परिभाषित है, जो पैकमैन नोड द्वारा उत्पन्न पूर्वाग्रह (bias) को ध्यान में रखता है।
   • त्रुटि सीमाएं: लेखक वास्तविक वैश्विक इष्टतम $x^*$ और अभिसरित बिंदु $\tilde{x}^*$ के बीच विचलन को स्पष्ट करते हैं, यह दिखाते हुए कि यह सीमित है।
   • समय विलंब: विश्लेषण दिखाता है कि विरोधी के कारण होने वाला निष्क्रिय समय कुल समय का एक स्थिर अंश है, जिससे यह सुनिश्चित होता है कि प्रभावी लर्निंग इटरेशन की संख्या समय के साथ रैखिक रूप से बढ़ती है।

प्रायोगिक परिणाम
लेखक सिंथेटिक लीनियर रिग्रेशन कार्यों और i.i.d. एवं non-i.i_d. डेटा विभाजन के तहत सार्वजनिक बेंचमार्क डेटासेट्स (MNIST) पर व्यापक सिमुलेशन के माध्यम से अपने सैद्धांतिक निष्कर्षों को मान्य करते हैं।

• जनसंख्या स्थिरता: विभिन्न ग्राफ टोपोलॉजी (पूर्ण, रैंडम रेगुलर, रिंग, Erdős–Rényi) पर सिमुलेशन पुष्टि करते हैं कि CIL के तहत RW जनसंख्या सीमित रहती है और विलुप्ति से उबरती है, जबकि DECAFORक बेसलाइन अक्सर पैरामीटर ट्यूनिंग के आधार पर स्थायी विलुप्ति का शिकार हो जाती है।
• अभिसरण प्रदर्शन: CIL विभिन्न ग्राफ प्रकारों में एक स्थिर लॉस वैल्यू तक अभिसरण प्राप्त करता है। हालांकि बड़े निर्माण थ्रेशोल्ड ($A$) के कारण लॉस कर्व में अस्थायी फ्लैट सेगमेंट (विलुप्ति और पुनरुत्थान के कारण) हो सकते हैं, एल्गोरिदम अंततः उबर जाता है। इसके विपरीत, यदि पैरामीटर पूरी तरह से ट्यून नहीं किए गए हैं, तो DECAFORK पूरी तरह से विफल हो सकता है।
• व्यापार-बंद (Trade-offs): परिणाम अभिसरण की गति और संचार ओवरहेड के बीच एक व्यापार-बंद को दर्शाते हैं। छोटे थ्रेशोल्ड ($A$) तीव्र अभिसरण की ओर ले जाते हैं लेकिन बार-बार RW निर्माण के कारण उच्च संचार लागत का कारण बनते हैं, जबकि बड़े थ्रेशोल्ड ओवरहेड को कम करते हैं लेकिन वास्तविक समय की प्रगति को धीमा कर देते हैं।
• सटीकता: Non-i.i.d. डेटा पर, CIL के तहत अंतिम मॉडल सटीकता DECAFORK के तुलनीय है लेकिन काफी अधिक मजबूत है, क्योंकि DECAFORK अक्सर विलुप्ति के कारण प्रशिक्षण पूरा करने में विफल रहता है।

महत्व और दावे
यह शोध पत्र दावा करता है कि CIL, RW-आधारित शिक्षण में एक महत्वपूर्ण भेद्यता: लर्निंग टोकन के शांत समापन (silent termination) के लिए एक मजबूत, पूर्णतः विकेंद्रीकृत समाधान प्रदान करता है। जनसंख्या अनुमान और डुप्लिकेशन से हटकर, स्थानीय, समय-आधारित निर्माण की ओर शिफ्ट होकर, एल्गोरिदम यह सुनिश्चित करता है कि एक एकल दुर्भावनापूर्ण नोड द्वारा सीखने की प्रक्रिया को स्थायी रूप से रोका नहीं जा सकता है। लेखक इस बात पर जोर देते हैं कि उनके दृष्टिकोण के लिए विरोधी की समाप्ति प्रायिकता या नेटवर्क के आकार के ज्ञान की आवश्यकता नहीं है, जो इसे वास्तविक दुनिया के विकेंद्रीकृत सिस्टम के लिए व्यावहारिक बनाता है। यह कार्य स्थापित करता है कि भले ही पैकमैन हमला अनुकूलन उद्देश्य (optimization objective) में एक पूर्वाग्रह पेश करता है, फिर भी यदि RW जनसंख्या को CIL तंत्र के माध्यम से स्व-नियमित किया जाता है, तो सीखने की प्रक्रिया अभिसारी और प्रभावी बनी रहती है।