Not All Learnable Distribution Classes are Privately Learnable

तकनीकी सारांश: "सभी सीखने योग्य वितरण वर्ग निजी तौर पर सीखने योग्य नहीं होते हैं"

समस्या विवरण
यह शोध पत्र सांख्यिकीय शिक्षण सिद्धांत (statistical learning theory) और विभेदक गोपनीयता (differential privacy - DP) के मिलन बिंदु में एक मौलिक प्रश्न को संबोधित करता है: क्या वितरणों का प्रत्येक वर्ग, जो मानक (गैर-निजी) परिवेश में सीखने योग्य है, $(\varepsilon, \delta)$-विभेदक गोपनीयता के प्रतिबंधों के तहत भी सीखने योग्य है?

जबकि यह स्थापित है कि शुद्ध विभेदक गोपनीयता ($\varepsilon$-DP, जहाँ $\delta=0$) सीखने योग्य और निजी तौर पर सीखने योग्य वर्गों के बीच सख्त अलगाव (separation) आरोपित करती है (जो अक्सर कवरिंग/पैकिंग संख्याओं द्वारा अभिलक्षित होती है), अनुमानित विभेदक गोपनीयता ($(\varepsilon, \delta)$-DP) की स्थिति एक खुला प्रश्न बनी हुई थी। हालिया साहित्य ने निजी वितरण शिक्षण के लिए तेजी से सामान्य ढांचे विकसित किए हैं, जिससे अश्तियानी [Ash22] ने यह परिकल्पना की कि उपरोक्त प्रश्न का उत्तर सकारात्मक होगा: कि प्रत्येक सीखने योग्य वितरण वर्ग निजी तौर पर सीखने योग्य है।

कार्यप्रणाली और निर्माण
लेखक इस परिकल्पना का खंडन करने के लिए एक विशिष्ट वितरण वर्ग का निर्माण करते हैं, जिसे $\mathcal{H}_w$ कहा जाता है, जो एक प्रति-उदाहरण (counterexample) के रूप में कार्य करता है। यह निर्माण मिश्रण वितरणों (mixtures of distributions) के माध्यम से एक "ट्रैपडोर" (trapdoor) तंत्र का उपयोग करता है:

1. वर्ग की संरचना: वर्ग $\mathcal{H}_{w,d}$ में $d+1$ घटकों का मिश्रण शामिल है जो एक सामान्य पैरामीटर वेक्टर $\mathbf{p} \in [0,1]^d$ साझा करते हैं।
   • "की" (Key) घटक: एक साझा पैरामीटर $\mathbf{p}$ के बारे में पूरी जानकारी प्रकट करने वाला $w$ मिश्रण भार वाला $\{0,1\}^d$ पर एक बाइनरी प्रोडक्ट डिस्ट्रीब्यूशन।
   • "हार्ड" (Hard) घटक: $d$ अतिरिक्त घटक, जिनमें से प्रत्येक $\{\pm j\}$ पर समर्थित है (जहाँ $j \in \{1, \dots, d\}$), जिसका मिश्रण भार $(1-w)/d$ है। इनमें से किसी भी घटक से प्राप्त नमूना $\mathbf{p}$ के केवल एक एकल निर्देशांक (coordinate) के बारे में जानकारी प्रकट करता है।
2. ट्रैपडोर: मिश्रण भार $w$ को $1/(2\alpha)$ (जहाँ $\alpha$ लक्षित त्रुटि है) के रूप में सेट किया गया है। यह सुनिश्चित करता है कि "हार्ड" घटक मिश्रण पर हावी हों (उच्च संभावना कि नमूना उनसे लिया जाएगा), जबकि "की" घटक दुर्लभ है।
3. आयामी युक्ति (Dimensionality Trick): वर्ग $\mathcal{H}_w$ को सभी आयामों $d \ge 2$ पर इन वर्गों के संघ (union) के रूप में परिभाषित किया गया है। निर्माण यह सुनिश्चित करता है कि जबकि आयाम $d$ पूर्व निर्धारित नहीं है, सीखने की कठिनाई $d$ के साथ बढ़ती है।

मुख्य परिणाम और प्रमाण
यह शोध पत्र टोटल वेरिएशन (TV) दूरी के संबंध में $\mathcal{H}_w$ के लिए गैर-निजी और निजी सीखने की क्षमता के बीच एक अलगाव स्थापित करता है:

1. गैर-निजी सीखने की क्षमता (सीमित नमूने):
   लेखक प्रदर्शित करते हैं कि $\mathcal{H}_w$ एक स्थिर संख्या में नमूनों (जो $d$ से स्वतंत्र है) के साथ एक स्थिर त्रुटि तक सीखने योग्य है।

   • तंत्र: चूंकि "की" घटक प्राय $w$ प्रायिकता के साथ आता है, इसलिए एक गैर-निजी एल्गोरिदम "की" घटक को देखने के लिए पर्याप्त नमूने एकत्र कर सकता है। एक बार देखे जाने के बाद, आयाम $d$ की पहचान की जा सकती है, और बाइनरी प्रोडक्ट डिस्ट्रीब्यूशन के नमूना माध्य (sample mean) के माध्यम से पैरामीटर वेक्टर $\mathbf{p}$ का अनुमान लगाया जा सकता है।
   • जटिलता: इसकी नमूना जटिलता $O(1/\alpha^3 \cdot \log(1/\beta))$ है, जो आयाम $d$ के संबंध में स्थिर है।

