Privately Learning Decision Lists and a Differentially Private Winnow

तकनीकी सारांश: निजी तौर पर निर्णय सूचियों (Decision Lists) को सीखना और एक विभेदक रूप से निजी विन्नो (Differentially Private Winnow)

लेखक: मार्क बुन (बोस्टन यूनिवर्सिटी) और विलियम फेंग (बोस्टन यूनिवर्सिटी)
स्थान: 37वां एल्गोरिदम लर्निंग थ्योरी पर अंतर्राष्ट्रीय सम्मेलन (ALT 2026)

1. समस्या विवरण

यह शोध पत्र कम्प्यूटेशनल लर्निंग थ्योरी में मौलिक अवधारणा वर्गों (concept classes) को सीखने के दौरान डिफरेंशियल प्राइवेसी (DP) बनाए रखने की चुनौती को संबोधित करता है। विशेष रूप से, यह दो क्लासिक समस्याओं को लक्षित करता है:

1. PAC मॉडल में निर्णय सूचियों (Decision Lists) को सीखना: निर्णय सूचियाँ ("यदि-तो-अन्यथा" नियमों के अनुक्रम) अत्यधिक व्याख्या योग्य (interpretable) हैं और स्वास्थ्य सेवा तथा वित्त जैसे संवेदनशील क्षेत्रों में व्यापक रूप से उपयोग की जाती हैं। जबकि वे गैर-निजी प्रोबेबली एप्रोक्सिमेटली करेक्ट (PAC) मॉडल में कुशलतापूर्वक सीखी जा सकती हैं, लेखक यह जांचते हैं कि क्या गोपनीयता प्रतिबंधों को जोड़ने से उनकी सैंपल कॉम्प्लेक्सिटी या कम्प्यूटेशनल दक्षता में महत्वपूर्ण गिरावट आती है।
2. ऑनलाइन मॉडल में लार्ज-मार्जिन हाफस्पेस (Large-Margin Halfspaces) को सीखना: ऑनलाइन लर्निंग सेटिंग में, एक शिक्षार्थी को क्रमवार भविष्यवाणियां करनी होती हैं, और एक विरोधी (adversary) के विरुद्ध गलतियों को कम करना होता है। लक्ष्य एक निजी संस्करण वाले विन्नो (Winnow) एल्गोरिदम को विकसित करना है, जो "एट्रीब्यूट-एफिशिएंट" (जिसका मिस्टेक बाउंड आयाम $d$ के पॉलीलॉगैरिथमिक पर निर्भर करता है) है।

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

A. निर्णय सूचियों के लिए (PAC मॉडल): DP-GreedyCover
लेखक DP-GreedyCover प्रस्तावित करते हैं, जो रिवेट (Rivest) के क्लासिक ग्रीडी दृष्टिकोण की नकल करने वाला एक पुनरावृत्ति (iterative) एल्गोरिदम है।

• तंत्र (Mechanism): एक फीचर-लेबल युग्म $(f, b)$ को नियत रूप से (deterministically) चुनने के बजाय (जो गोपनीयता लीक कर सकता है), एल्गोरिदम एक्सपोनेंशियल मैकेनिज्म (Exponential Mechanism) का उपयोग करता है जो शेष अनक्लासिफाइड नमूनों पर वर्गीकरण त्रुटि को कम करता है।
• प्राइवेसी विश्लेषण: मानक कंपोजिशन से जुड़े भारी गोपनीयता नुकसान (जो एक उप-इष्टतम सैंपल कॉम्प्लेक्सिटी $\tilde{O}(|F|^{3/2})$ की ओर ले जाता है) से बचने के लिए, लेखक पुनरावृत्ति एक्सपोनेंशियल मैकेनिज्म-आधारित कवरिंग एल्गोरिदम के लिए एक विशेष विश्लेषण का लाभ उठाते हैं। वे दिखाते हैं कि इसकी संरचना अनुमानित सेट कवर (approximate Set Cover) के समान एक टेम्पलेट का अनुसरण करती है, जिससे बहुत सटीक प्राइवेसी बाउंड प्राप्त होता है।

B. हाफस्पेस के लिए (ऑनलाइन मॉडल): DP-Winnow
लेखक DP-Winnow पेश करते हैं, जो लार्ज-मार्जिन हाफस्पेस के लिए डिज़ाइन किया गया विन्नो एल्गोरिदम का एक निजी संस्करण है।

