तकनीकी सारांश: ई-वैल्यूज़ के साथ विभेदक रूप से निजी परिकल्पना परीक्षण के लिए इष्टतम दरें

समस्या विवरण

यह कार्य सेंट्रल डिफरेंशियल प्राइवेसी (DP) की बाधाओं के तहत सरल परिकल्पना परीक्षण (simple hypothesis testing) की मौलिक समस्या को संबोधित करता है। विशेष रूप से, लेखक ई-वैल्यूज़ (e-values) का उपयोग करके $X \sim P^n$ (शून्य परिकल्पना/null hypothesis) के विरुद्ध $X \sim Q^n$ (वैकल्पिक परिकल्पना/alternative hypothesis) का परीक्षण करने की जांच करते हैं।

शास्त्रीय सेटिंग में, एक परीक्षण के प्रदर्शन को उसकी शक्ति (power/true positive rate) द्वारा मापा जाता है। ई-वैल्यू फ्रेमवर्क में, प्रदर्शन को ई-पावर (e-power) द्वारा मापा जाता है, जिसे $\mathbb{E}_Q[\log E]$ के रूप में परिभाषित किया गया है, जहाँ $E$ एक गैर-ऋणात्मक यादृच्छिक चर (non-negative random variable) है जो $\mathbb{E}_P[E] \le 1$ की शर्त को पूरा करता है। मुख्य प्रश्न यह है: $P$ के विरुद्ध $Q$ के परीक्षण के लिए एक $\varepsilon$-DP ई-वैल्यू के लिए अधिकतम प्राप्त करने योग्य ई-पावर क्या है?

लेखक दो सेटिंग्स पर विचार करते हैं:

1. बैच सेटिंग (Batch Setting): सभी $n$ डेटा बिंदु एक साथ उपलब्ध हैं।
2. अनुक्रमिक सेटिंग (Sequential Setting): डेटा एक-एक करके आता है, और विश्लेषक एक स्टॉपिंग टाइम (stopping time) $N$ को अनुकूल रूप से चुनता है। लक्ष्य सांख्यिकीय साक्ष्य के एक विशिष्ट स्तर को प्राप्त करने के लिए आवश्यक अपेक्षित स्टॉपिंग टाइम $\mathbb{E}_Q[N]$ को कम करना है।

जबकि निर्णय-सैद्धांतिक सेटिंग (बाइनरी आउटपुट) में विभेदक रूप से निजी परिकल्पना परीक्षण और स्थानीय DP (local DP) के तहत ई-वैल्यूज़ पर पूर्व कार्य मौजूद हैं, यह शोध पत्र सेंट्रल DP ई-वैल्यूज़ पर ध्यान केंद्रित करता है, एक ऐसी सेटिंग जहाँ बहुत सीमित पूर्व कार्य (विशेष रूप से बाउंडेड लाइकलिहुड रेश्यो वाले Csillag और Mesquita [10]) उपलब्ध हैं।

कार्यप्रणाली

1. इष्टतम ई-पावर का अभिलक्षण (Batch Setting)

लेखक ई-चर (e-variable) के निर्माण से गोपनीयता तंत्र (privacy mechanism) को अलग करते हैं। वे देखते हैं कि एक ई-चर बनाने के लिए किसी भी निश्चित $\varepsilon$-DP तंत्र $M$ के लिए, इष्टतम पोस्ट-प्रोसेसिंग आउटपुट वितरणों का लाइकलिहुड रेश्यो (likelihood ratio), $dM(Q^n)/dM(P^n)$, है। इस प्रकार, समस्या तंत्र के आउटपुट वितरणों के बीच कुलबैक-लीब्लर (KL) डाइवर्जेंस को अधिकतम करने में बदल जाती है:
$$R_{\varepsilon}(Q \| P) = \lim_{n \to \infty} \sup_{M \in \varepsilon\text{-DP}} \frac{1}{n} KL(M(Q^n) \| M(P^n))$$

इसे हल करने के लिए, लेखक एक मध्यवर्ती वितरण (intermediate distribution) $\tilde{Q}$ पेश करते हैं। वे $\tilde{Q}$ का निर्माण लाइकलिहुड रेश्यो $q(x)/p(x)$ द्वारा परिभाषित विशिष्ट क्षेत्रों में $Q$ के घनत्व (density) को संशोधित करके करते हैं:

• क्षेत्र A (निम्न लाइकलिहुड रेश्यो): $q(x) < c_1 p(x)$। यहाँ, $\tilde{q}(x) = c_1 p(x)$।
• क्षेत्र B (उच्च लाइकलिहुड रेश्यो): $q(x) > c_2 p(x)$। यहाँ, $\tilde{q}(x) = c_2 p(x)$।
• क्षेत्र M (मध्यवर्ती): $\tilde{q}(x) = q(x)$।

