📊 statistics

Less Random, More Private: What is the Optimal Subsampling Scheme for DP-SGD?

यह शोध पत्र यह प्रदर्शित करता है कि DP-SGD में मानक पॉइसन सबसैंपलिंग (Poisson subsampling) को एक संरचित बैलेंस्ड इटरेशन सबसैंपलिंग (Balanced Iteration Subsampling - BIS) योजना से बदलना, जो समान मार्जिनल भागीदारी बनाए रखते हुए भागीदारी विचरण (participation variance) को समाप्त करता है, बेहतर गोपनीयता प्रवर्धन (privacy amplification) प्राप्त करता है और कम-शोर वाले शासन (low-noise regimes) में आवश्यक शोर गुणक (noise multiplier) को 9.6% तक कम कर देता है।

मूल लेखक: Andy Dong, Ayfer Özgür

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

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

CC BY 4.0

मूल लेखक: Andy Dong, Ayfer Özgür

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

कल्पना कीजिए कि आप एक स्मार्ट कंप्यूटर (एक AI) को प्रशिक्षित करने के लिए एक विशाल, गुप्त मतदान प्रणाली चला रहे हैं। आपके पास लोगों की एक बहुत बड़ी सूची (डेटा) है, और चुनाव के हर दौर में, आप वोट देने के लिए कुछ लोगों को चुनते हैं। गोपनीयता की रक्षा के लिए, आप परिणामों में थोड़ा सा "स्टैटिक" (शोर/नॉइज़) जोड़ते हैं ताकि कोई भी ठीक से यह न जान सके कि किसने क्या वोट दिया।

पिछले एक दशक से, मतदाताओं को चुनने का मानक तरीका पॉइसन सबसैंपलिंग (Poisson Subsampling) रहा है। इसे एक लॉटरी की तरह सोचें जहाँ हर किसी को टिकट मिलता है, लेकिन उन्हें कितने टिकट मिलते हैं यह रैंडम (अनिश्चित) होता है। कुछ लोगों को शायद 10 बार चुना जाए, कुछ को 0 बार, और कुछ को 50 बार, जो पूरी तरह से संयोग पर निर्भर है। तर्क यह था: "अधिक रैंडमनेस equals अधिक गोपनीयता।"

बड़ी खोज
स्टैनफोर्ड के शोधकर्ताओं द्वारा लिखा गया यह पेपर तर्क देता है कि यह "लॉटरी" वाला दृष्टिकोण वास्तव में त्रुटिपूर्ण है। उन्होंने पाया कि एक व्यक्ति को कितनी बार चुना जाता है, इसमें जो रैंडमनेस है, वह एक छिपी हुई कमजोरी पैदा करती है। यह एक ऐसी लॉटरी की तरह है जहाँ कुछ लोग जैकपॉट 50 बार जीतते हैं जबकि अन्य कभी नहीं जीतते; यह असंतुलन वास्तव में हमलावर के लिए यह पता लगाना आसान बना देता है कि कौन सिस्टम में शामिल था।

वे एक नया तरीका प्रस्तावित करते हैं जिसे बैलेंस्ड इटरेशन सबसैंपलिंग (BIS) कहा जाता है।

रचनात्मक उपमा: एक पूर्ण रूप से संतुलित शिफ्ट

पुराना तरीका (पॉइसन):
कल्पना कीजिए कि आप 1,000 कर्मचारियों के लिए 100 दिनों के रूप में शिफ्ट शेड्यूल कर रहे हैं। आप सभी को बताते हैं, "हर सुबह एक सिक्का उछालें; यदि हेड आता है, तो आप काम करेंगे।"