2. निजी गैर-सीखने की क्षमता (अनंत नमूनों की आवश्यकता):
   लेखक सिद्ध करते हैं कि कोई भी $(\varepsilon, \delta)$-DP तंत्र सीमित नमूनों का उपयोग करके समान त्रुटि गारंटी के साथ इस वर्ग को नहीं सीख सकता है।

   • न्यूनीकरण (Reduction): वे $\mathcal{H}_{w,d}$ पर घनत्व अनुमान (density estimation) की समस्या को बाइनरी प्रोडक्ट डिस्ट्रीब्यूशन पर $\ell_1$-पैरामीटर अनुमान की समस्या में बदलने के लिए एक न्यूनीकरण का निर्माण करते हैं।
   • निम्नतम सीमा (Lower Bound): बाइनरी प्रोडक्ट डिस्ट्रीब्यूशन के निजी माध्य अनुमान के ज्ञात निम्नतम सीमाओं (विशेष रूप से [KLSU19] से) का लाभ उठाते हुए, वे दिखाते हैं कि DP के तहत $\mathcal{H}_{w,d}$ को सीखने के लिए नमूना जटिलता $\Omega(\sqrt{d}/(\sqrt{\alpha}\varepsilon))$ के रूप में स्केल करती है।
   • विरोधाभास: चूंकि वर्ग $\mathcal{H}_w$ में किसी भी $d \ge 2$ के लिए वितरण शामिल हैं, और आवश्यक नमूना आकार $\sqrt{d}$ के साथ बढ़ता है, इसलिए कोई भी परिमित नमूना आकार $n$ पूरे वर्ग $\mathcal{H}_w$ को DP के तहत सीखने के लिए पर्याप्त नहीं है। जैसे-जैसे $d \to \infty$, आवश्यक नमूना आकार अनंत की ओर बढ़ता है।

मुख्य योगदान

• परिकल्पना का खंडन: यह शोध पत्र अश्तियानी की उस परिकल्पना का स्पष्ट प्रति-उदाहरण प्रदान करता है कि प्रत्येक सीखने योग्य वितरण वर्ग $(\varepsilon, \delta)$-DP के तहत निजी तौर पर सीखने योग्य है।
• सीखने की क्षमता का अलगाव: यह एक ऐसा अलगाव प्रदर्शित करता है जहाँ एक वर्ग गैर-निजी रूप से $O(1)$ नमूनों के साथ सीखने योग्य है, लेकिन निजी तौर पर सीखने के लिए अनंत नमूनों की आवश्यकता होती है।
• ट्रैपडोर निर्माण: लेखक एक विशिष्ट "ट्रैपडोर" निर्माण पेश करते हैं जहाँ एक दुर्लभ घटक एक उच्च-आयामी पैरामीटर के लिए "की" के रूप में कार्य करता है, जो अन्यथा एक प्रभावी लेकिन कठिन-से-सीखने वाले घटक द्वारा छिपा हुआ होता है। यह संरचना निजी तंत्रों को गोपनीयता बाधाओं का उल्लंघन किए बिना या अत्यधिक नमूना आकार की आवश्यकता के बिना "की" तक पहुँचने से रोकती है।

महत्व और दावे
शोध पत्र दावा करता है कि यह परिकल्पना को "कमजोर रूप से खंडित" (weakly refute) करता है। लेखक स्पष्ट रूप से नोट करते हैं कि एक "मजबूत खंडन" के लिए यह दिखाना आवश्यक होगा कि वर्ग किसी भी लक्षित त्रुटि (केवल स्थिर त्रुटि ही नहीं) के लिए परिमित नमनों के साथ गैर-निजी रूप से सीखने योग्य है, जिसे वे सिद्ध नहीं करते हैं। हालांकि, उनका परिणाम महत्वपूर्ण है क्योंकि यह दिखाता है कि निरंतर त्रुटि गारंटी के लिए भी, निजी वितरण शिक्षण का परिदृश्य गैर-निजी शिक्षण से मौलिक रूप से भिन्न है।

यह कार्य इस बात पर प्रकाश डालता है कि सामान्य निजी शिक्षण एल्गोरिदम के डिजाइन करने वाले ढांचे, जो सभी सीखने योग्य वितरण वर्गों के लिए काम करते हैं, केवल गैर-निजी शिक्षार्थियों से ब्लैक-बॉक्स न्यूनीकरण पर निर्भर नहीं रह सकते हैं। यह स्थापित करता है कि एक "की" घटक का अस्तित्व जो दुर्लभ है लेकिन सीखने के लिए आवश्यक है, निजी एल्गोरिदम के लिए एक अजेय बाधा उत्पन्न कर सकता है, भले ही गैर-निजी एल्गोरिदम कुशल हो।

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