तकनीकी सारांश: निकट-इष्टतम सामान्यीकृत निजी परीक्षण (Near-Optimal Generalized Private Testing)

1. समस्या की परिभाषा

यह शोध पत्र सामान्यीकृत निजी परीक्षण (Generalized Private Testing) समस्या को संबोधित करता है, जो डिफरेंशियल प्राइवेसी (DP) में एक मौलिक चुनौती है जिसे Liu और Talwar (STOC 2019) द्वारा पेश किया गया था। मानक निजी थ्रेशोल्ड टेस्टिंग के विपरीत, जो सीमित लिप्सचिट्ज़ संवेदनशीलता (Lipschitz sensitivity) वाले वास्तविक-मान वाले इनपुट पर कार्य करती है, सामान्यीकृत निजी परीक्षण ब्लैक-बॉक्स $\varepsilon_t$-DP तंत्रों $(M_t)_{t \ge 1}$ की एक श्रृंखला पर कार्य करता है।

औपचारिक सेटअप:

• इनपुट: एक निजी डेटासेट $X$ (या डेटासेट्स की एक स्ट्रीम $X_t$), एक लक्षित सफलता प्रायिकता $p^* \in (0, 1)$, और तंत्रों की एक श्रृंखला $M_t: \mathcal{X} \to \{-1, +1\}$, जहाँ प्रत्येक $M_t$, $(\varepsilon_t, \delta_t)$-DP का पालन करता है।
• लक्ष्य: पहले ऐसे इंडेक्स $t$ की पहचान करना जहाँ सफलता प्रायिकता $p_t = \Pr[M_t(X) = +1]$, थ्रेशोल्ड $p^*$ से अधिक हो जाती है।
• प्रतिबंध: परीक्षण प्रक्रिया स्वयं एक वैश्विक $\varepsilon$-DP गारंटी का पालन करनी चाहिए।
• सटीकता (Accuracy): इसे एक रिजेक्शन थ्रेशोल्ड $\bar{p} < p^*$ द्वारा परिभाषित किया गया है। उच्च प्रायिकता के साथ, यदि $p_t \le \bar{p}$ है, तो तंत्र जारी रहता है; यदि $p_t \ge p^*$ है, तो यह रुक जाता है। लक्ष्य $p^* - \bar{p}$ के अंतर को न्यूनतम करना है।

मौजूदा समाधान महत्वपूर्ण ट्रेड-ऑफ का सामना करते हैं:

1. Liu और Talwar [LT19]: एक रिजेक्शन थ्रेशोल्ड प्राप्त करते हैं जो $\bar{p} \approx p^* (\beta^2/T)^{12\varepsilon_1/\varepsilon}$ के रूप में स्केल करता है, लेकिन उन्हें शुद्ध DP इनपुट की आवश्यकता होती है और वे केवल अनुमानित (approximate) DP आउटपुट प्राप्त करते हैं। उनकी सैंपल कॉम्प्लेक्सिटी स्ट्रीम की लंबाई $T$ के साथ खराब तरीके से स्केल करती है।
2. Cohen et al. [CLN+23] और Ghazi et al. [GKK+25]: शुद्ध DP इनपुट के लिए शुद्ध DP आउटपुट प्रदान करते हैं, लेकिन उनका रिजेक्शन थ्रेशोल्ड $\bar{p} \approx p^* \beta/T$ के रूप में स्केल करता है, जो [LT19] की तुलना में बड़े $T$ के लिए स्पर्शोन्मुख रूप से (asymptotically) बदतर है।

2. कार्यप्रणाली: जनरलाइज्ड थ्रेशोल्डिंग मैकेनिज्म (GTM)

लेखक एक नया एल्गोरिदम, जनरलाइज्ड थ्रेशोल्डिंग मैकेनिज्म (GTM) पेश करते हैं, जो शुद्ध या अनुमानित DP दोनों प्रकार के इनपुट के लिए शुद्ध DP गारंटी प्रदान करते हुए निकट-इष्टतम सटीकता और सैंपल कॉम्प्लेक्सिटी प्राप्त करता है।