परिणाम: कुछ कर्मचारी 80 दिन काम करते हैं, अन्य केवल 20 दिन। शेड्यूल अराजक है।
समस्या: क्योंकि कार्यभार इतना असमान है, एक जासूस कुल काम किए गए घंटों को देखकर अनुमान लगा सकता है कि, "आह, वह व्यक्ति जिसने 80 दिन काम किया, वही वह व्यक्ति है जिसे हम ढूंढ रहे हैं!" यह वैरिएंस (सबसे व्यस्त और सबसे कम व्यस्त के बीच का अंतर) जानकारी लीक करता है।

नया तरीका (BIS):
अब, कल्पना कीजिए कि आप सभी को बताते हैं, "हमें हर दिन ठीक 50 लोगों की आवश्यकता है, और 100 दिनों में, हर कोई ठीक 50 दिन काम करेगा।" आप ताश के पत्तों को इस तरह फेंटते और बांटते हैं कि हर किसी को ठीक 50 शिफ्ट मिलती हैं, लेकिन वे कौन से दिन काम करते हैं, यह अभी भी रैंडम है।

परिणाम: हर कोई ठीक समान मात्रा में काम करता है। शेड्यूल पूरी तरह से संतुलित है।
लाभ: एक जासूस कुल घंटों को देखता है और कहता है, "हर कोई 50 दिन काम करता है। मैं यह नहीं बता सकता कि कौन कौन है।" वैरिएंस (अंतर) को हटाकर, आप सिस्टम को क्रैक करना बहुत कठिन बना देते हैं।

यह पेपर वास्तव में क्या कहता है

कम रैंडमनेस, अधिक गोपनीयता: विरोधाभासी रूप से, यह पेपर सिद्ध करता है कि रैंडमनेस को सीमित करना (यह सुनिश्चित करना कि हर कोई ठीक समान संख्या में भाग ले) अधिक रैंडम होने की तुलना में मजबूत गोपनीयता प्रदान करता है।
दो चरम परिदृश्य: शोधकर्ताओं ने गणितीय रूप से सिद्ध किया कि यह नया तरीका दो चरम स्थितियों में "सर्वश्रेष्ठ संभव" है:
- जब शोर (Noise) बहुत कम हो (उच्च उपयोगिता): यह सबसे महत्वपूर्ण वास्तविक दुनिया का परिदृश्य है। यहाँ, पुराने लॉटरी तरीके की "असमानता" सबसे बड़ा लीक है। BIS इसे ठीक करता है, जिससे आप समान गोपनीयता सुरक्षा प्राप्त करने के लिए कम शोर (9.6% तक कम) का उपयोग कर सकते हैं। कम शोर का मतलब है कि AI बेहतर सीखता है और अधिक उपयोगी होता है।
- जब शोर बहुत अधिक हो: यहाँ, नया तरीका पुराने लॉटरी तरीके के समान ही प्रदर्शन करता है। यह कभी भी इससे खराब नहीं होता।
"मैथ मैजिक" (द अकाउंटेंट):
- इस नए "बैलेंस्ड" तरीके की सटीक गोपनीयता की गणना करना अविश्वसनीय रूप से कठिन है। यह ताश की गड्डी बांटने के हर संभावित तरीके को गिनने जैसा है, जो एक ऐसी संख्या है इतनी बड़ी कि यह एक सुपरकंप्यूटर को भी क्रैश कर देगी।
- लेखकों ने एक नया कैलकुलेटर (अकाउंटेंट) बनाया है जो एक चतुर ट्रिक का उपयोग करता है। यह पहले एक सुपर-फास्ट "स्क्रीनिंग टेस्ट" चलाता है यह देखने के लिए कि क्या कोई विशिष्ट परिदृश्य जांचने के लायक भी है या नहीं। यदि नहीं, तो यह उसे छोड़ देता है। यदि है, तो यह भारी गणित करता है।
- इसने उन्हें यह सिद्ध करने की अनुमति दी कि नया तरीका वास्तव में बेहतर है, बिना किसी "अनुमान" या ढीले सन्निकटन (approximations) के।

निचोड़

