Universal Shuffle Asymptotics, Part II: Non-Gaussian Limits for Shuffle Privacy -- Poisson, Skellam, and Compound-Poisson Regimes

هذا ملخص تقني مفصل لورقة "التقاربات الشاملة للخلط، الجزء الثاني: الحدود غير الغاوسية لخصوصية الخلط — أنظمة بواسون، سكيلام، والبوواسون المركب" (Universal Shuffle Asymptotics, Part II: Non-Gaussian Limits for Shuffle Privacy—Poisson, Skellam, and Compound-Poisson Regimes) بقلم أليكس شفيتس (مارس 2026).

1. بيان المشكلة والسياق

تتناول الورقة السلوك التقاربي لنموذج الخلط (Shuffle Model) للخصوصية التفاضلية (DP) عندما يتدرج معامل الخصوصية المحلي $\epsilon_0$ مع حجم المجتمع $n$.

• الخلفية: أثبت الجزء الأول من هذه السلسلة أنه عندما يكون الموزع العشوائي المحلي ثابتًا وله دعم كامل بعيد عن الصفر، فإن آلية الخلط تتقارب نحو حد غاوسي (يحقق خاصية التحلل المحلي التقاربي الطبيعي - LAN، والخصوصية التفاضلية الغاوسية - GDP).
• الفجوة: في الممارسة العملية، غالبًا ما ينمو $\epsilon_0(n)$ مع $n$ (على سبيل المثال، لتقليل تباين المقدر)، وفي هذا النظام، يفشل افتراض "الزيادات الصغيرة" الخاص بنظرية النهاية المركزية (CLT). يمكن للنتائج المحلية النادرة أن تسبب قفزات عيانية ($\Theta(1)$) في نسبة الارتياب في اللوغاريتم (log-likelihood ratio) على مستوى المجتمع.
• الهدف: تحدد الورقة الحد الحرج الذي تنهار عنده التقريبات الغاوسية الكلاسيكية. تهدف الورقة إلى اشتقاق نظريات حدودية غير غاوسية حادة (بواسون، سكيلام، والبوواسون المركب) لآلية الخلط تحت أنظمة قياس محددة حيث يكون احتمال الخطأ المحلي من رتبة $O(1/n)$.

2. المنهجية

يستخدم المؤلفون إطارًا صارمًا يعتمد على نظرية التجارب الإحصائية (نظرية لو كام - Le Cam theory) ونظريات حدود الاحتمالات.

• مسافة لو كام (Le Cam Distance): المقياس الأساسي للتقارب هو مسافة لو كام ($\Delta$) بين التجارب الثنائية. تثبت الورقة التقارب في مسافة التباين الكلي (TV distance) بين قوانين سجلات الخلط ذات النهاية $n$ وتوزيعاتها الحدية، مما يعني تقارب مسافة لو كام.
• أنظمة القياس (Scaling Regimes): يركز التحليل على القياس الحرج حيث يتقارب المعامل $a_n = e^{\epsilon_0(n)}/n$ إلى ثابت $c^2 \in (0, \infty)$.
  • تحت الحرج (Sub-critical): $a_n \to 0$ (النظام الغاوسي، تمت تغطيته في الجزء الأول).
  • الحرج (Critical): $a_n \to c^2$ (النظام غير الغاوسي، وهو موضوع هذه الورقة).
  • فوق الحرج (Super-critical): $a_n \to \infty$ (انهيار الخصوصية).
• تقنيات التقريب:
  • تقريب بواسون (Poisson Approximation): باستخدام حدود اقتران صريحة (من نوع تشين-ستين/لو كام) لتقريب تعدادات ثنائية الحدين للأحداث النادرة بتوزيعات بواسون.
    টি
  • توزيع سكيلام (Skellam Distribution): نمذجة الفرق بين متغيرين مستقلين من نوع بواسون للتركيبات النسبية.
  • البواسون المركب (Compound Poisson): التوسع ليشمل الأبجدية المحدودة العامة حيث تحدث أنواع متعددة من الأخطاء النادرة.
  • التفكيك الهجين (Hybrid Decomposition): لأنظمة "السيادة المزدوجة"، يتم تفكيك الإحصائية إلى مكون غاوسي (التقلبات المهيمنة) ومكون بواسون مركب (القفزات النادرة).

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