मुख्य तकनीकी अंतर्दृष्टि

GTM तीन प्राथमिक तकनीकी नवाचारों पर निर्भर करता है:

1. पॉइसनयुक्त सैंपलिंग और रैंडमाइज्ड रेट्स (Poissonized Sampling and Randomized Rates):
   निश्चित संख्या में मूल्यांकनों के बजाय, एल्गोरिदम मूल्यांकनों की संख्या $N_t$ को पॉइसन वितरण $N_t \sim \text{Po}(\lambda_t)$ से खींचता है। दर पैरामीटर $\lambda_t$ को वास्तविक सफलता प्रायिकता $p_t$ को अस्पष्ट करने के लिए रैंडमाइज किया जाता है। विशेष रूप से, $\lambda_t = \rho_t \exp(\varepsilon_t Z_t)$, जहाँ $Z_t$ एक्सपोनेंशियल वितरणों से प्राप्त एक नॉइज़ वेरिएबल है। यह संरचना स्पार्स वेक्टर तकनीक (SVT) के समान एक कपलिंग तर्क के उपयोग की अनुमति देती है, लेकिन इसे संभावabilistic तंत्रों के लिए अनुकूलित किया गया है।

2. डायरेक्शनल एडेप्टिविटी (दिशात्मक अनुकूलनशीलता - Flipped Variant):
   तंत्र एक दिशा पैरामीटर $s_t \in \{+1, -1\}$ के आधार पर दो मोड में कार्य करता है:

• डायरेक्ट ($s_t = +1$): यदि $+1$ परिणामों की गणना $K_t$ एक थ्रेशोल्ड से अधिक हो जाती है, तो यह रुक जाता है। यह तब इष्टतम होता है जब $p^*$ छोटा हो।
• फ्लिप्ड ($s_t = -1$): यदि $K_t$, एक थ्रेशोल्ड से कम हो जाता है (प्रभावी रूप से $1-p_t$ को $1-p^*$ के विरुद्ध टेस्ट करना), तो यह रुक जाता है। यह तब इष्टतम होता है जब $p^*$ 1 के करीब हो।
  एल्गोरिदम रिजेक्शन थ्रेशोल्ड गैप को कम करने के लिए दिशा को अनुकूल रूप से चुनता है, जिससे $\bar{p}_t = \max\left(\frac{p^*_t}{\gamma \Lambda_t}, 1 - \gamma \Lambda_t (1 - p^*_t)\right)$ प्राप्त होता है।

3. रैंडमाइज्ड रिस्पांस के माध्यम से शुद्धिकरण (Purification via Randomized Response):
   अनुमानित DP इनपुट $(\varepsilon_t, \delta_t)$ को संभालने के लिए, GTM एक "प्यूरिफिकेशन" स्टेप लागू करता है। प्रत्येक $M_t$ के मूल्यांकन को एक बाइनरी सिमेट्रिक चैनल के माध्यम से गुजारा जाता है जिसका क्रॉसओवर प्रोबेबिलिटी $\phi_t \approx \delta_t/\varepsilon_t$ है। यह एक अनुमानित DP तंत्र को शुद्ध $\varepsilon_t$-DP तंत्र में परिवर्तित करता है, जिसमें सफलता प्रायिकता में नगण्य व्यवधान होता है, जिससे GTM आउटपुट के लिए शुद्ध $\varepsilon$-DP गारंटी बनाए रखने में सक्षम होता है।

पैरामीटर ट्यूनिंग

तंत्र एक "नॉइज़ पेनल्टी" फैक्टर $\Lambda_t$ पेश करता है जो सटीकता हानि को नियंत्रित करता है। लेखक दिखाते हैं कि $\theta$ और $\gamma$ को ट्यून करके, $\Lambda_t$ को इस प्रकार बनाया जा सकता है:
$$\Lambda_t = \left( \frac{t}{\beta} \right)^{(2+\theta)\varepsilon_t/\varepsilon} \cdot \left( \frac{1}{\beta} \right)^{(3+\theta+2/\theta)\varepsilon_t/\varepsilon}$$
महत्वपूर्ण रूप से, $t$ और $\beta$ के घातांकों (exponents) को सैद्धांतिक निचली सीमाओं के अत्यंत निकट लाया जा सकता है।

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