स्थिरांक $c_1, c_2$ और क्षेत्र एक लैग्रेंज मल्टीप्लायर $\lambda^*$ द्वारा निर्धारित होते हैं जो यह सुनिश्चित करने के लिए एक निहित समीकरण को हल करता है कि $\tilde{Q}$ एक वैध संभाव्यता वितरण है। यह निर्माण $KL(Q' \| P) + \varepsilon \cdot TV(Q', Q)$ को न्यूनतम करता है।

लेखक सिद्ध करते हैं कि इष्टतम दर ठीक यही है:
$$R_{\varepsilon}(Q \| P) = KL(\tilde{Q} \| P) + \varepsilon \cdot TV(\tilde{Q}, Q)$$

इसके बाद, वे एक गैर-निजी ई-चर $E^*$ का निर्माण करते हैं जो इस $\tilde{Q}$ (विशेष रूप से, एक क्लिप्ड लाइकलिहुड रेश्यो) पर आधारित है, जिसका बाउंडेड लॉग-सेंसिटिविटी $\varepsilon$ है। इसे निजी बनाने के लिए, वे वोल्क और वांग के कार्य पर आधारित एक मर्जिंग फंक्शन $\Lambda_n$ प्रस्तावित करते हैं, जो ई-चर के गुण को बनाए रखते हुए और स्पर्शोन्मुख इष्टतमता (asymptotic optimality) को संरक्षित करते हुए, सावधानीपूर्वक कैलिब्रेटेड कंपेनसेटर के साथ लैपलेसियन शोर (Laplacian noise) जोड़ता है।

2. अनुक्रमिक सेटिंग और स्टॉपिंग टाइम्स

अनुक्रमिक सेटिंग में, लेखक एक $\varepsilon$-DP ई-प्रोसेस को एक $\varepsilon$-DP तंत्र द्वारा उत्पन्न ई-वैल्यूज़ के एक अनुक्रम के रूप में परिभाषित करते हैं। वे किसी भी ऐसे प्रोसेस के लिए अपेक्षित स्टॉपिंग टाइम पर एक निचली सीमा (lower bound) स्थापित करते हैं।

वास्तविक वितरण $Q$ और मध्यवर्ती वितरण $\tilde{Q}$ के बीच कपलिंग (coupling) को शामिल करते हुए एक पोटेंशियल फंक्शन तर्क का उपयोग करते हुए, वे सिद्ध करते हैं कि किसी भी स्टॉपिंग टाइम $N$ के लिए:
$$\mathbb{E}_Q[\log E_N] \le \mathbb{E}_Q[N] \cdot R_{\varepsilon}(Q \| P)$$
यह विशिष्ट स्तर की सांख्यिकीय साक्ष्य प्राप्त करने के लिए आवश्यक सैंपल कॉम्प्लेक्सिटी पर एक निचली सीमा लागू करता है।

इस सीमा से मेल खाने के लिए, वे एल्गोरिदम 1, एक "Batch to E-process Conversion" प्रस्तावित करते हैं। यह एल्गोरिदम:

• एक गैर-निजी ई-चर लेता है जिसकी बाउंडेड लॉग-सेंसिटिविटी हो।
• डेटा को बढ़ते आकार के बैचों में प्रोसेस करता है।
• प्रत्येक बैच के अंत में एक निजीकृत मर्जिंग फंक्शन (बैच केस के समान) लागू करता है।
• एक विशिष्ट रिकरेंस रिलेशन (recurrence relation) का उपयोग करता है ताकि बैच के आकार को निर्धारित किया जा सके, जिससे शुरुआती "स्टार्टअप" समय और दीर्घकालिक प्रतिस्पर्धी अनुपात (competitive ratio) के बीच संतुलन बनाया जा सके।

मुख्य योगदान और परिणाम