تؤسس الورقة صورة ثلاثية الأنظمة لخصوصية الخلط، حيث يمثل النظام الحرج المساهمة الجديدة.

أ. الزوج المجاور النموذجي: حد إزاحة بواسون (القسم 3)

• السيناريو: استجابة عشوائية ثنائية (Binary Randomized Response - RR) مع مجموعة بيانات تتكون من جميع الأصفار مقابل واحد "واحد" ($k=0$ مقابل $k=1$).
• القياس: $e^{\epsilon_0(n)} \sim c^2 n$.
• النتيجة: يتقارب سجل الخلط في مسافة TV إلى تجربة إزاحة بواسون.
  • الفرضية الصفرية $P_\infty \sim \text{Poi}(\lambda)$ حيث $\lambda = c^{-2}$.
  • الفرضية البديلة $Q_\infty \sim 1 + \text{Poi}(\lambda)$.
• منحنى الخصوصية: منحنى الخصوصية الحدي هو متسلسلة صريحة تتضمن ذيول بواسون.
• رؤية رئيسية (أرضية $\delta$): على عكس النظام الغاوسي حيث $\delta(\epsilon) \to 0$ مع $\epsilon \to \infty$، يُظهر حد بواسون أرضية عدم تطابق الدعم (support-mismatch floor). بما أن $Q_\infty$ لا تحتوي على كتلة عند 0 بينما $P_\infty$ تحتوي عليها، فإن منحنى الخصوصية ثنائي الجانب مقيد من الأسفل بـ $e^{-\lambda} = e^{-1/c^2}$ لجميع قيم $\epsilon$. وهذا يمثل حدًا جوهريًا على تعزيز الخصوصية في هذا النظام.

ب. التركيبات النسبية: حد إزاحة سكيلام (القسم 4)

• السيناريو: استجابة عشوائية ثنائية حيث يتقارب كسر الواحدات $\pi = k/n$ إلى ثابت $\pi \in (0, 1)$.
• النتيجة: يتقارب المدرج التكراري المتمركز إلى تجربة إزاحة سكيلام.
  • $P_\infty \sim \text{Skellam}(\lambda_0, \lambda_1)$ حيث $\lambda_0 = (1-\pi)c^{-2}$ و $\lambda_1 = \pi c^{-2}$.
  • $Q_\infty \sim 1 + \text{Skellam}(\lambda_0, \lambda_1)$.
• منحنى الخصوصية: يتم اشتقاق المنحنى صراحة باستخدام دالة كتلة الاحتمال لسكيلام (التي تتضمن دالات بيسل المعدلة).
• رؤية رئيسية: بالنسبة للتركيبات الداخلية ($\pi \in (0, 1)$)، يكون دعم توزيع سكيلام هو جميع الأعداد الصحيحة $\mathbb{Z}$. وبناءً على ذلك، لا توجد أرضية عدم تطابق الدعم؛ حيث يتلاشى منحنى الخصوصية إلى الصفر مع $\epsilon \to \infty$، على عكس حالة الحدود. وتعمل عائلة سكيلام كوسيط مستمر بين عائلات إزاحة بواسون عند الحدود $\pi=0$ و $\pi=1$.

ج. الأبجديات العامة: حد البواسون المركب متعدد المتغيرات (القسم 5)

• السيناريو: أبجديات مخرجات منتهية عامة مع أنظمة قياس "الأخطاء المتفرقة" الحرجة (المخرجات المهيمنة لها احتمال $1-O(1/n)$، والآخرون $O(1/n)$).
• النتيجة: يتقارب المدرج التكراري المتمركز إلى إزاحة بواسون مركبة متعددة المتغيرات.
  • الحد هو متجه من متغيرات بواسون المستقلة التي تمثل تعداد أخطاء معينة نادرة.
  • تعتمد الإزاحة على التركيبة $\pi$.