सैद्धांतिक ऊपरी सीमाएँ (Theoretical Upper Bounds)

यह शोध पत्र स्थापित करता है कि किसी भी $\theta > 0$ और $\gamma \in (1, 2]$ के लिए, GTM प्राप्त करता है:

• प्राइवेसी: शुद्ध $\varepsilon$-DP, भले ही इनपुट तंत्र केवल $(\varepsilon_t, \delta_t)$-DP हों।
• सटीकता: एक रिजेक्शन थ्रेशोल्ड $\bar{p}_t$ जिससे $p^*/\bar{p}_t$ का अनुपात $\tilde{O}((t/\beta)^{(2+\theta)\varepsilon_t/\varepsilon})$ के रूप में स्केल करता है। यह [LT19] में $12\varepsilon_1/\varepsilon$ के घातांक और [CLN+23] में लीनियर $\beta/T$ स्केलिंग में सुधार करता है।
• सैंपल कॉम्प्लेक्सिटी: चरण $t$ पर मूल्यांकनों की संख्या $N_t$ उच्च प्रायिकता के साथ सीमित है:
  $$N_t = O\left( \frac{\ln(t/\beta)}{(\gamma-1)^2} \cdot \max\left( \frac{\Lambda_t}{p^*_t}, \frac{1}{1-p^*_t} \right) \right)$$
  विशिष्ट पैरामीटर सेटिंग्स के तहत अमोर्टाइज्ड (amortized) सैंपल कॉम्प्लेक्सिटी $t$ के साथ लॉगरिदमिक रूप से स्केल करती है।

निचली सीमाएँ (Lower Bounds)

लेखक किसी भी सामान्यीकृत निजी टेस्टर के लिए मिलान करने वाली निचली सीमाएँ सिद्ध करते हैं। वे दिखाते हैं कि सटीकता हानि कारक $\Lambda_T$ अनिवार्य रूप से $(T/\beta)^{c \cdot \varepsilon_1/\varepsilon}$ के रूप में स्केल होना चाहिए, जहाँ $c$ एक स्थिरांक है। यह पुष्टि करता है कि GTM की $T$ और $\beta$ पर निर्भरता निकट-इष्टतम है, जो घातांकों में छोटे स्थिरांकों द्वारा भिन्न होती है।

एक्स-पोस्ट प्राइवेसी गारंटी (Ex-Post Privacy Guarantees)

यह शोध पत्र एक एक्स-पोस्ट प्राइवेसी वेरिएंट पेश करता है जहाँ प्राइवेसी लॉस $\tilde{\varepsilon}$ स्ट्रीम की लंबाई के साथ लॉगरिदमिक रूप से स्केल करता है ($\tilde{\varepsilon} \approx \varepsilon + \varepsilon_t \ln(t/\beta)$)। इस सेटिंग में, नॉइज़ पेनल्टी $\Lambda_t$ एक सार्वभौमिक स्थिरांक बन जाता है जो $t$ से स्वतंत्र है, जो लंबे स्ट्रीम के लिए सटीकता में काफी सुधार करता है।

4. अनुप्रयोग: निरंतर अवलोकन (CO) रिडक्शन

एक प्रमुख अनुप्रयोग जो प्रस्तुत किया गया है, वह कंटीन्यूअल ऑब्जर्वेशन (CO) ऑप्टिमाइज़ेशन को बैच (Batch) सेटिंग में एक ब्लैक-बॉक्स रिडक्शन है।

