Not All Learnable Distribution Classes are Privately Learnable

ملخص تقني: "ليست كل فئات التوزيعات القابلة للتعلم قابلة للتعلم بخصوصية"

بيان المشكلة
تتناول الورقة سؤالاً جوهرياً في التقاطع بين نظرية التعلم الإحصائي والخصوصية التفاضلية (DP): هل كل فئة من فئات التوزيعات القابلة للتعلم في الإطار القياسي (غير الخاص) هي أيضاً قابلة للتعلم تحت قيود الخصوصية التفاضلية التقريبية $(\varepsilon, \delta)$-DP؟

بينما ثبت أن الخصوصية التفاضلية النقية ($\varepsilon$-DP، حيث $\delta=0$) تفرض فواصل صارمة بين الفئات القابلة للتعلم والقابلة للتعلم بخصوصية (والتي تُحدد غالباً بأرقام التغطية/التعبئة)، ظل وضع الخصوصية التفاضلية التقريبية $(\varepsilon, \delta)$-DP مسألة مفتوحة. وقد أدت الأدبيات الحديثة إلى إنتاج أطر عمل أكثر عمومية لتعلم التوزيعات بخصوصية، مما دفع "أشتياني" [Ash22] إلى التخمين بأن الإجابة على السؤال أعلاه هي الإيجاب: أي أن كل فئة توزيعات قابلة للتعلم هي قابلة للتعلم بخصوصية.

المنهجية والبناء
يدحض المؤلفون هذا التخمين من خلال بناء فئة محددة من التوزيعات، يُرمز لها بـ $\mathcal{H}_w$، والتي تعمل كنموذج مضاد. يعتمد البناء على آلية "الباب الخلفي" (trapdoor) باستخدام مزيج من التوزيعات:

1. هيكل الفئة: تتكون الفئة $\mathcal{H}_{w,d}$ من مزيج فوق $d+1$ من المكونات التي تشترك في متجه بارامتر مشترك $\mathbf{p} \in [0,1]^d$.
   • مكون "المفتاح": توزيع منتج ثنائي فوق $\{0,1\}^d$ مع وزن خلط $w$. عينة واحدة من هذا المكون تكشف معلومات عن كامل متجه البارامتر $\mathbf{p}$.
   • المكونات "الصعبة": $d$ مكون إضافي، كل منها مدعوم على $\{\pm j\}$ لـ $j \in \{1, \dots, d\}$، مع وزن خلط $(1-w)/d$. أي عينة من هذه المكونات تكشف معلومات عن إحداثي واحد فقط من $\mathbf{p}$.
2. الباب الخلفي: يتم ضبط وزن الخلط $w$ ليكون $1/(2\alpha)$ (حيث $\alpha$ هو الخطأ المستهدف). يضمن ذلك أن المكونات "الصعبة" تهيمن على المزيج (احتمالية عالية لأخذ عينة من هذه المكونات)، بينما يكون مكون "المفتاح" نادراً.
3. خدعة الأبعاد: تُعرف الفئة $\mathcal{H}_w$ بأنها اتحاد هذه الفئات عبر جميع الأبعاد $d \ge 2$. يضمن البناء أنه بينما لا يكون البعد $d$ ثابتاً مسبقاً، فإن صعوبة التعلم تتناسب مع $d$.

النتائج الرئيسية والبراهين
تثبت الورقة وجود فاصل بين القدرة على التعلم بخصوصية وعدمها للفئة $\mathcal{H}_w$ فيما يتعلق بمسافة التباين الكلي (Total Variation - TV):

1. القدرة على التعلم غير الخاص (عينات محدودة):
   يُظهر المؤلفون أن $\mathcal{H}_w$ قابلة للتعلم بعدد ثابت من العينات (مستقل عن $d$) حتى خطأ ثابت.

   • الآلية: بما أن مكون "المفتاح" يظهر باحتمالية $w$، يمكن لخوارزمية غير خاصة جمع عينات كافية لملاحظة مكون المفتاح. بمجرد ملاحظته، يتم تحديد البعد $d$، ويمكن تقدير متجه البارامتر $\mathbf{p}$ عبر المتوسط الحسابي للعينات من التوزيع المنتج الثنائي.
   • التعقيد: تعقيد العينات هو $O(1/\alpha^3 \cdot \log(1/\beta))$، وهو ثابت بالنسبة للبعد $d$.

2. عدم القدرة على التعلم بخصوصية (تطلب عينات لانهائية):
   يثبت المؤلفون أنه لا توجد آلية $(\varepsilon, \delta)$-DP يمكنها تعلم هذه الفئة بنفس ضمان الخطأ باستخدام عدد محدود من العينات.

   • الاختزال: يقومون ببناء اختزال من مشكلة تقدير الكثافة على $\mathcal{H}_{w,d}$ إلى مشكلة تقدير بارامتر $\ell_1$ للتوزيعات المنتجة الثنائية.
   • الحد الأدنى: بالاستفيد من الحدود الدنيا المعروفة لتقدير المتوسط الخاص بالتوزيعات المنتجة الثنائية (تحديداً من [KLSU19])، يظهرون أن تعقيد العينات لتعلم $\mathcal{H}_{w,d}$ تحت نظام DP يتناسب مع $\Omega(\sqrt{d}/(\sqrt{\alpha}\varepsilon))$.
   • التناقض: بما أن الفئة $\mathcal{H}_w$ تتضمن توزيعات لأي $d \ge 2$، وبما أن حجم العينات المطلوب ينمو مع $\sqrt{d}$، فلا يوجد حجم عينات نهائي $n$ يكفي لتعلم الفئة بأكملها $\mathcal{H}_w$ تحت نظام DP. ومع اقتراب $d \to \infty$، يقترب حجم العينات المطلوب من اللانهاية.

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

• دحض التخمين: توفر الورقة نموذجاً مضاداً صريحاً لتخمين "أشتياني" بأن كل فئة توزيعات قابلة للتعلم هي قابلة للتعلم بخصوصية تحت $(\varepsilon, \delta)$-DP.
• الفصل في القدرة على التعلم: توضح وجود فصل صارخ حيث تكون الفئة قابلة للتعلم بـ $O(1)$ من العينات غير الخاص، ولكنها تتطلب عدداً لانهائياً من العينات للتعلم بخصوصية.
• بناء الباب الخلفي: قدم المؤلفون بناء "باب خلفي" خاص حيث يعمل مكون نادر كـ "مفتاح" لبارامتر عالي الأبعاد، والذي يكون بدونه يصعب تعلمه بسبب المكون المهيمن والصعب. هذا الهيكل يمنع آليات الخصوصية من الوصول إلى "المفتاح" دون انتهاك قيود الخصوصية أو طلب أحجام عينات باهظة.

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

يسلط العمل الضوء على أن أطر العمل العامة لتعلم التوزيعات بخصوصية لا يمكنها ببساطة الاعتماد على اختزالات "الصندوق الأسود" من المتعلمين غير الخاصين دون افتراضات هيكلية إضافية. كما يثبت أن وجود مكون "مفتاح" نادر ولكنه ضروري للتعلم يمكن أن يخلق حاجزاً لا يمكن تجاوزه للخوارزميات الخاصة، حتى عندما تكون الخوارزمية غير الخاصة فعالة.

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