💻 computer science

Exactly Optimal and Communication-Efficient Private Estimation via Block Designs

यह शोधपत्र कॉम्बिनेटोरियल ब्लॉक डिज़ाइन्स और उनके रिलैक्स्ड रेगुलर पेयरवाइज़-बैलेंस्ड वेरिएंट्स पर आधारित लोकल डिफरेंशियल प्राइवेसी स्कीम्स के लिए एक एकीकृत ढांचा प्रस्तुत करता है, जो डिस्क्रीट डिस्ट्रीब्यूशन एस्टीमेशन के लिए न्यूनतम संचार लागत के साथ सटीक रूप से इष्टतम या निकट-इष्टतम प्राइवेसी-यूटिलिटी ट्रेड-ऑफ प्राप्त करते हैं।

मूल लेखक: Hyun-Young Park, Seung-Hyun Nam, Si-Hyeon Lee

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

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

CC BY 4.0

मूल लेखक: Hyun-Young Park, Seung-Hyun Nam, Si-Hyeon Lee

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

कल्पना कीजिए कि आप एक बड़े शहर की जनगणना करने की कोशिश कर रहे हैं ताकि यह समझ सकें कि लोग क्या पसंद करते हैं (जैसे, उनका पसंदीदा आइसक्रीम फ्लेवर)। हालाँकि, आपके पास एक सख्त नियम है: कोई भी अपना असली उत्तर सीधे नहीं बता सकता, क्योंकि इससे उनकी गोपनीयता का उल्लंघन होगा।

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

बड़ा चुनौती इस खेल में है: एक ट्रेड-ऑफ (सौदा):

प्राइवेसी (गोपनीयता): आप जितना अधिक झूठ बोलेंगे (रैंडमाइजेशन करेंगे), व्यक्ति उतना ही सुरक्षित होगा, लेकिन आपका डेटा उतना ही खराब होगा।
यूटिलिटी (उपयोगिता): आप जितना अधिक सच बोलेंगे, आपका डेटा उतना ही बेहतर होगा, लेकिन आपकी प्राइवेसी उतनी ही कम होगी।
कम्युनिकेशन कॉस्ट (संचार लागत): आपका उत्तर कितनी "जगह" लेता है? यदि शहर में 1,000 फ्लेवर हैं, तो "मुझे वैनिला पसंद है" कहना आसान है। लेकिन यदि प्राइवेसी नियम आपको मजबूर करता है कि आप कहें "मुझे वैनिला पसंद है, या शायद चॉकलेट, या शायद मिंट..." एक जटिल कोड में, तो आपको एक बहुत बड़ा संदेश भेजना पड़ सकता है।

वर्तमान समाधानों के साथ समस्या

पेपर नोट करता है कि गणितज्ञों ने पहले ही प्राइवेसी और डेटा गुणवत्ता के बीच संतुलन बनाने का "परफेक्ट" तरीका (जिसे सबसेट सिलेक्शन या SS स्कीम कहा जाता है) खोज लिया है। यह एक परफेक्ट रेसिपी खोजने जैसा है।

हालाँकि, एक पेंच है: यह परफेक्ट रेसिपी भेजने में अविश्वसनीय रूप से महंगी है। यह एक लाइब्रेरी की किताबें भेजने जैसा है सिर्फ यह कहने के लिए कि "मुझे वैनिला पसंद है।" वास्तविक दुनिया में, इतना सारा डेटा भेजना बहुत धीमा और महंगा है।

अन्य मौजूदा तरीके "सस्ते" होने की कोशिश करते हैं (छोटे संदेश भेजना), लेकिन वे केवल "काम चलाऊ" रेसिपी की तरह हैं। वे काम तो करते हैं, लेकिन वे पूरी तरह से कुशल नहीं हैं, और कभी-कभी उनके द्वारा बनाया गया डेटा थोड़ा शोरयुक्त (नॉइज़ी) होता है।

नया समाधान: ब्लॉक्स के साथ निर्माण करना

लेखक इन प्राइवेसी स्कीम्स को बनाने का एक नया तरीका प्रस्तावित करते हैं जिसे कॉम्बिनेटोरियल ब्लॉक डिज़ाइन्स (Combinatorial Block Designs) नामक गणितीय अवधारणा का उपयोग करके बनाया गया है।

