2025-11-22T06:46:16.153487

A hierarchy of convex relaxations for the total variation distance

Lasserre
Given two measures $μ$, $ν$ on Rd that satisfy Carleman's condition, we provide a numerical scheme to approximate as closely as desired the total variation distance between $μ$ and $ν$. It consists of solving a sequence (hierarchy) of convex relaxations whose associated sequence of optimal values converges to the total variation distance, an additional illustration of the versatility of the Moment-SOS hierarchy. Indeed each relaxation in the hierarchy is a semidefinite program whose size increases with the number of involved moments. It has an optimal solution which is a couple of degree-2n pseudo-moments which converge, as n grows, to moments of the Hahn-Jordan decomposition of $μ$-$ν$.
academic

تسلسل هرمي من الاسترخاءات المحدبة لمسافة التباين الكلي

المعلومات الأساسية

  • معرّف الورقة: 2401.01086
  • العنوان: A hierarchy of convex relaxations for the total variation distance
  • المؤلف: Jean B. Lasserre
  • التصنيف: math.OC (التحسين والتحكم)
  • تاريخ النشر: يناير 2024 (arXiv v3: 16 أكتوبر 2025)
  • رابط الورقة: https://arxiv.org/abs/2401.01086

الملخص

تقدم هذه الورقة مخطط عددي لتقريب مسافة التباين الكلي بين قياسين μ و ν يحققان شرط كارليمان بدقة عشوائية. يعتمد المخطط على حل سلسلة من مسائل الاسترخاء المحدبة (الهرمية)، حيث تتقارب سلسلة القيم المثلى إلى مسافة التباين الكلي. يوضح هذا المزيد من تعدد استخدامات التسلسل الهرمي Moment-SOS. كل استرخاء في التسلسل الهرمي يمثل مسألة برمجة شبه محددة، يزداد حجمها مع زيادة عدد العزوم المعنية، مع وجود حل أمثل—زوج من العزوم الكاذبة بدرجة 2n، يتقارب عند نمو n إلى عزوم تحليل Hahn-Jordan لـ μ-ν.

خلفية البحث والدافع

أهمية المشكلة

يعتبر الحساب العددي لمسافة التباين الكلي (Total Variation, TV) مشكلة مهمة وتحديًا كبيرًا، مع تطبيقات واسعة في:

  1. الاختبارات الإحصائية: الاختبارات المتجانسة واختبارات الاستقلالية
  2. التحسين القوي للتوزيع: تحديد مجموعات عدم اليقين
  3. علوم البيانات والتعلم الآلي: قياس المسافة بين القياسات

حدود الطرق الموجودة

  1. مشاكل المقدرات التجريبية: المقدرات التجريبية القائمة على العينات العشوائية غالبًا ما تكون غير متسقة، خاصة لمسافة TV
  2. التحديات الحسابية: مسافة TV تعادل استخدام دالة تكلفة "سيئة" c(x,y) = 1_{x≠y} لمسافة Wasserstein، مما يصعب الحساب الفعال
  3. فضاء الدوال كبير جدًا: فضاء الدوال المقيسة المحدودة في الصيغة الثنائية القياسية كبير جدًا، مما يصعب التقييم الفعال
  4. قيود المجموعة الداعمة: تتطلب الطرق الموجودة عادةً مجموعات داعمة مضغوطة

دافع البحث

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

المساهمات الأساسية

  1. مخطط الحساب العددي: تقديم سلسلة استرخاء برمجة شبه محددة بناءً على التسلسل الهرمي Moment-SOS، يمكنها تقريب مسافة TV بدقة عشوائية
  2. الضمانات النظرية: إثبات الرتابة والتقارب للسلسلة الاسترخائية، مع تقارب القيم المثلى من الأسفل إلى مسافة TV الحقيقية
  3. معالجة الدعم غير المضغوط: تنطبق الطريقة على القياسات ذات الدعم غير المضغوط، وتتطلب فقط تحقق شرط كارليمان
  4. الحل الدقيق للحالات الخاصة: بالنسبة للقياسات الذرية على المحور الحقيقي، يمكن الحصول على حل دقيق عندما تكون درجة الاسترخاء n ≥ maxm₁,m₂
  5. النظرية الثنائية: توفير برمجة شبه محددة ثنائية، توضح كيفية تقوية صيغة TV الثنائية الكلاسيكية من خلال التقييد على كثيرات الحدود وإضافة حدود عقوبة

شرح الطريقة

تعريف المهمة

بالنظر إلى قياسين محدودين Borel μ, ν ∈ M(ℝᵈ)₊، احسب مسافة التباين الكلي بينهما: ∥μ−ν∥TV=sup⁡f{∫fdμ−∫fdν:∥f∥∞≤1}\|\mu - \nu\|_{TV} = \sup_f \left\{\int f d\mu - \int f d\nu : \|f\|_\infty \leq 1\right\}

الافتراضات الأساسية

الافتراض 2.5:

  1. جميع عزوم μ و ν محدودة
  2. يحقق μ و ν الشرط: ∫exp⁡(c∣xi∣)dμ<∞\int \exp(c|x_i|) d\mu < \infty، لبعض c > 0 وجميع i = 1,...,d

