Differentially Private Best-Arm Identification

إليك ملخص تقني مفصل للورقة البحثية بعنوان "تحديد أفضل ذراع بخصوصية تفاضلية" (Differentially Private Best-Arm Identification) من إعداد Azize وآخرون.

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

تتناول الورقة مشكلة تحديد أفضل ذراع (Best Arm Identification - BAI) ضمن إطار الثقة الثابتة (Fixed-Confidence - FC)، مع تعزيزها بقيود الخصوصية التفاضلية (Differential Privacy - DP).

• السياق: في مسألة FC-BAI، يتفاعل وكيل مع $K$ من توزيعات المكافآت غير المعروفة (الأذرع) لتحديد الذراع ذات المتوسط الأعلى ($a^*$) باحتمالية لا تقل عن $1-\delta$. الهدف هو تقليل تعقيد العينات (عدد السحبات $\tau_\delta$) المطلوب لتحقيق هذه الثقة.
• نماذج الخصوصية: يدرس المؤلفون نموذجين مختلفين من نماذج الثقة:
  1. الخصوصية المحلية $\epsilon$-LDP: لا يثق المستخدمون في المنسق المركزي. يقوم كل مستخدم بتعديل مكافأته الخاصة قبل إرسالها إلى الخوارزمية.
  2. الخصوصية العالمية $\epsilon$-GDP: يثق المستخدمون في المنسق المركزي، الذي لديه إمكانية الوصول إلى المكافآت الخام، ولكن يجب عليه ضمان أن المخرجات النهائية (وربما تاريخ التفاعل) تحقق الخصوصية التفاضلية.
• الدوافع: تتضمن تطبيقات مثل التجارب السريرية التكيفية، وضبط المعلمات الفائقة (hyperparameter tuning)، والدراسات المستخدمة بيانات حساسة حيث يمكن أن يؤدي الكشف عن تسلسل الإجراءات أو المكافآت إلى تسريب معلومات خاصة.

2. المنهجية والإطار النظري

2.1 الحدود الدنيا (تعقيد العينات)

يستنتج المؤلفون حدوداً دنيا أساسية لمتوسط تعقيد العينات لأي خوارزمية تحقق شرط $\delta$ وتلتزم بالخصوصية التفاضلية. ومن النتائج الرئيسية وجود نظامين للخصوصية:

• نظام الخصوصية المنخفضة: عندما تكون ميزانية الخصوصية $\epsilon$ كبيرة، يتطابق تعقيد العينات مع الحد الأدنى غير الخاص (الذي يحكمه تباعد كولباك - ليبلر (KL)). يمكن تحقيق الخصوصية هنا "مجاناً".
• نظام الخصوصية العالية: عندما تكون $\epsilon$ صغيرة، يهيمن قيود الخصوصية على تعقيد العينات.
  • بالنسبة لـ $\epsilon$-LDP: يعتمد الصعوبة على مربع مسافة التباين الكلي (Total Variation - TV). يتضمن الحد الأدنى زمناً مميزاً $T^*_{TV2}$، يتناسب مع $\mathcal{O}(\epsilon^{-2} T^*_{TV2})$. ويصبح مقياس التمييز هو $\min\{KL, c(\epsilon)TV^2\}$.
  • بالنسبة لـ $\epsilon$-GDP: تعتمد الصعوبة على مسافة التباين الكلي (TV) (وليس مربعها). يتضمن الحد الأدنى زمناً مميزاً $T^*_{TV}$، يتناسب مع $\mathcal{O}(\epsilon^{-1} T^*_{TV})$. ومقياس التمييز هو $\min\{KL, \epsilon \cdot TV\}$.

يثبت المؤلفون هذه الحدود باستخدام حجج الاقتران المتسلسل (sequential coupling arguments) المبتكرة و"لمة تغيير القياس" المعممة والمكيفة للخصوصية التفاضلية، والتي تربط تباعد KL لنتائج الضجيج بمسافة TV للتوزيعات الأساسية.

2.2 تصميم الخوارزمية

تقترح الورقة متغيرات من خوارزميات "أعلى اثنين" (Top Two - TT)، وتحديداً بناءً على الخوارزمية الميتا (meta-algorithm) المسماة TTUCB (Jourdan & Degenne, 2024)، والتي تختار ذراع "القائد" وذراع "المتحدي" في كل خطوة.

أ. لـ $\epsilon$-الخصوصية المحلية (LDP): خوارزمية CTB-TT

• الآلية: تستخدم مُقدّر "التحويل إلى برنولي" (Convert-To-Bernoulli - CTB) القائم على الاستجابة العشوائية (Randomized Response).
• الاستراتيجية: تقوم فعلياً بتحويل مسألة البنديت (bandit) الأصلية إلى مسألة برنولي معدلة حيث يتم تغيير متوسطاتها بواسطة ضجيج الخصوصية.
• الأداء: الخوارزمية مثالية تقاربيًا؛ فهي تستعيد الحد الأدنى غير الخاص حتى عامل ثابت (2 في الحد غير الخاص، و4 في حد الخصوصية العالية).

ب. لـ $\epsilon$-الخصوصية العالمية (GDP): خوارزميتا AdaP-TT و AdaP-TT$^\star$
للتعامل مع الخصوصية العالمية بكفاءة، قدم المؤلفون مُقدّر DAF ($\epsilon$) (التعميد والنسيان - Doubling-And-Forgetting).

• آلية DAF:

  1. التعميد (Doubling): يتم تحديث تقديرات المتوسط فقط عندما يتضاعف عدد السحبات لذراع معين.
  2. النسيان (Forgetting): يتم التخلص من الملاحظات الماضية من "المراحل" (episodes) السابقة لذراع ما.
  3. الضجيج: إضافة ضجيج لابلاس (Laplace noise) مُعاير إلى المتوسط التجريبي للمرحلة الحالية.
  • الأهمية: يسم هذا الهيكل الخوارزمية على تحقيق $\epsilon$-GDP دون الحاجة إلى التركيب المتسلسل لفقدان الخصوصية، حيث أن كل مرحلة مستقلة.

