ملخص تقني: مرشحات الخصوصية التفاضلية f-Differential Privacy: الصلاحية والحلول التقريبية

بيان المشكلة

تتناول الورقة البحثية تحدي حساب فقدان الخصوصية تحت التركيب التكيفي الكامل (fully adaptive composition) في الخصوصية التفاضلية (DP). في الإعدادات التكيفية بالكامل، قد يعتمد اختيار الآليات ومعايير الخصوصية الخاصة بها على تاريخ المخرجات السابقة، وهو سيناريو شائع في الخوارزميات التكرارية مثل التدرج الاشتقاقي العشوائي ذي الخصوصية التفاضلية (DP-SGD).

بينما توجد مرشحات خصوصية (قواعد إيقاف) لـ $(\epsilon, \delta)$-DP وRényi DP (RDP)، فإن صلاحية المرشحات القائمة على الخصوصية التفاضلية f-DP تظل غير واضحة. تميز f-DP المدى الكامل لاختبار الفرضيات العدائي عبر دالات المقايضة (trade-off functions)، وتستعيد $(\epsilon, \delta)$-DP من خلال دالات مقايضة خطية مجزأة. ومن المعروف أن نواتج التنسور (tensor products) لـ f-DP توفر أدق نتائج التركيب في الإعدادات غير التكيفية. السؤال المركزي هو ما إذا كان "مرشح f-DP الطبيعي" — الذي يتتبع ناتج التنسور المتراكم لدالات المقايضة ويتوقف عند تجاوز منحنى محدد — يظل صالحاً تحت التكيف الكامل.

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

1. تحليل صلاحية مرشح f-DP الطبيعي

يتحقق المؤلفون من "مرشح f-DP الطبيعي"، المعرف بالاستمرار طالما ظل ناتج التنسور لدالات المقايضة المتحققة $f_1 \otimes \dots \otimes f_t$ فوق منحنى الميزانية $f_B$.

• بناء المثال المضاد: تُظهر الورقة أن هذا النهج غير صالح بشكل أساسي في الإعداد التكيفي الكامل. حتى لو كانت الآليات الفردية صالحة، ودالة المقايضة المركبة لم تتجاوز العتبة على طول مسار محدد، فإن التركيب التكيفي يمكن أن ينتهك الميزانية.
• آلية الفشل: ينشأ الفشل لأن ناتج التنسور التكيفي لدالات المقايضة يعتمد على التحقق المحدد للمخرجات، والذي يحدد اختيار الآليات اللاحقة. إذا احتوت عائلة من دالات المقايضة المستقبلية المحتملة على "نقطة معايرة" (حيث تتقاطع الدالات)، يمكن للاختيار التكيفي استغلال ذلك لتحقيق ملف فقدان خصوصية أسوأ (دالة مقايضة أقل) من الحد الأدڽ لناتج التنسور للفروع الفردية. تحدث هذه الظاهرة حتى في آليات غاوس الفرعية (subsampled Gaussian mechanisms)، وهي الأداة الأساسية في تعلم الآلة الخاص.

2. توصيف شروط الصلاحية

يضع المؤلفون شروطاً ضرورية وكافية لصلاحية مرشح f-DP الطبيعي:

• سلاسل بلاكويل (Blackwell Chains): يكون المرشح صالحاً إذا وفقط إذا كانت عائلة دالات المقايضة المتاحة (ونواتج التنسور الخاصة بها) تشكل سلسلة بلاكويل. تُعد العائلة سلسلة بلاكويل إذا كانت أي دالتين في العائلة مرتبتين كلياً (إحداهما تهيمن على الأخرى نقطة بنقطة).
• الاستنتاج: يفسر هذا سبب امتلاك RDP وGaussian DP (GDP) لمرشحات بسيطة وصالحة: ضماناتها هي قيم قياسية (أو تشكل سلاسل بلاكويل مثل دالات مقايضة غاوس $G_\mu$ حيث $\mu$ هو قيمة قياسية)، مما يضمن القابلية للمقارنة. في المقابل، دالات مقايضة f-DP العامة ليست دائماً مرتبة وفق نظام بلاكويل، مما يؤدي إلى فشل المرشح الطبيعي.

3. نظرية الحد المركزي (CLT) التكيفية الكاملة

لتجاوز عدم صلاحية مرشحات f-DP الدقيقة، تثبت الورقة نظرية حد مركزي (CLT) لـ f-DP تكيفية بالكامل.

• المنهج: ينمذج المؤلفون فقدان الخصوصية كعملية عشوائية لمتغيرات عشوائية لفقدان الخصوصية (PLRVs). باستخدام نسخة مارينج (martingale variant) من حد Berry–Esissen (Fan, 2019)، يثبتون أنه تحت شروط انتظام محددة (متوسطات وتباينات شرطية محدودة، وعزوم رتب أعلى مضبوطة)، يتقارب فقدان الخصوصية التراكمي إلى توزيع غاوسي.
• النتيجة: يسمح هذا التقارب ببناء مرشحات GDP تقريبية. بدلاً من تتبع دالة المقايضة الكاملة، يمكن تتبع المتوسطات والتباينات الشرطية التراكمية لـ PLRVs. يتم تحديد خطأ هذا التقريب بواسطة حد الخطأ في نظرية الحد المركزي $\Delta$.