एनालॉजी: लेगो सेट (Lego Set)
सोचिए कि अलग-अलग प्राइवेसी स्कीम्स लेगो ब्रिक्स से एक टावर बनाने के विभिन्न तरीकों की तरह हैं।

पुराना तरीका (SS): आपके पास परफेक्ट टावर डिज़ाइन है, लेकिन इसके लिए लाखों छोटे, अद्वितीय ब्रिक्स की आवश्यकता है। आप इसे जल्दी या सस्ते में नहीं बना सकते।
पुराना सस्ता तरीका (HR/PGR): आप कुछ बड़े, मानक ब्रिक्स का उपयोग करते हैं। यह तेज़ और सस्ता है, लेकिन टावर थोड़ा डगमगाता है (कम सटीक है)।
नया तरीका (ब्लॉक डिज़ाइन्स): लेखकों ने महसूस किया कि "परफेक्ट" टावर और "सस्ते" टावर वास्तव में एक ही अंतर्निहित तर्क का उपयोग करके बनाए गए हैं: सिमेट्री (समरूपता)।

उन्होंने पाया कि यदि आप अपने लेगो ब्रिक्स को विशिष्ट, सममित पैटर्न (जिन्हें ब्लॉक डिज़ाइन्स कहा जाता है) में व्यवस्थित करते हैं, तो आप एक ऐसा टावर बना सकते हैं जो है:

पूरी तरह से स्थिर: यह "परफेक्ट" महंगी रेसिपी के समान ही डेटा सटीकता प्राप्त करता है।
हल्का (लाइटवेट): इसमें बहुत कम ब्रिक्स का उपयोग होता है (बहुत कम कम्युनिकेशन कॉस्ट)।

उन्होंने यह कैसे किया

पेपर दो मुख्य उपकरण पेश करता है:

ब्लॉक डिज़ाइन स्कीम्स:
ये एक विशिष्ट, पहले से बने हुए लेगो सेट को खोजने जैसा है जो आपके लोगों की संख्या और प्राइवेसी नियमों के अनुकूल हो। लेखकों ने पाया कि कई मौजूदा "सस्ते" तरीके वास्तव में इन ब्लॉक डिज़ाइन्स के विशेष, सीमित संस्करण थे। इन ब्लॉक डिज़ाइन्स के पूरे परिवार को देखकर, उन्होंने नए, पहले से अज्ञात सेट खोजे जो पूरी तरह से सटीक और भेजने में सस्ते दोनों हैं।
RPBD स्कीम्स ("लचीला" संस्करण):
कभी-कभी, आपके लोगों की विशिष्ट संख्या के लिए (उदाहरण के लिए, आपके पास 101 लोग हैं, लेकिन परफेक्ट सेट केवल 100 या 102 के लिए मौजूद है) परफेक्ट लेगो सेट मौजूद नहीं होता है।
इसे ठीक करने के लिए, लेखकों ने एक "रिलैक्स्ड" (शिथिल) संस्करण बनाया जिसे RPBD (रेगुलर एंड पेयरवाइज-बैलेंस्ड डिज़ाइन्स) कहा जाता है।

एनालॉजी: कल्पना कीजिए कि आपको 101 लोगों के लिए एक वर्गाकार मेज चाहिए, लेकिन आपके पास केवल 100 लोगों वाली मेज है। हार मानने के बजाय, आप 102 लोगों वाली मेज लेते हैं और उसका एक पैर काट देते हैं। यह अब पूरी तरह से वर्गाकार नहीं है, लेकिन यह लगभग वैसा ही काम करता है, और इसे बनाना अभी भी बहुत सस्ता है।
यह उन्हें लगभग किसी भी संख्या के लोगों के लिए लगभग-परफेक्ट समाधान बनाने की अनुमति देता है, जबकि पहले वे उन अंतरालों में फंसे हुए थे जहाँ कोई अच्छा समाधान मौजूद नहीं था।

"हैडामार्ड" रहस्य

पेपर एक प्रसिद्ध अनसुलझे गणितीय पहेली हैडामार्ड कंजेक्चर (Hadamard Conjecture) पर भी चर्चा करता है।

