2025-11-22T15:28:16.372787

An Augmented Lagrangian Value Function Method for Lower-level Constrained Stochastic Bilevel Optimization

Nie, Li, Wen
Recently, lower-level constrained bilevel optimization has attracted increasing attention. However, existing methods mostly focus on either deterministic cases or problems with linear constraints. The main challenge in stochastic cases with general constraints is the bias and variance of the hyper-gradient, arising from the inexact solution of the lower-level problem. In this paper, we propose a novel stochastic augmented Lagrangian value function method for solving stochastic bilevel optimization problems with nonlinear lower-level constraints. Our approach reformulates the original bilevel problem using an augmented Lagrangian-based value function and then applies a penalized stochastic gradient method that carefully manages the noise from stochastic oracles. We establish an equivalence between the stochastic single-level reformulation and the original constrained bilevel problem and provide a non-asymptotic rate of convergence for the proposed method. The rate is further enhanced by employing variance reduction techniques. Extensive experiments on synthetic problems and real-world applications demonstrate the effectiveness of our approach.
academic

طريقة دالة القيمة لاغرانج المعززة للتحسين ثنائي المستوى العشوائي مع قيود المستوى الأدنى

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

  • معرّف الورقة: 2509.24249
  • العنوان: طريقة دالة القيمة لاغرانج المعززة للتحسين ثنائي المستوى العشوائي مع قيود المستوى الأدنى
  • المؤلفون: Hantao Nie (جامعة بكين)، Jiaxiang Li (جامعة مينيسوتا)، Zaiwen Wen (جامعة بكين)
  • التصنيف: math.OC (التحسين الرياضي والتحكم)
  • تاريخ النشر: يناير 2025 (نسخة أولية على arXiv)
  • رابط الورقة: https://arxiv.org/abs/2509.24249v2

الملخص

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

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

  1. خلفية المشكلة: يظهر التحسين ثنائي المستوى مع قيود المستوى الأدنى (LC-BLO) على نطاق واسع في مجال التعلم الآلي، بما في ذلك تحسين المعاملات الفائقة والتعلم الفوقي والتعلم المعزز. تتميز هذه المشاكل ببنية هرمية، حيث يعتمد حل المستوى الأعلى على الحل الأمثل لمشكلة التحسين المقيدة في المستوى الأدنى.
  2. قيود الطرق الموجودة:
    • تركز معظم الطرق الموجودة على الحالات الحتمية أو مشاكل القيود الخطية
    • تفتقر المشاكل غير الخطية المقيدة في الحالة العشوائية إلى حلول فعالة
    • يكمن التحدي الرئيسي في انحياز التدرج الفائق وتباينه الناجم عن الحل غير الدقيق للمشكلة الأدنى
  3. التحديات التقنية:
    • عدم سلاسة دالة الهدف الفائقة
    • انحياز التدرج الفائق الناجم عن الحل غير الدقيق للمشكلة الأدنى
    • إدارة الضوضاء من الأوراكل العشوائي
  4. الدافع البحثي: سد الفجوة في النظرية والخوارزميات للتحسين ثنائي المستوى غير الخطي المقيد العشوائي، وتوفير خوارزميات فعالة مع ضمانات نظرية للتطبيقات العملية في التعلم الآلي.

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

  1. طريقة إعادة البناء المبتكرة: تقترح إعادة صياغة المشكلة ثنائي المستوى بناءً على دالة لاغرانج المعززة العشوائية وغلافها Moreau، مما يعالج بفعالية الضوضاء الناجمة عن الحل غير الدقيق للمشكلة الأدنى
  2. التكافؤ النظري: تثبت التكافؤ بين إعادة البناء أحادي المستوى العشوائي والمشكلة ثنائي المستوى الأصلية، مما يوفر طريقة عملية وذات أساس نظري متين
  3. أول تحليل تقارب: توفر أول تحليل تقارب لطريقة دالة القيمة في إعدادات عشوائية لـ LC-BLO غير الخطية، مما يثبت تعقيد العينة Õ(cε⁻²)، Õ(cc₁²ε⁻²)
  4. تحسين تقليل التباين: تحسن تعقيد العينة للمتغيرات في المستوى الأعلى إلى Õ(c^1.5ε⁻^1.5) من خلال تقنيات تقليل التباين

شرح الطريقة

تعريف المهمة

ضع في الاعتبار مشكلة التحسين ثنائي المستوى العشوائي مع قيود المستوى الأدنى:

المشكلة في المستوى الأدنى:

min_{y∈Y} G(x,y) = E_{ξ~D_ξ}[g(x,y;ξ)]
s.t. H_i(x,y) ≤ 0, i = 1,...,p

المشكلة في المستوى الأعلى:

min_{x∈X} F(x,y*(x)) = E_{ζ~D_ζ}[f(x,y*(x);ζ)]
s.t. y*(x) ∈ arg min_{y∈Y(x)} G(x,y)

