💻 computer science

Pure-DP Statistical Query Release at the Conjectured Square-Root Rate

यह शोध पत्र निकोलोव और उल्मैन के एक अनुमान (conjecture) को हल करता है, जिसमें एक सूचना-सैद्धांतिक (information-theoretic), $\varepsilon$ -डिफरेंशियल प्राइवेट मैकेनिज्म प्रस्तुत किया गया है जो $T$ आकार के ब्रह्मांड (universe) पर $k$ सांख्यिकीय प्रश्नों (statistical queries) को जारी करता है, जिसका अपेक्षित वर्स्ट-कोऑर्डिनेट एरर (worst-coordinate error) सभी पैरामीटर व्यवस्थाओं में अनुमानित वर्गमूल दर $O(\sqrt{\log(2T)\log(2k)/(\varepsilon n)})$ से मेल खाता है।

मूल लेखक: Jack Fitzsimons

प्रकाशित 2026-07-23

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

CC BY 4.0

मूल लेखक: Jack Fitzsimons

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

कल्पना कीजिए कि आप एक लाइब्रेरियन हैं जिसके पास नामों की एक गुप्त किताब है। आप उस किताब में मौजूद लोगों के बारे में कुछ दिलचस्प आंकड़े साझा करना चाहते हैं—जैसे औसत ऊंचाई या सबसे आम पसंदीदा रंग—बिना यह बताए कि वास्तव में किताब में कौन शामिल है। यह डिफरेंशियल प्राइवेसी (differential privacy) की दुनिया है, जो एक गणितीय ढाल है जो हमें व्यक्तिगत रहस्यों की रक्षा करते हुए डेटा से सीखने की अनुमति देती है। इसे एक "नॉइज़ मशीन" (शोर बनाने वाली मशीन) की तरह समझें जो उत्तरों में बस इतना 'स्टैटिक' (शोर) जोड़ देती है कि यदि कोई डेटा को रिवर्स-इंजीनियर करके किसी विशिष्ट व्यक्ति को खोजने का प्रयास करता है, तो वह स्टैटिक इसे असंभव बना देता है।

इस ढाल को बनाने के दो मुख्य तरीके हैं। एक है "अनुमानित" (approximate) ढाल, जो लीक होने की एक बहुत मामूली, लगभग अदृश्य संभावना की अनुमति देती है (जैसे एक दरवाज़ा जो 99.9% लॉक है)। दूसरा है "शुद्ध" (pure) ढाल, जो 100% गारंटी देती है कि कोई भी रहस्य कभी नहीं सुलझाया जा सकता, चाहे कितनी भी कोशिश क्यों न की जाए। लंबे समय तक, गणितज्ञों को पता था कि "शुद्ध" ढाल का उपयोग करना बहुत कठिन था। जब आप एक साथ कई प्रश्न पूछते थे, तो शुद्ध ढाल के पुराने तरीके बहुत बोझिल और धीमे थे, जिससे उत्तर बहुत धुंधले मिलते थे। यह केवल एक मोटे, गाढ़े ब्रश का उपयोग करके एक विस्तृत चित्र बनाने जैसा था। एक बड़ा सवाल हवा में लटका हुआ था: क्या हम एक शुद्ध ढाल बना सकते हैं जो अनुमानित ढाल जितनी ही सटीक और स्पष्ट हो?

यह शोध पत्र कहता है, "हाँ, हम कर सकते हैं।" लेखकों ने, जैक फिट्ज़िमोन के नेतृत्व में, एक नया गणितीय यंत्र तैयार किया है जो एक निजी डेटाबेस के बारे में कई प्रश्नों के उत्तर देते हुए सख्त "शुद्ध" गोपनीयता गारंटी बनाए रखता है। उन्होंने सिद्ध किया कि यह मशीन उस सटीकता स्तर को प्राप्त कर सकती है जो पहले केवल एक अनुमान था। विशेष रूप से, उन्होंने दिखाया कि उत्तरों में त्रुटि (error) डेटाबेस में लोगों की संख्या के वर्गमूल (square root) की दर से घटती है, न कि पुराने तरीकों की धीमी क्यूब-रूट (cube-root) दर से। यह उस गाढ़े ब्रश को एक बारीक टिप वाले पेन से बदलने जैसा है, जिससे सख्त नियमों के बावजूद एक स्पष्ट चित्र बनाना संभव हो जाता है।

"प्राइवेसी एनवेलप" (गोपनीयता लिफाफा) की कहानी