संबंध: लेखक दिखाते हैं कि यदि यह गणितीय पहेली सत्य है (जैसा कि अधिकांश गणितज्ञ मानते हैं), तो लगभग किसी भी समूह के आकार के लिए, एक "परफेक्ट" प्राइवेसी स्कीम मौजूद है जो सबसे सस्ती भी है।
परिणाम: इस पहेली को हल किए बिना भी, उनके नए तरीके पहले से ही ऐसे बहुत सारे परिदृश्यों को कवर करते हैं जहाँ हम सर्वोत्तम का मेल पा सकते हैं: अधिकतम प्राइवेसी, अधिकतम सटीकता और न्यूनतम डेटा लागत।

सारांश

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

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

तकनीकी सारांश: ब्लॉक डिज़ाइन्स के माध्यम से सटीक रूप से इष्टतम और संचार-कुशल निजी अनुमान

समस्या का निरूपण
यह शोध पत्र लोकल डिफरेंशियल प्राइवेसी (LDP) ढांचे के तहत निजी डिस्क्रीट डिस्ट्रीब्यूशन एस्टीमेशन (अनुमान) की समस्या को संबोधित करता है। इस सेटिंग में, $n$ क्लाइंट्स एक अज्ञात वितरण $P$ से प्राप्त डेटा पॉइंट्स $X_i$ को देखते हैं, जो आकार $v$ वाले डोमेन पर आधारित होते हैं। प्रत्येक क्लाइंट एक गोपनीयता तंत्र $Q$ लागू करता है ताकि $\epsilon$ -LDP को संतुष्ट करने वाला एक निजी आउटपुट $Y_i$ उत्पन्न किया जा सके, जिसे बाद में एक केंद्रीय सर्वर को भेजा जाता है। सर्वर फिर $P$ को रिकवर करने के लिए एक एस्टिमेटर $\hat{P}_n$ का निर्माण करता है। उद्देश्य एक विशिष्ट लॉस फंक्शन (मुख्य रूप से $1 \le u \le 2$ के लिए $\ell_u^u$ ) के तहत वर्स्ट-केस रिस्क (अनुमान त्रुटि) को कम करना है, और साथ ही संचार लागत (communication cost) को कम करना है, जिसे आउटपुट अल्फाबेट का आकार $b = |\mathcal{Y}|$ द्वारा परिभाषित किया गया है।

जबकि सबसेट सिलेक्शन (SS) योजना सभी $(v, \epsilon)$ के लिए सटीक रूप से इष्टतम (exactly optimal) गोपनीयता-उपयोगिता ट्रेड-ऑफ प्राप्त करने के लिए जानी जाती है, यह अत्यधिक उच्च संचार लागत (जो $v$ के सापेक्ष घातीय/exponential है) से ग्रस्त है। इसके विपरीत, संचार-कुशल योजनाएं जैसे हैडामार्ड रिस्पॉन्स (HR) और प्रोजेक्टिव ज्योमेट्री रिस्पॉन्स (PGR) अक्सर केवल ऑर्डर-ऑप्टिमल या निकट-इष्टतम प्रदर्शन ही प्राप्त करती हैं, और मध्यम गोपनीयता शासन (medium privacy regimes) में इनके प्रदर्शन का अंतर महत्वपूर्ण हो जाता है। यह शोध पत्र इस अंतर को पाटने के लिए ऐसे समाधान खोजने का प्रयास करता है जो सटीक रूप से इष्टतम (या निकट-इष्टतम) और संचार-कुशल दोनों हों।

कार्यप्रणाली (Methodology)
लेखक कॉम्बिनेटोरियल ब्लॉक डिज़ाइन्स और एक व्यापक वर्ग जिसे रेगुलर एंड पेयरवाइज-बैलेंस्ड डिज़ाइन्स (RPBD) कहा जाता है, पर आधारित एक नया LDP क्लास प्रस्तावित करते हैं।