معمارية الطريقة

1. إعادة صياغة البرمجة الخطية اللانهائية الأبعاد

إعادة صياغة مسافة TV كبرمجة خطية لانهائية الأبعاد: τ=inf⁡ϕ+,ϕ−∈M(Rd)+{ϕ+(1)+ϕ−(1):ϕ+−ϕ−=μ−ν}\tau = \inf_{\phi_+,\phi_- \in M(\mathbb{R}^d)_+} \{\phi_+(1) + \phi_-(1) : \phi_+ - \phi_- = \mu - \nu\}

2. تعزيز القيود الرئيسية

إضافة قيود الهيمنة للحصول على مسألة معادلة: ρ=inf⁡ϕ+,ϕ−∈M(Rd)+{ϕ+(1)+ϕ−(1):ϕ+−ϕ−=μ−ν;ϕ+≤μ;ϕ−≤ν}\rho = \inf_{\phi_+,\phi_- \in M(\mathbb{R}^d)_+} \{\phi_+(1) + \phi_-(1) : \phi_+ - \phi_- = \mu - \nu; \phi_+ \leq \mu; \phi_- \leq \nu\}

3. تحويل شروط العزوم

باستخدام اللمة 2.2، قيود الهيمنة تعادل شروط مصفوفة العزوم: ϕ≤μ⇔Mn(ϕ)⪯Mn(μ),∀n∈N\phi \leq \mu \Leftrightarrow M_n(\phi) \preceq M_n(\mu), \forall n \in \mathbb{N}

4. استرخاء البرمجة الشبه المحددة

مسألة الاسترخاء من الدرجة n: ρn=min⁡ϕ,ψ{ϕ(1)+ψ(1):ϕα−ψα=μα−να,∀α∈N2nd;\rho_n = \min_{\phi,\psi} \{\phi(1) + \psi(1) : \phi_\alpha - \psi_\alpha = \mu_\alpha - \nu_\alpha, \forall \alpha \in \mathbb{N}^d_{2n};0⪯Mn(ϕ)⪯Mn(μ);0⪯Mn(ψ)⪯Mn(ν)}0 \preceq M_n(\phi) \preceq M_n(\mu); 0 \preceq M_n(\psi) \preceq M_n(\nu)\}

نقاط الابتكار التقني

  1. الدور الحاسم لقيود الهيمنة: على الرغم من أنها زائدة في الصيغة اللانهائية الأبعاد، إلا أنها أداة ضغط مفيدة جدًا في مخطط الاسترخاء
  2. الاستخدام الماهر لشرط كارليمان: يضمن تفرد القياس، مما يجعل قيود العزوم معادلة لقيود الهيمنة
  3. ظهور تحليل Hahn-Jordan بشكل طبيعي: يتقارب الحل الأمثل إلى عزوم تحليل Hahn-Jordan لـ μ-ν
  4. تقييد كثيرات الحدود للمسألة الثنائية: معالجة قيد ‖f‖∞ ≤ 1 من خلال التقييد على فضاء كثيرات الحدود وإضافة حدود عقوبة

إعداد التجارب

أدوات التنفيذ

  • البرنامج: GloptiPoly 3 لتحسين كثيرات الحدود
  • المحلل: محلل البرمجة الشبه المحددة SeDuMi 1.03
  • المنصة: دفتر HP Elitebook Ubuntu 24

حالات الاختبار

1. القياسات المنفصلة

  • الدعم المنفصل: X = {-1.0, 0.0, 1.0, 2.0}, Y = {-0.7, 0.3, 1.3, 2.3}
  • نقطة مشتركة واحدة: X ∩ Y = {-1.0}
  • ذرات قريبة: اختبار الاستقرار العددي

2. القياسات الغاوسية

  • توزيعات غاوسية بمتوسطات وتباينات مختلفة N(m₁,σ₁) و N(m₂,σ₂)
  • عدد العزوم من 2n = 4 إلى 2n = 8

مؤشرات التقييم

  • قرب القيم المثلى للاسترخاء ρₙ من مسافة TV الحقيقية
  • سرعة التقارب والاستقرار العددي
  • وقت الحساب (جميع النتائج اكتملت في أقل من 0.35 ثانية)

نتائج التجارب

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

1. التحقق النظري (النظرية 3.4)

بالنسبة للقياسات الذرية على المحور الحقيقي، يتم الحصول على حل دقيق عندما n ≥ maxm₁,m₂:

  • المثال 1: μ = δ₀, ν = δₑ، ρ₁ = 2 (دقيق)
  • المثال 2: أربع ذرات، نقطة مشتركة واحدة، ρ₄ = 1.499 ≈ 1.5
  • المثال 3: ذرات منفصلة، ρ₄ = 1.9999 ≈ 2

2. نتائج القياسات الغاوسية

(m₁,σ₁)(m₂,σ₂)ρ₁ρ₂ρ₃ρ₄
(0,0.1)(1,0.1)1.92311.99361.99911.9997
(0,0.2)(1,0.2)1.72411.90491.93761.939
(0,0.5)(1,0.5)1.00001.00001.16531.1897