حيث Y(x) := {y ∈ Y | H(x,y) ≤ 0} هي المنطقة الممكنة للمستوى الأدنى.

معمارية النموذج

1. إعادة البناء لاغرانج المعززة

إدخال حد العقوبة لاغرانج المعززة:

A_{γ₁}(x,y,z) = (1/2γ₁)∑ᵢ[γ₁zᵢ + Hᵢ(x,y)]²₊

تعريف دالة لاغرانج المعززة:

L_{γ₁}(x,y,z) = G(x,y) + A_{γ₁}(x,y,z)

2. دالة قيمة غلاف Moreau

بناء الدالة المزدوجة وغلافها Moreau:

D_{γ₁}(x,z) = min_{y∈Y} L_{γ₁}(x,y,z)
E^{γ₂}_{γ₁}(x,z) = max_{λ∈ℝ^p₊} {D_{γ₁}(x,λ) - (γ₂/2)||λ-z||²}

3. إعادة البناء أحادي المستوى

إعادة صياغة المشكلة ثنائي المستوى الأصلية إلى:

min_{(x,y,z)∈X×Y×ℝ^p₊} F(x,y)
s.t. Ĝ(x,y,z;ξ) ≤ ε₁, (1/2)∑ᵢ[Hᵢ(x,y)]²₊ ≤ ε₂²

حيث Ĝ(x,y,z;ξ) = G(x,y) - ℓ_γ(x,z,ŵ(ξ),λ̂(ξ)).

4. طريقة العقوبة

اعتماد إعادة بناء العقوبة لاغرانج المعززة:

min_{(x,y,z)∈X×Y×Z} E_ξ[Ψ(x,y,z;ξ)]

حيث Ψ(x,y,z;ξ) := F(x,y) + c₁Ĝ(x,y,z;ξ) + (c₂/2)∑ᵢHᵢ(x,y)²₊

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

  1. بنية الخوارزمية ثنائية الحلقة:
    • الحلقة الداخلية: استخدام طريقة لاغرانج المعززة العشوائية (SALM) لحل المشاكل الفرعية
    • الحلقة الخارجية: تطبيق الانحدار العشوائي على المشكلة المعاد بناؤها
  2. آلية التحكم في الانحياز: التخفيف من مشكلة التدرج المنحاز من خلال التحكم في دقة حل المستوى الأدنى
  3. تقنية تقليل التباين: اعتماد قواعد التحديث المشابهة لـ STORM لتقليل تعقيد العينة للمتغيرات في المستوى الأعلى

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

مجموعات البيانات

  1. المشاكل الاصطناعية: أمثلة اختبار من Jiang et al. (2012)، مع إضافة ضوضاء غاوسية σ = 0.1
  2. تحسين معاملات SVM الفائقة: إجراء على مجموعات بيانات Diabetes و Fourclass
  3. ضبط تسوس الوزن: استخدام شبكة MLP ذات طبقتين على مجموعة بيانات digit لتحسين معاملات تسوس الوزن للشبكة العصبية

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

  • دقة الاختبار
  • وقت التقارب
  • عدد التكرارات
  • قيمة دالة الهدف

طرق المقارنة

  • LV-HBA: طريقة قائمة على دالة قيمة لاغرانج
  • GAM: طريقة التدرج المعزز
  • BLOCC: طريقة التحكم في القيود للتحسين ثنائي المستوى
  • SALVF: الطريقة الأساسية المقترحة في هذه الورقة
  • SALVF-VR: نسخة تقليل التباين المقترحة في هذه الورقة