यह पेपर इस लंबे समय से चली आ रही धारणा को उलट देता है कि "अधिक रैंडमनेस हमेशा गोपनीयता के लिए बेहतर होती है।" इसके बजाय, यह दिखाता है कि संरचना और संतुलन श्रेष्ठ है।

अराजक लॉटरी (पॉइसन) से बदलकर एक पूर्ण रूप से संतुलित शेड्यूल (BIS) अपनाकर, आप ऐसे निजी AI मॉडल को प्रशिक्षित कर सकते हैं जो अधिक सटीक (क्योंकि आपको कम शोर की आवश्यकता है) होते हैं और साथ ही समान स्तर की गोपनीयता बनाए रखते हैं। लेखकों ने इस नए कैलकुलेटर के लिए कोड भी जारी किया है ताकि अन्य लोग तुरंत इसका उपयोग कर सकें।

संक्षेप में: यदि आप अपने AI के लिए सर्वोत्तम गोपनीयता चाहते हैं, तो पासे को रैंडम तरीके से लुढ़कने देना बंद करें। हर किसी को निश्चित संख्या में बारी दें, और आप एक मजबूत ढाल प्राप्त करेंगे।

तकनीकी सारांश: कम यादृच्छिकता, अधिक गोपनीयता (Less Random, More Private)

समस्या विवरण (Problem Statement)

डिफरेंशियल प्राइवेसी स्टोकेस्टिक ग्रेडिएंट डिसेंट (DP-SGD) में, डेटा सबसैंपलिंग स्कीम का चयन प्राइवेसी-यूटिलिटी ट्रेडऑफ (privacy-utility tradeoff) का एक केंद्रीय चालक है। पिछले एक दशक से, पॉइसन सबसैंपलिंग (Poisson subsampling) डिफ़ॉल्ट तंत्र रहा है, जहाँ प्रत्येक नमूना एक निश्चित प्रायिकता के साथ प्रत्येक इटरेशन में स्वतंत्र रूप से भाग लेता है। यह विकल्प विश्लेषणात्मक सुविधा और इस अंतर्ज्ञान से प्रेरित है कि अनस्ट्रक्चर्ड रैंडमनेस (unstructured randomness) प्राइवेसी एम्प्लीफिकेशन को अधिकतम करती है।

हालाँकि, लेखक इस दृष्टिकोण में एक मौलिक दोष की पहचान करते हैं: पॉइसन सबसैंपलिंग की अनियंत्रित रैंडमनेस पर्याप्त पार्टिसिपेशन वेरिएंस (participation variance) पेश करती है। पॉइसन सबसैंपलिंग में, एक विशिष्ट नमूना कितने इटरेशन में भाग लेता है, यह द्विपद वितरण (binomial distribution) का अनुसरण करता है, जिससे विभिन्न नमूनों के बीच भागीदारी की संख्या में महत्वपूर्ण उतार-चढ़ाव होता है। शोध पत्र का तर्क है कि यह वेरिएंस केवल एक व्यावहारिक आर्टिफैक्ट नहीं है, बल्कि सब-ऑप्टिमल प्राइवेसी एम्प्लीफिकेशन का एक मौलिक स्रोत है, विशेष रूप से लो-नॉइज़ रिजीम (low-noise regimes) में जो उच्च-यूटिलिटी ट्रेनिंग के लिए प्रासंगिक हैं।

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

कार्यप्रणाली (Methodology)

1. प्राइवेसी लॉस का सैद्धांतिक विश्लेषण (Theoretical Analysis of Privacy Loss)

लेखक ज़ीरो-आउट एडजसेंसी रिलेशन (zero-out adjacency relation) के तहत प्राइवेसी लॉस रैंडम वेरिएबल $L(y) = \log(P(y)/Q(y))$ का विश्लेषण करते हैं, जहाँ $P$ एक भिन्न उदाहरण के साथ आउटपुट वितरण है और $Q$ बिना उस उदाहरण के वितरण है। वे नॉइज़ मल्टीप्लायर $\sigma$ के दो चरम क्षेत्रों में प्राइवेसी लॉस के एसिम्प्टोटिक व्यवहार को व्युत्पन्न करते हैं:

लो-नॉइज़ लिमिट ( $\sigma \to 0$ ):
इस रिजीम में, जो उच्च-यूटिलिटी परिनियोजन के लिए प्रासंगिक है, प्राइवेसी लॉस टर्म $\|x\|_2^2 / (2\sigma^2)$ द्वारा संचालित होता है, जहाँ $x$ भागीदारी वेक्टर है। विश्लेषण प्रकट करता है कि प्राइवेसी लॉस का ऊपरी टेल (upper tail) मुख्य रूप से $\|x\|_2^2$ (भागीदारी की संख्या) में उतार-चढ़ाव द्वारा संचालित होता है।
- ऑप्टिमाइज़ेशन रणनीति: प्राइवेसी लॉस को न्यूनतम करने के लिए, सबसे पहले $\|x\|_2^2$ के वेरिएंस को समाप्त करना आवश्यक है। इसके लिए एक नियत (deterministic) भागीदारी संख्या $k$ को लागू करना आवश्यक है। केवल वेरिएंस को स्थिर करने के बाद ही, वितरण की एंट्रॉपी (वैध पैटर्न के बीच रैंडमनेस को अधिकतम करना) दूसरा अनुकूलन कारक बन जाता है।
- परिणाम: पॉइसन सबसैंपलिंग, जो भागीदारी गणनाओं में वेरिएंस की अनुमति देती है, सब-ऑप्टिमल है। इष्टतम रणनीति बैलेंस्ड इटरेशन सबसैंपलिंग (BIS) है, जहाँ प्रत्येक नमूना $T$ में से ठीक $k$ इटरेशन में भाग लेता है, जिसे यूनिफॉर्मली रैंडम तरीके से चुना जाता है।
हाई-नॉइज़ लिमिट ( $\sigma \to \infty$ ):
इस रिजीम में, डोमिनेंट टर्म मार्जिनल भागीदारी प्रायिकताओं $\mu = E[x]$ द्वारा नियंत्रित होता है।
- ऑप्टिमाइज़ेशन रणनीति: फर्स्ट-ऑर्डर टर्म के लिए यूनिफॉर्म मार्जिनल प्रायिकताओं ( $\mu_t = k/T$ ) की आवश्यकता होती है। पॉइसन और BIS दोनों इसे संतुष्ट करते हैं। सेकंड-ऑर्डर टर्म भागीदारी वेक्टर के कोवेरिएंस मैट्रिक्स $\Sigma$ से संबंधित है। वर्स्ट-केस टेल को न्यूनतम करने के लिए, स्कीम को ऑल-वन्स वेक्टर की दिशा में वेरिएंस को समाप्त करना चाहिए (अर्थात, $\text{Var}(\sum x_t) = 0$ )।
- परिgetResult: BIS इष्टतम है क्योंकि यह भागीदारी की कुल संख्या को नियत (deterministically) करता है, इस वेरिएंस को समाप्त करता है। जबकि पॉइसन सबसैंपलिंग लीडिंग ऑर्डर में BIS से मेल खाती है, BIS सेकंड-ऑर्डर उतार-चढ़ाव को न्यूनतम करता है, जो सैद्धांतिक रूप से एक स्केल्ड फुल-बैच अपडेट के मौलिक निचली सीमा (lower bound) के करीब पहुँचता है।

2. नियर-एक्ज़ैक्ट मोंटे कार्लो अकाउंटिंग (Near-Exact Monte Carlo Accounting)

