2025-11-16T12:28:12.323029

Almost sure convergence rates of adaptive increasingly rare Markov chain Monte Carlo

Hofstadler, Latuszynski, Roberts et al.
We consider adaptive increasingly rare Markov chain Monte Carlo (MCMC) algorithms, which are adaptive MCMC methods, where the adaptation concerning the "past'' happens less and less frequently over time. Under a contraction assumption with respect to a Wasserstein-like function we deduce upper bounds of the convergence rate of Monte Carlo sums taking a renormalisation factor into account that is "almost'' the one that appears in a law of the iterated logarithm. We demonstrate the applicability of our results by considering different settings, among which are those of simultaneous geometric and uniform ergodicity. All proofs are carried out on an augmented state space, including the classical non-augmented setting as a special case. In contrast to other adaptive MCMC limit theory, some technical assumptions, like diminishing adaptation, are not needed.
academic

معدلات التقارب شبه المؤكد لسلاسل مارkov مونت كارلو التكيفية المتناقصة بشكل متزايد

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

  • معرّف الورقة: 2402.12122
  • العنوان: معدلات التقارب شبه المؤكد لسلاسل مارkov مونت كارلو التكيفية المتناقصة بشكل متزايد
  • المؤلفون: جوليان هوفستادلر (جامعة باث)، كريستوف لاتوسزينسكي (جامعة وارويك)، جاريث أو. روبرتس (جامعة وارويك)، دانيال رودولف (جامعة باساو)
  • التصنيفات: math.NA cs.NA math.PR math.ST stat.TH
  • تاريخ النشر: 14 أكتوبر 2025 (نسخة arXiv)
  • رابط الورقة: https://arxiv.org/abs/2402.12122

الملخص

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

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

تعريف المشكلة

في الإحصاء الحسابي، يتمثل التحدي الشامل في تقريب القيم المتوقعة: ν(f)=∫Xf(x)ν(dx)\nu(f) = \int_X f(x)\nu(dx) حيث ν\nu هي التوزيع المستهدف و f:X→Rf: X \to \mathbb{R} هي دالة قابلة للتكامل ذات اهتمام.

دافع البحث

  1. صعوبة الأخذ العينات المباشر: عندما يكون الأخذ المباشر من ν\nu مستحيلاً أو غير قابل للتطبيق من الناحية الحسابية (على سبيل المثال، الكثافة تحتوي على ثابت تطبيع غير معروف)، هناك حاجة إلى طرق بديلة.
  2. تحديات MCMC التكيفية: تحدّث طرق MCMC التكيفية التقليدية آلية الانتقال أحادية الخطوة من خلال النظر في السجل الكامل، مما يؤدي إلى عملية غير ماركوفية، مما يعقد التحليل الرياضي.
  3. الحاجة إلى تبسيط الافتراضات التقنية: تتطلب نظرية MCMC التكيفية الحالية عادة افتراضات تقنية (مثل التكيف المتناقص)، مما يحد من قابلية تطبيق الطريقة.

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

  • الطبيعة غير الماركوفية لـ MCMC التكيفية تؤدي إلى تقنيات إثبات معقدة
  • تتطلب شروط تقنية صارمة لضمان التقارب
  • نقص النتائج المتعلقة بتقارب مجاميع مونت كارلو المعاد تطبيعها

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

  1. اقتراح إطار عمل نظري AIR MCMC: إنشاء نظرية معدل التقارب شبه المؤكد لخوارزميات AIR تحت افتراضات انكماش Wasserstein.
  2. معدلات تقارب محسّنة: الحصول على معدلات تقارب من الشكل r(n)=n(log⁡n)1/2+εr(n) = \sqrt{n}(\log n)^{1/2+\varepsilon} أو r(n)=n1/2+εr(n) = n^{1/2+\varepsilon}، القريبة من معدل التقارب الأمثل لقانون اللوغاريتم المتكرر.
  3. تبسيط الافتراضات التقنية: عدم الحاجة إلى افتراضات تقنية تقليدية مثل التكيف المتناقص، مما يوسع نطاق تطبيق الطريقة.
  4. تحليل فضاء الحالة المعزز: إجراء التحليل على فضاء الحالة المعزز Y=X×ΦY = X \times \Phi، مع تضمين الإعدادات غير المعززة الكلاسيكية كحالات خاصة.
  5. قابلية تطبيق واسعة: تنطبق النتائج على إعدادات متعددة مثل الإرجوديكية الهندسية والإرجوديكية المنتظمة المتزامنة.

