ملخص تقني: المعدلات المثلى لاختبار الفرضيات ذي الخصوصية التفاضلية باستخدام قيم-e

بيان المشكلة

يتناول هذا العمل المشكلة الجوهرية لاختبار الفرضية البسيطة تحت قيود الخصوصية التفاضلية المركزية (Central DP). وتحديداً، يبحث المؤلفون في اختبار مجموعة بيانات $X \sim P^n$ (الفرضية الصفرية) مقابل $X \sim Q^n$ (الفرضية البديلة) باستخدام قيم-e (e-values).

في الإطار الكلاسيكي، يُقاس أداء الاختبار من خلال قدرته (معدل الإيجاب الحقيقي). أما في إطار قيم-e، فيُقاس الأداء بـ قدرة-e (e-power)، والتي تُعرف بـ $\mathbb{E}_Q[\log E]$، حيث $E$ متغير عشوائي غير سالب يحقق $\mathbb{E}_P[E] \le 1$. السؤال الجوهري هو: ما هي أقصى قدرة-e يمكن تحقيقها لقيمة-e تتبع $\varepsilon$-DP عند اختبار $P$ ضد $Q$؟

لقد نظر المؤلفون في حالتين:

1. إعداد الدفعات (Batch Setting): تتوفر جميع نقاط البيانات الـ $n$ في وقت واحد.
2. الإعداد المتسلسل (Sequential Setting): تصل البيانات واحدة تلو الأخرى، ويختار المحلل زمن التوقف $N$ بشكل تكيفي. والهدف هو تقليل زمن التوقف المتوقع $\mathbb{E}_Q[N]$ المطلوب لتحقيق مستوى معين من الأدلة الإحصائية.

بينما توجد أعمال سابقة حول اختبار الفرضيات ذي الخصوصية التفاضلية في الإطار اتخاذي القرار (المخرجات الثنائية) وعلى قيم-e تحت الخصوصية التفاضلية المحلية (Local DP)، يركز هذا البحث على قيم-e ذات الخصوصية التفاضلية المركزية، وهو إطار لم يوجد فيه سوى أعمال محدودة سابقاً (تحديداً عمل Csillag و Mesquita [10]، والذي كان مقتصرًا على نسب الاحتمال المحدودة).

المنهجية

1. توصيف القدرة-e المثلى (إعداد الدفعات)

يقوم المؤلفون بفصل آلية الخصوصية عن بناء متغير-e. وقد لاحظوا أنه لأي آلية $\varepsilon$-DP ثابتة $M$، فإن المعالجة اللاحقة المثلى لإنشاء متغير-e هي نسبة الاحتمال لتوزيعات المخرجات، $dM(Q^n)/dM(P^n)$. وبالتالي، تتقلص المشكلة إلى تعظيم تباعد كولباك - ليبلر (KL divergence) بين توزيعات المخرجات للآلية:
$$R_{\varepsilon}(Q \| P) = \lim_{n \to \infty} \sup_{M \in \varepsilon\text{-DP}} \frac{1}{n} KL(M(Q^n) \| M(P^n))$$

ولحل هذه المشكلة، قدم المؤلفون توزيعاً وسيطاً $\tilde{Q}$. حيث يقومون ببناء $\tilde{Q}$ عن طريق تعديل كثافة $Q$ بالنسبة لـ $P$ في مناطق محددة معرفة بنسبة الاحتمال $q(x)/p(x)$:

• المنطقة A (نسبة احتمال منخفضة): $q(x) < c_1 p(x)$. هنا، $\tilde{q}(x) = c_1 p(x)$.
• المنطقة B (نسبة احتمال عالية): $q(x) > c_2 p(x)$. هنا، $\tilde{q}(x) = c_2 p(x)$.
• المنطقة M (الوسطى): $\tilde{q}(x) = q(x)$.

يتم تحديد الثوابت $c_1, c_2$ والمناطق بواسطة مضاعف لاجرانج $\lambda^*$ الذي يحل معادلة ضمنية تضمن أن $\tilde{Q}$ هو توزيع احتمالي صالح. هذا البناء يقلل من الدالة الوظيفية $KL(Q' \| P) + \varepsilon \cdot TV(Q', Q)$.

يثبت المؤلفون أن المعدل الأمثل هو بالضبط:
$$R_{\varepsilon}(Q \| P) = KL(\tilde{Q} \| P) + \varepsilon \cdot TV(\tilde{Q}, Q)$$

بعد ذلك، يقومون ببناء متغير-e غير خاص $E^*$ بناءً على هذا الـ $\tilde{Q}$ (تحديداً نسبة احتمال مقصوصة) والتي تمتلك حساسية لوغاريتمية محدودة $\varepsilon$. ولجعلها خاصة بالخصوصية، يقترحون دالة دمج $\Lambda_n$ بناءً على عمل Vovk و Wang، حيث يتم إضافة ضجيج لابلاسي (Laplacian noise) مع معوض مُعاير بعناية للحفاظ على خاصية المتغير-e مع الحفاظ على الأمثلية التقاربية.

2. الإعداد المتسلسل وأزمنة التوقف

في الإعداد المتسلسل، يعرّف المؤلفون عملية-e (e-process) ذات $\varepsilon$-DP كمتتالية من قيم-e يتم إنتاجها بواسطة آلية $\varepsilon$-DP. وقد وضعوا حداً أدنى لزمن التوقف المتوقع لأي عملية من هذا النوع.

