तकनीकी सारांश: किसी भी सबसेंपलेबल (Subsamplable) इनपुट के दूसरे-मोमेंट मैट्रिक्स का एक निजी सन्निकटन (Private Approximation)

समस्या विवरण

यह शोध पत्र उच्च-आयामी स्थान ($\mathbb{R}^d$) में डेटासेट के दूसरे-मोमेंट मैट्रिक्स (तुल्यकालिक कोवेरिएंस मैट्रिक्स) के डिफरेंशियल प्राइवेट (DP) अनुमान की समस्या को संबोधित करता है। जबकि इस मैट्रिक्स का अनुमान लगाना मशीन लर्निंग और सांख्यिकी में मौलिक है, मौजूदा DP दृष्टिकोण अक्सर प्रतिबंधात्मक धारणाओं पर निर्भर करते हैं, जैसे कि इनपुट डेटा एक गाऊसी (Gaussian) वितरण से लिया गया हो या उसके आइगेनवैल्यू (eigenvalues) सुव्यवस्थित हों।

लेखक एक अधिक सामान्य परिदृश्य पर ध्यान केंद्रित करते हैं जहाँ इनपुट डेटा में अक्षों (axes) के बीच महत्वपूर्ण विचरण अंतर (बड़ा कंडीशन नंबर) हो सकता है और इसमें आउटलेर्स (outliers) भी हो सकते हैं। ऐसे परिदृश्यों में, मानक अभिसरण सीमाएँ (concentration bounds) विफल हो सकती हैं, और पारंपरिक DP एल्गोरिदम (जैसे कि प्रति-बिंदु सीमित लीवरेज स्कोर पर आधारित) अत्यधिक नमूना जटिलता (sample complexity) का सामना कर सकते हैं या पूरी तरह विफल हो सकते हैं यदि आउटलेर्स में उच्च लीवरेज हो। मुख्य चुनौती एक विशिष्ट संरचनात्मक गुण वाले 'वर्स्ट-केस' इनपुट के लिए मजबूत गोपनीयता-उपयोगिता ट्रेड-ऑफ प्राप्त करना है, बिना यह धारणा किए कि अंतर्निहित वितरण गाऊसी है।

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

सबसेंपलेबिलिटी (Subsamplability) धारणा

केंद्रीय सैद्धांतिक योगदान $(m, \alpha, \beta)$-सबसेंपलेबिलिटी का औपचारिककरण है। एक डेटासेट $X$ को $(m, \alpha, \beta)$-सबसेंपलेबल तब कहा जाता है यदि आकार $m$ (या उससे अधिक) का एक यादृच्छिक उपनमूना (random subsample), मूल दूसरे-मोमेंट मैट्रिक्स $\Sigma$ की स्पेक्ट्रल संरचना को $(1 \pm \alpha)$ के गुणक कारक तक कम से कम $1 - \beta$ प्रायिकता के साथ संरक्षित करता है।

• यह धारणा मानक मैट्रिक्स अभिसरण सीमाओं की तुलना में कमजोर है, जिन्हें पर्याप्त बड़े $m$ के लिए किसी भी $\alpha, \beta$ के लिए ऐसी सुरक्षा की आवश्यकता होती है। यहाँ, लेखक केवल कुछ $\alpha, \beta$ और एक संगत $m$ के अस्तित्व की आवश्यकता रखते हैं।
• यह गुण एल्गोरिदम को आउटलेर्स वाले वितरणों को संभालने की अनुमति देता है, बशर्ते कि आउटलेर्स यादृच्छिक उपनमूहों के वैश्विक स्पेक्ट्रल ढांचे पर हावी न हों।

एल्गोरिद्मिक ढांचा

लेखक कामथ एट अल. (2019) के दृष्टिकोण पर आधारित एक रिकर्सिव (recursive) एल्गोरिद्मिक ढांचे का प्रस्ताव करते हैं, लेकिन इसे गाऊसी सेटिंग के बजाय सबसेंपलेबल सेटिंग के अनुकूल बनाते हैं। एल्गोरिदम जीरो-कंसेंट्रेटेड डिफरेंशियल प्राइवेसी (zCDP) ढांचे के तहत कार्य करता है।

