📊 statistics

Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems

تقدم هذه الورقة طرقاً من الدرجة الأولى تعتمد على الجزاءات لمسائل الأمثلية ثنائية المستوى ذات الهياكل التقليلية-التعظيمية (minimax) في كلا المستويين، حيث تُثبت تحسيناً في حدود تعقيد الأوراكل لتصل إلى $\tilde{O}(\epsilon^{-4})$ في الحالات الحتمية و $\tilde{O}(\epsilon^{-9})$ في الحالات العشوائية دون اشتراط فرضيات التحدب القوي على مسألة المستوى الأدنى.

المؤلفون الأصليون: Yiyang Shen, Yutian He, Weiran Wang, Qihang Lin

نُشر 2026-05-11

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Yiyang Shen, Yutian He, Weiran Wang, Qihang Lin

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

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

عادةً ما يكون قرار المستوى السفلي مثل البحث عن أدنى نقطة في وادٍ (تقليل - minimization). لكن هذه الورقة البحثية تتناول سيناريو أكثر صعوبة بكثير: ماذا لو كان قرار المستوى السفلي عبارة عن "شد حبل"؟

المشكلة الجوهرية: "شد الحبل" داخل اللغز

في هذه الورقة، ينظر المؤلفون إلى نوع معين من المسائل حيث:

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

على الرئيس أن يختار استراتيجية وهو يعلم أن الفريق سيبدأ فوراً في القتال فيما بينهم لإيجاد "نقطة السرج" (saddle point) (وهي حالة توازن لا يمكن لأي طرف فيها الفوز بتغيير حركته).

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

الحل: استراتيجية "العقوبة"

يقترح المؤلفون طريقة جديدة لحل ذلك باستخدام طريقة قائمة على العقوبة (Penalty-Based Method).

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

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

من خلال القيام بذلك، قاموا بتحويل مسألة معقدة ذات طبقتين إلى لعبة "الحد الأدنى الأقصى" (Min-Max) ضخمة وبسيطة يمكن للحواسيب القياسية التعامل معها بشكل أسرع بكثير.

ما حققوه (النتائج)

تدعي الورقة تحقيق انتصارين رئيسيين باستخدام نهج "الحكم الصارم" هذا:

تسريع الحالة الحتمية (بدون ضجيج):
عندما تكون الرياضيات مثالية وواضحة (حتمية/deterministic)، تجد طريقتهم حلاً جيداً بتعقيد يبلغ تقريباً $\tilde{O}(\epsilon^{-4})$ .
- الترجمة: إذا كنت تريد إجابة أكثر دقة بـ 10 مرات، فلن تحتاج إلى القيام بـ 1,000 ضعف العمل؛ بل ستحتاج فقط إلى القيام بحوالي 10,000 ضعف العمل.
- المقارنة: كانت الطرق السابقة لمسائل مشابهة مع قيود أبطأ بكثير (حوالي $\epsilon^{-7}$ ). لقد حسن المؤلفون هذا الأمر بشكل كبير.
التعامل مع الحالة الفوضوية والمشوشة (العشوائية):
في العالم الحقيقي، تكون البيانات مشوشة (مثل محاولة سماع محادثة في غرفة مزدحمة). قام المؤلفون بتوسيع طريقتهم لتتعامل مع هذا الإعداد "العشوائي" (stochastic).
- لقد أثبتوا أن طريقتهم لا تزال تعمل، حيث تجد حلاً "شبه مثالي" بتعقيد $\tilde{O}(\epsilon^{-9})$ .
- ملاحظة: رغم أن $\epsilon^{-9}$ تبدو رقماً مرتفعاً، إلا أن المؤلفين يقرون بأن هذه خطوة أولى لهذا النوع المحدد من المسائل، ويقترحون أن العمل المستقبلي (باستخدام تقليل التباين) يمكن أن يجعلها أسرع.

اختبارات من العالم الحقيقي

لم يكتف المؤلفون بالرياضيات فقط؛ بل اختبروا ذلك على شيئين:

المسائل الخطية الاصطناعية: أنشأوا ألغازاً رياضية وهمية لمقارنة طريقتهم مع الطرق الموجودة (FOP و SMO). وجدت طريقتهم أنها تتقارب بشكل أسرع وتجد حلولاً أفضل، خاصة عندما قاموا بضبط حساسية "الحكم".
ضبط المعلمات الفائقة (Hyperparameter Tuning) للذكاء الاصطناعي القوي: طبقوا هذا على مسألة واقعية تسمى التحسين القوي توزيعياً (Distributionally Robust Optimization - DRO).
- السيناريو: تخيل تدريب ذكاء اصطنا-ي للتعرف على الطيور. معظم الصور هي لطيور على اليابسة، لكن القليل منها هو لطيور على الماء. الذكاء الاصطناعي القياسي قد يغش عبر مجرد النظر إلى الخلفية (يابسة مقابل ماء) بدلاً من الطائر نفسه.
- الحل: استخدم المؤلفون هذه الطريقة ثنائية المستوى لضبط الذكاء الاصطناعي بحيث يعمل بشكل جيد حتى في "الحالة الأسوأ" (مثلاً: الطيور التي على الماء).
- النتيجة: حسنت طريقتهم الدقة على "المجموعة الأسوأ" بشكل كبير (على سبيل المثال، القفز من 41% إلى 75% في إحدى مجموعات البيانات) مقارنة بالطرق الموجودة، دون التأثير سلباً على الأداء المتوسط العام.