4. مرشح GDP التقريبي لآليات غاوس الفرعية

كحالة تطبيقية ملموسة، يستنتج المؤلفون تقريبات العزوم ذات الصيغة المغلقة لآليات غاوس الفرعية في نظامين تقاربيين:

• أخذ عينات منخفض ($q \ll 1$): يتم تقريب متوسط وتباين PLRV باستخدام مفكوك تايلور.
• أخذ عينات مرتفع ($q \approx 1$): يتم اشتقاق تقريبات مماثلة للحد الذي تقترب فيه معدل أخذ العينات من 1.
• الخوارزمية: يقترحون خوارزمية تتتبع تقريبات العزوم هذه لفرض ميزانية. يتجنب هذا المرشح تتبع دالة المقايضة الكاملة، مما يوفر بديلاً فعالاً حاسوبياً للمحاسبة القائمة على تحويل فورييه السريع (FFT) العددي.

النتائج الرئيسية

1. عدم صلاحية المرشحات الطبيعية: مرشح f-DP الطبيعي غير صالح للتركيبات التكيفية الكاملة لآليات غاوس الفرعية. تُظهر الأمثلة المضادة الصريحة أن التركيب التكيفي يمكن أن ينتهك الميزانية حتى عندما تحقق جميع الفروع غير التكيفية تلك الميزانية.
2. توصيف الصلاحية: يكون المرشح الطبيعي صالحاً إذا وفقط إذا كانت عائلة دالات المقايضة تشكل سلسلة بلاكويل. يوفر هذا حداً نظرياً حاداً متى يكون الحساب القائم على دالة المقايضة ممكناً تحت التكيف الكامل.
3. التقريب القائم على CLT: تثبت نظرية الحد المركزي (CLT) التكيفية الكاملة أن خسائر الخصوصية التراكمية تتقارب نحو توزيعات غاوسية. وهذا يتيح بناء مرشحات GDP تقريبية صالحة في الأنظمة التقاربية.
4. مقارنة الأداء:
   • في الأنظمة التقاربية ($q \ll 1$ و $q \approx 1$)، يوفر مرشح GDP التقريبي المقترح ضمانات خصوصية أدق بشكل صارم من محاسبة RDP التكيفية بالكامل (تحديداً مرشح $(1, B)$-RDP من الدرجة الواحدة).
   • تشير الورقة إلى أنه بينما يُعرف عن محاسبة RDP أنها فضفاضة، فإن هذا التراخي ينبع من الاختزال الخاسر إلى تباعدات Rényi وليس من عائق جوهري في التركيب التكيفي.
   • ومع ذلك، فإن التقريب القائم على CLT يُعرف بأنه متفائل (يقلل من تقدير فقدان الخصوصية) عند معدلات أخذ عينات واقعية ومعتدلة (مثل $q=0.1$)، وهو قصور تشترك فيه مع تقريبات CLT غير التكيفية.

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

تدعي الورقة أنها تحل سؤالاً مركزياً مفتوحاً بخصوص مرشحات f-DP:

• الحل النظري: تُظهر الورقة بشكل قاطع أن الامتداد البديهي لتركيب f-DP القياسي إلى مرشحات تكيفية يفشل، مما يوضح لماذا تنجح المفاهيم القائمة على التباعد (RDP) حيث تفشل مفاهيم d-DP العامة (المبنية على دالة المقايضة) دون قيود هيكلية.
• المساهمة البنائية: من خلال إثبات CLT التكيفي الكامل، توفر الورقة منهجية عامة لبناء مرشحات GDP تقريبية لأي عائلة آليات يمكن فيها تقريب عزوم PLRV تحليلياً.
• الآثار العملية: بالنسبة لآليات غاوس الفرعية، يوفر المرشح المقترح بديلاً فعالاً وذا صيغة مغلقة للمحاسبة العددية. في أنظمة أخذ العينات القصوى، يوفر ضمانات أكثر دقة من مرشحات RDP الحالية، مما يثبت أن "التراخي" في RDP هو نتاج لطريقة التمثيل وليس تكلفة متأصلة في التكيف.

يظل المؤلفون متواضعين بشأن القيود، حيث يقرون بأن النهج القائم على CLT متفائل عند معدلات أخذ عينات واقعية ومعتدلة، وأن سد الفجوة عند المعدلات المعتدلة يظل تحدياً مفتوحاً. كما يشيرون أيضاً إلى أن صلاحية المرشح الطبيعي تقتصر على شروط هيكلية محددة لا تتوفر دائماً في آليات f-DP التعسفية.