Stable and Budget-Feasible Coalition Formation for Clustered Federated Learning: A Hedonic Potential-Game Approach

तकनीकी सारांश: क्लस्टर्ड फेडरेटेड लर्निंग के लिए स्थिर और बजट-व्यवहार्य गठबंधन निर्माण

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

1. स्थिरता (Stability): प्रतिभागियों के पास अपने निर्धारित गठबंधन को छोड़कर किसी अन्य गठबंधन में जाने या किसी गंतव्य गठबंधन द्वारा अस्वीकार किए जाने का कोई प्रोत्साहन न हो (नैश स्थिरता/Nash stability) या (व्यक्तिगत स्थिरता/Individual stability)।
2. बजट व्यवहार्यता (Budget Feasibility): समन्वय करने वाली इकाई (coordinating entity) प्रतिभागियों को मुआवजा देने के लिए आवश्यक हस्तांतरण (transfers) को वित्तपोषित कर सके बिना किसी घाटे के।
3. दक्षता (Efficiency): परिणामी स्थिर विभाजन वैश्विक सामाजिक कल्याण इष्टतम (global social welfare optimum) के निकट हो।

मौजूदा दृष्टिकोण अक्सर स्थिरता और बजट बाधाओं को अलग-अलग मानते हैं या अधिशेष (surplus) की सुपरएडिटिविटी (superadditivity) मान लेते हैं, जो विषम, गैर-कॉन्वेक्स FL सेटिंग्स में लागू नहीं होता है।

कार्यप्रणाली
यह शोध समस्या को हस्तांतरणीय अधिशेष (transferable surplus) वाले एक हेडोनिक कोलिशन-फॉर्मेशन गेम के रूप में मॉडल करता है।

• सिस्टम मॉडल: प्रतिभागी $N$ को गठबंधनों में विभाजित किया गया है। प्रत्येक गठबंधन $S$ भारित स्थानीय उद्देश्यों (weighted local objectives) का उपयोग करके एक गठबंधन-विशिष्ट मॉडल $\theta_S$ को प्रशिक्षित करता है। यह मॉडल संचार विफलताओं (ड्रॉप किए गए अपडेट्स) को एक सुरक्षित-एकत्रीकरण नियम (safe-aggregation rule) के माध्यम से संभालता है, जो यदि कोई अपडेट प्राप्त नहीं होता है तो मॉडल को अपरिवर्तित छोड़ देता है।
• आर्थिक मॉडल:
  • अधिशेष (Surplus): कुल हस्तांतरणीय अधिशेष $W(S)$ को अपेक्षित शिक्षण लाभ $B(S)$ में से समन्वयक लागत $C_0(S)$ और प्रतिभागी लागत $d_i(S)$ को घटाकर परिभाषित किया गया है।
  • हस्तांतरण (Transfers): एक समन्वयक प्रतिभागियों को हस्तांतरण $t_i(S)$ का भुगतान करता है। प्रतिभागी उपयोगिता (utility) $U_i(S) = t_i(S) - d_i(S)$ है।
  • बजट व्यवहार्यता: एक आवंटन नियम कमजोर रूप से बजट व्यवहार्य है यदि समन्वयक प्रत्येक गठित गठबंधन में गैर-ऋणात्मक अधिशेष ($R_0(S) \ge 0$) बनाए रखता है।
• हेडोनिक प्राथमिकताएँ (Hedonic Preferences): प्राथमिकताएँ एक आवंटन नियम द्वारा प्रेरित होती हैं जो अधिशेष को उपयोगिताओं में परिवर्तित करती है। शोध पत्र सममित युग्व (symmetric pairwise) अधिशेष आवंटन पर ध्यान केंद्रित करता है, जहाँ एक गठबंधन में प्रतिभागी की उपयोगिता अन्य सदस्यों $j \in S$ के साथ सभी युग्व मूल्यों $v_{ij}$ का योग है।
• गेम-थ्योरेटिक विश्लेषण:
  • लेखक सिद्ध करते हैं कि सममित युग्व आवंटन एक सटीक क्षमता गेम (exact potential game) को प्रेरित करते हैं। पोटेंशियल फंक्शन (potential function) गठबंधनों के भीतर युग्व मूल्यों का योग है।
  • यह संरचना एक नैश-स्थिर विभाजन (Nash-stable partition) के अस्तित्व को सुनिश्चित करती है और यह सुनिश्चित करती है कि बेहतर-रिस्पॉन्स (better-response) मूव्स का कोई भी क्रम परिमित चरणों में समाप्त होता है।
  • व्यक्तिगत स्थिरता (Individual Stability) (जहाँ गंतव्य सदस्यों को प्रवेश करने वाले की सहमति आवश्यक है) का भी विश्लेषण किया गया है, जो दर्शाता है कि यदि युग्व मूल्य गैर-ऋणात्मक हैं, तो नैश स्थिरता व्यक्तिगत स्थिरता को दर्शाती है।