इन एसिम्प्टोटिक अंतर्दृश्यों को परिमित-नॉइज़ गारंटी (finite-noise guarantees) में अनुवादित करने के लिए, लेखक BIS के सटीक प्राइवेसी कॉस्ट का मूल्यांकन करने की कम्प्यूटेशनल जटिलता को संबोधित करते हैं। सटीक मूल्यांकन के लिए $\binom{T}{k}$ संयोजनों को जोड़ना आवश्यक है, जो कॉम्बिनेटोरियल रूप से विस्फोटक है।

वे एक स्क्रीन-देन-एक्ज़ैक्ट (Screen-Then-Exact) मोंटे कार्लो अकाउंटेंट पेश करते हैं:

**डायनेमिक प्रोग्रामिंग ($O(Tk) $):** वे सटीक लाइकलीहुड रेशियो$ P(y)/Q(y) $को$ O(Tk) $समय में कंप्यूट करने के लिए एक डायनेमिक प्रोग्रामिंग फॉर्मूलेशन व्युत्पन्न करते हैं, जो जटिलता को$ O(\binom{T}{k})$ से कम करता है।
स्क्रीनिंग बाउंड ( $O(T)$ ): वे लाइकलीहुड रेशियो पर एक तेज़ अपर बाउंड (Lemma 4.1) सिद्ध करते हैं जिसे $O(T)$ समय में कंप्यूट किया जा सकता है।
फिल्टरिंग मैकेनिज्म: मोंटे कार्लो अकाउंटिंग में, एक नमूना प्राइवेसी बजट $\delta$ में तभी योगदान देता है यदि उसका लॉग-लाइकेलीहुड रेशियो लक्षित $\epsilon$ से अधिक हो। $O(T)$ स्क्रीनिंग बाउंड एक फ़िल्टर के रूप में कार्य करता है: यदि बाउंड $\le \epsilon$ है, तो महंगे $O(Tk)$ सटीक कंप्यूटेशन को चलाने के बिना नमूने को छोड़ दिया जाता है।
दक्षता: अनुभवजन्य रूप से, केवल $O(\delta)$ अंश के नमूने ही बाउंड से ऊपर जाते हैं। यह ह्यूरिस्टिक अपेक्षित रनटाइम को $O(T + \delta Tk)$ तक कम कर देता है, जिससे बड़े पैमाने पर ट्रेनिंग के लिए नियर-एक्ज़ैक्ट अकाउंटिंग व्यवहार्य हो जाता है।

मुख्य योगदान (Key Contributions)

सैद्धांतिक इष्टतमता (Theoretical Optimality): यह पेपर सिद्ध करता है कि स्वतंत्र-उदाहरण सबसैंपलिंग स्कीमों के बीच, बैलेंस्ड इटरेशन सबसैंपलिंग (BIS) नॉइज़ स्पेक्ट्रम के दोनों छोरों ( $\sigma \to 0$ और $\sigma \to \infty$ ) पर इष्टतम है। यह इस सामान्य धारणा को उलट देता है कि अधिकतम रैंडमनेस अधिक मजबूत प्राइवेसी प्रदान करती है; इसके बजाय, भागीदारी-गणना के वेरिएंस को समाप्त करना प्राइवेसी एम्प्लीफिकेशन का प्राथमिक चालक है।
नियर-एक्ज़ैक्ट फाइनाइट-नॉइज़ अकाउंटिंग: लेखक BIS के लिए एक व्यावहारिक मोंटे कार्लो अकाउंटेंट पेश करते हैं जो मौजूदा रेनी डिफरेंशियल प्राइवेसी (RDP) और कंपोजिशन-आधारित प्राइवेसी लॉस डिस्ट्रीब्यूशन (PLD) विश्लेषणों में निहित विश्लेषणात्मक ढील (analytical slack) को हटा देता है। यह $O(Tk) $डायनेमिक प्रोग्राम और$ O(T)$ स्क्रीनिंग बाउंड के माध्यम से प्राप्त किया जाता है।
अनुभवजन्य सत्यापन (Empirical Validation): 60 से अधिक व्यावहारिक DP-SGD कॉन्फ़िगरेशनों के मूल्यांकन के माध्यम से, अध्ययन प्रदर्शित करता है कि BIS लो-नॉइज़ रिजीम में पॉइसन सबसैंपलिंग की तुलना में लगातार बेहतर प्रदर्शन करता है।