इसे समझने के लिए, कल्पना कीजिए कि आप लोगों के एक समूह की औसत ऊंचाई का अनुमान लगाने की कोशिश कर रहे हैं, लेकिन आप केवल ऐसे प्रश्न पूछ सकते हैं जैसे, "क्या यह व्यक्ति 5 फीट से लंबा है?" इस कार्य को निजी रूप से करने का मानक तरीका मल्टीप्लिकेटिव वेट्स (PMW) कहलाता है। PMW को एक जासूस के रूप में सोचें जो "संदियों" (संभावित डेटा वितरण) की एक सूची रखता है और हर बार जब वह एक प्रश्न पूछता है, तो अपने विश्वास को अपडेट करता है।

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

लेखकों ने महसूस किया कि जासूस की "कोहरे वाली खिड़की" ही समस्या थी। उन्हें जासूस की दृष्टि को तीक्ष्ण बनाए रखने के साथ-साथ सख्त गोपनीयता नियमों का पालन करने की आवश्यकता थी। उनका समाधान एक प्राइवेसी एनवेलप (Privacy Envelope) बनाना था।

जासूस की संदिग्धों की सूची को एक मानचित्र के रूप में कल्पना करें। पुराने तरीके ने कहा, "हम मानचित्र पर तभी भरोसा कर सकते हैं जब हम 100% सुनिश्चित हों कि डेटा बिल्कुल नहीं बदला है।" नया तरीका कहता है, "आइए हम मानचित्र को देखें, लेकिन हम उन सभी मानचित्रों को भी देखें जो लगभग एक जैसे हैं, बस थोड़े से बदलाव के साथ।"

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

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

"ब्लॉकिंग" (समूहीकरण) का जादू

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

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

परिणाम

यह शोध पत्र सिद्ध करता है कि यह नया तरीका किसी भी आकार के डेटाबेस और प्रश्नों की किसी भी संख्या के लिए काम करता है। उत्तरों में त्रुटि एक विशिष्ट सूत्र का पालन करती है: जैसे-जैसे डेटाबेस बड़ा होता जाता है, यह कम होती जाती है, जो लगभग लोगों की संख्या के वर्गमूल (square root) की दर से घटती है। यह उस सर्वोत्तम प्रदर्शन से मेल खाता है जिसे गणितज्ञों ने सैद्धांतिक रूप से संभव माना था, जिससे अंततः उस अंतर को पाट दिया गया है जो हमारे सोचने और हमारे करने की क्षमता के बीच था।

लेखकों ने केवल अनुमान नहीं लगाया; उन्होंने एक कठोर गणितीय प्रमाण बनाया ताकि यह दिखाया जा सके कि यह कैसे काम करता है। उन्होंने अपने काम की दोबारा जांच करने के लिए 'लीन' (Lean) नामक एक कंप्यूटर प्रोग्राम का भी उपयोग किया, जिससे यह सुनिश्चित हुआ कि उनके तर्क का हर एक चरण सही है। हालांकि यह विधि वर्तमान में एक सैद्धांतिक ब्लूप्रिंट (यह एक "गणितीय रेसिपी" है न कि कोई तैयार ऐप) है, लेकिन यह दशकों पुराने पहेली को हल करती है। यह दिखाता है कि हमें सख्त गोपनीयता और सटीक उत्तरों के बीच चुनाव करने की आवश्यकता नहीं है; सही "एनवेलप" के साथ, हम दोनों पा सकते हैं।

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

तकनीकी सारांश: अनुमानित वर्ग-मूल दर पर प्योर-डीपी (Pure-DP) सांख्यिकीय क्वेरी रिलीज

समस्या विवरण
यह शोध पत्र प्योर डिफरेंशियल प्राइवेसी (pure DP) के अंतर्गत सांख्यिकीय क्वेरी रिलीज समस्या को संबोधित करता है। एक आकार $n$ के निजी डेटाबेस $x$ को, जो आकार $T$ के ब्रह्मांड (universe) $D$ पर आधारित है, और $k$ सीमित क्वेरीज़ $Q$ के सेट के लिए, एक एकल रैंडम वेक्टर जारी करने का लक्ष्य है जो सभी क्वेरीज़ के वास्तविक उत्तरों $F(x)$ के करीब हो। त्रुटि मीट्रिक अपेक्षित सबसे खराब-कोऑर्डिनेट त्रुटि ( $\ell_\infty$ नॉर्म) है।

एक अनुमानित डीपी (approximate DP) तंत्र (जो एक छोटा विफलता प्रायिकता $\delta > 0$ की अनुमति देता है) $O(\sqrt{\frac{\log T \log k}{\varepsilon n}})$ की त्रुटि दर प्राप्त करता है, जबकि ज्ञात प्योर डीपी तंत्र (जहाँ $\delta = 0$ है) पहले क्यूब-रूट दर $O((\frac{\log T \log k}{\varepsilon n})^{1/3})$ तक सीमित थे। निकोलोव और उलमैन [NU21] ने अनुमान लगाया था कि अपेक्षित त्रुटि के तहत प्योर डीपी के लिए वर्ग-रूट दर प्राप्त करना संभव है। यह शोध पत्र उस अनुमान को सिद्ध करता है।