• कल्याण और दक्षता:
  • सामाजिक कल्याण को प्रतिभागी उपयोगिता (जो पोटेंशियल फंक्शन से जुड़ी है) और समन्वयक-रिटेंड स्लैक (coordinator-retained slack) में विभाजित किया गया है।
  • यह स्थापित करता है कि सटीक बजट संतुलन (शून्य रिटेंड स्लैक) एक तभी कल्याण-इष्टतम नैश-स्थिर विभाजन प्रदान करता है जब अधिशेष सटीक रूप से युग्व-प्रतिनिधनीय (pairwise-representable) हो।
  • यदि अधिशेष सटीक रूप से प्रतिनिधित्व योग्य नहीं है, तो बजट व्यवहार्यता के तहत कल्याण हानि असीमित हो सकती है। हालाँकि, यदि रिटेंड स्लैक इष्टतम के सापेक्ष सीमित है, तो एक गुणक दक्षता गारंटी (Price of Stability) प्राप्त की जाती है।
  • वैश्विक क्षमता अधिकतमकरण (global potential maximization) को वेटेड मैक्सिमम-एग्रीमेंट कोरिलेशन क्लस्टरिंग के समकक्ष दिखाया गया है। शोध पत्र एक पाइपलाइन प्रस्तावित करता है: क्लस्टरिंग को अनुमानित करें, फिर एक स्थिर विभाजन तक पहुँचने के लिए स्ट्रिक्ट बेहतर-रिस्पॉन्स स्थिरीकरण लागू करें जबकि अनुमान गारंटी को संरक्षित रखें।
• सत्यापन: शोध पत्र बजट व्यवहार्यता के लिए एक बहुपद-समय (polynomial-time) ऑरेकल सत्यापन प्रदान करता है जब रिटेंड स्लैक सबमॉड्यूलर (submodular) होता है।

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

1. मॉडलिंग: एक गठबंधन-विशिष्ट FL मॉडल पेश करता है जो अनिर्भाषित एकत्रीकरण के बिना असफल संचार राउंड को संभालता है और सुपरएडिटिविटी का अनुमान नहीं लगाता है।
2. आर्थिक पृथक्करण: शिक्षण लाभ, लागत, हस्तांतरण और रिटेंड कोऑर्डिनेटर सरप्लस को स्पष्ट रूप से अलग करता है, जिससे बजट व्यवहार्यता और व्यक्तिगत तर्कसंगतता के लिए स्थितियाँ प्राप्त होती हैं।
3. स्थिरता गारंटी: सिद्ध करता है कि सममित युग्व आवंटन एक सटीक क्षमता गेम बनाते हैं, जो नैश-स्थिर और व्यक्तिगत रूप से स्थिर विभाजनों के अस्तित्व और परिमित अभिसरण (finite convergence) की गारंटी देते हैं।
4. दक्षता सीमाएँ: रिटेंड कोऑर्डिनेटर स्लैक और कल्याण दक्षता के बीच संबंध को स्पष्ट करता है। यह सिद्ध करता है कि सटीक संतुलन केवल एक विशिष्ट वर्ग के अधिशेष पर ही इष्टतम स्थिरता प्रदान करता है, जबकि सीमित सापेक्ष स्लैक एक टाइट मल्टीप्लिकेटिव एफिशिएंसी बाउंड प्रदान करता है।
5. कंप्यूटेशनल जटिलता: वैश्विक क्षमता अधिकतमकरण को कोरिलेशन क्लस्टरिंग (NP-hard) से जोड़ता है और अनुमान-प्लस-स्थिरीकरण पाइपलाइनों के लिए एंड-टू-एंड कल्याण गारंटी प्राप्त करता है।
6. सत्यापन: दिखाता है कि यदि रिटेंड स्लैक सबमॉड्यूलर है, तो घातीय (exponentially) कई बजट बाधाओं को बहुपद ऑरेकल समय में सत्यापित किया जा सकता है।
7. प्रायोगिक सत्यापन: $n=4$ प्रतिभागियों के साथ CIFAR-10 पर एक प्री-रजिस्टर्ड अध्ययन आयोजित किया गया।