• समस्या: CO में, डेटा एक स्ट्रीम के रूप में आता है, और वैश्विक DP बनाए रखते हुए हर चरण पर एक समाधान आउटपुट किया जाना चाहिए। मानक तकनीकें जैसे स्पार्स वेक्टर तकनीक यहाँ विफल हो जाती हैं क्योंकि ऑप्टिमाइज़ेशन (जैसे सबमॉड्यूलर मैक्सिमाइजेशन) में उपयोग किए जाने वाले यूटिलिटी फंक्शन अक्सर सीमित लिप्सचिट्ज़ संवेदनशीलता की कमी रखते हैं।
• समाधान: GTM यह निगरानी करने की अनुमति देता है कि क्या किसी बैच एल्गोरिदम की आउटपुट गुणवत्ता महत्वपूर्ण रूप से गिर गई है। बैच एल्गोरिदम को एक ब्लैक-बॉक्स तंत्र के रूप में मानकर, GTM केवल आवश्यकता होने पर ही पुन: गणना (re-computation) को ट्रिगर करता है।
• प्रभाव: यह एक बड़े वर्ग के मैक्सिमाइजेशन समस्याओं (कार्डिनैलिटी/मैट्रॉइड बाधाओं के तहत सबमॉड्यूलर मैक्सिमाइजेशन, डेंसेस्ट सबग्राफ और मैक्स-कट सहित) के लिए CO सेटिंग में पहले DP एल्गोरिदम प्रदान करता है।
• लाभ: $\sqrt{t}$ स्केलिंग के माध्यम से कंपोजिशन की आवश्यकता वाले पिछले दृष्टिकोणों के विपरीत, यह विधि $\varepsilon_t \approx \varepsilon / \ln^2(t/\beta)$ प्राइवेसी पैरामीटर्स के साथ सटीकता गारंटी प्राप्त करती है, जो लंबे स्ट्रीम्स पर उच्च सटीकता बनाए रखती है।

5. महत्व और दावे

शोध पत्र सामान्यीकृत निजी परीक्षण में गोपनीयता, सटीकता और सैंपल कॉम्प्लेक्सिटी के बीच के तनाव को हल करने का दावा करता है:

1. इष्टतमता (Optimality): GTM निकट-इष्टतम सटीकता और सैंपल कॉम्प्लेक्सिटी प्राप्त करता है, जो मौजूदा ऊपरी और निचली सीमाओं के बीच के अंतर को पाटता है।
2. मजबूती (Robustness): यह अनुमानित DP इनपुट के लिए शुद्ध DP गारंटी प्रदान करता है, जो [LT19] जैसे पिछले कार्यों में मौजूद विशेषता नहीं थी।
3. व्यावहारिकता (Practicality): अनुकूलित थ्रेशोल्डिंग और एक्स-पोस्ट प्राइवेसी सेटिंग्स लचीले ट्रेड-ऑफ की अनुमति देते हैं, जो विशेष रूप से हाइपरपैरामीटर ऑप्टिमाइज़ेशन और निरंतर सीखने (continual learning) के परिदृश्यों के लिए फायदेमंद है जहाँ स्ट्रीम की लंबाई अनिश्चित होती है।
4. नई क्षमताएं: CO सेटिंग में रिडक्शन, मौजूदा बैच DP एल्गोरिदम को डायनेमिक डेटा स्ट्रीम्स पर लागू करने की अनुमति देता है, बिना उन प्रतिबंधात्मक लिप्सचिट्ज़ संवेदनशीलता धारणाओं की आवश्यकता के जो पहले इन रिडक्शन के लिए आवश्यक मानी जाती थीं।

लेखक इस बात पर जोर देते हैं कि हालांकि तंत्र एक नॉइज़ पेनल्टी $\Lambda_t$ पेश करता है, यह पेनल्टी अपरिहार्य है (जैसा कि निचली सीमाओं द्वारा दिखाया गया है) और उनके निर्माण द्वारा इसे अधिकतम संभव सीमा तक कम किया गया है। कार्य यह दावा नहीं करता है कि $T$ और $\beta$ पर बहुपद निर्भरता (polynomial dependence) को पूरी तरह से समाप्त किया जा सकता है, बल्कि यह प्रदर्शित करता है कि उनके घातांकों को सैद्धांतिक न्यूनतम के अत्यंत निकट लाया जा सकता है।