الفائدة الأساسية لتحديثات التبادل في التحسين الأقصى-الأدنى

خوارزمية التدرج الهابط-الصاعد (GDA)، المصممة لحل مشاكل التحسين التبادلي (minimax)، تتخذ خطوات التناقص والزيادة إما بشكل متزامن (Sim-GDA) أو بشكل متغير (Alt-GDA). وعلى الرغم من أن Alt-GDA يُلاحظ عادةً تقاربًا أسرع، إلا أن الفجوة في الأداء بين النوعين لم تُفهم بعد نظريًا بشكل كافٍ، خاصة فيما يتعلق بمعدلات التقارب العالمية. ولسد هذه الفجوة بين النظرية والتطبيق، نقدم تحليلات دقيقة لسلوك التقارب لكلا الخوارزميتين في حالات الوظائف ذات التحدب القوي والانحناء القوي (strongly-convex-strongly-concave) والوظائف ذات التدرج ليبشيتز (Lipschitz-gradient). ونُظهر أن الحد الأعلى لتعقيد التكرار (iteration complexity) لخوارزمية Alt-GDA أصغر صارمًا من الحد الأدنى لـ Sim-GDA؛ أي أن Alt-GDA أسرع بشكل مثبت. علاوةً على ذلك، نقترح إطارًا خوارزميًا عامًا يُسمى خوارزمية GDA بالاستخلاص المتغير (Alex-GDA)، والذي يشمل كلاً من Sim-GDA وAlt-GDA، حيث يعتمد الفكرة الأساسية على أخذ التدرجات بشكل متغير من تقديرات (استخلاصات) للحلول المتكررة. ونُظهر أن Alex-GDA تحقق حدًا أصغر لتعقيد التكرار، مطابقًا تمامًا لحد تعقيد طريقة التدرج الإضافي (Extra-gradient)، مع الحاجة إلى عدد أقل من حسابات التدرج. كما نثبت أن Alex-GDA تتمتع بتوافق خطي (linear convergence) في المشكلات الثنائية الخطية (bilinear problems)، بينما تفشل كل من Sim-GDA وAlt-GDA تمامًا في التقارب في هذه الحالات.