A Hierarchical Sampling Framework for bounding the Generalization Error of Federated Learning

तकनीकी निष्कर्ष: फेडरेटेड लर्निंग के सामान्यीकरण त्रुटि (Generalization Error) को सीमित करने के लिए एक पदानुक्रमित नमूनाकरण ढांचा (Hierarchical Sampling Framework)

समस्या विवरण
फेडरेटेड लर्निंग (FL) कई क्लाइंट्स को स्थानीय डेटा रखते हुए एक वैश्विक मॉडल को संयुक्त रूप से प्रशिक्षित करने में सक्षम बनाता है। जबकि केंद्रीकृत सुपरवइज्ड लर्निंग के लिए सामान्यीकरण सीमाएं (generalization bounds) मौजूद हैं, FL में उनका सीधा अनुप्रयोग अक्सर विफल हो जाता है क्योंकि वे पदानुक्रमित नमूनाकरण रणनीतियों (hierarchical sampling strategies) से उत्पन्न होने वाली गैर-i.i.d. प्रकृति का लाभ उठाने में विफल रहते हैं। मौजूदा साहित्य में विभिन्न पदानुक्रमित नमूनाकरण रणनीतियों और संचार संरचनाओं को समाहित करने वाले एक एकीकृत ढांचे का अभाव है; यह अक्सर उन धारणाओं पर निर्भर करता है जो FL की वितरित प्रकृति के साथ संघर्ष करती हैं या पदानुक्रमित डेटा स्रोतों द्वारा प्रेरित निर्भरताओं (dependencies) को समझने में विफल रहती हैं।

कार्यप्रणाली
लेखक एक बहु-स्तरीय ट्री संरचना के रूप में मॉडल किए गए पदानुक्रमित फेडरेटेड लर्निंग (HFL) के लिए एक सामान्यीकृत ढांचे का प्रस्ताव करते हैं। इस सेटअप में:

• पदानुक्रमित नमूनाकरण (Hierarchical Sampling): डेटासेट को एक निश्चित टोपोलॉजी वाले ट्री द्वारा इंडेक्स किया गया है। रूट (Root) एक मेटा-डिस्ट्रीब्यूशन $D$ का प्रतिनिधित्व करता है। मध्यवर्ती परतों के नोड्स क्लाइंट्स या क्लस्टर्स (उपवर्ती नोड्स पर वितरण) का प्रतिनिधित्व करते हैं, और लीफ नोड्स (Leaf nodes) वास्तविक डेटा बिंदुओं का प्रतिनिधित्व करते हैं। रूट से लीफ तक पुनरावर्ती (recursive) रूप से नमूनाकरण होता है, जिससे क्लाइंट डेटासेट्स के बीच निर्भरता उत्पन्न होती है।
• सुपरसैंपल्स का निर्माण: सामान्यीकरण का विश्लेषण करने के लिए, लेखक "सुपरसैंपल" तकनीक (मूल रूप से स्टीनके एट अल., 2020 द्वारा) को अनुकूलित करते हैं। वे एक "घोस्ट" (ghost) डेटासेट $\bar{\mu}$ का निर्माण करते हैं जिसमें मूल डेटासेट $\mu$ के समान सांख्यिकीय गुण होते हैं। प्रत्येक ट्री नोड के लिए, एक बाइनरी वेरिएबल $U$ या तो मूल नोड या उसकी घोस्ट कॉपी को चुनता है। यह नमूनाकरण ट्री के भीतर एक एकल नोड में परिवर्तन के प्रति एल्गोरिदम की संवेदनशीलता को मापने में सक्षम बनाता है।
• वॉसरस्टीन दूरी (Wasserstein Distance): सामान्यीकरण त्रुटि को एक विशिष्ट नोड चयन पर आधारित आउटपुट हाइपोथीसिस के वितरण और अनकंडीशनल (unconditional) वितरण के बीच वॉसरस्टीन-1 दूरी ($W$) का उपयोग करके सीमित किया जाता है। यह दृष्टिकोण इस धारणा पर निर्भर करता है कि लॉस फंक्शन $\ell(w, z)$ हाइपोथीसिस $w$ के संबंध में $L$-लिप्सचिट्ज (Lipschitz) निरंतर है।

मुख्य योगदान

1. सामान्यीकृत HFL ढांचा: यह कार्य विभिन्न पदानुक्रमित नमूनाकरण रणनीतियों और पूर्ववर्ती FL ढांचों को विशेष मामलों के रूप में समाहित करने वाला एक ढांचा प्रस्तुत करता है, जो ट्री संरचना द्वारा प्रेरित निर्भरताओं को स्पष्ट रूप से मॉडल करता है।
2. वॉसरस्टीन सामान्यीकरण सीमा: लेखक वॉसरस्टीन दूरी के संदर्भ में एक नई सामान्यीकरण सीमा प्राप्त करते हैं। यह सीमा व्यापक रेंज के लॉस फंक्शन्स (लिप्सचिट्ज धारणा के तहत) पर लागू होती है और बाउंडेड लॉस के लिए मौजूदा स्टेट-ऑफ-द-आर्ट कंडीशनल म्यूचुअल इंफॉर्मेशन (CMI) की तुलना में स्पष्ट रूप से अधिक सटीक (tighter) सिद्ध होती है।
3. गोपनीयता-जागरूक सीमाएं (Privacy-Aware Bounds): ढांचे को डिफरेंशियल प्राइवेसी (DP) संबंधी धारणाओं को शामिल करने के लिए विस्तारित किया गया है। ट्री के भीतर एग्रीगेशन चरणों पर स्थानीय गोपनीयता बाधाओं को लागू करके, लेखक एल्गोरिथमिक प्राइवेसी के आधार पर सामान्यीकरण सीमाएं प्राप्त करते हैं।
4. गौसियन लोकेशन मॉडल (GLM) पर केस स्टडी: प्राप्त सीमाओं की सटीकता का मूल्यांकन एक गौसियन लोकेशन मॉडल का उपयोग करके किया गया है। लेखक प्रदर्शित करते हैं कि उनकी सीमा डेटा बिंदुओं की संख्या के संबंध में सामान्यीकरण त्रुटि की सही एसिम्प्टोटिक दर (asymptotic rate) को पुनः प्राप्त करती है, हालांकि यह वास्तविक त्रुटि की तुलना में नमूनाकरण ट्री की गहराई के संबंध में एक स्केलिंग विचलन प्रदर्शित करती है।