الملخص

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

ملخص تقني: طرق الرتبة الأولى القائمة على العقوبة لمسائل التحسين ثنائي المستوى مع مسائل المينيمكس والمسائل ذات المستوى الأدنى المقيد

صياغة المسألة

تتناول هذه الورقة فئة من مسائل التحسين ثنائية المستوى (Bilevel Optimization) حيث تظهر كل من المسألة في المستوى الأعلى والمستوى الأدنى هياكل "مينيمكس" (Minimax). يتم تعريف الصياغة العامة كالتالي:
$\min_{x_1, y_1, y_2} \left\{ \max_{x_2} f(x_1, x_2, y_1, y_2) \mid (y_1, y_2) \in \arg\min_{z_1} \max_{z_2} \tilde{f}(x_1, z_1, z_2) \right\}$
حيث تمثل $(y_1, y_2)$ نقطة السرج (Saddle-point) للدالة $\tilde{f}$ في المستوى الأدنى. يفترض المؤلفون خصائص هيكلية محددة: يمكن تفكيك $f$ و $\tilde{f}$ إلى مكونات سلسة ودوال محدبة مغلقة مناسبة، مع خصائص محدبة/تحدبية محددة فيما يتعلق بمتغيراتها المعنية (على سبيل المثال، $\tilde{f}$ محدبة في $y_1$ وتحدبية في $y_2$ ).

