Composition Theorems for Multiple Differential Privacy Constraints

यहाँ कैदिर, नजीब और शकेल के शोध पत्र "Composition Theorems for Multiple Differential Privacy Constraints" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र तब होने वाली चुनौतियों को संबोधित करता है जब एक एकल तंत्र (mechanism) को एक साथ कई विभेदक गोपनीयता (differential privacy - DP) बाधाओं को संतुष्ट करना होता है।

• संदर्भ: कई गोपनीयता अनुप्रयोगों में, एक तंत्र से केवल एक $(\epsilon, \delta)$-DP गारंटी ही नहीं, बल्कि कई गारंटी (जैसे कि $(\epsilon_1, \delta_1)$-DP और $(\epsilon_2, \delta_2)$-DP को एक साथ संतुष्ट करना) की आवश्यकता होती है। यह अक्सर $f$-Differential Privacy ($f$-DP) के सन्निकटन (approximation) के दौरान होता है, जहाँ ट्रेड-ऑफ फंक्शन $f$ को कई $(\epsilon, \delta)$ बाधाओं के प्रतिच्छेदन (intersection) द्वारा अनुमानित किया जाता है।
• अंतराल (The Gap): मौजूदा कंपोजिशन थ्योरम्स (जैसे कि कैरौज़ एट अल., गाज़ी एट अल., डोंग एट अल. द्वारा) मुख्य रूप से एकल बाधाओं या विशिष्ट विषम मामलों (जैसे शुद्ध $\epsilon$-DP) को संभालते हैं। 'डबल-डीपी' (double-DP) या '$n$-डीपी' बाधाओं को एक साथ संतुष्ट करने वाले तंत्रों के $k$-फोल्ड कंपोजिशन के लिए कोई सटीक ढांचा उपलब्ध नहीं था।
• लक्ष्य: उन तंत्रों के लिए सटीक कंपोजिशन क्षेत्रों (composition regions) को व्युत्पन्न करना जो कई DP बाधाओं को संतुष्ट करते हैं, और इसका उपयोग $f$-DP कंपोजिशन के लिए अधिक सटीक सन्निकटन प्रदान करने के लिए करना।

2. कार्यप्रणाली (Methodology)

लेखक परिकल्पना परीक्षण (hypothesis testing) के दृष्टिकोण का लाभ उठाते हैं, जहाँ गोपनीयता को टाइप I और टाइप II त्रुटियों के बीच ट्रेड-ऑफ फंक्शन के रूप में वर्णित किया जाता है।

• मिश्रणों के लिए संरचनात्मक लेम्मा (Lemma 1):
  मुख्य सैद्धांतिक योगदान एक लेम्मा है जो परिकल्पना परीक्षणों के मिश्रण (mixture of hypothesis tests) के ट्रेड-ऑफ फंक्शन का वर्णन करता है। यदि एक तंत्र $M$, $\alpha_i$ भार और $f_i$ ट्रेड-ऑफ फंक्शन वाले $n$ उप-तंत्रों का एक संभाव्य मिश्रण है, तो परिणामी ट्रेड-ऑफ फंक्शन $f_m$ व्यक्तिगत $f_i$ का भारित इन्फिमल कॉन्वोल्यूशन (weighted infimal convolution) है:
  $$f_m(t) = \min_{\substack{t_i \in [0,1] \\ \sum \alpha_i t_i = t}} \sum_{i=1}^n \alpha_i f_i(t_i)$$
  ज्यामितीय रूप से, मिश्रण का गोपनीयता क्षेत्र व्यक्तिगत गोपनीयता क्षेत्रों का उत्तल आवरण (convex hull/weighted sum) है।