شرح الطريقة

تعريف خوارزمية AIR MCMC

بالنظر إلى معامل β>0\beta > 0، حدد kj=⌈jβ⌉k_j = \lceil j^\beta \rceil، وقم بالتكيف فقط في نقاط زمنية محددة: Tm=∑j=1mkjT_m = \sum_{j=1}^m k_j

الملاحظة الرئيسية: لأي β>0\beta > 0، توجد ثوابت cβ,Cβc_\beta, C_\beta بحيث: cβm1+β≤Tm≤Cβm1+βc_\beta m^{1+\beta} \leq T_m \leq C_\beta m^{1+\beta}

هذا يعني أن تكرار التكيف يتناقص.

الإطار التقني الأساسي

1. دوال تشبه Wasserstein

لدالة المسافة d:Y×Y→R+d: Y \times Y \to \mathbb{R}_+، عرّف: W(μ1,μ2):=inf⁡ξ∈C(μ1,μ2)∫Y2d(x,y)ξ(dx,dy)W(\mu_1, \mu_2) := \inf_{\xi \in C(\mu_1,\mu_2)} \int_{Y^2} d(x,y)\xi(dx,dy)

2. الافتراضات الرئيسية (الافتراض 3.1)

لكل γ∈I\gamma \in I، افترض:

  • πγ\pi_\gamma هي التوزيع الثابت لـ PγP_\gamma
  • τ(Pγ)≤M\tau(P_\gamma) \leq M و τ(Pγk0)≤τ\tau(P_\gamma^{k_0}) \leq \tau حيث M∈[1,∞)M \in [1,\infty)، τ∈[0,1)\tau \in [0,1)، k0∈Nk_0 \in \mathbb{N} مستقلة عن γ\gamma.

3. حل معادلة بواسون

لدالة h:Y→Rh: Y \to \mathbb{R} و γ∈I\gamma \in I، حل معادلة بواسون هو: uγ(y)=∑ℓ=0∞(Pγℓf(y)−πγ(f))u_\gamma(y) = \sum_{\ell=0}^{\infty}(P_\gamma^\ell f(y) - \pi_\gamma(f))

تقنية التقريب بالمارتينجيل

استخدم تحلل معادلة بواسون لمجاميع مونت كارلو: ∑j=1n(h(Yj)−πΓj−1(h))=Mn+Rm+حدود محدودة\sum_{j=1}^n (h(Y_j) - \pi_{\Gamma_{j-1}}(h)) = M_n + R_m + \text{حدود محدودة}

حيث:

  • MnM_n: حد المارتينجيل
  • RmR_m: الحد المتبقي، يتم تبسيطه بشكل كبير لخوارزمية AIR

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

النظرية 3.5 (حالة β≥1\beta \geq 1)

تحت افتراض الانحراف المحدود، لأي ε>0\varepsilon > 0: lim⁡n→∞1n(log⁡n)1/2+ε∑j=1n(f(Xj)−ν(f))=0تقريباً مؤكداً\lim_{n \to \infty} \frac{1}{\sqrt{n}(\log n)^{1/2+\varepsilon}} \sum_{j=1}^n (f(X_j) - \nu(f)) = 0 \quad \text{تقريباً مؤكداً}

النظرية 3.6 (حالة β∈(0,1)\beta \in (0,1))

لـ ε>11+β−12\varepsilon > \frac{1}{1+\beta} - \frac{1}{2}: lim⁡n→∞1n1/2+ε∑j=1n(f(Xj)−ν(f))=0تقريباً مؤكداً\lim_{n \to \infty} \frac{1}{n^{1/2+\varepsilon}} \sum_{j=1}^n (f(X_j) - \nu(f)) = 0 \quad \text{تقريباً مؤكداً}

