ملخص تقني: محاسبة الخصوصية الخالية من أخذ العينات لآليات المصفوفات تحت التوزيع العشوائي

بيان المشكلة

تتناول الورقة البحثية تحدي حساب ضمانات الخصوصية الحتمية والمحكمة للتدريب على النماذج المعتمد على الخصوصية التفاضلية التي تستخدم آليات تحليل المصفوفات (Matrix Factorization Mechanisms) مقترنة بـ التوزيع العشوائي (المعروف أيضًا باسم مخطط "الكرات في الصناديق" أو التوزيع الفرعي المتوازن للدورات).

بينما يعد تضخيم الخصوصية عن طريق أخذ العينات الفرعية تقنية قياسية لتقليل الضوضاء في خوارزمية (DP-SGD)، إلا أن مخطط "الكرات في الصناديق" يُفضل على أخذ العينات من نوع "بواسون" (Poisson subsampling) في التدريب واسع النطاق نظرًا لكفاءته الحسابية وتغطيته الموحدة للبيانات. ومع ذلك، عند الجمع بينه وبين تحليل المصفوفات (الذي يُدخل ضوضاء مترابطة عبر الدورات لتحسين المنفعة)، تواجه طرق محاسبة الخصوصية الحالية قيودًا كبيرة:

1. الاعتماد على مونت كارلو: تعتمد النهج الحديثة (مثل Choquette-Choo et al., 2025) على أخذ عينات مونت كارلو لتقدير معاملات التضخيم. هذا النهج مكلف حاسوبيًا، لا سيال في أن عدد العينات المطلوبة لزيادة الدقة يزداد عكسيًا مع $\delta$ (على سبيل المثال، إظهار أن الوصول إلى $(\epsilon, 10^{-8})$-DP يكلف $10^5$ مرة أكثر من $(\epsilon, 10^{-3})$-DP).
2. الضمانات الاحتمالية: غالبًا ما تقدم هذه الأساليب القائمة على أخذ العينات ضمانات تتحقق فقط "باحتمالية عالية" أو تتطلب من الآلية استخدام "الامتناع العشوائي" (Random Abstention)، بدلاً من تقديم حدود $(\epsilon, \delta)$-DP حتمية.
3. التعقيد غير القابل للحل: إن توزيع فقدان الخصوصية لآليات المصفوفات تحت التوزيع العشوائي يتضمن خليطًا عالي الأبعاد، مما يجعل التقييم الدقيق لتباعد "هوكاي ستيك" (Hockey-stick divergence) مستعصيًا دون أخذ عينات.

المنهجية

يقترح المؤلفون إجراءين منفصلين لـ المحاسبة الخالية من أخذ العينات (Sampling-free) يقومان بحساب حدود حتمية بشكل صريح، وذلك بالاستفيد من بنية مخطط التوزيع العشوائي والارتباطات الناتجة عن تحليل المصفوفات.

1. محاسب تباعد ريني (البرمجة الديناميكية)

تحسب هذه الطريقة حدًا علويًا لتباعد ريني، والذي يتم تحويله بعد ذلك إلى $(\epsilon, \delta)$-DP باستخدام نظريات التحويل القياسية.

• الرؤية الجوهرية: يمكن التعبير عن توزيع فقدان الخصوصية لاتجاه "الإزالة" (حيث يتم إزالة نقطة بيانات من مجموعة البيانات) كمجموع لمصفوفة جرام $G$ مشتقة من مصفوفة الاستراتيجية $C$.
• تقليل التعقيد: بالنسبة للمصفوفات العامة، ثبت أن حساب هذا المجموع هو مسألة من نوع #P-complete. ومع ذلك، بالنسبة للمصفوفات المهيكلة (مثل المصفوفات النطاقية حيث يكون للمصفوفة الاستراتيجية $C$ عرض نطاق $p$)، فإن مصفوفة الجرام $G$ ترث بنية نطاقية دائرية (Cyclically banded).
• الخوارزمية: يصيغ المؤلفون نهج البرمجة الديناميكية لحساب المجموع بدقة للمصفوفات ذات النطاق $p$.
  • التعقيد: تم تقليل وقت التشغيل من تعقيد أسي $O(2^\alpha)$ (في الرتبة $\alpha$) إلى تعقيد متعدد الحدود $O(b p \alpha^{2p})$، حيث $b$ هو عدد الدفعات لكل حقبة.
  • القطع (Truncation): بالنسبة للمصفوفات التي ليست نطاقية تمامًا ولكنها تمتلك مدخلات تتلاشى بسرعة (مثل المصفوفات النطاقية المعكوسة)، تقوم الطريقة بقطع مصفوفة الجرام وإضافة حد تصحيح إضافي قابل للحساب لضمان بقاء الحد صالحًا.
• اتجاه الإضافة: تم اشتقاق حد علوي تحليلي محكم ومنفصل لاتجاه "الإضافة" باستخدام متباينة المتوسط الحسابي والهندسي (AM-GM).

2. محاسب التركيب الشرطي

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