परिणाम (Results)

प्राइवेसी लाभ: लो-नॉइज़ रिजीम (उच्च उपयोगिता) में, नए नियर-एक्ज़ैक्ट अकाउंटेंट के साथ मूल्यांकन करने पर, BIS पॉइसन सबसैंपलिंग की तुलना में आवश्यक नॉइज़ मल्टीप्लायर को 9.6% तक कम कर देता है।
हाई-नॉइज़ में अभिसरण (Convergence): हाई-नॉइज़ रिजीम में, BIS और पॉइसन सबसैंपलिंग के प्राइवेसी गारंटियाँ, एसिम्प्टोटिक थ्योरी के अनुसार, एक दूसरे के करीब आती हैं, जिसमें BIS मौलिक निचली सीमा से मेल खाता है।
अकाउंटिंग स्लैक (Accounting Slack): अध्ययन से पता चलता है कि RDP या कंपोजिशन-आधारित PLD (जैसे, "RA-PLD") का उपयोग करके BIS के पिछले विश्लेषणों ने महत्वपूर्ण विश्लेषणात्मक ढील पेश की थी। कुछ सेटिंग्स में, इन ढीले बाउंड्स ने गलत तरीके से सुझाव दिया कि BIS को पॉइसन की तुलना में 20.5% अधिक शोर की आवश्यकता है, जिससे यह गलत प्रतीत हुआ कि BIS निम्न स्तर का है। नियर-एक्ज़ैक्ट मोंटे कार्लो अकाउंटिंग इसे सुधारता है, यह दिखाते हुए कि BIS स्पष्ट रूप से बेहतर या समकक्ष है।
सहसंबंध (Correlation): BIS का अनुभवजन्य लाभ $\epsilon/k$ के अनुपात के साथ मजबूती से सहसंबंधित है (पियर्सन सहसंबंध 0.93), जो पुष्टि करता है कि लाभ तब सबसे अधिक होता है जब प्रति भागीदारी प्राइवेसी बजट अधिक होता है (लो-नॉइज़ रिजीम)।

महत्व और दावे (Significance and Claims)

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

इस कार्य का महत्व यहाँ है:

DP अंतर्ज्ञान को परिष्कृत करना: यह प्राइवेसी एम्प्लीफिकेशन के लिए एंट्रॉपी को अधिकतम करने से ध्यान हटाकर भागीदारी प्रक्रिया में वेरिएंस को न्यूनतम करने पर केंद्रित करता है।
व्यावहारिक उपयोगिता: आवश्यक नॉइज़ मल्टीप्लायर को कम करके, BIS प्राइवेसी बजट को बढ़ाए बिना उच्च उपयोगिता वाले निजी मॉडल सक्षम बनाता है, या समान उपयोगिता के लिए सख्त प्राइवेसी गारंटी प्रदान करता है।
पद्धतिगत कठोरता: "स्क्रीन-देन-एक्ज़ैक्ट" अकाउंटेंट का विकास जटिल सबसैंपलिंग तंत्र के लिए सटीक, नियर-एक्ज़ैक्ट प्राइवेसी गारंटी प्राप्त करने के लिए एक ब्लूप्रिंट प्रदान करता है, जो कंपोजिशन-आधारित बाउंड्स की ढील से आगे जाता है।

लेखक निष्कर्ष निकालते हैं कि BIS, पॉइसन सबसैंपलिंग का एक मजबूत, सिद्धांत-आधारित विकल्प है, जो प्राइवेसी-यूटिलिटी पैरेटो फ्रंटियर (Pareto frontier) को आगे बढ़ाने के लिए एक कठोर मार्ग प्रदान करता है।