प्रायोगिक परिणाम
अध्ययन विषम वितरण वाले CIFAR-10 के पांच सीड्स पर तंत्र का मूल्यांकन करता है:

• कल्याण इष्टतमता (Welfare Optimality): एक "बेनाइन" (benign) कैलिब्रेशन में, विकेंद्रीकृत तंत्र ने सभी पांच सीड्स के लिए प्रमाणित अनुमानित-टेबल कल्याण इष्टतम प्राप्त किया। प्रायोगिक 'प्राइस ऑफ स्टेबिलिटी' (Price of Stability) ठीक 1 था।
• बनाम बेसलाइन स्थिरता: इसके विपरीत, एक "इक्वल-सरप्लस शेयरिंग" बेसलाइन पांच में से तीन सीड्स पर नैश-स्थिर परिणाम देने में विफल रही (नैश-स्थिर सेट खाली था, और डायनेमिक्स चक्रित/cycle हुए)।
• अभिसरण (Convergence): विकेंद्रीकृत बेहतर-रिस्पॉन्स प्रक्रिया विभिन्न इनिशियलाइजेशन से तेजी से अभिसरित हुई (औसत 1.53 मूव्स)।
• संवेदनशीलता: एक "लीन" (lean - लागत-संवेदनशील) कैलिब्रेशन में, स्थिरता लागत बढ़ गई (प्राइस ऑफ स्टेबिलिटी 1.29 तक), और इष्टतम विभाजन अनुमान त्रुटियों के प्रति संवेदनशील हो गया, जो बजट टाइटनेस और स्थिरता के बीच ट्रेड-ऑफ को उजागर करता है।
• अनुमान: पेयरवाइज वैलिडेशन गेन (PVG) एस्टिमेटर्स ने ग्रेडिएंट एलाइनमेंट की तुलना में काफी अधिक विश्वसनीय पेयर साइन प्रदान किए, जो गलत सकारात्मक (false positives) के प्रति संवेदनशील था।

महत्व और दावे
यह शोध पत्र दावा करता है कि यह स्थानीय संतुलन, वैश्विक इष्टतमता और कम्प्यूटेशनल सुलभता को मिलाए बिना लर्निंग वैल्यू, मौद्रिक हस्तांतरण, स्थिरता और आर्थिक दक्षता को जोड़ता है।

• सैद्धांतिक: यह नैश इक्विलिब्रियम को एक स्थानीय क्षमता इष्टतम के रूप में सही ढंग से व्याख्या करके और सुपरएडिटिविटी का अनुमान न लगाकर प्रारंभिक कार्य की सीमाओं को सुधारता है। यह स्थापित करता है कि स्थिरता और दक्षता दो अलग अवधारणाएं हैं जो समन्वयक के रिटेंड स्लैक द्वारा जुड़ी हुई हैं।
• व्यावहारिक: प्रस्तावित तंत्र विषम फेडरेटेड लर्निंग प्रतिभागियों को व्यवस्थित करने का एक प्रमाणित स्थिर और बजट-व्यवहार्य तरीका प्रदान करता है। प्रायोगिक परिणाम दर्शाते हैं कि जबकि सरल सरप्लस-स्प्लिटिंग नियम स्थिर होने में विफल हो सकते हैं, प्रस्तावित युग्व क्षमता दृष्टिकोण एक स्थिर अवस्था तक पहुँचने की गारंटी देता है जो कल्याण इष्टतम के साथ मेल खा सकती है।
• सीमाएँ: लेखक नोट करते हैं कि वर्तमान मॉडल मानता है कि समन्वयक लागत और लाभों को जानता है या अनुमान लगाता है (इंसेंटिव एलोकेशन, न कि ट्रुथफुल मैकेनिज्म डिजाइन)। प्रायोगिक सत्यापन $n=4$ प्रतिभागियों तक सीमित है ताकि सटीक गणना और प्रमाणन संभव हो सके, और परिणाम प्रयोग के अनुमानित मान तालिकाओं के विशिष्ट हैं।

यह कार्य निष्कर्ष निकालता है कि हालांकि सटीक बजट संतुलन सामान्य रूप से कल्याण इष्टतमता की गारंटी नहीं देता है, प्रस्तावित ढांचा क्लस्टर्ड फेडरेटेड लर्निंग में स्थिर, बजट-व्यवहार्य गठबंधन निर्माण के लिए एक मजबूत सैद्धांतिक आधार और व्यावहारिक तंत्र प्रदान करता है।