कार्यप्रणाली (Methodology)
प्रस्तावित तंत्र सूचना-सैद्धांतिक (information-theoretic) है और तीन प्राथमिक चरणों से मिलकर बना है:

चयन-मात्र (Selection-Only) PMW ट्रांसक्रिप्ट:
निर्माण एक मानक प्राइवेट मल्टीप्लिकेटिव वेट्स (PMW) एल्गोरिदम से शुरू होता है लेकिन इसके आउटपुट को संशोधित करता है। प्रत्येक दौर में शोर युक्त संख्यात्मक उत्तर जारी करने के बजाय, तंत्र केवल एक्सपोनेंशियल मैकेनिज्म द्वारा चुनी गई क्वेरीज़ के इंडेक्स और संकेतों (signs) से बना एक ट्रांसक्रिप्ट $\omega$ उत्पन्न करता है। यह "चयन-मात्र" ट्रांसक्रिप्ट सटीक है और इसमें अच्छे परिमित-क्रम प्राइवेसी-लॉस मोमेंट्स (रेनी डाइवर्जेंस बाउंड्स) हैं, लेकिन यह अपने आप में प्योर डीपी को संतुष्ट नहीं करता है।
प्राइवेसी एनवेलप (Privacy Envelope) निर्माण:
इस मोमेंट-बाउंडेड ट्रांसक्रिप्ट को प्योर डीपी तंत्र में बदलने के लिए, लेखक मूल ट्रांसक्रिप्ट के प्रायिकता द्रव्यमान फलन $p_x(\omega)$ को एक डिस्टेंस-पेनलाइज्ड लाइकलीहुड एनवेलप (distance-penalized likelihood envelope) से बदलते हैं। एक निश्चित डेटाबेस $x$ के लिए, एक ट्रांसक्रिप्ट $\omega$ का अननॉर्मलाइज्ड प्रायिकता निम्न प्रकार है:
$\tilde{p}_x(\omega) = \max_{y \in D^n} e^{-(\varepsilon/2)d_H(x,y)} p_y(\omega)$
जहाँ $d_H$ हैमिंग दूरी (Hamming distance) है। यह एनवेलप सुनिश्चित करता है कि इनपुट डेटाबेस को एक पंक्ति से बदलने पर लाइकलीहुड (likelihood) अधिकतम $e^{\varepsilon/2}$ के कारक से बदलती है। $Z_x$ द्वारा नॉर्मलाइजेशन के बाद, परिणामी तंत्र प्योर $\varepsilon$ -DP को संतुष्ट करता है।
पब्लिक डिकोडिंग (Public Decoding):
चुना गया ट्रांसक्रिप्ट PMW अपडेट्स के संपूर्ण सिंथेटिक प्रक्षेपवक्र (trajectory) को निर्धारित करता है। तंत्र औसत सिंथेटिक वितरण से प्राप्त क्वेरी उत्तरों को आउटपुट करता है। यह डिकोडिंग चरण नियतात्मक (deterministic) है और कोई अतिरिक्त प्राइवेसी लागत नहीं लेता है।

प्रमुख तकनीकी चुनौतियाँ और समाधान
प्राथमिक कठिनाई यह सुनिश्चित करना है कि एनवेलप संशोधन मूल PMW ट्रांसक्रिप्ट की उपयोगिता (सटीकता) को नष्ट न करे। एनवेलप उन ट्रांसक्रिप्ट्स को प्रायिकता प्रदान करता है जो गलत उत्तरों को डिकोड कर सकते हैं। लेखक इसे एक Maurey-प्रकार के तर्क का उपयोग करके प्रबंधित करते हैं:

लाइकलीहुड-लेवल मौरी (Maurey) तर्क: एक हैमिंग बॉल के त्रिज्या $R$ के भीतर अधिकतम लाइकलीहुड को बांधने के लिए, लेखक एक मौरी-प्रकार के तर्क का उपयोग करते हैं। वे दिखाते हैं कि सभी डेटाबेस के ऊपर अधिकतम लाइकलीहुड को "सरोगेट" (surrogate) लक्ष्य वेक्टर्स के एक छोटे परिवार (रैंडम पंक्ति प्रतिस्थापन के माध्यम से निर्मित) के ऊपर अधिकतम द्वारा ऊपरी सीमा (upper bound) के रूप में बांधा जा सकता है। यह सभी डेटाबेस पर योग करने के कारण होने वाले घातांकीय विस्फोट (exponential blowup) से बचाता है।
दो-रेजीम विश्लेषण (Two-Regime Analysis):
- निकटवर्ती डेटाबेस: कम हैमिंग दूरी के लिए, लेखक रेनी मोमेंट बाउंड्स और होल्डर की असमानता (Hölder's inequality) का उपयोग करके लाइकलीहुड अनुपात को नियंत्रित करते हैं।
- दूरस्थ डेटाबेस: बड़ी दूरियों के लिए, मोमेंट बाउंड्स बहुत महंगे हो जाते हैं। इसके बजाय, अधिकतम लाइकलीहुड को लाइकलीहुड्स के योग (मिक्सचर बाउंड) द्वारा बांधा जाता है, जो इस तथ्य का लाभ उठाता है कि प्रत्येक एक प्रायिकता वितरण है।
ब्लॉक समेशन (Blocked Summation): सभी पूर्णांक हैमिंग त्रिज्याओं पर एक साधारण योग $1/\varepsilon$ के अवांछित कारक को पेश कर सकता है। लेखक त्रिज्याओं को $\Theta(1/\varepsilon)$ चौड़ाई के ब्लॉकों में समूहबद्ध करते हैं। प्रत्येक ब्लॉक के भीतर, लाइकलीहुड की वृद्धि को बाहरी त्रिज्या द्वारा नियंत्रित किया जाता है, जबकि प्राइवेसी पेनल्टी को आंतरिक त्रिज्या द्वारा नियंत्रित किया जाता है। यह तकनीक $1/\varepsilon$ के अतिरिक्त नुकसान को समाप्त करती है, जिससे वर्ग-र melalui दर बनी रहती है।

मुख्य परिणाम
शोध पत्र निम्नलिखित प्रमेय स्थापित करता है:

प्रमेय 1.1: एक सार्वभौमिक स्थिरांक $C > 0$ मौजूद है, जो किसी भी परिमित ब्रह्मांड $D$ ( $|D|=T$ ), परिमित क्वेरी सेट $Q$ ( $|Q|=k$ ), डेटाबेस आकार $n$ , और प्राइवेसी पैरामीटर $\varepsilon > 0$ के लिए, एक प्योर $\varepsilon$ -डिफरेंशियल प्राइवेसी तंत्र $M$ मौजूद है जो निम्नलिखित को संतुष्ट करता है:
$\sup_{x \in D^n} \mathbb{E} \|M(x) - F(x)\|_\infty \leq C \min\left(1, \sqrt{\frac{\log(2T) \log(2k)}{\varepsilon n}}\right)$

यह परिणाम मानक उच्च-आयामी व्यवस्थाओं में ज्ञात निचली सीमाओं (lower bounds) से मेल खाता है, जो अपेक्षित त्रुटि के लिए प्योर डीपी के तहत अनुमानित इष्टतम दर की पुष्टि करता है।

महत्व और दावे

ओपन प्रॉब्लम 1 का समाधान: यह कार्य Nikolov और Ullman [NU21] द्वारा DifferentialPrivacy.org पर रखी गई ओपन प्रॉब्लम 1 को हल करता है, जो सांख्यिकीय क्वेरी रिलीज के लिए एप्रोक्सिमेट और प्योर डीपी दरों के बीच के अंतर को समाप्त करता है।
सूचना-सैद्धांतिक गारंटी: तंत्र सूचना-सैद्धांतिक है, जिसका अर्थ है कि ट्रांसक्रिप्ट स्पेस और एनवेलप में मैक्सिमाइजेशन परिमित है (यद्यपि संभावित रूप से घातांकीय रूप से बड़ा है)। शोध पत्र स्पष्ट रूप से नोट करता है कि इस दर के साथ एक पॉलीनोमियल-टाइम कार्यान्वयन खोजना एक खुला प्रश्न बना हुआ है।
औपचारिक सत्यापन (Formal Verification): निर्माण और प्रमाण को Lean 4 का उपयोग करके मशीन-चेक किया गया है, जो परिमित निर्माण, प्योर प्राइवेसी गुणों और स्पष्ट त्रुटि सीमाओं को सत्यापित करता है।
कार्यक्षेत्र: यह परिणाम सभी पैरामीटर विकल्पों पर समान (uniform) है। "min" और शिफ्टेड लॉगारिदम डिजेनरेट मामलों (जैसे, छोटा $n$ या $k$ ) में भी वैधता सुनिश्चित करते हैं, हालांकि पेपर इन डिजेनरेट व्यवस्थाओं के लिए मिलान करने वाली निचली सीमाओं का दावा नहीं करता है।

शोध पत्र निष्कर्ष निकालता है कि एनवेलप तकनीक सफलतापूर्वक चयन-मात्र PMW की स्थानीय उपयोगिता को डेटासेट्स की संख्या के दंड या $1/\varepsilon$ कारक के बिना, वैश्विक प्योर डीपी नियम में बदल देती है।

"प्राइवेसी एनवेलप" (गोपनीयता लिफाफा) की कहानी

"ब्लॉकिंग" (समूहीकरण) का जादू

परिणाम

इसी तरह के और पेपर