• विषम कंपोजिशन (Heterogeneous Composition) में न्यूनीकरण:
  लेखक दिखाते हैं कि एक तंत्र जो एक साथ $(\epsilon_1, \delta_1)$ और $(\epsilon_2, \delta_2)$ बाधाओं को संतुष्ट करता है, उसे सरल तंत्रों के मिश्रण के रूप में मॉडल किया जा सकता है। विशेष रूप से, वे एक ऐसा तंत्र निर्मित करते हैं जो $1-\alpha$ प्रायिकता के साथ $\epsilon_1$-DP तंत्र के रूप में व्यवहार करता है और $\alpha$ प्रायिकता के साथ $\epsilon_2$-DP तंत्र के रूप में व्यवहार करता है ($\delta > 0$ के लिए "लीकेज" घटक के साथ)।
  यह डबल-डीपी कंपोजिशन की समस्या को विषम कंपोजिशन (Heterogeneous Composition) की समस्या (अर्थात $x$ प्रकार-1 के तंत्र और $y$ प्रकार-2 के तंत्र का कंपोजिशन) में बदलने की अनुमति देता है।

• एल्गोरिदम 1 के माध्यम से सटीक गणना:
  वे $x$ $\epsilon_1$-DP और $y$ $\epsilon_2$-DP तंत्रों के विषम कंपोजिशन के लिए सटीक गोपनीयता क्षेत्र की गणना करने हेतु एक एल्गोरिदम प्रदान करते हैं। इसमें शामिल है:

  1. कंपोजिशन द्वारा उत्पन्न सभी संभावित लाइकलीहुड रेशियो स्लोप्स (likelihood ratio slopes) की पहचान करना।
  2. प्रत्येक स्लोप के लिए संगत $\delta$ ऑफसेट्स की गणना करना।
  3. परिणामी $(\epsilon, \delta)$ क्षेत्रों का प्रतिच्छेदन (intersection) करना।

3. मुख्य योगदान (Key Contributions)

A. डबल-डीपी के लिए सटीक कंपोजिशन थ्योरम्स (Exact Composition Theorems for Double-DP)

शोध पत्र दो थ्योरम प्रस्तुत करता है जो दो एक साथ बाधाओं को संतुष्ट करने वाले तंत्रों के $k$-फोल्ड कंपोजिशन के लिए सटीक गोपनीयता क्षेत्र $R^k(\epsilon, \delta)$ को परिभाषित करते हैं:

• थ्योरम 2: इस क्षेत्र को विषम कंपोजिशन क्षेत्रों $C_{i, k-i}(\epsilon_1, \epsilon_2)$ के मिश्रण के रूप में व्यक्त करता है। यह संरचनात्मक लेम्मा पर निर्भर करता है जो यह दर्शाता है कि डबल-कन्स्ट्रेंट तंत्रों का कंपोजिशन शुद्ध $\epsilon$-DP तंत्रों के कंपोजिशन के मिश्रण के बराबर है।
• थ्योरम 3: बिना विषम कंपोजिशन एल्गोरिदम को स्पष्ट रूप से बुलाए, सीधे कंपोज्ड तंत्र के लाइकलीहुड रेश्यो का विश्लेषण करके, इस क्षेत्र के लिए एक क्लोज्ड-फॉर्म एक्सप्रेशन (closed-form expression) प्रदान करता है।

B. विषम कंपोजिशन थ्योरम (Theorem 1)

लेखक $x$ संख्या में $(\epsilon_1, 0)$-DP और $y$ संख्या में $(\epsilon_2, 0)$-DP तंत्रों के कंपोजिशन के लिए सटीक गोपनीयता क्षेत्र व्युत्पन्न करते हैं।

• यह परिणाम स्वतंत्र रूप से भी महत्वपूर्ण है क्योंकि यह शुद्ध $\epsilon$-DP कंपोजिशन के पिछले कार्यों का सामान्यीकरण करता है।
• यह क्षेत्र की सीमाओं के क्लोज्ड-फॉर्म लक्षण वर्णन प्रदान करके मौजूदा विषम कंपोजिशन विधियों (जैसे मुरटाघ एट अल.) की तुलना में कम कम्प्यूटेशनल जटिलता प्रदान करता है।