1. आरंभीकरण (Initialization): एल्गोरिदम यह मानता है कि इनपुट $L_2$-नॉर्म द्वारा $R$ से सीमित है और दूसरा-मोमेंट मैट्रिक्स $\Sigma$ इस प्रकार है कि $I \preceq \Sigma \preceq R^2 I$। यह मौजूदा DP उपकरणों का उपयोग करके रेंज $R$ और न्यूनतम आइगेनवैल्यू $\lambda_{\min}$ का अनुमान लगाकर प्राप्त किया जाता है।
2. रिकर्सिव प्रीकंडीशनिंग (Recursive Preconditioning):
   • प्रत्येक पुनरावृत्ति (iteration) में, गोपनीयता सुनिश्चित करने के लिए अनुभवजन्य दूसरे-मोमेंट मैट्रिक्स में शोर (noise) जोड़ा जाता है।
   • एल्गोरिदम उस सबस्पेस $V$ की पहचान करता है जो बड़े आइगेनवैल्यूज़ (वे जो $\ge \psi \kappa$ हैं, जहाँ $\kappa$ आइगेनवैल्यूज़ की वर्तमान ऊपरी सीमा है) के अनुरूप है।
   • एक रैखिक रूपांतरण $\Pi$ लागू किया जाता है ताकि डेटा बिंदुओं के $V$ पर प्रोजेक्शन को एक कारक $\eta$ (विशेष रूपकर $\eta = 1/2$) द्वारा सिकोड़ा जा सके।
   • महत्वपूर्ण रूप से, गाऊसी मामले के विपरीत जहाँ सभी बिंदु समान रूप से सिकुड़ते हैं, लेखकों को उन बिंदुओं को संभालना होगा जिनके नॉर्म (norm) रूपांतरण के बाद नए बाउंड से अधिक हो जाते हैं। वे एक "टेल सेट" $P_{tail}$ को परिभाषित करते हैं जिसमें वे बिंदु शामिल हैं जो सबसेंपलेबिलिटी सीमाओं का उल्लंघन करते हैं।
   • एल्गोरिदम $P_{tail}$ में मौजूद बिंदुओं पर एक सिकुड़ने वाला फलन (shrinking function) $S$ लागू करता है ताकि उन्हें नए रेडियस बाउंड ($\sqrt{3/7}R$) के भीतर लाया जा सके।
3. टेल विश्लेषण (Tail Analysis): विश्लेषण सिद्ध करता है कि सिकुड़ने की आवश्यकता वाले बिंदु $P_{tail}$ का हिस्सा हैं, जो डेटासेट का एक छोटा अंश ($\approx \beta/m$) है। इसके अलावा, इन बिंदुओं को हटाने या सिकोड़ने से शेष "अच्छे" डेटा के दूसरे-मोमेंट मैट्रिक्स के निचले स्तर (lower bound) में महत्वपूर्ण गिरावट नहीं आती है।
4. समाप्ति (Termination): पुनरावृत्ति तब तक जारी रहती है जब तक कि कंडीशन नंबर $\kappa$ को एक स्थिर ($O(m)$) तक कम न कर दिया जाए। इस चरण पर, $(1 \pm \gamma)$-सन्निकटन प्राप्त करने के लिए सरल शोर जोड़ना ही पर्याप्त होता है।

बेसलाइन तुलना

यह शोध पत्र सबसेंपल-एंड-अग्रेगेट (Nissim et al., 2007) ढांचे को अष्टियानी और लियाव (Ashtiani & Liaw, 2022) की कॉनवेक्स सेमीमेट्रिक स्पेस तकनीकों के साथ जोड़कर एक बेसलाइन स्थापित करता है। यह बेसलाइन एक $(1 \pm 2\alpha)$-सन्निकटन प्रदान करती है, लेकिन इसके लिए काफी अधिक नमूना जटिलता की आवश्यकता होती है, विशेष रूप से आउटलेर्स के साथ निपटने के दौरान।

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

