The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting

तकनीकी सारांश: अनुमानित विभेदक गोपनीयता (Approximate Differential Privacy) के लिए बाइनरी ट्री मैकेनिज्म इष्टतम है

समस्या विवरण
यह शोध पत्र निजी निरंतर गणना (private continual counting) की मौलिक समस्या को संबोधित करता है। इस सेटिंग में, एक संगठन $n$ लंबाई का एक बाइनरी स्ट्रीम $x \in \{0, 1\}^n$ देखता है, जहाँ समय चरण $i$ पर '1' का होना यह दर्शाता है कि एक एकल व्यक्ति द्वारा घटना में योगदान दिया गया है। लक्ष्य प्रत्येक समय चरण $i \in [n]$ पर रनिंग काउंट्स (प्रिफिक्स सम्स) $Ax$को जारी करना है, जबकि$(\epsilon, \delta)$-डिफरेंशियल प्राइवेसी (DP) का पालन करना है। यहाँ, $A$ $n \times n$ लोअर ट्राइएंगुलर प्रिफिक्स-सम मैट्रिक्स है। सटीकता के लिए प्राथमिक मीट्रिक अपेक्षित $\ell_\infty$ त्रुटि है, जिसे $\mathbb{E}[\|M(x) - Ax\|_\infty]$ के रूप में परिभाषित किया गया है, जो सभी समय चरणों पर सबसे खराब स्थिति (worst-case) की त्रुटि को दर्शाता है।

हालाँकि बाइनरी ट्री मैकेनिज्म इस कार्य के लिए मानक एल्गोरिदम है, लेकिन अनुमानित DP सेटिंग ($\delta > 0$) में इसकी इष्टतमता एक खुला प्रश्न था। पिछले विश्लेषणों ने दिखाया कि बाइनरी ट्री मैकेनिज्म $\ell_\infty$ त्रुटि $O(\log^{3/2} n \cdot \sqrt{\log(1/\delta)}/\epsilon)$ प्राप्त करता है। हालाँकि, अब तक का सर्वोत्तम ज्ञात निचला स्तर (lower bound) केवल $\Omega(\log n / \epsilon)$ था (विशेष रूप से अपेक्षित वर्गित सबसे खराब स्थिति के वर्गमूल के लिए), जिससे यह अंतराल बना रहा कि क्या स्ट्रीम की लंबाई $n$ पर $\log^{3/2} n$ की निर्भरता आवश्यक है।

कार्यप्रणाली और प्रमाण अवलोकन
लेखक यह सिद्ध करते हैं कि बाइनरी ट्री मैकेनिज्म एसिम्प्टोटिक रूप से इष्टतम है, जिसके लिए वे $\Omega(\log^{3/2} n / \max\{\epsilon, \delta\})$ का एक मिलान करने वाला निचला स्तर स्थापित करते हैं। प्रमाण कई प्रमुख तकनीकी चरणों के माध्यम से आगे बढ़ता है:

1. ओब्लिवियस मैकेनिज्म में न्यूनीकरण (Reduction to Oblivious Mechanisms): पूर्ववर्ती कार्यों का अनुसरण करते हुए, लेखक समस्या को $M(x) = Ax + z$प्रकार के ओब्लिवियस मैकेनिज्म के विश्लेषण में कम करते हैं, जहाँ$z$ एक शोर वेक्टर (noise vector) है जो इनपुट $x$ से स्वतंत्र है। लक्ष्य $\mathbb{E}[\|z\|_\infty]$ को निचला स्तर प्रदान करना बन जाता है।
2. ट्री बेसिस डिकंपोजिशन (Tree Basis Decomposition): मानक आधार (basis) में सीधे शोर का विश्लेषण करने के बजाय, लेखक शोर वेक्टर $z$ को एक पूर्ण बाइनरी ट्री द्वारा प्रेरित आधार में विघटित करते हैं। विशेष रूप से, वे सब-ट्री (subtrees) के अनुरूप (इंडिकेटर्स ऑफ लीव्स इन अ सब-ट्री) वेक्टर $\chi_u$ को परिभाषित करते हैं। इस आधार में, किसी भी लीफ $i$ पर शोर, रूट से लीफ तक के पथ के साथ गुणांकों $b_u$ का योग होता है। यह समस्या को अधिकतम कोऑर्डिनेट त्रुटि को बाउंड करने से बदलकर रूट-टू-लीफ पथों के साथ शोर के संचय को बाउंड करने में बदल देता है।
3. शोर संचय और अवशिष्ट अनिश्चितता (Noise Accumulation and Residual Uncertainty): प्रमाण "अवशिष्ट शोर" (residual noise) $\sigma_u$ की अवधारणा पेश करता है। यह तर्क देता है कि यदि किसी नोड $u$ पर शोर का अनुमान उसके नीचे के सब-ट्री के शोर से उच्च सटीकता के साथ लगाया जा सकता है, तो गोपनीयता का उल्लंघन होगा। लेखक $\sigma_u$ को सब-ट्री के शोर को देखते हुए नोड के शोर गुणांक की भविष्यवाणी करने में अपेक्षित पूर्ण त्रुटि के रूप में परिभाषित करते हैं। वे दिखाते हैं कि अपेक्षित $\ell_\infty$ त्रुटि रैंडम रूट-टू-लीफ पथों के साथ इन अवशिष्ट अनिश्चितताओं के भारित योग (weighted sum) द्वारा निचला स्तर प्रदान करती है।
4. "भविष्यवाणी" बाधा को पार करना (Overcoming the "Prediction" Obstacle): एक बड़ी चुनौती यह है कि एक हमलावर (adversary) वर्तमान नोड के शोर की भविष्यवाणी करने के लिए सब-ट्री शोर को सीधे नहीं देख सकता क्योंकि इनपुट $x$ अज्ञात है। इसे बायपास करने के लिए, लेखक "ग्रैंडचिल्ड्रन" रणनीति का उपयोग करते हैं। वे दिखाते हैं कि विशिष्ट सब-ट्री पर ध्यान केंद्रित करके और मैकेनिज्म की तीन स्वतंत्र प्रतियों का उपयोग करके (DP के कंपोजिशन गुणों का लाभ उठाते हुए), एक हमलावर मीडियन-ऑफ-थ्री ट्रिक का उपयोग करके शोर के वेरिएंस को कम कर सकता है। यह एक व्युत्पन्न मैकेनिज्म के निर्माण की अनुमति देता जहाँ हमलावर $x_i \nu_i + q$ जैसे रैखिक मापन (linear measurements) की गणना कर सकता है, जहाँ $q$ का वेरिएंस नियंत्रित है।
5. रैखिक मापन और हॉर वेवलेट्स (Linear Measurements and Haar Wavelets): अंतिम चरण हॉर वेवलेट बेसिस (Haar wavelet basis) से प्रेरित रैखिक मापन का उपयोग करके एक हमलावर का निर्माण करता है। ऑर्थोगोनल मेजरमेंट वेक्टर्स चुनकर, लेखक हमलावर के अनुमानों के वर्ग त्रुटियों के योग को अवशिष्ट शोर के $\ell_2$ नॉर्म से जोड़ते हैं। वे प्रदर्शित करते हैं कि यदि अवशिष्ट शोर $\sigma_u$ छोटा होता, तो हमलावर उच्च प्रायिकता के साथ पड़ोसी इनपुट्स के बीच अंतर कर सकता था, जो डिफरेंशियल प्राइवेसी का उल्लंघन करता। यह $\sigma_u = \Omega(\sqrt{\log n} / \max\{\epsilon, \delta\})$ को बड़ा होने के लिए मजबूर करता है।
6. योग (Summation): इन अवशिष्ट अनिश्चितताओं को पथ के साथ जोड़ने से अंतिम $\Omega(\log^{3/2} n)$ निचला स्तर प्राप्त होता है।

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