ब्लॉक डिज़ाइन स्कीम्स:
- तंत्र का निर्माण एक इनसिडेंस स्ट्रक्चर (incidence structure) $(X, Y, I)$ का उपयोग करके किया जाता है जहाँ $X$ इनपुट डोमेन है और $Y$ आउटपुट डोमेन है।
- संरचना को मापदंडों $(v, b, r, k, \lambda)$ द्वारा परिभाषित किया जाता है, जो इनपुट आकार, आउटपुट आकार, रेगुलैरिटी, यूनिफॉर्मिटी और पेयरवाइज बैलेंस को दर्शाते हैं।
- तंत्र $e^\epsilon$ के अनुपात में एक तत्व $y \in I_x$ को आउटपुट करता है और अन्यथा $Y \setminus I_x$ के एक तत्व को आउटपुट करता है।
- विशिष्ट सेटों में गिरने वाले आउटपुट्स की गणना के आधार पर एक कैनोनिकल अनबायस्ड एस्टिमेटर व्युत्पन्न किया जाता है।
- मुख्य अंतर्दृष्टि: लेखक यह स्थापित करते हैं कि एक निश्चित इनपुट आकार $v$ और प्राइवेसी बजट $\epsilon$ के लिए, एक ब्लॉक डिज़ाइन स्कीम का रिस्क केवल पैरामीटर $k$ (इनपुट और आउटपुट सेटों के बीच इंटरसेक्शन का आकार) पर निर्भर करता है, न कि $b, r,$ या $\lambda$ पर। विशेष रूप से, समान $k$ वाले दो ब्लॉक डिज़ाइन स्कीम्स "मार्जिनली इक्विवेलेंट" हैं और डिकम्पोजेबल लॉस फंक्शन्स के लिए समान रिस्क प्रदान करती हैं।
इष्टतमता की शर्तें (Optimality Conditions):
- SS योजना की ज्ञात सटीक इष्टतमता का लाभ उठाते हुए, यह शोध पत्र सिद्ध करता है कि कोई भी ब्लॉक डिज़ाइन स्कीम जिसका पैरामीटर $k \in K^*_{v,\epsilon}$ (रिस्क फंक्शन को न्यूनतम करने वाले पूर्णांकों का सेट) है, वह भी सटीक रूप से इष्टतम है।
- यह शोध पत्र $K^*_{v,\epsilon}$ को सटीक रूप से वर्णित करता है, यह दिखाते हुए कि एक स्कीम तब सटीक रूप से इष्टतम होती है जब $k$ $\epsilon$ और $v$ से संबंधित विशिष्ट सीमाओं को पूरा करता है।
संचार दक्षता (Communication Efficiency):
- फिशर की असमानता (Fisher's inequality) यह निर्धारित करती है कि किसी भी अनबायस्ड या कंसिस्टेंट स्कीम के लिए $b \ge v$ होना चाहिए।
- लेखक सिमेट्रिक ब्लॉक डिज़ाइन्स पर ध्यान केंद्रित करते हैं जहाँ $b = v$ , जो अनबायस्ड स्कीम्स के लिए सैद्धांतिक न्यूनतम संचार लागत प्राप्त करता है।
- जब दिए गए $(v, \epsilon)$ के लिए एक सिमेट्रिक ब्लॉक डिज़ाइन के साथ इष्टतम $k$ मौजूद नहीं होता है, तो यह शोध पत्र गैर-सिमेट्रिक स्कीम्स बनाने के लिए डेरि्व्ड (derived) और रेसिडुअल (residual) ब्लॉक डिज़ाइन्स का उपयोग करता है जो सटीक रूप से इष्टतम या निकट-इष्टतम बने रहते हैं और जिनका $b$ कम होता है।
RPBD स्कीम्स:
- ब्लॉक डिज़ाइन्स की "स्पार्स अस्तित्व" (sparse existence) की समस्या को हल करने के लिए, लेखक यूनिफॉर्मिटी की आवश्यकता को शिथिल करते हुए, रेगुलर एंड पेयरवाइज-बैलेंस्ड डिज़ाइन्स (RPBD) प्रस्तावित करते हैं।
- RPBD स्कीम्स यह अनिवार्यता छोड़ देती हैं कि सभी $y$ के लिए $|I_y| = k$ हो, केवल रेगुलैरिटी ( $r$ ) और पेयरवाइज बैलेंस ( $\lambda$ ) को बनाए रखती हैं।
- लेखक दिखाते हैं कि RPBD स्कीम्स, जिनका अनुपात $[b:r:\lambda]$ इष्टतम SS स्कीम के समान है, निकट-इष्टतम जोखिम प्राप्त करती हैं। इन्हें मौजूदा सिमेट्रिक ब्लॉक डिज़ाइन्स को ट्रंकेट (truncate) करके बनाया जा सकता है।

मुख्य परिणाम

कम लागत के साथ सटीक इष्टतमता: यह शोध पत्र कई नए LDP स्कीम्स की पहचान करता है जो न्यूनतम संचार लागत ( $b=v$ ) के साथ सटीक रूप से इष्टतम प्राइवेसी-उपयोगिता ट्रेड-ऑफ (लोअर बाउंड $M_{v,u,\epsilon}$ के बराबर) प्राप्त करते हैं। यह पहले ज्ञात रेंज की तुलना में अधिक $(v, \epsilon)$ जोड़ों के लिए संभव है।
एकीकरण (Unification): यह ढांचा मौजूदा स्कीम्स (रैंडमाइज्ड रिस्पॉन्स, सबसेट सिलेक्शन, हैडामार्ड रिस्पॉन्स, प्रोजेक्टिव ज्योमेट्री रिस्पॉन्स) को ब्लॉक डिज़ाइन्स के एकल छत्र के तहत एकीकृत करता है।
ट्रंकेशन के माध्यम से निकट-इष्टतमता: उन मामलों के लिए जहाँ सटीक इष्टतम ब्लॉक डिज़ाइन्स मौजूद नहीं हैं, यह शोध पत्र प्रदर्शित करता है कि सिमेट्रिक ब्लॉक डिज़ाइन्स को RPBD स्कीम्स बनाने के लिए ट्रंकेट करने से पिछले स्टेट-ऑफ-द-आर्ट तरीकों (जैसे PGR) की तुलना में काफी कम संचार लागत के साथ निकट-इष्टतम प्रदर्शन प्राप्त होता है।
- उदाहरण: $v=100, \epsilon=1$ के लिए, एक क्वार्टिक रेसिड्यू डिफरेंस सेट पर आधारित ट्रंकेटेड RPBD स्कीम, ट्रंकेटेड PGR स्कीम (~8.41 बिट्स) की तुलना में कम अनुमान त्रुटि प्राप्त करती है और इसमें प्रति क्लाइंट ~6.66 बिट्स की आवश्यकता होती है।
हैडामार्ड कंजेक्चर कनेक्शन: यह शोध पत्र हाई प्राइवेसी रिजीम ( $\epsilon \approx 0$ ) में न्यूनतम संचार लागत के साथ सटीक रूप से इष्टतम स्कीम्स के अस्तित्व को हैडामार्ड कंजेचर से जोड़ता है। यदि यह कंजेचर सत्य है, तो सभी $v$ के लिए $b=v$ (या $b=2v$ ) के साथ सटीक रूप से इष्टतम स्कीम्स मौजूद हैं।

महत्व
यह शोध पत्र दावा करता है कि यह सटीक प्राइवेसी-यूटिलिटी ट्रेड-ऑफ (कॉन्स्टेंट फैक्टर्स सहित) का विश्लेषण करने के महत्व को रेखांकित करता है, और प्रस्तावित ब्लॉक डिज़ाइन दृष्टिकोण सटीक इष्टतमता प्राप्त करने का एक कठोर मार्ग प्रदान करता है बिना संचार दक्षता से समझौता किए। यह कार्य एक नवीन, एकीकृत ढांचा प्रदान करने का दावा करता है जो उन LDP स्कीम्स की खोज करता है जो पारंपरिक ट्रेड-ऑफ (सटीक इष्टतमता बनाम संचार दक्षता) को पार कर सकें। ब्लॉक डिज़ाइन्स के कॉम्बिनेटोरियल गुणों पर ध्यान केंद्रित करके, लेखक प्रदर्शित करते हैं कि:

पहले प्रस्तावित कई स्कीम्स (HR, PGR) वास्तव में विशिष्ट रिजीम्स के लिए सटीक रूप से इष्टतम हैं, एक तथ्य जो पहले स्थापित नहीं था।
नए स्कीम्स को कम संचार लागत के साथ सटीक इष्टतमता प्राप्त करने के लिए व्यवस्थित रूप से जेनरेट किया जा सकता है।
RPBD स्कीम्स में ढील देने से उन परिदृश्यों में निकट-इष्टतम प्रदर्शन प्राप्त करना संभव होता है जहाँ सटीक इष्टतम ब्लॉक डिज़ाइन्स का निर्माण गणितीय रूप से असंभव है।

वर्तमान समाधानों के साथ समस्या

नया समाधान: ब्लॉक्स के साथ निर्माण करना

उन्होंने यह कैसे किया

"हैडामार्ड" रहस्य

सारांश

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