ملخص تقني: دالات المقايضة لـ DP-SGD القائم على أخذ العينات عبر الترتيب العشوائي (Random Shuffling)

بيان المشكلة

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

ومع ذلك، فإن التطبيقات العملية لـ DP-SGD والتحسين العشوائي تستخدم عادةً الترتيب العشوائي (Random Shuffling)، حيث يتم تبديل ترتيب مجموعة البيانات مرة واحدة في كل حقبة (epoch) وتقسيمها إلى دفعات صغيرة ذات حجم ثابت. هذا التباين بين الخوارزمية التي يتم تحليلها (بواسون) والخوارزمية المستخدمة فعلياً (الترتيب العشوائي) ترك ضمانات أنظمة العالم الحقيقي غير محددة بدقة. لقد قدمت الأعمال السابقة حول DP-SGD المعتمد على الترتيب العشوائي فقط حدوداً عليا لدالة المقايضة (حدود دنيا لخسارة الخصوصية) عبر أحداث معادية صريحة أو تقييمات عددية، مفتقرة إلى تعبيرات مغلقة وصريحة وشفافة. علاوة على ذلك، تشير النتائج الأخيرة حول الاستحالة إلى أنه بالنسبة لمعاملات الضجيج المنخفضة ($\sigma \le 1/\sqrt{2 \ln M}$)، فإن دالة المقايضة تكون محصورة بوضوح بعيداً عن قطر التخمين العشوائي المثالي ($1-a$)، ولكن ظل سلوكها في نظام الضجيج العالي مسألة مفتوحة تتطلب تحليلاً دقيقاً بصيغة مغلقة.

المنهجية

اشتق المؤلفون تحليلاً دقيقاً بصيغة مغلقة لدالة المقايضة لـ DP-SGD مع الترتيب العشوائي ضمن إطار عمل $f$-DP. تمر المنهجية عبر المراحل التالية:

1. الاختزال المعادي (Adversarial Reduction): تم اختزال المشكلة إلى مشكلة اختبار فرضية قياسية. تحت نموذج الخصم الأسوأ (والذي يمكنه عزل مساهمة سجل واحد مختلف)، يراقب الخصم $M$ من الجولات. تحت الفرضية الصفرية ($H_0$)، تكون جميع الملاحظات عبارة عن ضجيج نقي $N(0, 1)$. تحت الفرضية البديلة ($H_1$)، تحتوي جولة واحدة بالضبط (يختارها الترتيب العشوائي عشوائياً) على ملاحظة مزاحة $N(1/\sigma, 1)$، بينما تظل بقية الجولات ضجيجاً.
2. اختبار نسبة الأرجحية (Likelihood Ratio Test): من خلال مبرهنة نيمان-بيرسون، يقوم الاختبار الأمثل بتحديد عتبة نسبة الأرجحية، مما يقلل المسألة إلى تحديد عتبة متوسط عينة من متغيرات لوغاريتمية طبيعية $Y_j = \exp(X_j/\sigma - 1/(2\sigma^2))$، حيث $X_j \sim N(0, 1)$.
3. التحليل غير التقاربي (Berry-Esseen): بالنسبة لحقبة واحدة، طبق المؤلفون مبرهنة بير-إيسين (Berry-Esseen) لتحديد معدل تقارب متوسط العينة لهذه المتغيرات اللوغاريتمية الطبيعية إلى التوزيع الطبيعي. ينتج عن ذلك حد أدنى ملموس وغير تقاربي لدالة المقايضة $f(a)$ في النظام $\sigma \ge \sqrt{3/\ln M}$. يتم التعبير عن الحد كـ $f(a) \ge 1 - a - \delta$، حيث $\delta$ هي دالة صريحة لـ $\sigma$ و $M$.
4. التحليل التقاربي (Edgeworth Expansion): لتحسين حدود بير-إيسين، والتي تقتصر على خطأ قدره $O(1/\sqrt{M})$، قدم المؤلفون تقنية إثبات تعتمد على توسيع إدجويرث (Edgeworth expansion) ذي الحدين. يسمح هذا التعميم لنظرية النهاية المركزية بتقدير تقاربي أدق لتوزيع مجموع المتغيرات اللوغاريتمية الطبيعية. يحدد هذا النهج السلوك التقاربي لدالة المقايضة عندما $M \to \infty$ مع توسع عدد الحقبات $E = c_M^2 M$ حيث $c_M \to 0$.

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

1. حد أدنى بصيغة مغلقة لحقبة واحدة: توفر الورقة أول حد أدنى دقيق بصيغة مغلقة لدالة المقايضة لـ DP-SGD المعتمد على الترتيب العشوائي في نظام الضجيج العالي ($\sigma \ge \sqrt{3/\ln M}$). يُعطى الحد كالتالي:
   $$f(a) \ge 1 - a - \delta$$
   حيث يتم تعريف $\delta$ صراحة بدلالة $\sigma$ و $M$ (النظرية 4.1). هذه النتيجة دقيقة حتى عوامل ثابتة ضمن إطار عمل إثبات بير-إيسين.
