💻 computer science

Missing Mass for Differentially Private Domain Discovery

यह शोध पत्र अज्ञात डेटा पर डोमेन डिस्कवरी के लिए एक निकट-इष्टतम (near-optimal), डिफरेंशियल प्राइवेट समाधान के रूप में वेटेड गॉसियन मैकेनिज्म (WGM) को प्रस्तुत करता है, जो सैद्धांतिक गारंटियों और प्रतिस्पर्धी प्रयोगात्मक परिणामों के माध्यम से प्राइवेट टॉप- $k$ और $k$ -हिटिंग सेट एल्गोरिदम के लिए एक पूर्ववर्ती के रूप में इसकी प्रभावशीलता को प्रदर्शित करता है।

मूल लेखक: Travis Dick, Matthew Joseph, Vinod Raman

प्रकाशित 2026-03-17

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

CC BY 4.0

मूल लेखक: Travis Dick, Matthew Joseph, Vinod Raman

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

कल्पना कीजिए कि आप एक विशाल, अराजक शहर के मेयर हैं जहाँ हर कोई अपनी पसंदीदा चीजों की एक गुप्त सूची रखता है: गाने, फिल्में, किताबें, या यहाँ तक कि अजीब शौक भी। आप एक विशाल पार्टी आयोजित करना चाहते हैं जो पूरे शहर की सबसे लोकप्रिय वस्तुओं का जश्न मनाती हो। लेकिन एक पेच है: आपको सबकी गोपनीयता का सम्मान करना होगा। आप सीधे किसी से यह नहीं पूछ सकते, "आपका नंबर 1 पसंदीदा गाना क्या है?" क्योंकि इससे उनकी पहचान उजागर हो जाएगी।

यह डिफरेंशियल प्राइवेट डोमेन डिस्कवरी (Differentially Private Domain Discovery) की समस्या है। शहर (डेटा) बहुत बड़ा है, और सभी संभावित वस्तुओं की सूची (डोमेन) इतनी बड़ी है कि वह व्यावहारिक रूप से अनंत है। आपको यह पता लगाना है कि लोकप्रिय वस्तुएं कौन सी हैं, बिना किसी की निजी सूची में झाँके।

यह शोध पत्र एक चतुर, तीन-चरणीय रणनीति का प्रस्ताव देता है, जो वेटेड गॉसियन मैकेनिज्म (Weighted Gaussian Mechanism - WGM) नामक एक विधि का उपयोग करती है। यह कैसे काम करता है, इसका विवरण रोजमर्रा के उपमाओं के माध्यम से यहाँ दिया गया है:

1. समस्या: "अनंत पुस्तकालय"

एक पुस्तकालय की कल्पना करें जिसमें अरबों किताबें हैं, लेकिन आप नहीं जानते कि उनमें से कौन सी मौजूद हैं। आपके पास केवल 10,000 लोग हैं, और प्रत्येक व्यक्ति के पास पढ़ी हुई किताबों का एक छोटा सा ढेर है।

लक्ष्य: शहर की शीर्ष 100 सबसे लोकप्रिय किताबें ढूँढना।
गोपनीयता का नियम: आप हर किताब को गिन नहीं सकते क्योंकि यदि आप ऐसी किताब देखते हैं जो केवल एक व्यक्ति के पास है, तो आप ठीक उसी व्यक्ति को पहचान लेंगे। आपको गोपनीयता बनाए रखने के लिए "शोर" (noise/confusion) जोड़ना होगा।
पुराना तरीका: पिछले तरीके ऐसे थे जैसे लोगों से उनकी सूचियों को जोर से चिल्लाकर बताने के लिए कहना ताकि हर किताब को गिना जा सके। यह धीमा था, अव्यवस्थित था, या आपके पास इस बात की गारंटी नहीं थी कि आपने सर्वश्रेष्ठ किताबें ही चुनी हैं।

2. समाधान: "नॉइज़ी फ़िल्टर" (WGM)

