Composition Theorems for Multiple Differential Privacy Constraints

إليك ملخص تقني مفصل لورقة "نظريات التركيب للقيود المتعددة للخصوصية التفاضلية" (Composition Theorems for Multiple Differential Privacy Constraints) من إعداد كادير، ونجيب، وشكيل.

1. بيان المشكلة

تتناول الورقة تحدي تركيب آليات الخصوصية التفاضلية (DP) عندما يجب أن تستوفي آلية واحدة قيود خصوصية تفاضلية متعددة في آن واحد.

• السياق: في العديد من تطبيقات الخصوصية، يُطلب من الآلية ألا تكتفي بتحقيق ضمان $(\epsilon, \delta)$-DP واحد فحسب، بل مجموعة منها (على سبيل المثال، تحقيق كل من $(\epsilon_1, \delta_1)$-DP و $(\epsilon_2, \delta_2)$-DP في وقت واحد). غالبًا ما ينشأ هذا عند تقريب الخصوصية التفاضلية من نوع $f$ ($f$-DP)، حيث يتم تقريب دالة المقايضة $f$ عبر تقاطع عدة قيود $(\epsilon, \delta)$.
• الفجوة: تتعامل نظريات التركيب الحالية (مثل أعمال كيروز وآخرون، وغازي وآخرون، ودونغ وآخرون) بشكل أساسي مع القيود الفردية أو الحالات غير المتجانسة المحددة (مثل $\epsilon$-DP الصرفة). لم يكن هناك إطار عمل دقيق للتركيب $k$-fold للآليات التي تستوفي قيود الخصوصية المزدوجة (double-DP) (أو $n$-DP) في آن واحد.
• الهدف: اشتقاق مناطق تركيب دقيقة للآليات التي تستوفي قيود خصوصية تفاضلية متعددة، واستخدام ذلك لتوفير تقريبات أكثر إحكامًا لتركيب $f$-DP.

2. المنهجية

يستفيد المؤلفون من منظور اختبار الفرضيات للخصوصية التفاضلية، حيث تُوصَف الخصوصية من خلال دالة المقايضة بين خطأ النوع الأول (Type I) وخطأ النوع الثاني (Type II).

• تمهيدية هيكلية للمزيج (التمهيدية 1):
  المساهمة النظرية الجوهرية هي تمهيدية تصف دالة المقايضة لـ مزيج من اختبارات الفرضيات. إذا كانت الآلية $M$ عبارة عن مزيج احتمالي من $n$ من الآليات الفرعية بأوزان $\alpha_i$ ودوال مقايضة $f_i$، فإن دالة المقايضة الناتجة $f_m$ هي الالتفاف السفلي الموزون (weighted infimal convolution) لدوال المقايضة الفردية $f_i$:
  $$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)$$
  هندسياً، منطقة الخصوصية للمزيج هي الغلاف المحدب (المجموع الموزون) لمناطق الخصوصية الفردية.

• الاختزال إلى التركيب غير المتجانس:
  يوضح المؤلفون أن الآلية التي تستوفي قيود $(\epsilon_1, \delta_1)$ و $(\epsilon_2, \delta_2)$ في آن واحد يمكن نمذجتها كمزيج من آليات أبسط. وتحديداً، يقومون ببناء آلية تتصرف كآلية $\epsilon_1$-DP باحتمال $1-\alpha$ وآلية $\epsilon_2$-DP باحتمال $\alpha$ (بالإضافة إلى مكون "تسريب" لـ $\delta > 0$).
  يسمح هذا باختزال مشكلة تركيب الخصوصية المزدوجة (Double-DP composition) إلى مشكلة التركيب غير المتجانس (تركيب $x$ من الآليات من النوع 1 و $y$ من الآليات من النوع 2).

• الحساب الدقيق عبر الخوارزمية 1:
  يقدم المؤلفون خوارزمية لحساب منطقة الخصوصية الدقيقة للتركيب غير المتجانس لـ $x$ من آليات $\epsilon_1$-DP و $y$ من آليات $\epsilon_2$-DP. يتضمن ذلك:

  1. تحديد جميع ميول نسب الاحتمال (likelihood ratio slopes) الممكنة الناتجة عن التركيب.
  2. حساب إزاحات $\delta$ المقابلة لكل ميل.
  3. تقاطع مناطق $(\epsilon, \delta)$ الناتجة.

3. المساهمات الرئيسية

أ. نظريات التركيب الدقيقة للخصوصية المزدوجة (Double-DP)

تقدم الورقة نظريتين تصفان منطقة الخصوصية الدقيقة $R^k(\epsilon, \delta)$ للتركيب $k$-fold للآليات التي تستوفي قيدين متزامنين:

• النظرية 2: تعبر عن المنطقة كمزيج من مناطق التركيب غير المتجانس $C_{i, k-i}(\epsilon_1, \epsilon_2)$. وهي تعتمد على التمهيدية الهيكلية لإظهار أن تركيب آليات القيود المزدوجة يكافئ مزيجاً من تركيبات آليات $\epsilon$-DP الصرفة.
• النظرية 3: توفر تعبيراً بصيغة مغلقة (closed-form expression) للمنطقة دون استدعاء خوارزمية التركيب غير المتجانس صراحة، وذلك من خلال تحليل نسب الاحتمال للآلية المركبة مباشرة.

ب. نظرية التركيب غير المتجانس (النظرية 1)

يشتق المؤلفون منطقة الخصوصية الدقيقة لتركيب $x$ من آليات $(\epsilon_1, 0)$-DP و $y$ من آليات $(\epsilon_2, 0)$-DP.

• هذه النتيجة ذات أهمية مستقلة لأنها تعمم العمل السابق على تركيب $\epsilon$-DP الصرف.
• توفر تعقيداً حسابياً أقل مقارنة بطرق التركيب غير المتجانس الموجودة (مثل أعمال مورتغ وآخرون) من خلال توفير توصيف لصيغة مغلقة لحدود المنطقة.

ج. تقريب تركيب $f$-DP

يقترح المؤلفون طريقة لتقريب تركيب آلية $f$-DP عشوائية:

1. التقريب: تقريب دالة المقايضة المستهدفة $f$ من الأسفل ($f_{\epsilon^-, \delta^-}$) ومن الأعلى ($f_{\epsilon^+, \delta^+}$}$) باستخدام دوال مقايضة Double-DP. ويتم ذلك عبر "دوران طبيعي" لرسم دالة المخطط لإيجاد خطوط المماس المثلى.
2. التركيب: استخدام النظريتين 2 و 3 لحساب التركيب $k$-fold الدقيق لهذه الآليات المزدوجة (Double-DP) المحيطة.
3. النتيجة: ينتج عن ذلك حدود دنيا وعليا محكمة لمنطقة الخصوصية لآلية $f$-DP المركبة.

4. النتائج والتقييم

• الإحكام (Tightness): تثبت الورقة أن الحدود المقترحة أكثر إحكاماً بشكل ملحوظ من المراجع السابقة (مثل تقاطع حدود التركيب الفردية أو حدود التباين الكلي) خاصة مع زيادة عدد التراكيب $k$.
• مثال آلية غاوس (Gaussian Mechanism): عند تطبيق الطريقة على آلية غاوس (التي هي $G_\mu$-DP)، تنتج الطريقة حدوداً تجريبية تتقارب بسرعة مع منطقة التركيب الدقيقة.
• المقارنة: تظهر النتائج أنه بينما تكون التقريبات السابقة (مثل نهج نظر المركز المحدود من قبل دونغ وآخرون) دقيقة تقاربياً، فإن نهج الـ Double-DP المقترح يوفر ضمانات أفضل للعينات المحدودة ويتجنب التعقيد الحسابي لطرق FFT (تحويل فوريه السريع).

5. الأهمية

• التقدم النظري: يجسّر هذا العمل الفجوة بين $\epsilon, \delta$-DP البسيطة وإطار عمل $f$-DP الأكثر عمومية من خلال تقديم أول نظريات تركيب دقيقة للآليات ذات القيود المتعددة في آن واحد.
• الفائدة العملية: يوفر طريقة فعالة حسابياً لتحليل ميزانيات الخصوصية المعقدة حيث يجب أن تستوفي الآليات معايير متعددة (على سبيل المثال، حدود $\epsilon$ صارمة لبعض الاستعلامات وحدود $\delta$ مخففة لأخرى).
• أساس للأعمال المستقبلية: توفر التمهيدية الهيكلية المتعلقة بمزيج اختبارات الفرضيات أداة عامة لتحليل آليات الخصوصية المعقدة. ويشير المؤلفون إلى إمكانية تعميم هذا الإطار لـ $n$-DP (قيود متعددة في آن واحد)، مما يمهد الطريق لمحاسبة خصوصية أكثر دقة في الأنظمة المعقدة.

باختاًصار، تقدم الورقة إطاراً رياضياً رصيناً للتعامل مع تركيب الآليات تحت قيود خصوصية معقدة ومتعددة الأوجه، مما يحسن بشكل كبير من دقة محاسبة فقدان الخصوصية في تطبيقات الخصوصية التفاضلية العملية.