Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits

ملخص تقني: الخصوصية التفاضلية للخلط والخصوصية المشتركة للمتعدد الأذرع السياقي ذي الخطوط العامة (GLM)

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

تتناول الورقة مشكلة المتعدد الأذرع السياقي ذي الخطوط العامة (GLM Bandits) تحت قيود الخصوصية. في إعداد المتعدد الأذرع السياقي القياسي، يختار المتعلم ذراعاً من مجموعة مكونة من $K$ من الأذرع (يمثل كل منها متجه ميزات ذي $d$ من الأبعاد) لتعظيم المكافآت التراكمية. في نماذج GLM، يتم أخذ عينة من المكافأة من توزيع عائلة أسية حيث يكون المتوسط دالة غير خطية (دالة الربط $\mu$) للمنتج الداخلي بين السياق والمعامل المجهول $\theta^*$.

بينما ركزت الأعمال السابقة على المتعدد الأذرع الخطي (Linear Bandits) (الذي يسمح بوجود مقدرات ريج (ridge) ذات صيغة مغلقة)، تفرض نماذج GLM ثلاث عقبات تقنية أساسية:

1. عدم وجود مقدر بصيغة مغلقة: يتطلب تقدير $\theta^*$ تحسيناً محدباً تكرارياً، مما يستهلك ميزانية الخصوصية ويؤدي إلى خطأ في التحسين.
2. مصفوفات التصميم غير الرتيبة: في الإعدادات العدائية، تؤدي آليات الخصوصية (مثل آلية الشجرة الثنائية) إلى إدخال ضوضاء تجعل مصفوفات التصميم غير رتيبة، مما يكسر تقنيات تحليل الندم القياسية.
3. تسرب الخصوصية: في الإعدادات التكيفية، يمكن أن يؤدي توقيت "تبديل السياسات" (عندما يقوم المتعلم بتحديث نموذجه) في حد ذاته إلى تسريب معلومات حساسة عن البيانات.

2. المنهجية

يستقصي المؤلف نموذجين مختلفين للخصوصية وإعدادات السياق:

• النموذج 1 (السياقات العشوائية + خصوصية الخلط - Shuffle DP): تُسحب السياقات بشكل مستقل وموزع (i.i.d.) من توزيع مجهول. تستخدم الورقة نموذج خصوصية الخلط (SDP)، حيث يطبق المستخدمون عشوائية محلية ويقوم "خلاط" موثوق بتبديل الرسائل. يوفر هذا حلاً وسطاً بين الخصوصية المحلية (Local DP) الضعيفة والخصوصية المركزية (Central DP) القوية.
• النموذج 2 (السياقات العدائية + الخصوصية المشتركة - Joint DP): قد يتم اختيار السياقات من قبل خصم. تستخدم الورقة الخصوصية التفاضلية المشتركة (JDP)، والتي تتطلب أن يكون الإجراء عند الزمن $t$ خاصاً بالنسبة لجميع أزواج السياق والمكافأة الأخرى.

الأطر الخوارزمية:

• الخوارزمية 1 (ShuffleGLM): تعتمد نهج الدفعات (batched approach). تستخدم تصميم G-optimal لاختيار الذراع ومحسن محدب خاص بالخلط (الاشتقاق المتدرج المسقط - Projected Gradient Descent) لتقدير $\theta^*$ في نهاية كل دفعة. وتستخدم نهج "الذراع المقيّس" لضمان بقاء حساسية بروتوكول الجمع المخلط محدودة.
• الخوارزمية 2 (Joint-DP GLM): مصممة للإعداد العدائي. تستخدم آلية الشجرة الثنائية لإصدار مصفوفات التصميم بشكل مستمر. كما تقدم معيار نمو اتجاهي للتعامل مع المصفوفات الصاخبة غير الرتيبة، ومحسن DP-SGD متخصص للتعامل مع تحديثات السياسة.

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

• أول نماذج GLM تحت خصوصية الخلط/الخصوصية المشتركة: هذا هو العمل الأول الذي يوسع هذه النماذج للخصوصية لتشمل إعدادات الخطوط العامة، متجاوزاً الافتراضات الطيفية المقيدة التي تطلبتها أعمال الخصوصية المحلية السابقة.
• إزالة $\kappa$ من الحد الرئيسي للندم: في نماذج GLM، يمكن للمعامل $\kappa$ (المتعلق بانحناء دالة الربط) أن ينمو أسياً مع معيار المعامل. نجح المؤلف في تصميم خوارزميات حيث يظهر $\kappa$ فقط في الحدود الفرعية، مما يضمن أن الحد الرئيسي $\sqrt{T}$ "خالٍ من $\kappa$".
• خصوصية أوقات التبديل: تقدم الورقة برهاناً جديداً على أن توقيت تحديثات السياسة (الذي يعتمد على البيانات) لا ينتهك ضمانات الخصوصية، وذلك باستخدام تفكيك نسبة الاحتمال (log-likelihood-ratio) عبر الشجرة الثنائية.
• المتانة تجاه السياقات: على عكس العمل السابق، لا تتطلب النتائج افتراضات طيفية محددة (مثل القيم الذاتية الدنيا) على توزيع السياق، بل تتطلب فقط حدود $\ell_2$.

4. النتائج

تقدم الورقة حدود ندم صارمة لكلا الإعدادين:

• خصوصية الخلط (العشوائية): تحقق ندماً قدره $\tilde{O}\left(\frac{d^{3/2}\sqrt{T}}{\sqrt{\kappa^* \epsilon}}\right)$. هذا المعدل قريب من المثالية، حيث يختلف عن المعدل غير الخاص بعامل $\sqrt{d}/\epsilon$.
• الخصوصية المشتركة (العدائية): تحقق ندماً قدره $\tilde{O}\left(\sqrt{d\sqrt{T}\log T} + \frac{d^{3/4}\sqrt{T}}{\sqrt{\epsilon}} \dots \right)$. والأهم من ذلك أن الحد الرئيسي يطابق المعدل غير الخاص $\tilde{O}(d\sqrt{T}\log T)$، مما يعني أن الخصوصية تساهم فقط بتصحيح إضافي.
• التحقق التجريبي: تُظهر المحاكاة على نماذج Probit وLogistic أن الخوارزمية المقترحة تظل مستقرة حتى مع زيادة عدم الخطية ($\kappa$)، متفوقة على خوارزميات GLM-UCB وGLOC القياسية.

5. الأهمية

هذا العمل مهم لأنه يسد الفجوة بين نماذج الخصوصية النظرية ونماذج المكافأة غير الخطية العملية. من خلال إثبات إمكانية تحقيق الخصوصية بندم "شبه مجاني" (حيث لا يتأثر الحد الرئيسي بمعامل الخصوصية $\epsilon$ في الحالة العدائية)، توفر الورقة مخططاً لنشر أنظمة المتعدد الأذرع السياقي في المجالات شديدة الحساسية مثل الرعاية الصحية، وتوصيات الأخبار، والتعليم الشخصي دون التضحية بالمنفعة بشكل كبير.