النظرية 3.11 (شرط Lyapunov)

تحت افتراض وجود دالة Lyapunov، لـ ε>max⁡{0,11+β+1p−12}\varepsilon > \max\{0, \frac{1}{1+\beta} + \frac{1}{p} - \frac{1}{2}\}: lim⁡n→∞1n1/2+ε∑j=1n(f(Xj)−ν(f))=0تقريباً مؤكداً\lim_{n \to \infty} \frac{1}{n^{1/2+\varepsilon}} \sum_{j=1}^n (f(X_j) - \nu(f)) = 0 \quad \text{تقريباً مؤكداً}

أمثلة التطبيق

1. إعداد الإرجوديكية المنتظمة

استخدم المقياس البديهي d(y1,y2)=1{y1≠y2}d(y_1, y_2) = \mathbf{1}_{\{y_1 \neq y_2\}}، حيث يتوافق WW مع مسافة التباين الكلي.

النتيجة 4.5: لدالة محدودة ff، تحت β≥1\beta \geq 1 و ε>0\varepsilon > 0: ∣1n∑j=1n(f(Xj(ω))−ν(f))∣≤(log⁡n)1/2+εnC(ω)\left|\frac{1}{n}\sum_{j=1}^n (f(X_j(\omega)) - \nu(f))\right| \leq \frac{(\log n)^{1/2+\varepsilon}}{\sqrt{n}} C(\omega)

2. إعداد الإرجوديكية الهندسية

ضع في الاعتبار شرط الانجراف والمجموعة الصغيرة (الافتراض 4.7)، واستخدم المقياس المرجح: dq(y1,y2)=1{y1≠y2}(Vq(y1)+Vq(y2))d_q(y_1, y_2) = \mathbf{1}_{\{y_1 \neq y_2\}}(V^q(y_1) + V^q(y_2))

3. الإرجوديكية الضعيفة لـ Harris

استخدم دالة المسافة: d~q(y1,y2)=d(y1,y2)(1+Vq(y1)+Vq(y2))\tilde{d}_q(y_1, y_2) = \sqrt{d(y_1, y_2)(1 + V^q(y_1) + V^q(y_2))}

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

1. التحكم المبسط في الحد المتبقي

الميزة الرئيسية لخوارزمية AIR هي أن معظم الحدود الصعبة في الحد المتبقي RmR_m تلغي بعضها البعض، بحيث: ∣Rm∣≤n1/(1+β)⋅ثابت|R_m| \leq n^{1/(1+\beta)} \cdot \text{ثابت}

2. عدم الحاجة إلى التكيف المتناقص

بخلاف الطرق التقليدية، لا تتطلب افتراض ∥Γn−Γn−1∥→0\|\Gamma_n - \Gamma_{n-1}\| \to 0.

3. معالجة فضاء الحالة المعزز

من خلال الإعداد Y=X×ΦY = X \times \Phi، قم بمعالجة موحدة للحالات المعقدة مثل التوزيعات متعددة الأنماط.

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

الورقة موجهة بشكل أساسي نحو التحليل النظري، مع التحقق من النتائج بالطرق التالية:

1. أمثلة الخوارزميات المحددة

  • خوارزمية Metropolis للمشي العشوائي التكيفي
  • خوارزمية MCMC الإسقاط الكروي التكيفية
  • خوارزمية Crank-Nicolson المسبقة (pCN)

2. مراجع المقارنة الرقمية

الاستشهاد بالتجارب الرقمية من CLR18، مما يوضح أن خوارزمية AIR تحقق أداء مماثلة للطرق التكيفية البحتة عند β∈[1,2]\beta \in [1,2].

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

نظرية MCMC التكيفية الكلاسيكية

  • قانون الأعداد الكبيرة: HST01, AR05, AM06, RR07, SV10, FMP11, PHL20
  • نظرية الحد المركزي: AM06, SV10
  • التقارب إلى مقياس الهدف الصحيح: RR07, FMP11