परिणाम

• मुख्य प्रमेय (प्रमेय 5): लिप्सचिट्ज धारणा के तहत, अपेक्षित सामान्यीकरण त्रुटि, एक चयनित नोड पर आधारित हाइपोथीसिस वितरण और अनकंडीशनल हाइपोथीसिस वितरण के बीच अपेक्षित वॉसरस्टीन दूरी के योग द्वारा सीमित होती है।
• CMI के साथ संबंध (अनुलग्नक 6 और 9): बाउंडेड लॉस के लिए, वॉसरस्टीन सीमा मौजूदा CMI सीमाओं को निहित करती है। लेखक दिखाते हैं कि उनका व्युत्पन्न पिछले CMI-आधारित प्रमाणों में असमानताओं की श्रृंखला (जैसे बार-बार लागू पिंस्कर असमानता) द्वारा पेश की गई ढील (looseness) से बचता है, जिसके परिणामस्वरूप एक स्पष्ट रूप से अधिक सटीक सीमा प्राप्त होती है।
• गोपनीयता के निहितार्थ (प्रमेय 13): स्थानीय एग्रीगेशन के लिए $\epsilon$-डिफरेंशियल प्राइवेसी धारणाओं के तहत, सामान्यीकरण त्रुटि परतों में प्राइवेसी पैरामीटर्स $\epsilon_l$ के एक फलन द्वारा सीमित होती है, विशेष रूप से $\sqrt{\min(\epsilon_l, \epsilon_l(e^{\epsilon_l}-1))}$ को शामिल करते हुए।
• GLM विश्लेषण: गौसियन लोकेशन मॉडल में, वास्तविक सामान्यीकरण त्रुटि $\sqrt{\frac{\sum \sigma_l^2/N_l}{\sum \sigma_l^2}}$ के रूप में स्केल करती है। व्युत्पन्न वॉसरस्टीन सीमा $\sum \frac{\sigma_l}{N_l}$ के रूप में स्केल करती है। जबकि यह सीमा डेटा बिंदुओं ($N_l$) के साथ स्केलिंग को पकड़ती है, लेखक नोट करते हैं कि यह वास्तविक त्रुटि में देखे गए ट्री डेप्थ ($L$) के विशिष्ट स्केलिंग को पकड़ने में विफल रहती है, विशेष रूप से जब परतों में वेरिएंस होमोजेनियस (homogeneous) होता है।

महत्व और दावे
यह कार्य पदानुक्रमित डेटा निर्भरताओं को स्पष्ट रूप से ध्यान में रखकर फेडरेटेड लर्निंग में सामान्यीकरण को समझने के लिए एक अधिक सामान्य और सटीक सैद्धांतिक आधार प्रदान करने का दावा करता है। वॉसरस्टीन दूरी का लाभ उठाकर, यह ढांचा वितरण की ज्यामिति और नमूनाकरण संरचना के प्रति लर्निंग एल्गोरिदम की संवेदनशीलता को पिछले सूचना-सैद्धांतिक दृष्टिकोणों की तुलना में अधिक प्रभावी ढंग से कैप्चर करता है। लेखक दावा करते हैं कि उनकी सीमा बाउंडेड लॉस के लिए मौजूदा CMI सीमाओं को स्पष्ट रूप से निहित करती है, जो केवल एक विकल्प के बजाय एक शोधन (refinement) का प्रतिनिधित्व करती है। इसके अलावा, डिफरेंशियल प्राइवेसी धारणाओं के साथ सहजता से एकीकृत होने की ढांचे की क्षमता गोपनीयता-संरक्षित FL सिस्टम के विश्लेषण में इसकी उपयोगिता को प्रदर्शित करती है। लेखक सीमाओं को स्वीकार करते हुए कहते हैं कि वर्तमान सीमा संचार बाधाओं या व्यक्तिगत नोड्स की कम्प्यूटेशनल बाधाओं को स्पष्ट रूप से ध्यान में नहीं रखती है, लेकिन सुझाव देते हैं कि इन्हें इंडिपेंडेंस कंडीशंस के माध्यम से एकीकृत किया जा सकता है, जैसा कि उनके कोरोलरी 10 के व्युत्पन्न में दिखाया गया है। सामान्य (गैर-निश्चित) ट्री संरचनाओं तक विस्तार करने के लिए भविष्य के कार्य का प्रस्ताव दिया गया है।