2. توصيات محددة للمعلمات: اشتق المؤلفون إعدادات محددة للمعلمات لتحقيق خصوصية تفاضلية ذات معنى. لحقبة واحدة ($E=1$) مع $\sigma=1$ و $\delta=10^{-2}$، أظهروا أن حجم مجموعة بيانات $N \approx 1.14 \times 10^7$ مقسمة إلى $M \approx 1.14 \times 10^6$ جولة يكفي. يوضح هذا أن الخصوصية ذات المعنى يمكن تحقيقها في سيناريوهات التعلم الاتحادي مع مجموعات بيانات كبيرة وحقبة واحدة.
3. توصيف Gaussian-DP التقاربي: باستخدام توسيعات إدجويرث، تثبت الورقة أنه بالنسبة لـ $\sigma$ ثابتة، عندما $M \to \infty$ و $E = c_M^2 M$ مع $c_M \to 0$، فإن دالة المقايضة المركبة لـ $E$ من الحقبات تتقارب بشكل موحد نحو قطر التخمين العشوائي ($1-a$). يحسن هذا الاعتماد على عدد الحقبات من العقوبة الخطية $O(E)$ المقترحة بالتركيب الساذج إلى انفصال تقاربي $O(\sqrt{E})$ (الاستنتاج 5.3).
4. المقارنة مع أخذ العينات بنمط بواسون: قارن المؤلفون نتائجهم التقاربية مع نتائج أخذ العينات بنمط بواسون المقابلة. وجدوا أنه في حد الضجيج المنخفض ($\sigma \to 0$)، يكون الترتيب العشوائي أقرب تقاربيًا بـ عامل $\sqrt{2}$ من قطر التخمين العشوائي المثالي مقارنة بأخذ العينات بنمط بواسون، بينما يصبح النظامان متكافئين في حد الضجيج العالي ($\sigma \to \infty$).

النتائج

• صلاحية النظام: التحليل صالح لـ $\sigma \ge \sqrt{3/\ln M}$. هذا النظام مكمل لنتيجة الاستحالة لـ Ertan و van Dijk [12]، والتي تظهر أنه لـ $\sigma < 1/\sqrt{2 \ln M}$، تكون دالة المقايضة محصورة بعيداً عن $1-a$. معاً، ترسم هذه النتائج مشهد الخصوصية لـ DP-SGD المعتمد على الترتيب العشوائي.
• حدود التركيب:
  • غير التقاربية: يؤدي تكرار حد الحقبة الواحدة إلى $f^{\otimes E}(a) \ge (1-\delta)^E - a$، مما يعني اعتماداً خطياً على $E$ لخسارة الخصوصية.
  • التقاربية: يشير التحليل القائم على إدجويرث إلى اعتماد أكثر دقة، حيث يتناسب الانفصال عن القطر كـ $O(\mu \sqrt{E})$ بدلاً من $O(\mu E)$، بشرط أن يتوسع $E$ دون خطي مع $M$.
• الآثار العملية: تحدد الورقة نظام الحقبة الواحدة باعتباره "النقطة المثالية العملية" لـ DP-SGD المعتمد على الترتيب العشوائي. في سيناريوهات التعلم الاتحادي حيث يشارك العملاء في حقبات قليلة، يمكن تحقيق ضمانات خصوصية ذات معنى ($\delta \approx 0.01$) مع أحجام مجموعات بيانات واقعية. وعلى العكس من ذلك، تسلط الورقة الضوء على "انفجار تعدد الحقبات" حيث يؤدي زيادة $E$ تحت حد التركيب الخطي بسرعة إلى جعل حجم مجموعة البيانات المطلوب $N$ غير عملي (على سبيل المثال، يتطلب $N \sim 10^{11}$ لـ $E=100$).

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

تدعي الورقة أنها توفر تحليلاً دقيقاً بصيغة مغلقة يحل التباين بين الخوارزميات التي يتم تحليلها في الأدبيات (بواسون) وتلك المستخدمة فعلياً (الترتيب العشوائي). من خلال اشتقاق حدود شفافة وقابلة للتفسير، تمكن المؤلفين الممارسين من استخراج متطلبات المعلمات مباشرة دون الاعتماد على أدوات عددية غامضة.

تكمن أهمية العمل في:

1. سد الفجوة بين النظرية والتطبيق: التحقق من أن الترتيب العشوائي، وهو المعيار في أطر التعلم الآلي، يسمح بتحليل خصوصية صارم غالباً ما يكون أكثر ملاءمة من أخذ العينات بنمط بواسون في أنظمة الضجيج المنخفض.
2. تحديد مشهد الخصوصية: استكمال نتائج الاستحالة الموجودة لتحديد عتبات الضجيج الدقيقة المطلوبة لخصوصية ذات معنى في DP-SGD المعتمد على الترتيب العشوائي.
3. توجيه اختيار المعلمات: تقديم صيغ ملموسة لاختيار $M$ و $N$ و $\sigma$ لتحقيق ميزانيات خصوصية محددة، وهو أمر ذو صلة خاصة بتطبيقات التعلم الاتحادي.

يظل المؤلفون متواضعين فيما يتعلق بالعمل المستقبلي، مشيرين إلى أنه بينما تشير النتائج التقاربية إلى اعتماد $\sqrt{E}$ محسن لعدد الحقبات المتعددة، فإن اشتقاق إثبات ملموس بصيغة مغلقة لهذا الاعتماد (بدلاً من الحد التقاربي) يظل مسألة مفتوحة. بالإضافة إلى ذلك، تم تحديد جعل تسلسلات $\delta_M$ و $\gamma_M$ في توسيع إدجويرث صريحة للحصول على حد ملموس لتعدد الحقبات كاتجاه للبحث المستقبلي.