يركز جزء كبير من هذا العمل على مسائل التحسين ثنائية المستوى حيث يكون المستوى الأدنى عبارة عن مسألة تقليل محدبة مع قيود غير خطية محدبة:
$\min_{x_1, y_1} \left\{ f(x_1, y_1) \mid y_1 \in \arg\min_{z_1} \{ \bar{f}(x_1, z_1) \mid \bar{g}(x_1, z_1) \leq 0 \} \right\}$
بموجب شرط سلاتر (Slater's condition)، تتم إعادة صياغة هذه المسألة المقيدة كحالة خاصة من إطار عمل المينيمكس ثنائي المستوى العام عبر ثنائية لاغرانج (Lagrangian duality).

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

المنهجية

يستخدم النهج المقترح إعادة صياغة عقوبة دالة القيمة (Value-function penalty reformulation). حيث يتم تحويل مسألة التحسين ثنائية المستوى المقيدة إلى مسألة مينيمكس غير مقيدة (أو مقيدة بشكل أبسط) عن طريق إدخال معامل عقوبة $\rho$ .

الإعداد الحتمي (Deterministic Setting)

إعادة صياغة العقوبة: تتم إعادة صياغة المسألة الأصلية إلى مسألة مينيمكس أحادية المستوى:
$\min_{x_1, y_1, y_2} \max_{x_2, z_1, z_2} P_\rho(x_1, x_2, y_1, y_2, z_1, z_2)$
حيث تتضمن $P_\rho$ دالة الهدف وحريد العقوبة $\rho(p(x_1, y_1) - d(x_1, y_2))$ ، والذي يمثل فجوة الثنائية (Duality gap) لمسألة المستوى الأدنى.
الخوارزمية: يقترح المؤلفون طريقة النقطة القريبة غير الدقيقة (Inexact proximal point method). تقوم الحلقة الخارجية بتحديث متغيرات الثنائي-الأولي (Primal-dual) عن طريق حل سلسلة من المسائل الفرعية ذات التحدب القوي والتحدب الشديد (SCSC).
حل المسألة الفرعية: يتم حل كل مسألة فرعية باستخدام طريقة الرتبة الأولى المثلى (تحديداً نسخة من طريقة Lu و Mei [52] أو Kovalev و Gasnikov [37])، والتي يُرمز لها بـ OptFOM.
التعقيد: تجد الطريقة نقطة $\epsilon$ -KKT بتعقيد أوراكل قدره $\tilde{O}(\epsilon^{-4})$ .

الإعداد العشوائي (Stochastic Setting)

عندما تتوفر فقط أوراكل التدرج العشوائي للمكونات السلسة:

الخوارزمية: يتم تكييف طريقة النقطة القريبة الحتمية لاستخدام طريقة الأسلوب الثنائي المتسارع العشوائي (SAPD) (تحديداً SAPD+ من Zhang et al. [75]) لحل المسائل الفرعية الداخلية.
التقارب: تجد الطريقة نقطة "شبه" $\epsilon$ -KKT (حيث يكون الحل ضمن مسافة $\epsilon$ من نقطة $\epsilon$ -KKT دقيقة) بتعقيد أوراكل عشوائي قدره $\tilde{O}(\epsilon^{-9})$ .

التطبيق على مسائل المستوى الأدنى المقيد

بالنسبة للحالة المحددة للتحسين ثنائي المستوى مع مستوى أدنى محدب مقيد (المسألة 4)، يوضح المؤلفون أنه بموجب شرط سلاتر، تكون مضاعفات لاغرانج محصورة داخل صندوق $[0, B]^l$ . وهذا يسمح بإعادة صياغة المسألة المقيدة كمسألة المينيمكس ثنائية المستوى العامة (المسألة 1) عن طريق إدخال المتغيرات الثنائية كمتغيرات تحسين صريحة مع قيود الصندوق. تتجنب هذه إعادة الصياغة الحاجة إلى معامل عقوبة داخلي، مما يؤدي إلى تحسين حدود التعقيد مقارنة بالأعمال السابقة.

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

أول نتائج تعقيد للمينيمكس ثنائي المستوى: تقدم الورقة أول حدود تعقيد لطرق الرتبة الأولى الحتمية والعشوائية للتحسين ثنائي المستوى حيث يكون المستوى الأدنى مسألة مينيمكس.
- التعقيد الحتمي: $\tilde{O}(\epsilon^{-4})$ .
- التعقيد العشوائي: $\tilde{O}(\epsilon^{-9})$ .
تحسين الحدود لمسائل التحسين ثنائية المستوى المقيدة: من خلال إعادة صياغة مسائل التحسين ثنائية المستوى ذات المستويات الأدنى المحدبة المقيدة كحالات من إطار عمل المينيمكس المقترح، حقق المؤلفون تعقيداً قدره $\tilde{O}(\epsilon^{-4})$ . وهذا يحسن النتائج الحالية للمستويات الأدنى المحدبة فقط ( $\tilde{O}(\epsilon^{-7})$ في [53]) والمستويات الأدنى المحدبة بقوة ( $\tilde{O}(\epsilon^{-6})$ في [51]). يأتي هذا التحسن من تجنب استخدام معامل عقوبة ثانٍ للقيود الداخلية، مما أدى سابقاً إلى رفع معاملات النعومة.
التحقق التجريبي:
- البيانات الاصطناعية: في مسائل التحسين ثنائية المستوى الخطية المقيدة، تظهر الطريقة المقترحة سرعات تقارب تنافسية ضد طرق العقوبة الموجودة (FOP و SMO)، خاصة عند ضبط ثابت ليبشيتز (Lipschitz constant).
- التطبيق الواقعي: تم تطبيق الطريقة على ضبط المعلمات الفائقة لـ التحسين المتين توزيعياً (DRO) في التعلم العميق. في مجموعات بيانات CelebA و Waterbirds، تتفوق نهج الـ DRO ثنائي المستوى العشوائي المقترح على طرق DRO القياسية من حيث دقة أسوأ مجموعة (worst-group accuracy) مع الحفاظ على دقة متوسطة مماثلة.

النتائج والأهمية

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

الأهمية النظرية: يربط هذا العمل الفجوة بين التحسين ثنائي المستوى وتحسين المينيمكس، مما يوفر ضمانات تقارب صارمة دون الاعتماد على افتراضات التحدب القوي للمستوى الأدنى. إن تقليل التعقيد من $\tilde{O}(\epsilon^{-7})$ إلى $\tilde{O}(\epsilon^{-4})$ للمستويات الأدنى المقيدة يُقدم كتقدم نظري كبير.
الأهمية العملية: يوضح التطبيق على DRO فائدة الطريقة في سيناريوهات التعلم الآلي التي تتضمن تحولات في التوزيع. تُظهر النتائج على مجموعات بيانات CelebA و Waterbirds أن الطريقة يمكنها التعامل بفعالية مع تحدي تحسين "أسوأ مجموعة"، محققة دقة أعلى لأسوأ مجموعة مقارنة بطرق DRO المرجعية.

يقر المؤلفون بوجود قيود، بما في ذلك الحاجة إلى نطاقات مجال مدمجة (compact feasible domains)، واستخدام فضاء مرفوع (lifted space) لتعريفات KKT، والتعقيد العالي في الحالة العشوائية ( $\tilde{O}(\epsilon^{-9})$ )، مشيرين إلى أن تقنيات تقليل التباين قد تكون اتجاهاً للعمل المستقبلي.