3. النتائج المهمة

  • ρ₁ يتطابق تماماً مع الحد الأدنى التحليلي في المرجع 1
  • تحسن كبير ابتداءً من n=2، مع نتائج أفضل عند n=3,4
  • عند التباينات الصغيرة، يقترب السلوك من القياسات المتعارضة تماماً (مسافة TV قريبة من 2)

تحليل التقارب

النظرية 3.1 تضمن:

  1. لكل استرخاء حل أمثل موجود
  2. ρₙ ↑ ‖μ-ν‖_ يتقارب بشكل رتيب
  3. الحل الأمثل يتقارب إلى عزوم تحليل Hahn-Jordan

الأعمال ذات الصلة

الاتجاهات البحثية الرئيسية

  1. المقدرات التجريبية: تقدير المسافة بناءً على العينات، لكن مقدرات مسافة TV غالباً ما تكون غير متسقة
  2. الحدود التحليلية: توفير حدود عليا وسفلى لفئات توزيع محددة (مثل الغاوسيات عالية الأبعاد، خليط غاوسي)
  3. طرق عدم المساواة: عدم مساواة Pinsker، حدود مسافة Hellinger
  4. النقل الأمثل: خوارزميات متخصصة لمقياس Kantorovich (مثل خوارزمية Sinkhorn)

مزايا هذه الورقة

  1. العمومية: تنطبق على القياسات العامة التي تحقق شرط كارليمان
  2. الدعم غير المضغوط: لا تتطلب مجموعات داعمة مضغوطة
  3. التقارب المضمون: ضمان نظري للتقارب الرتيب
  4. العملية: يمكنها التعامل مع كل من الصيغ المغلقة والعزوم التجريبية

الخلاصة والنقاش

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

  1. توفير مخطط عددي عام لحساب مسافة TV
  2. تحقيق تقريب دقيق عشوائي تحت افتراضات ضعيفة نسبياً
  3. كل استرخاء يوفر حد أدنى مضمون
  4. يمكن الحصول على حل دقيق للقياسات المنفصلة

القيود

  1. الحساسية للبعد: الطريقة حساسة للبعد، حالياً محدودة بمسائل البعد الصغير
  2. قيود محلل البرمجة الشبه المحددة: لا يمكن توقع حل مسائل استرخاء عالية الدرجة
  3. الدقة العددية: قد تواجه مشاكل عددية عندما تكون الذرات قريبة جداً
  4. متطلبات حجم العينة: عند استخدام العزوم التجريبية، يتطلب حجم عينة كافٍ

الاتجاهات المستقبلية

  1. توفير حدود سفلى بديلة أقل تكلفة حسابية
  2. التوسع للتعامل مع المسائل عالية الأبعاد
  3. تحسين الاستقرار العددي
  4. دراسات مقارنة مع مقاييس المسافة الأخرى

التقييم المتعمق

المزايا

  1. الصرامة النظرية: إثبات كامل للتقارب والنظرية الثنائية
  2. جدة الطريقة: أول تطبيق للتسلسل الهرمي Moment-SOS على حساب مسافة TV
  3. القيمة العملية: يمكنها التعامل مع كل من البيانات المغلقة والعينات
  4. ضمان الدقة: يمكن الحصول على حل دقيق للحالات الخاصة (القياسات الذرية)

أوجه القصور

  1. التعقيد الحسابي: التعقيد الحسابي لبرمجة شبه محددة يحد من نطاق التطبيق
  2. محدودية التجارب: الاختبارات تركز بشكل أساسي على مسائل منخفضة الأبعاد وتوزيعات بسيطة
  3. نقص المقارنة مع الطرق الموجودة: افتقار إلى مقارنة منهجية مع طرق حساب مسافة TV الأخرى

التأثير

  1. المساهمة النظرية: توفير إطار نظري جديد لحساب مسافة TV
  2. القيمة المنهجية: توضيح إمكانات التسلسل الهرمي Moment-SOS في حساب مقاييس الاحتمالية
  3. التطبيقات العملية: توفير أدوات جديدة لمجالات مثل التحسين القوي للتوزيع

السيناريوهات المناسبة

  1. متطلبات الحساب الدقيق: الحاجة إلى حد أدنى مضمون نظرياً لمسافة TV
  2. المسائل منخفضة الأبعاد: التطبيقات العملية ذات البعد المنخفض نسبياً
  3. التوزيعات الخاصة: التوزيعات الغاوسية والأسية وخليطها
  4. التوزيعات المنفصلة: القياسات الذرية ذات الدعم المحدود

المراجع

تستشهد الورقة بـ 28 مرجعاً ذا صلة، تغطي مجالات متعددة بما فيها النقل الأمثل ومسائل العزوم والبرمجة الشبه المحددة ومقاييس الاحتمالية، خاصة سلسلة أعمال المؤلف في التسلسل الهرمي Moment-SOS 21,24,26 التي تشكل الأساس النظري لهذه الورقة.