باستخدام حجة دالة الجهد (potential function) تتضمن اقتراناً (coupling) بين التوزيع الحقيقي $Q$ والتوزيع الوسيط $\tilde{Q}$، يثبتون أنه لأي زمن توقف $N$:
$$\mathbb{E}_Q[\log E_N] \le \mathbb{E}_Q[N] \cdot R_{\varepsilon}(Q \| P)$$
وهذا يعني حداً أدنى لتعقيد العينة المطلوب لتحقيق قدرة معينة.

ولمطابقة هذا الحد، يقترحون الخوارزمية 1، وهي "تحويل الدفعات إلى عملية-e". تقوم هذه الخوارزمية بما يلي:

• تأخذ متغير-e غير خاص ذا حساسية لوغاريتمية محدودة.
• تعالج البيانات في دفعات متزايدة الحجم.
• تطبق دالة دمج خاصة بالخصوصية (مشابهة لحالة الدفعات) في نهاية كل دفعة.
• تستخدم علاقة تكرارية محددة لتحديد أحجام الدفعات، مما يحسن المقايضة بين وقت "البداية" الأولي والنسبة التنافسية طويلة الأمد.

المساهمات والنتائج الرئيسية

1. نتيجة الصعوبة الخاصة بالحالة (Theorem 2.2): تقدم الورقة صيغة صريحة وقابلة للحساب لأقصى قدرة-e يمكن تحقيقها تحت $\varepsilon$-DP. ويتم توصيف هذا المعدل من خلال تباعد KL إلى توزيع وسيط $\tilde{Q}$ مضافاً إليه عقوبة التباين الكلي (total variation penalty).
2. بناء خوارزمية مثلى (Theorem 2.4): يبني المؤلفون متغير-e ذو $\varepsilon$-DP يحقق هذا المعدل الأمثل تقاربياً. يتضمن البناء عملية قص محددة لنسبة الاحتمال متبوعة بمخطط للخصوصية باستخدام ضجيج لابلاسي ومعوض (compensator).
3. الحد الأدنى المتسلسل (Theorem 3.1): يستنتجون حداً أدنى عالمياً لزمن التوقف المتوقع لأي عملية-e ذات $\varepsilon$-DP، موضحين أنه يتناسب عكسياً مع معدل القدرة-e الأمثل $R_{\varepsilon}(Q \| P)$.
4. خوارزمية متسلسلة مثلى (Theorem 3.2): يقدمون الخوارزمية 1، التي تحول متغير-e غير خاص إلى عملية-e ذات $\varepsilon$-DP. تطابق هذه الخوارزمية الحد الأدنى النظري لأزمنة التوقف حتى معامل ضرب ثابت (النسبة التنافسية) لجميع أزمنة التوقف الكبيرة بما يكفي.
5. بديل مستقل عن التوزيع (الملحق C): إدراكاً منهم أن حساب $\tilde{Q}$ الأمثل قد يكون مستعصياً في الحالات المعقدة، يقترحون إحصائية "نسبة الاحتمال المقطوعة والمدرجة" (tsLR). تحقق هذه الإحصائية المستقلة عن التوزيع معدلاً يقع ضمن عامل ثابت من المعدل الأمثل.

التحقق التجريبي

أجرى المؤلفون تجارب عددية لمقارنة الخوارزمية 1 الخاصة بهم مع اختبار DP-SPRT (اختبار نسبة الاحتمال المتسلسل ذي الخصوصية التفاضلية) المقترح من قبل Michel وآخرون [25].

• الإعداد: اختبار $P = \text{Bernoulli}(0.3)$ مقابل $Q = \text{Bernoulli}(q)$.
• المقياس: دوال التوزيع التراكمي (CDFs) لأزمنة التوقف.
• النتيجة: عبر مستويات خصوصية مختلفة ($\varepsilon$) وتوزيعات بديلة مختلفة ($q$)، توقفت العملية-e المقترحة باستمرار في وقت أبكر من DP-SPRT. ومن الجدير بالذكر أن هذا التحسن في الأداء تم تحقيقه رغم أن الخوارزمية المقترحة لا تضع أي افتراضات معلمية (parametric assumptions) حول البيانات، بينما صُمم DP-SPRT خصيصاً للعائلات الأسية (exponential families).

الأهمية والادعاءات

تدعي الورقة أنها توفر فهماً كاملاً للحدود الجوهرية لاختبار الفرضيات البسيطة باستخدام قيم-e تحت الخصوصية التفاضلية المركزية.

• الأساس النظري: من خلال توصيف المعدل الأمثل $R_{\varepsilon}(Q \| P)$ وتوفير خوارزمية تطابقه، يضع هذا العمل حجر الأساس لما يمكن تحقيقه في التحليل المتسلسل الحافظ للخصوصية.
• الفائدة العملية: تتطلب الخوارزميات المقترحة بيانات أقل (أزمنة توقف أقل) من الطرق الحالية (مثل DP-SPRT) عبر مجموعة من الإعدادات.
• الاتجاهات المستقبلية: يشير المؤلفون إلى أن نتائج الصعوبة الخاصة بهم وتقنياتهم (تحديداً استخدام الأزواج الأقل تفضيلاً/least-favorable pairs) يمكن أن تعمل كأساس لتوسيع هذه النتائج إلى اختبار الفرضيات المركبة والتقدير ذي الخصوصية التفاضلية الأمثل حسب الحالة، على غرار العمل التأسيسي في المجالات غير الخاصة التي دفعت التقدم في تلك المجالات. كما يشيرون إلى أن توسيع هذه النتائج لتشمل الخصوصية التفاضلية التقريبية ($\delta > 0$) لا يزال سؤالاً مفتوحاً.