• AdaP-TT (نهج الإدخال المباشر - Plug-in Approach):

  • يستخدم مُقدّر DAF ولكنه يحتفظ بـ تكاليف النقل غير الخاصة (القائمة على تباعد KL) لاختيار المتحدي وقاعدة التوقف.
  • القصور: رغم أنها تحقق $\delta$-صحة، إلا أنها غير مثالية في نظام الخصوصية العالية للحالات ذات الفجوات المتوسطة غير المتجانسة. فهي تفشل في مطابقة الحد الأدنى لأنها لا تأخذ في الاعتبار البنية المحددة لضجيج الخصوصية في تكلفة النقل.

• AdaP-TT$^\star$ (النهج المُكيف):

  • الابتكار: تعدل تكاليف النقل وعتبة التوقف لتشمل صراحةً ميزانية الخصوصية $\epsilon$.
  • الآلية: تستخدم تكلفة النقل $W^{G,\epsilon}_{a,b}$ متوسط فجوة مقصوصة $\min\{\epsilon/2, \Delta\}$، مما يعكس الحد الأدنى المستنتج لنظام الخصوصية العالمية. كما يتم تكييف عتبة التوقف لتكون "واعية بالمتوسط".
  • الأداء: تحقق هذه الخوارزمية المثالية التقاربية في نظام الخصوصية العالية (حتى عامل ضرب صغير، مثلاً 48)، وهي تضاهي الحد الأدنى المستنتج. وهي تتفوق على AdaP-TT عندما $\epsilon \to 0$.

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

1. الحدود الأساسية: أول استنتاج للحدود الدنيا الوثيقة لتعقيد العينات في FC-BAI تحت كل من $\epsilon$-LDP و $\epsilon$-GDP. يحدد العمل أن مسافة التباين الكلي (TV) (ومربعها) هي المقياس الطبيعي للصعوبة الناجمة عن الخصوصية، بدلاً من تباعد KL في نظام الخصوصية العالية.
2. النظامان: توصيف دقيق للانتقال بين نظامي الخصوصية المنخفضة (الذي يهيمن عليه KL) والخصوصية العالية (الذي يهيمن عليه TV).
3. الحلول الخوارزمية:
   • CTB-TT: خوارزمية LDP مثالية تستخدم الاستجابة العشوائية.
   • مُقدّر DAF: مُقدّر متوسط خاص لـ GDP باستخدام تقنيتي التعميد والنسيان لتجنب تكاليف التركيب.
   • AdaP-TT$^\star$: أول خوارزمية تحقق المثالية التقاربية لـ $\epsilon$-GDP في نظام الخصوصية العالية عبر تكييف تكاليف النقل مع ميزانية الخصوصية $\epsilon$.
4. التحقق التجريبي: تؤكد التجارب الواسعة على نماذج برنولي وجود النظامين نظرياً وتفوق AdaP-TT$^\star$ على النماذج المرجعية (مثل DP-SE) وعلى نهج الإدخال المباشر (AdaP-TT) في إعدادات الخصوصية العالية.

4. النتائج

• الحدود الدنيا:
  • LDP: $E[\tau_\delta] \gtrsim \max(T^*_{KL}, \epsilon^{-2} T^*_{TV2})$.
  • GDP: $E[\tau_\delta] \gtrsim \max(T^*_{KL}, \epsilon^{-1} T^*_{TV})$.
• الحدود العليا:
  • CTB-TT: يطابق الحد الأدنى لـ LDP حتى عامل ثابت (الحد هو 4 عندما $\epsilon \to 0$).
  • AdaP-TT: يطابق الحد غير الخاص حتى عامل 16 في نظام الخصوصية المنخفضة، ولكنه غير مثالي في نظام الخصوصية العالية.
  • AdaP-TT$^\star$: يطابق الحد الأدنى لـ GDP حتى عامل ثابت (الحد هو 48 عندما $\epsilon \to 0$) في نظام الخصوصية العالية.
• التكيفية: تتطلب الخوارزميات المقترحة فقط $O(K \log^2(T^*_{KL} \log(1/\delta)))$ من جولات التكيف (الدفعات)، مما يجعلها عملية في الإعدادات التي يكون فيها التواصل المتكرر مكلفاً.

5. الأهمية

تجسّر هذه الورقة فجوة حرجة في الأدبيات من خلال الانتقال من تقليل الندم (regret minimization) إلى تحديد أفضل ذراع (Best Arm Identification) تحت الخصوصية التفاضلية.

• الأثر النظري: تثبت أن "تكلفة الخصوصية" في BAI تختلف جوهرياً عن تقليل الندم، حيث تعتمد على مسافات التباين الكلي (TV) بدلاً من مجرد تباعد KL. كما تقدم أول حدود عليا ودنيا متطابقة لنظام الخصوصية العالية في الخصوصية العالمية (GDP).
• الأثر العملي: توفر الخوارزميات المقترحة (خاصة AdaP-TT$^\star$) إطاراً عملياً لإجراء تجارب تكيفية تحافظ على الخصوصية (مثل التجارب السريرية، أو اختبارات A/B) حيث يكون الهدف هو تحديد العلاج أو المعلمة المثلى، وليس مجرد تقليل الخسارة التراكمية. توفر تقنية "التعميد والنسيان" (Doubling-And-Forgetting) طريقة قوية لإدارة ميزانيات الخصوصية في التعلم المتسلسل دون تراكم مفرط للضجيج.