1. इंस्टेंस-विशिष्ट हार्डनेस परिणाम (Theorem 2.2): यह शोध पत्र $\varepsilon$-DP के तहत अधिकतम प्राप्त करने योग्य ई-पावर के लिए एक स्पष्ट, गणना योग्य सूत्र प्रदान करता है। इस दर को एक मध्यवर्ती वितरण $\tilde{Q}$ के KL डाइवर्जेंस और टोटल वेरिएशन पेनल्टी द्वारा अभिलक्षित किया गया है।
2. इष्टतम एल्गोरिदम निर्माण (Theorem 2.4): लेखक एक $\varepsilon$-DP ई-चर का निर्माण करते हैं जो इस इष्टतम दर को स्पर्शोन्मुख रूप से प्राप्त करता है। निर्माण में बाउंडेड लॉग-सेंसिटिविटी वाला एक विशिष्ट क्लिपिंग और फिर लैपलेसियन शोर और कंपेनसेटर टर्म का उपयोग करके एक निजीकरण योजना शामिल है।
3. अनुक्रमिक निचली सीमा (Theorem 3.1): वे किसी भी $\varepsilon$-DP ई-प्रोसेस के अपेक्षित स्टॉपिंग टाइम पर एक सार्वभौमिक निचली सीमा प्राप्त करते हैं, जो यह दर्शाता है कि यह इष्टतम ई-पावर दर $R_{\varepsilon}(Q \| P)$ के व्युत्क्रमानुपाती है।
4. इष्टतम अनुक्रमिक एल्गोरिदम (Theorem 3.2): वे एल्गोरिदम 1 प्रस्तुत करते हैं, जो एक गैर-निजी ई-चर को $\varepsilon$-DP ई-प्रोसेस में परिवर्तित करता है। यह एल्गोरिदम सभी पर्याप्त बड़े स्टॉपिंग टाइम्स के लिए एक स्थिरांक गुणात्मक कारक (competitive ratio) तक सैद्धांतिक निचली सीमा से मेल खाता है।
5. वितरण-स्वतंत्र विकल्प (Appendix C): यह पहचानते हुए कि जटिल वितरणों के लिए इष्टतम $\tilde{Q}$ की गणना करना कठिन हो सकता है, वे एक "ट्रंकेटेड एंड स्केल्ड लाइकलिहुड रेश्यो" (tsLR) सांख्यिकी प्रस्तावित करते हैं। यह वितरण-स्वतंत्र सांख्यिकी इष्टतम दर के भीतर एक स्थिरांक कारक के भीतर दर प्राप्त करती है।

प्रयोगात्मक सत्यापन

लेखकों ने अपने एल्गोरिदम 1 की DP-SPRT (Michel et al. [25] द्वारा प्रस्तावित डिफरेंशियल प्राइवेसी अनुक्रमिक प्रोबेबिलिटी रेश्यो टेस्ट) के विरुद्ध संख्यात्मक प्रयोग किए।

• सेटअप: $P = \text{Bernoulli}(0.3)$ के विरुद्ध $Q = \text{Bernoulli}(q)$ का परीक्षण।
• मेट्रिक: स्टॉपिंग टाइम्स के अनुभवजन्य संचयी वितरण फलन (CDFs)।
• परिणाम: विभिन्न गोपनीयता स्तरों ($\varepsilon$) और वैकल्पिक वितरणों ($q$) में, प्रस्तावित निजी ई-प्रोसेस ने DP-SPRT की तुलना में लगातार पहले स्टॉप किया। उल्लेखनीय रूप से, यह प्रदर्शन लाभ तब भी प्राप्त किया गया जब प्रस्तावित एल्गोरिदम डेटा के बारे में कोई पैरामीट्रिक धारणा नहीं बनाता है, जबकि DP-SPRT विशेष रूप से एक्सपोनेंशियल फैमिली के लिए डिज़ाइन किया गया है।

महत्व और दावे

यह शोध पत्र दावा करता है कि यह सेंट्रल डिफरेंशियल प्राइवेसी के तहत ई-वैल्यूज़ का उपयोग करके सरल परिकल्पना परीक्षण की मौलिक सीमाओं की पूर्ण समझ प्रदान करता है।

• सैद्धांतिक आधार: $R_{\varepsilon}(Q \| P)$ की इष्टतम दर को अभिलक्षित करके और एक एल्गोरिदम प्रदान करके जो इसके अनुरूप है, यह कार्य गोपनीयता-संरक्षित अनुक्रमिक विश्लेषण में जो कुछ भी प्राप्त किया जा सकता है, उसका एक आधार रेखा स्थापित करता है।
• व्यावहारिक उपयोगिता: प्रस्तावित एल्गोरिदम मौजूदा अत्याधुनिक तरीकों (DP-SPRT) की तुलना में कम डेटा (कम स्टॉपिंग टाइम्स) की आवश्यकता रखते हैं।
• भविष्य की दिशाएं: लेखक सुझाव देते हैं कि उनके हार्डनेस परिणाम और तकनीकें (विशेष रूप से लीस्ट-फेवरेबल पेयर्स का उपयोग) कंपोजिट हाइपोथीसिस टेस्टिंग और इंस्टेंस-ऑप्टिमल DP एस्टीमेशन तक विस्तार करने के लिए एक आधार के रूप में कार्य कर सकते हैं। वे यह भी नोट करते हैं कि इन परिणामों को अनुमानित DP ($\delta > 0$) तक विस्तारित करना एक खुला प्रश्न बना हुआ है।