लेखक एक सरल, स्केलेबल टूल का सुझाव देते हैं जिसे वेटेड गॉसियन मैकेनिज्म (WGM) कहा जाता है। इसे एक स्मार्ट, थोड़े धुंधले कैमरे के रूप में सोचें।

हर वस्तु को पूरी तरह से देखने के बजाय, कैमरा तीन चीजें करता है:

सैंपलिंग (Sampling): यह सभी की सूचियों का एक त्वरित, यादृच्छिक (random) स्नैपशॉट लेता है, लेकिन यह सीमित करता है कि एक व्यक्ति कितनी वस्तुओं को दिखा सकता है (ताकि कोई एक व्यक्ति फोटो पर हावी न हो जाए)।
धुंधलापन (Blurring/Adding Noise): यह प्रत्येक वस्तु की गिनती में थोड़ा सा "स्टैटिक" या "कोहरा" जोड़ देता है। यदि कोई किताब 100 बार पढ़ी गई थी, तो कैमरा कह सकता है "100, 102, या 98"। यह गोपनीयता की रक्षा करता है।
थ्रेशोल्ड (The Threshold): कैमरा केवल उन्हीं वस्तुओं को रखता है जो कोहरे के बीच से स्पष्ट रूप से दिखाई देती हैं। यदि किसी वस्तु की गिनती बहुत कम है (कोहरे में दब गई है), तो उसे हटा दिया जाता है।