• कॉन्फिडेंटविन्नो (ConfidentWinnow - सबरूटीन): वे पहले कॉन्फिडेंटविन्नो नामक एक गैर-निजी संस्करण डिजाइन करते हैं। मानक विन्नो के विपरीत, यह अपने वेट वेक्टर को केवल तभी अपडेट करता है जब यह गलत होता है या "अनकॉन्फिडेंट" होता है (अर्थात, भविष्यवाणी मार्जिन बहुत छोटा है)। यह सुनिश्चित करता है कि "कॉन्फिडेंट करेक्ट" भविष्यवाणियां गोपनीयता तंत्र द्वारा पेश किए गए शोर (noise) के प्रति मजबूत रहें।
• स्पार्स वेक्टर तकनीक (SVT): अपडेट के समय की गोपनीयता को संभालने के लिए (क्योंकि अपडेट राउंड का अनुक्रम जानकारी लीक कर सकता है), वे स्पार्स वेक्टर तकनीक को एकीकृत करते हैं। यह सुनिश्चित करता है कि गोपनीयता लागत कुल समय क्षितिज $T$ के बजाय अपडेट की संख्या के साथ स्केल होती है।
• वेट एप्रोक्सिमेशन: सटीक वेट वेक्टर $w$ को जारी करने के बजाय, एल्गोरिदम एक रैंडमाइज्ड एप्रोक्सिमेशन $\tilde{w}$ जारी करता है जिसे मल्टीप्लिकेटिव वेट्स वितरण से नमूना लेकर प्राप्त किया जाता है।

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

• निर्णय सूचियों का कुशल PAC लर्निंग:
  • परिणाम: यह एल्गोरिदम एक $(\epsilon, \delta)$-DP $(\alpha, \beta)$-PAC लर्नर प्राप्त करता है।
  • जटिलता: यह $\tilde{O}(|F| \cdot \log(1/\delta)/\epsilon)$ नमूनों का उपयोग करता है और $\text{poly}(|F|)$ समय में चलता है। यह लॉगरिदमिक कारकों तक सर्वोत्तम गैर-निजी एल्गोरिदम की सैंपल कॉम्प्लेक्सिटी से मेल खाता है।
• हाफस्पेस का निजी ऑनलाइन लर्निंग:
  • परिणाम: एल्गोरिदम एक मिस्टेक बाउंड (रिग्रेट) प्राप्त करता है जो आयाम $d$ और समय क्षितिज $T$ में पॉलिलॉगैरिथमिक है, और मार्जिन $\rho$ में इनवर्स पॉलीनोमियल है।
  • जटिलता: मिस्टेक बाउंड $\tilde{O}\left(\frac{\log^3 d \cdot \log^{5/2}(T/\beta) \cdot \log^2(1/\delta)}{\epsilon^4 \rho^6}\right)$ है। यह एक महत्वपूर्ण परिणाम है क्योंकि अधिकांश निजी ऑनलाइन कॉन्वेक्स ऑप्टिमाइज़ेशन तकनीकें आयाम $d$ के साथ बहुपद (polynomial) रूप से स्केल करती हैं।
• निर्णय सूचियों पर अनुप्रयोग:
  • लेखक दर्शाते हैं कि DP-Winno का उपयोग ऑनलाइन मॉडल में निर्णय सूचियों को निजी तौर पर सीखने के लिए किया जा सकता है, जो अत्याधुनिक गैर-निजी गारंटियों के साथ गुणात्मक मिलान प्रदान करता है।

4. महत्व

यह शोध पत्र कम्प्यूटेशनल लर्निंग थ्योरी और प्राइवेसी-प्रिजर्विंग मशीन लर्निंग के बीच एक महत्वपूर्ण अंतर को पाटता है।

1. डायमेंशनलिटी बैरियर को तोड़ना: ऑनलाइन सेटिंग में, लेखक सफलतापूर्वक उन एल्गोरिदम से आगे बढ़ते हैं जो आयाम $d$ के साथ बहुपद रूप से स्केल करते हैं, और उच्च-आयामी डेटा के लिए आवश्यक "एट्रीब्यूट-एफिशिएंट" पॉलिलॉगैरिथमिक निर्भरता प्राप्त करते हैं।
2. व्याख्यात्मकता (Interpretability) को संरक्षित करना: निर्णय सूचियों के लिए कुशल निजी लर्नर्स प्रदान करके, यह शोध पत्र गोपनीयता-संवेदनशील, उच्च-दांव वाले वातावरण (जैसे वित्त और चिकित्सा) में सीखने की प्रक्रिया की दक्षता से समझौता किए बिना अत्यधिक व्याख्या योग्य मॉडलों की तैनाती को सक्षम बनाता है।
3. सैद्धांतिक मजबूती: यह कार्य नए अंतर्दृष्टि प्रदान करता है कि कैसे एल्गोरिदम के संरचनात्मक गुणों (जैसे विन्नो में "कॉन्फिडेंस" या निर्णय सूचियों की "कवरिंग" प्रकृति) का उपयोग इष्टतम प्राइवेसी-यूटिलिटी ट्रेड-ऑफ प्राप्त करने के लिए किया जा सकता है।