1. सबसेंपलेबल इनपुट के लिए रिकर्सिव एल्गोरिदम: लेखक एक रिकर्सिव एल्गोरिदम प्रस्तुत करते हैं जो किसी भी $(m, \alpha, \beta)$-सबसेंपलेबल इनपुट के लिए दूसरे-मोमेंट मैट्रिक्स का $(1 \pm \gamma)$-सन्निकटन प्राप्त करता है। एल्गोरिदम $\rho$-zCDP का पालन करता है।
2. आउटलेर्स को संभालना: विधि को आउटलेर्स के एक उल्लेखनीय अंश के प्रति मजबूत दिखाया गया है। विशेष रूप से, एक सुव्यवस्थित वितरण $D$ और एक $\eta$-अंश के आउटलेर्स के मिश्रण के लिए, एल्गोरिदम तब सफल होता है जब आउटलेर्स का दूसरा-मोमेंट मैट्रिक्स $\Sigma_{out}$ इस प्रकार हो कि $\Sigma_{out} \preceq O(1/\eta)\Sigma_D$।
3. बेहतर नमूना जटिलता (Sample Complexity):
   • सामान्य वितरणों (भारी-पूंछ वाले वितरणों सहित) के लिए, प्रस्तावित एल्गोरिदम लगभग $\tilde{O}\left(\frac{d}{\gamma^2} + \frac{d^{3/2}}{\gamma\sqrt{\rho}}\right)$ की नमूना जटिलता प्राप्त करता है।
   • इसके विपरीत, सबसेंपल-एंड-अग्रेगेट बेसलाइन को $\tilde{O}\left(\frac{d^2}{\epsilon \gamma^3}\right)$ की आवश्यकता होती है, जो विशेष रूप से आउटलेर्स की उपस्थिति में काफी अधिक है, जहाँ बेसलाइन की आउटलेर अंश $\eta$ पर आवश्यकता ( $\eta = O(1/m)$ बनाम प्रस्तावित विधि की सहनशीलता) बहुत सख्त है।
4. सबसेंपलेबिलिटी का औपचारिककरण: शोध पत्र एक कठोर सबसेंपलेबिलिटी परिभाषा प्रदान करता है और यह प्रदर्शित करता है कि कैसे यह सख्त गाऊसी धारणाओं की आवश्यकता के बिना टेल व्यवहार (tail behavior) को नियंत्रित करने के लिए एक व्यवहार्य प्रॉक्सी के रूप में कार्य करती है।

महत्व और दावे

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

• मजबूती (Robustness): एल्गोरिदम बड़े कंडीशन नंबर वाले दूसरे-मोメント अनुमान के लिए तैयार किया गया है, जहाँ पिछले तरीके (जैसे ब्राउन एट अल., 2023) महत्वपूर्ण त्रुटियां कर सकते हैं यदि आउटलेर्स छोटे आइगेनवैल्यूज़ की दिशाओं के साथ सह-संबंधित (correlate) होते हैं।
• कमजोर धारणाएं: यूनिफॉर्म लीवरेज स्कोर बाउंड्स के बजाय सबसेंपलेबिलिटी पर भरोसा करके, विधि कई आउटलेर्स की उपस्थिति को सहन करती है, बशर्ते कि वे यादृच्छिक उपनमूहों के समग्र स्पेक्ट्रम पर हावी न हों।
• उपयोगिता (Utility): शोध पत्र प्रदर्शित करता है कि जब इनपुट रेंज न्यूनतम आइगेनवैल्यू की तुलना में काफी अधिक हो, तब भी मजबूत उपयोगिता गारंटी (अनिश्चित $(1 \pm \gamma)$ सन्निकटन) प्राप्त की जा सकती है, जो एक ऐसी स्थिति है जहाँ मानक DP तकनीकें अक्सर संघर्ष करती हैं।

लेखक स्पष्ट रूप से नोट करते हैं कि हालांकि उनके विश्लेषण के लिए रेंज $R$ पर निर्भर $\beta$ पैरामीटर के बाउंड की आवश्यकता है, यह एक ट्रेड-ऑफ है जो आउटलेर्स वाले सुव्यवस्थित वितरणों को संभालने की अनुमति देता है। उन्होंने इस निर्भरता को $O(1)$ बाउंड से बदलने को एक दिलचस्प ओपन प्रॉब्लम के रूप में पहचाना है। यह कार्य वास्तविक दुनिया के डेटासेट पर प्रयोगात्मक सत्यापन प्रस्तावित नहीं करता है, बल्कि ट्रंकेटेड पारेटो वितरणों और उत्तल दीर्घवृत्त (convex ellipsoids) पर यूनिफॉर्म वितरणों सहित विशिष्ट वितरण मॉडलों के लिए सैद्धांतिक गारंटी और नमूना जटिलता सीमाएं प्रदान करता है।