نتائج الإرجوديكية الكمية

  • AA07, AW15: توضح ∥P(Xn∈⋅)−ν∥tv≤C/n\|P(X_n \in \cdot) - \nu\|_{tv} \leq C/n
  • AW15, CLR18: حدود الخطأ التربيعي المتوسط، توضح تقارب الرتبة 1/n1/n

تفرد مساهمة هذه الورقة

  1. حدود التقارب للمسار: بخلاف حدود الخطأ المتوقعة الموجودة، توفر تقارب المسار شبه المؤكد
  2. إعداد انكماش Wasserstein: توسيع الإطار التقليدي للإرجوديكية المنتظمة/الهندسية
  3. معدل قريب من الأمثل: معدل التقارب قريب من القيمة النظرية المثلى لقانون اللوغاريتم المتكرر

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

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

  1. تتمتع خوارزمية AIR MCMC بخصائص تقارب شبه مؤكدة جيدة تحت افتراضات انكماش Wasserstein
  2. معدل التقارب قريب من الأمثل، بصيغة n(log⁡n)1/2+ε\sqrt{n}(\log n)^{1/2+\varepsilon}
  3. الافتراضات التقنية مبسطة بشكل كبير مقارنة بالطرق التقليدية

القيود

  1. متطلبات الاتساق: يتطلب الافتراض 3.1 أن تكون جميع الحدود موحدة فيما يتعلق بـ γ\gamma، وهو أمر مقيد إلى حد ما
  2. نظام β\beta الصغير: عندما يكون β∈(0,1)\beta \in (0,1)، يتدهور معدل التقارب، مما يتطلب افتراضات إضافية للتحسين
  3. الخوارزميات البحتة التكيفية: لا تزال هناك حاجة إلى مزيد من البحث لحالة β=0\beta = 0 البحتة التكيفية

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

  1. إضعاف افتراضات الاتساق: قد يكون من الممكن تخفيف الافتراض 3.1 في إطار خوارزميات التقريب العشوائي
  2. التوسع إلى التكيف البحت: استخدام تقنيات SV10 للتعامل مع حالة β=0\beta = 0
  3. تحسين نظام β\beta الصغير: تطوير تقنيات للتعامل مع β∈(0,1)\beta \in (0,1) دون الحاجة إلى افتراضات إضافية

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

المزايا

  1. العمق النظري: إنشاء نظرية AIR MCMC كاملة في إطار انكماش Wasserstein
  2. الابتكار التقني: الاستخدام الماهر لبنية AIR لتبسيط التحكم في الحد المتبقي في تقريب المارتينجيل
  3. قابلية التطبيق الواسعة: تغطي إعدادات متعددة مثل الإرجوديكية المنتظمة والهندسية والضعيفة لـ Harris
  4. القيمة العملية: توفير حدود تقارب المسار، مما له معنى عملي لمحاكاة واحدة

أوجه القصور

  1. تقييد الافتراضات: قد يكون من الصعب التحقق من افتراضات الاتساق في التطبيقات العملية
  2. معالجة نظام β\beta الصغير: تتطلب شروط Lipschitz الإضافية وشروط التكيف المتناقص
  3. التحقق الرقمي المحدود: موجهة بشكل أساسي نحو التحليل النظري، مع نقص التجارب الرقمية الكافية

التأثير

  1. المساهمة النظرية: توفير أساس نظري متين لـ AIR MCMC
  2. القيمة المنهجية: قد تلهم طريقة انكماش Wasserstein تحليل الخوارزميات الأخرى
  3. الآفاق العملية: حدود تقارب المسار لها أهمية كبيرة لتشخيص MCMC ومعايير التوقف

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

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

المراجع

تتضمن الورقة 34 مرجعاً مهماً، تغطي التطورات الرئيسية في نظرية MCMC التكيفية، خاصة:

  • CLR18: الاقتراح الأصلي لخوارزمية AIR
  • AM06, SV10: نظرية MCMC التكيفية الكلاسيكية
  • HMS11: الأساس النظري لطريقة انكماش Wasserstein
  • PHL20: طريقة فضاء الحالة المعزز