• المفهوم: بدلًا من افتراض خطوات مستقلة، تستخدم الطريقة التركيب الشرطي. فهي تحدد النتائج "الجيدة" حيث تهيمن التوزيعات الشرطية للآلية عند الخطوة $n$ على زوج من التوزيعات العاملة الثابتة $(P^{(n)}, Q^{(n)})$.
• الأحداث السيئة: تأخذ الطريقة في الاعتبار "الأحداث السيئة" (حيث يفشل الهيمنة) من خلال حصر احتمال حدوثها $\delta_E$. إجمالي فقدان الخصوصية هو تركيب الخطوات المستقلة بالإضافة إلى $\delta_E$.
• معيار الهيمنة: يشتق المؤلفون معيارًا يعتمد على دوال المخاطر العكسية لأوزان خليط غاوس. ويظهرون أنه إذا كانت دالة المخاطر العكسية اللاحقة (Posterior reverse hazard function) أصغر نقطيًا من دالة المخاطر العكسية لتوزيع مستهدف، فإن الهيمنة تتحقق.
• الحدود الذيلية: لتحديد بارامترات التوزيعات المهيمنة، يشتق المؤلفون حدودًا ذيلية تحليلية لفقدان الخصوصية لخليط غاوس الثلاثي. ويستخدمون عائلة تباينية (Variational family) من التوزيعات لتضييق هذه الحدود، مع تحسين بارامترات درجة الحرارة لتقليل الانحراف المعياري لحد الذيل.
• الكفاءة: بينما يكون التقييم الأولي هو $O(N^2 b^2)$، يمكن جعل التقييمات اللاحقة لمختلف مضاعفات الضوضاء $\sigma$ متوافقة عبر التكلفة المتدرجة لتصبح $O(N b^2)$، مما يجعلها فعالة لمعايرة الآلية.

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

1. المحاسبة الحتمية: تقدم الورقة أول طرق خالية من أخذ العينات لحساب ضمانات $(\epsilon, \delta)$-DP لآليات المصفوفات تحت التوزيع العشوائي، مما يلغي الحاجة إلى تقدير مونت كارلو.
2. تحسين التعقيد لـ DP-SGD: في الحالة الخاصة للضوضاء غير المترابطة (DP-SGD القياسي)، يحسن محاسب ريني المقترح التعقيد الحسابي للمحاسبة الدقيقة تحت التوزيع العشوائي من تعقيد أسي $O(2^\alpha)$ إلى تعقيد متعدد الحدود $O(b \alpha^2)$، وهو ما يتفوق بشكل كبير على الطرق الدقيقة السابقة.
3. التعميم على الضوضاء المترابطة: يوسع الإطار العمل لآليات المصفوفات النطاقية وغير النطاقية (بما في ذلك Banded Square Root، وBanded Inverse، وBuffered Linear Toeplitz)، مع التعامل مع الارتباطات المعقدة بين الخطوات المتأصلة في هذه الآليات.
4. الدقة في الأنظمة المزدوجة: يوفر الجمع بين محاسب ريني (القوي في نظام الخصوصية المنخفضة/$\epsilon$ الكبيرة) ومحاسب التركيب الشرطي (الأكثر إحكامًا في نظام الخصوصية العالية/$\epsilon$ الصغيرة) حلاً شاملاً للمحاسبة.

النتائج

يقيم المؤلفون طرقهم مقابل محاسب مونت كارلو الذي يعد الأحدث (State-of-the-art) عبر مختلف آليات المصفوفات (DP-SGD, BSR, BISR, BandMF, BandInvMF, BLT) وفي إعدادات مختلفة (حقبة واحدة أو حقبات متعددة).

• الدقة: في نظام الخصوصية المنخفضة ($\epsilon \ge 2$)، يطابق محاسب ريني مرجع مونت كارلو عن كثب. وفي نظام الخصوصية العالية ($\epsilon \le 1$)، يحقق محاسب التركيب الشرطي حدودًا أكثر إحكامًا، مما يسمح بمعايرة مضاعفات ضوضاء $\sigma$ أصغر مقارلة بتقديرات مونت كارلو.
• المتانة: تظل الأداء ثابتًا عبر مختلف عرض النطاق ($p$) وعدد الدفعات ($b$).
• المنفعة: تُظهر التجارب على CIFAR-10 أن مضاعفات الضوضاء المستمدة من هذه الضمانات الخالية من أخذ العينات تحافظ على فوائد المنفعة لاستخدام الضوضاء المترابطة مقارنة بالضوضاء غير المترابطة.
• وقت التشغيل: تتغلب الطرق على اعتماد مونت كارلو على $O(\delta^{-1})$. وبينما يكون للتركيب الشرطي تكلفة أولية أعلى لـ $N$ الكبير، فإن تكلفته المتدرجة للمعايرة أقل بكثير من مونت كارلو بالنسبة لميزانيات الخصوصية الصارمة.

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

تدعي الورقة أنها توفر أول محاسبة خالية من أخذ العينات للخصوصية للآليات ذات التدرجات والارتباطات المترابطة. وتكمن أهميتها في:

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

يقر المؤلفون بوجود قيود، مشيرين إلى أن تعقيد محاسب ريني يظل أسيًا في عرض النطاق $p$ (وإن كان متعدد الحدود في $\alpha$)، وأن طريقة التركيب الشرطي تعتمد على تقسيم تقريبي للنتائج مما قد يكون متشائمًا. ويقترحون أن العمل المستقبلي يمكن أن يستكشف تقسيمات أكثر دقة واستدلالًا تباينيًا أكثر كفاءة لزيادة إحكام الحدود.