تفاصيل التنفيذ

  • حجم الخطوة للحلقة الداخلية: ηⱼ = η/(j+1)، ρⱼ = ρ/(j+1)
  • حجم الخطوة للحلقة الخارجية: αₖ = α < 1/(2L_Ψ)
  • حجم العينة: rₖ = r، qₖ = q، sₖ = s (ثابت)
  • معاملات العقوبة: يتم اختيار c₁، c₂ وفقاً للتحليل النظري

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

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

  1. المشاكل الاصطناعية: يتقارب كل من SALVF و SALVF-VR بالقرب من الحل الأمثل العام، مع توزيع أكثر تركيزاً لـ SALVF-VR، مما يتحقق من تأثير التسريع لتقليل التباين
  2. تحسين معاملات SVM الفائقة:
    • يتفوق SALVF على جميع الطرق الأساسية من حيث دقة الاختبار
    • على الرغم من أن BLOCC يمكنه أيضاً الوصول إلى دقة ذروة مماثلة، إلا أن SALVF أكثر كفاءة في الوقت من حيث التكرار
    • يحقق حوالي 80% دقة اختبار على مجموعة بيانات Diabetes، وحوالي 75% على مجموعة بيانات Fourclass
  3. ضبط تسوس الوزن:
    • تتفوق جميع طرق التحسين ثنائي المستوى على الخط الأساسي بدون تسوس وزن، مما يقلل بفعالية الإفراط في التدريب
    • يحقق SALVF الكفاءة الزمنية الأمثل، بفضل بساطة عملية التكرار ثنائية الحلقة

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

  1. تعقيد العينة:
    • SALVF: (Õ(cε⁻²)، Õ(cc₁²ε⁻²))
    • SALVF-VR: (Õ(c^1.5ε⁻^1.5)، Õ(c^1.5c₁²ε⁻^2.5))
  2. معدل التقارب:
    • SALVF: تعقيد التكرار Õ(cε⁻¹)
    • SALVF-VR: تعقيد التكرار Õ(c^1.5ε⁻^1.5)

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

  1. فعالية تقليل التباين: يحقق SALVF-VR تحسناً ملحوظاً مقارنة بـ SALVF من حيث تركيز التوزيع وسرعة التقارب
  2. ميزة الكفاءة الزمنية: تتمتع البنية ثنائية الحلقة بميزة حسابية واضحة مقارنة بطرق ثلاثية الحلقة (مثل BLOCC)
  3. التحقق من الجدوى العملية: الأداء الممتازة في مهام التعلم الآلي الحقيقية، مما يتحقق من القيمة العملية للطريقة

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

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

  1. طرق التدرج الضمني (IG): تركز بشكل أساسي على حساب التدرج الفائق، لكنها تتطلب مشتقات من الدرجة الثانية، مما يزيد من التكلفة الحسابية
  2. طرق دالة قيمة المستوى الأدنى (LLVF): إدخال دالة قيمة المشكلة الأدنى، كبديل خالٍ من Hessian
  3. طرق العقوبة: تحويل المشاكل المقيدة إلى مشاكل غير مقيدة للحل

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

  1. أول تحليل عشوائي غير خطي مقيد: تركز الأعمال الموجودة بشكل أساسي على الحالات الحتمية أو المقيدة خطياً
  2. ضمانات نظرية: توفير تحليل معدل تقارب غير مقارب
  3. الجدوى العملية: لا تتطلب حساب Hessian، مناسبة للمشاكل الكبيرة الحجم

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

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

  1. حل بنجاح مشكلة التحسين ثنائي المستوى غير الخطي المقيد العشوائي، وهي مشكلة مهمة لكن لم تُدرس بشكل كافٍ
  2. تظهر طريقة دالة القيمة لاغرانج المعززة المقترحة أداءً ممتازاً من الناحية النظرية والعملية
  3. تحسن تقنية تقليل التباين بفعالية أداء الخوارزمية

القيود

  1. اعتماد تعقيد العينة: لا يزال تعقيد العينة للمتغيرات في المستوى الأدنى مرتفعاً (O(c₁²ε⁻¹))
  2. اختيار المعاملات: يعتمد اختيار معاملات العقوبة c₁، c₂ على معاملات المشكلة، وقد يتطلب ضبطاً
  3. افتراض التحدب القوي: تتطلب المشكلة في المستوى الأدنى افتراض التحدب القوي

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

  1. تحسين تعقيد العينة: استكشاف ما إذا كان يمكن تقليل تعقيد العينة للمتغيرات في المستوى الأعلى والأدنى في نفس الوقت
  2. اختيار المعاملات التكيفية: تطوير استراتيجيات لاختيار معاملات العقوبة بشكل تكيفي
  3. التوسع غير المحدب: التوسع إلى حالات المشاكل غير المحدبة في المستوى الأدنى

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

المزايا

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

أوجه القصور

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

التأثير

  1. القيمة الأكاديمية: سد فجوة نظرية مهمة، توفير أساس للأبحاث اللاحقة
  2. القيمة العملية: تطبيقات محتملة في عدة تطبيقات مهمة في التعلم الآلي
  3. قابلية إعادة الإنتاج: توفير وصف خوارزمي مفصل وتحليل نظري

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

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

المراجع

تستشهد الورقة بـ 49 مرجعاً ذا صلة، تشمل بشكل أساسي:

  • الأعمال الكلاسيكية والتطورات الحديثة في التحسين ثنائي المستوى
  • الأساس النظري لطرق لاغرانج المعززة
  • تقنيات التحسين العشوائي وتقليل التباين
  • حالات التطبيق في التعلم الآلي

التقييم الشامل: هذه ورقة عالية الجودة تجمع بين النظرية والتطبيق، محققة تقدماً جوهرياً في مشكلة مهمة لكن صعبة، مما يساهم بشكل كبير في مجال التحسين ثنائي المستوى المقيد العشوائي. الطريقة مبتكرة، والنظرية صارمة، والتجارب شاملة، مع قيمة أكاديمية وآفاق عملية جيدة جداً.