C. $f$-DP कंपोजिशन का सन्निकटन (Approximation of $f$-DP Composition)

लेखक एक मनमाने $f$-DP तंत्र के कंपोजिशन को सन्निकट करने की विधि प्रस्तावित करते हैं:

1. सन्निकटन (Approximation): डबल-डीपी ट्रेड-ऑफ फंक्शनों का उपयोग करके लक्ष्य ट्रेड-ऑफ फंक्शन $f$ को नीचे से ($f_{\epsilon^-, \delta^-}$) और ऊपर से ($f_{\epsilon^+, \delta^+}$) सन्निकट करना। यह अनुकूल टेंजेंट लाइनों को खोजने के लिए फंक्शन ग्राफ के "नॉर्मल रोटेशन" के माध्यम से प्राप्त किया जाता है।
2. कंपोजिशन (Composition): इन बाउंडिंग डबल-डीपी तंत्रों के $k$-फोल्ड कंपोजिशन की गणना करने के लिए थ्योरम 2 और 3 का उपयोग करना।
3. परिणाम: यह कंपोज्ड $f$-DP तंत्र के गोपनीयता क्षेत्र पर सटीक निचले और ऊपरी स्तर (lower and upper bounds) प्रदान करता है।

4. परिणाम और मूल्यांकन (Results and Evaluation)

• सटीकता (Tightness): शोध पत्र प्रदर्शित करता है कि प्रस्तावित सीमाएँ (bounds) पिछले बेसलाइनों (जैसे व्यक्तिगत कंपोजिशन बाउंड्स का प्रतिच्छेदन या टोटल वेरिएशन बाउंड्स) की तुलना में काफी सटीक हैं, विशेष रूप से जैसे-जैसे कंपोजिशन की संख्या $k$ बढ़ती है।
• गौसियन मैकेनिज्म उदाहरण: गौसियन मैकेनिज्म (जो $G_\mu$-DP है) पर लागू होने पर, यह विधि ऐसे अनुभवजन्य बाउंड्स (empirical bounds) उत्पन्न करती है जो सटीक कंपोजिशन क्षेत्र की ओर तेजी से अभिसरण (converge) करते हैं।
• तुलना: परिणाम दिखाते हैं कि जबकि पिछले सन्निकटन (जैसे डोंग एट अल. द्वारा CLT दृष्टिकोण) स्पर्शोन्मुख रूप से (asymptotically) सटीक हैं, प्रस्तावित डबल-डीपी दृष्टिकोण बेहतर 'फाइनाइट-सैंपल' गारंटी प्रदान करता है और FFT-आधारित विधियों की कम्प्यूटेशनल जटिलता से बचता है।

5. महत्व (Significance)

• सैद्धांतिक प्रगति: यह कार्य सरल $(\epsilon, \delta)$-DP और अधिक सामान्य $f$-DP ढांचे के बीच के अंतर को पाटता है, जो कई एक साथ बाधाओं वाले तंत्रों के लिए पहले सटीक कंपोजिशन थ्योरम प्रदान करता है।
• व्यावहारिक उपयोगिता: यह जटिल गोपनीयता बजटों का विश्लेषण करने का एक कुशल तरीका प्रदान करता है जहाँ तंत्रों को कई मानदंडों (जैसे कुछ प्रश्नों के लिए सख्त $\epsilon$ सीमाएं और अन्य के लिए शिथिल $\delta$ सीमाएं) को संतुष्ट करना आवश्यक है।
• भविष्य के कार्य का आधार: हाइपोथीसिस टेस्टिंग के मिश्रणों के संबंध में संरचनात्मक लेम्मा एक सामान्य उपकरण प्रदान करता है। लेखक अनुमान लगाते हैं कि इस ढांचे को $n$-डीपी बाधाओं ($n$ एक साथ बाधाओं) के लिए सामान्य किया जा सकता है, जो जटिल प्रणालियों में अधिक सटीक गोपनीयता अकाउंटिंग का मार्ग प्रशस्त करता है।

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