जादू: यह शोध पत्र सिद्ध करता है कि भले ही इस "कोहरे" के साथ काम करना पड़े, यदि डेटा एक प्राकृतिक पैटर्न (जैसे जिप्स लॉ (Zipf's Law)—जहाँ कुछ वस्तुएं बेहद लोकप्रिय हैं और अधिकांश दुर्लभ हैं) का पालन करता है, तो यह धुंधला कैमरा अभी भी शहर के लगभग सभी "द्रव्यमान" (लोकप्रियता) को पकड़ लेता है। यह ऐसा है जैसे यह कहना कि, "भले ही फोटो थोड़ी धुंधली हो, फिर भी हम प्रसिद्ध स्थलों को स्पष्ट रूप से देख सकते हैं।"

3. दो-चरणीय पार्टी योजना

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

अ. "टॉप-के" चयन (शीर्ष 100 को चुनना)

कार्य: शीर्ष $k$ सबसे लोकप्रिय वस्तुओं को चुनें।
रणनीति: पहले, संभावित उम्मीदवारों (डोमेन) की एक प्रबंधनीय सूची खोजने के लिए धुंधले कैमरे का उपयोग करें। फिर, केवल उस संक्षिप्त सूची पर एक मानक, उच्च-परिशुद्धता एल्गोरिदम चलाकर विजेताओं को चुनें।
परिणाम: यह पूरे अनंत पुस्तकालय से विजेताओं को चुनने की तुलना में बहुत बेहतर है। शोध पत्र सिद्ध करता है कि यह विधि गोपनीयता नियमों के साथ भी बहुत उच्च सटीकता के साथ वास्तविक शीर्ष वस्तुओं को खोज लेती है।

ब. "हिटिंग सेट" ("सबको कवर करने वाला" खेल)

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

4. यह क्यों महत्वपूर्ण है ( "अहा!" क्षण)

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

यह शोध पत्र इस प्रक्रिया पर एक स्पीडोमीटर लगाता है। उन्होंने गणितीय रूप से सिद्ध किया कि:

उनका "धुंधला कैमरा" (WGM) वास्तविक दुनिया के रुझानों (जिप्सियन) के लिए इष्टतम (near-optimal) है।
यह बिना डेटा वितरण के नियमों को जाने (distribution-free) भी काम करता है।
वास्तविक दुनिया के परीक्षणों में (Reddit, Amazon और Steam के डेटा का उपयोग करके), उनकी विधि सबसे जटिल मौजूदा विधियों के बराबर या उनसे बेहतर थी, लेकिन यह बहुत तेज़ और सरल थी।

सारांश

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

यहाँ ICLR 2026 में प्रकाशित शोध पत्र "Missing Mass for Differentially Private Domain Discovery" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र डिफरेंशियल प्राइवेट (DP) डोमेन डिस्कवरी की चुनौती को संबोधित करता है। कई आधुनिक डेटा विश्लेषण परिदृश्यों (जैसे, खोज क्वेरी, खरीदारी का इतिहास, समीक्षाएं) में, संभावित वस्तुओं का ब्रह्मांड (डोमेन) अज्ञात या अत्यधिक विशाल होता है। उपयोगकर्ता इस साझा लेकिन अज्ञात डोमेन से वस्तुओं के उपसमुच्चय (subsets) रखते हैं।

मुख्य रूप से संबोधित की जाने वाली समस्याएँ हैं:

सेट यूनियन (की सिलेक्शन): वस्तुओं का एक सूचनात्मक उपसमुच्चय आउटपुट करना जो डेटासेट के "डोमेन" को कवर करता हो।
प्राइवेट टॉप- $k$ : पूरे डोमेन को पहले से जाने बिना $k$ सबसे अधिक बार आने वाली वस्तुओं की पहचान करना।
प्राइवेट $k$ -हिटिंग सेट: $k$ वस्तुओं का एक ऐसा सेट चुनना जो अधिकतम उपयोगकर्ता उपसमुच्चयों के साथ प्रतिच्छेद (intersect) करता हो (डेटा सारांशीकरण के लिए उपयोगी)।

चुनौती: इन समस्याओं के लिए मौजूदा DP एल्गोरिदम अक्सर प्रमाणित उपयोगिता गारंटी (provable utility guarantees) की कमी रखते हैं, विशेष रूप से "अज्ञात डोमेन" सेटिंग में। अधिकांश पूर्व कार्य कार्डिनैलिटी (विशिष्ट वस्तुओं की संख्या) या सापेक्ष त्रुटि (relative error) पर केंद्रित हैं, जो उच्च-आवृत्ति वाले डेटा को कैप्चर करने के संदर्भ में रिकवर किए गए डोमेन की गुणवत्ता को सटीक रूप से नहीं दर्शा सकते हैं।

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

लेखक एक एकीकृत ढांचे का प्रस्ताव करते हैं जो वेटेड गॉसियन मैकेनिज्म (WGM) और एक नए उपयोगिता मीट्रिक: मिसिंग मास (Missing Mass) पर केंद्रित है।

अ. मीट्रिक: मिसिंग मास (Missing Mass)

उपयोगिता को रिकवर की गई विशिष्ट वस्तुओं की संख्या (कार्डिनैलिटी) के बजाय, यह पेपर मिसिंग मास ($MM$) के माध्यम से उपयोगिता को परिभाषित करता है।

परिभाषा: $MM(W, S) = \sum_{x \in \text{Universe} \setminus S} \frac{N(x)}{N}$ , जहाँ $N(x)$ वस्तु $x$ की आवृत्ति है और $N$ कुल वस्तुओं की संख्या है।
महत्व: मिसिंग मास को कम करने से यह सुनिश्चित होता है कि आउटपुट सेट $S$ डेटा के अधिकांश प्रोबेबिलिटी मास (आवृत्ति) को कैप्चर करता है, न कि केवल बड़ी संख्या में दुर्लभ वस्तुओं को। यह पेपर इसे $\ell_p$ नॉर्म्स के लिए भी सामान्यीकृत करता है, विशेष रूप से $\ell_1$ (मानक मिसिंग मास) और $\ell_\infty$ (अधिकतम मिसिंग फ्रीक्वेंसी) पर ध्यान केंद्रित करता है।

ब. मुख्य मैकेनिज्म: वेटेड गॉसियन मैकेनिज्म (WGM)

लेखक डोमेन डिस्कवरी के अग्रदूत के रूप में WGM (Gopi et al., 2020) का उपयोग करते हैं।

सबसैंपलिंग (Subsampling): संवेदनशीलता (sensitivity) को नियंत्रित करने के लिए प्रत्येक उपयोगकर्ता के आइटम सेट को एक सीमा $\Delta_0$ तक सबसैंपल किया जाता है।
वेटेड हिस्टोग्राम (Weighted Histogram): एक वेटेड हिस्टोग्राम बनाया जाता है जहाँ एक उपयोगकर्ता जिसके पास $k$ आइटम हैं, वह प्रत्येक आइटम के काउंट में $1/\sqrt{k}$ का योगदान देता है। यह यूनिट $\ell_2$ नॉर्म तक योगदान को स्केल करता है।
नॉइज़ जोड़ना (Noise Addition): वेटेड काउंट्स में मीन-जीरो गॉसियन नॉइज़ जोड़ा जाता है।
थ्रेशोल्डिंग (Thresholding): वे आइटम जिनका नॉइज़ी काउंट थ्रेशोल्ड $T$ से ऊपर है, उन्हें रिलीज़ किया जाता है।

स. दो-चरणीय ढांचा (Two-Stage Framework)

Top- $k$ और $k$ -हिटिंग सेट समस्याओं के लिए, लेखक एक मेटा-एल्गोरिदम प्रस्तावित करते हैं:

चरण 1 (डोमेन डिस्कवरी): आधे प्राइवेसी बजट के साथ डोमेन $D$ उत्पन्न करने के लिए WGM चलाएं।
चरण 2 (ज्ञात-डोमेन एल्गोरिदम): शेष प्राइवेसी बजट का उपयोग करके प्रतिबंधित डोमेन $D$ पर एक मानक DP एल्गोरिदम (जैसे, Top- $k$ के लिए पीलिंग एक्सपोनेंशियल मैकेनिज्म, या $k$ -हिटिंग सेट के लिए एक प्राइवेटेड ग्रीडी एल्गोरिदम) चलाएं।

3. प्रमुख योगदान (Key Contributions)

सैद्धांतिक गारंटी (Theoretical Guarantees)

जिप्सियन (Zipfian) डेटा पर निकट-इष्टतम $\ell_1$ मिसिंग मास:
- लेखकों ने सिद्ध किया है कि जिप्सियन वितरण (आवृत्तियों का पावर-लॉ डिके) वाले डेटासेट्स के लिए, WGM एक निकट-इष्टतम $\ell_1$ मिसिंग मास बाउंड प्राप्त करता है।
- यह बाउंड जिप्सियन मापदंडों ( $C, s$ ) के साथ स्केल करती है और जैसे-जैसे डेटासेट का आकार $N$ बढ़ता है, वैसे-वैसे घटती जाती है।
- लोअर बाउंड (Lower Bound): उन्होंने एक मिलान लोअर बाउंड भी सिद्ध किया है, जो दर्शाता है कि कोई भी DP एल्गोरिदम जो "साउंडनेस" (soundness) गुण को संतुष्ट करता है (आउटपुट इनपुट आइटम्स का एक उपसमुच्चय होना चाहिए) जिप्सियन डेटा पर काफी बेहतर मिसिंग मास प्राप्त नहीं कर सकता है।
डिस्ट्रीब्यूशन-फ्री $\ell_\infty$ मिसिंग मास:
- महत्वपूर्ण रूप से, लेखक $\ell_\infty$ नॉर्म (अधिकतम मिसिंग फ्रीक्वेंसी को कम करना) के लिए एक डिस्ट्रीब्यूशन-फ्री गारंटी सिद्ध करते हैं।
- यह परिणाम डेटा के जिप्सियन होने की आवश्यकता नहीं रखता है, जिससे यह किसी भी मनमाने डेटासेट के लिए लागू होता है।
अज्ञात डोमेन वेरिएंट के लिए उपयोगिता गारंटी:
- Top- $k$ : पीलिंग एक्सपोनेंशियल मैकेनिज्म के साथ $\ell_\infty$ WGM बाउंड को जोड़कर, वे अज्ञात डोमेन में Top- $k$ चयन के लिए उपयोगिता गारंटी प्राप्त करते हैं। त्रुटि $k$ , $\epsilon$ , और अधिकतम उपयोगकर्ता योगदान पर निर्भर करती है।
- $k$ -हिटिंग सेट: वे "यूज़र पीलिंग मैकेनिज्म" (एक प्राइवेटेड ग्रीडी दृष्टिकोण) को डिस्कवर्ड डोमेन पर काम करने के लिए अनुकूलित करते हैं। वे WGM के $\ell_\infty$ मिसिंग मास पर निर्भर एक एडिटिव एरर टर्म के साथ $(1 - 1/e)$ का एप्रोक्सिमेशन गारंटी सिद्ध करते हैं।

अनुभवजन्य परिणाम (Empirical Results)

लेखकों ने छह वास्तविक दुनिया के डेटासेट्स (Reddit, Amazon Games/Magazine/Pantry, Movie Reviews, Steam Games) पर अपने तरीकों का मूल्यांकन किया।

सेट यूनियन: WGM-आधारित दृष्टिकोण जटिल, अत्याधुनिक अनुक्रमिक "पॉलिसी" मैकेनिज्म के 5% के भीतर मिसिंग मास प्राप्त करता है, लेकिन काफी बेहतर स्केलेबिलिटी के साथ।
Top- $k$ : प्रस्तावित विधि सभी $k$ मानों के लिए "लिमिटेड-डोमेन" बेसलाइन (Durfee & Rogers, 2019) से लगातार बेहतर प्रदर्शन करती है, और प्रदर्शन का अंतर $k$ बढ़ने के साथ बढ़ता जाता है।
$k$ -हिटिंग सेट: विधि नॉन-प्राइवेट बेसलाइन्स के तुलनीय प्रदर्शन करती है और उस प्राइवेट बेसलाइन से बेहतर प्रदर्शन करती है जो डोमेन के सार्वजनिक ज्ञान को मानती है। यह प्रदर्शित करता है कि WGM के माध्यम से एक छोटा, उच्च-गुणवत्ता वाला डोमेन खोजना वास्तव में बाद के ऑप्टिमाइज़ेशन समस्या को सरल बनाता है।

4. महत्व और प्रभाव (Significance and Impact)

प्रथम पूर्ण उपयोगिता गारंटी: यह अज्ञात-डोमेन समस्याओं के लिए DP सेट यूनियन और संबंधित समस्याओं के लिए (अन्य एल्गोरिदम के सापेक्ष नहीं बल्कि) पूर्ण (absolute) उपयोगिता गारंटी प्रदान करने वाला पहला कार्य है।
उपयोगिता मीट्रिक में बदलाव: कार्डिनैलिटी से मिसिंग मास की ओर बढ़ते हुए, यह पेपर सैद्धांतिक गारंटियों को व्यावहारिक उपयोगिता के साथ संरेखित करता है। कई अनुप्रयोगों (जैसे, अनुशंसा प्रणाली) में, शीर्ष 1% बार आने वाली वस्तुओं को कैप्चर करना 1 मिलियन दुर्लभ वस्तुओं को कैप्चर करने की तुलना में बहुत अधिक मूल्यवान है।
व्यावहारिक स्केलेबिलिटी: प्रस्तावित तरीके सरल, गैर-पुनरावृत्ति (non-iterative) मैकेनिज्म (WGM + मानक ज्ञात-डोमेन एल्गोरिदम) पर निर्भर करते हैं, जो उन्हें बड़े डेटासेट्स पर अत्यधिक स्केलेबल बनाता है।
मजबूती (Robustness): डिस्ट्रीब्यूशन-फ्री $\ell_\infty$ गारंटी यह सुनिश्चित करती है कि उनके तरीके तब भी अच्छी तरह काम करते हैं जब डेटा सख्ती से पावर-लॉ वितरण का पालन नहीं करता है, जो पिछले साहित्य में एक सामान्य धारणा है।

संक्षेप में, यह शोध पत्र अनिश्चित डोमेन में उच्च-आवृत्ति वाले डेटा को रिकवर करने के लिए एक सरल, स्केलेबल मैकेनिज्म (WGM) पर्याप्त है, जो प्रभावी Top- $k$ और $k$ -हिटिंग सेट समाधानों को सक्षम करता है, इसके लिए एक कठोर सैद्धांतिक आधार स्थापित करता है।