• बाइनरी ट्री मैकेनिज्म की इष्टतमता: यह शोध पत्र सिद्ध करता है कि अनुमानित DP के लिए, किसी भी निरंतर गणना वाले मैकेनिज्म को $\Omega(\log^{3/2} n / \max\{\epsilon, \delta\})$ की अपेक्षित $\ell_\infty$ त्रुटि उठानी ही होगी। यह बाइनरी ट्री मैकेनिज्म के ऊपरी स्तर (upper bound) से मेल खाता है (कॉन्स्टेंट फैक्टर्स तक), जिससे यह खुला प्रश्न हल हो जाता है कि क्या $\log^{3/2} n$ की निर्भरता आवश्यक है।
• शुद्ध DP (Pure DP) बाउंड्स को कड़ा करना: शुद्ध DP ($\delta = 0$) के लिए, यह परिणाम ज्ञात ऊपरी स्तर $O(\log^2 n / \epsilon)$ और निचले स्तर के बीच के अंतर को कम करता है, जिससे $\Omega(\log^{3/2} n / \epsilon)$ का निचला स्तर प्राप्त होता है।
• हेरेडिटरी डिस्क्रेपेंसी (Hereditary Discrepancy) से अलगाव: एक उप-परिणाम के रूप में, लेखक हेरेडिटरी डिस्क्रेपेंसी और निजी रैखिक प्रश्नों की त्रुटि के बीच सबसे बड़े संभावित अलगाव को प्राप्त करते हैं। वे दिखाते हैं कि सामान्य ऊपरी स्तर $err_{\epsilon, \delta}^\infty(A) = O(\log^{3//2} m \cdot \text{herdisc}_\infty(A))$ अपने क्वेरीज़ की संख्या $m$ पर निर्भरता में टाइट है, क्योंकि प्रिफिक्स-सम मैट्रिक्स का हेरेडिटरी डिस्क्रेपेंसी 1 है लेकिन इसे $\Omega(\log^{3/2} n)$ त्रुटि की आवश्यकता होती है।

महत्व
यह शोध पत्र दावा करता है कि वह अनुमानित DP सेटिंग में निरंतर गणना के लिए बाइनरी ट्री मैकेनिज्म की एसिम्प्टोटिक इष्टतमता को सिद्ध करके डिफरेंशियल प्राइवेसी में एक केंद्रीय खुले प्रश्न को हल करता है। विकसित की गई तकनीकें, विशेष रूप से ट्री-आधारित शोर अपघटन, अवशिष्ट शोर विश्लेषण, और रैखिक मापन हमलों को संभालने के लिए मीडियन-ऑफ-थ्री ट्रिक का संयोजन, नवीन विचार हैं जो निचले स्तरों को सिद्ध करने के लिए अन्य अनुप्रयोगों में भी मिल सकते हैं। यह परिणाम पुष्टि करता है कि वर्तमान अत्याधुनिक एल्गोरिदम स्ट्रीम की लंबाई $n$ पर अपनी निर्भरता के संदर्भ में महत्वपूर्ण रूप से बेहतर नहीं किए जा सकते हैं।