• النظام الهجين (مخرجات مهيمنة مزدوجة): إذا تم تقسيم الكتلة المهيمنة بين مخرجين (لا تنهار إلى واحد)، فإن الحد هو توزيع هجين (غاوسي/بواسون مركب).
  • الكتلة المهيمنة تتذبذب على مقي scale $\sqrt{n}$.
  • الأخطاء النادرة تشكل مجال قفزات بواسون مركب.
  • تثبت الورقة أنه بينما لا تتقارب التجربة الكاملة في مسافة TV (بسبب الجزء الغاوسي المستمر)، فإن منحنيات الخصوصية لا تزال تتقارب، ويعمل المكون الغاوسي كعامل مشترك لا يؤثر على ملف الخصوصية (عبر حجج التنعيم الشرطي).

د. مخطط الطور والنظام فوق الحرج (القسم 6)

• تحت الحرج ($a_n \to 0$): حدود غاوسية/GDP (الجزء الأول).
• الحرج ($a_n \to c^2$): حدود بواسون/سكيلام/بواسون مركب (هذه الورقة).
• فوق الحرج ($a_n \to \infty$): تنهار الخصوصية تمامًا. تقترب مسافة التباين الكلي بين مجموعات البيانات المتجاورة من 1، مما يعني أنها قابلة للتمييز تقاربيًا بغض النظر عن ميزانية الخصوصية.

4. الأهمية والآثار المترتبة

1. كسر الشمولية (Breaking Universality): توضح الورقة أن "الشمولية الغاوسية" لنموذج الخلط هشة. بمجرد أن يتدرج معامل الخصوصية المحلي بحيث يصبح عدد الأخطاء المتوقع $O(1)$، تتغير نظرية الحد بشكل جذري من العمليات الغاوسية إلى عمليات من نوع بواسون.
2. أرضية الخصوصية: تحدد الورقة حدًا صلبًا لتعزيز الخصوصية في النظام الحرج للتركيبات الحدية. حتى مع $\epsilon$ لانهائية، تظل $\delta$ غير صفرية بسبب احتمال وجود صفر أخطاء في الحد. وهذا يتحدى الحدس القائل بأن زيادة $\epsilon$ تؤدي دائمًا إلى جعل $\delta$ تقترب من الصفر.
3. إرشادات التصميم: توفر النتائج مخطط طور لمصممي البروتوكولات:
   • لتحقيق سلوك مشابه للغاوسي، يجب إبقاء $e^{\epsilon_0} \ll n$.
   • للعمل بالقرب من الحد الحرج ($e^{\epsilon_0} \approx n$)، يجب استخدام معايرة بواسون/سكيلام، وليس المعايرة الغاوسية.
   • إذا كان $e^{\epsilon_0} \gg n$، تضيع الخصوصية تمامًا.
4. المقارنة مع الحدود الحالية: تُظهر الورقة أن حدود التعزيز الموجودة حاليًا (مثل Balle et al. و Feldman et al.) تفشل في هذا النظام.
   • يعتمد التفكيك "الشامل" لـ Balle et al. على مساهمات صغيرة عديدة، وهو ما لا ينطبق عندما يكون عدد الأخطاء من رتبة $O(1)$.
   • نموذج تعزيز $n^{-1/2}$ الخاص بـ Feldman et al. يفتقد أرضية بواسون.
5. تطبيق نظرية لو كام: من خلال صياغة المشكلة في إطار مسافة لو كام ومعدلات TV الصريحة ($O(1/n)$)، توفر الورقة أساسًا صارمًا لمقارنة التجارب الإحصائية، متجاوزة مجرد التوزيعات التقاربية البسيطة.

5. الخاتمة

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