طريقة لحلّ مسائل البرمجة المحدَّبة بمعدّل تقارُب O(1/k²)

لنبدأ بالمسألة الأساسية: تصغير دالة محدّبة ملساء $f(\theta)$ — وهذا هو الإطار الذي يقوم عليه تدريب معظم نماذج التعلّم الآلي. أبسط الطرق هي النزول التدرّجي:

$\theta_{k+1} = \theta_k - \eta \nabla f(\theta_k)$

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

$f(\theta_k) - f(\theta^*) \leq O\!\left(\frac{1}{k}\right)$

ماذا يعني هذا عملياً؟ لكي تُنصّف الخطأ عليك مضاعفة عدد التكرارات. في فضاء بمئة بُعد — وهو صغير بمقاييس اليوم — يتحوّل هذا التقارب الخطّي إلى ملايين حسابات تدرّج مهدورة.

عام 1964 اقترح بوريس بولياك حلاً: أضِف زَخَماً. بدل الاعتماد على التدرّج الحالي وحده، اجمع سرعة متراكمة من التدرّجات السابقة:

$v_{k+1} = \mu\, v_k - \eta \nabla f(\theta_k)$ $\theta_{k+1} = \theta_k + v_{k+1}$

معامل الزَّخَم $\mu$ (عادةً 0.9) يدفع المُحسِّن للتحرّك في اتجاهات متّسقة ويُخمد التعرّج. على الدوال التربيعية كان الأداء أسرع بكثير. لكن المشكلة أن طريقة بولياك لم تملك أي ضمان نظري للدوال المحدّبة عموماً، بل كانت تتجاوز الهدف وتتذبذب قرب الحلّ الأمثل — لأن السرعة المتراكمة «عمياء»: لا تعرف ما ينتظرها أمامها.

جوهر فكرة نيستيروف تعديل واحد أنيق على زَخَم بولياك. بدل حساب التدرّج عند الموضع الحالي $\theta_k$، اقفز أولاً خطوة زَخَم إلى نقطة «استطلاعية»، ثم احسب التدرّج هناك. عملياً، تحتفظ الطريقة بمتتاليتين:

• $x_k$: الموضع «المُصحَّح» حيث تُخزَّن التدرّجات
• $y_k$: موضع «الاستطلاع» حيث يُحسَب التدرّج فعلياً

يتناوب التحديث بين خطوة تدرّج وخطوة زَخَم:

الفرق الحاسم عن بولياك هو مكان حساب التدرّج. بولياك يحسب $\nabla f(\theta_k)$ — التدرّج عند موقعك الحالي. نيستيروف يحسب $\nabla f(y_{k-1})$ — التدرّج عند الموقع الذي كان الزَّخَم سيأخذك إليه. فكّر فيها كمن يستطلع التضاريس قبل أن يلتزم بخطوته:

• إذا كشف الاستطلاع أن الميل يشتد، يكون التصحيح أكبر فتتسارع.
• إذا كشف أن الميل يتسطّح (اقتراب من القاع)، ينخفض التصحيح تلقائياً — فتفرمل قبل أن تتجاوز الهدف لا بعده.

هذا التصحيح الاستباقي هو ما يمنع التذبذبات التي يُعاني منها الزَّخَم التقليدي قرب الحلّ الأمثل، وهو السبب الرئيسي وراء التقارب الأسرع المُبرهَن.

أثبت نيستيروف نتيجتين متكاملتين تُغلقان السؤال تماماً حول أفضل تقارب ممكن للأساليب التي تعتمد على التدرّجات فقط:

الحدّ الأعلى (التحقيق). الطريقة المُسرَّعة تتقارب وفق: $f(x_k) - f(x^*) \leq \frac{2L\|x_0 - x^*\|^2}{(k+1)^2}$ حيث $L$ ثابت ليبشتز للتدرّج، و$x_0$ نقطة البداية، و$x^*$ الحلّ الأمثل. هذا هو المعدّل O(1/k²) — بعد $k$ خطوة ينكمش الخطأ تربيعياً.

الحدّ الأدنى (المِثالية). مهما كانت الطريقة المُستخدمة — طالما أنها تعتمد على حساب التدرّج فقط وتُجري $k$ تقييماً على الأكثر — فهناك دوال محدّبة ملساء يبقى فيها الخطأ $\Omega(1/k^2)$ على الأقل. بمعنى آخر: لا أحد يستطيع أن يفعل أفضل من O(1/k²) في أسوأ الحالات. وطريقة نيستيروف تبلغ هذا الحدّ — فهي مِثالية.

البرهان مبني على أداة تُسمّى «المتتاليات التقديرية» — مجموعة من حدود دنيا تربيعية تتتبّع تقدّم الخوارزمية وتضمنه في كل خطوة. التفاصيل التقنية معقّدة، لكن الفكرة الأساسية أن معامل الزَّخَم $(k-1)/(k+r)$ ليس اختياراً عشوائياً: هو بالضبط الجدول الذي يُبقي تلك الحدود التربيعية مُحكمة.

حين تكون الدالة ليست محدّبة فحسب بل محدّبة بقوة — بمعنى أنها تنحني صعوداً بمعدّل لا يقل عن وعاء تربيعي (معامل التحدّب القوي $\mu > 0$) — يصبح تسريع نيستيروف أكثر دراماتيكية. رقم الحالة $\kappa = L/\mu$ يقيس مدى «استطالة» سطح الدالة $f$: كلما كبر $\kappa$ زادت صعوبة الأمثَلة.

النزول التدرّجي العادي يتقارب خطياً بمعامل $(1 - 1/\kappa)$ — كلما ارتفع $\kappa$ تباطأ التقارب. نيستيروف يحسّن هذا إلى $(1 - 1/\sqrt{\kappa})$: يأخذ الجذر التربيعي من صعوبة المسألة. مثال عملي: لدالة برقم حالة $\kappa = 10{,}000$ (وارد جداً في التعلّم العميق)، النزول التدرّجي يحتاج نحو 10,000 تكرار لتنصيف الخطأ، بينما نيستيروف يحتاج 100 تكرار فقط.

ورقة نيستيروف عام 1983 كانت نظرية أمثَلة محدّبة بحتة — لم تتطرّق إلى الشبكات العصبية أصلاً. بعد ثلاثة عقود، جاء سَتسكيفر ومارتنز ودال وهينتون (2013) وأظهروا أن زَخَم نيستيروف مع تهيئة مدروسة يُدرّب شبكات عميقة وتكرارية بأداء لم يكن يتحقّق من قبل إلا بأساليب الرتبة الثانية كأمثَلة هِسيان الحرة. أبرز ما وجدوه:

• زَخَم نيستيروف يتحمّل معاملات أعلى من الزَّخَم التقليدي دون تذبذب — وهذا بالضبط ما تتنبأ به النظرية من استقرار.
• جدول زَخَم يتصاعد تدريجياً (من $\mu = 0.5$ إلى $\mu = 0.99$) كان شرطاً أساسياً لنجاح التدريب على الشبكات العميقة.
• كلا العنصرين ضروري: تهيئة جيدة بلا زَخَم تفشل، وزَخَم بلا تهيئة جيدة يفشل أيضاً.

بعد هذه الورقة أصبح زَخَم نيستيروف هو الخيار المعياري في النزول التدرّجي العشوائي للتعلّم العميق. حين تكتب torch.optim.SGD(..., momentum=0.9, nesterov=True) فأنت تستخدم نسخة عشوائية من خوارزمية 1983.

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

• التدرّجات العشوائية. خطوة الاستطلاع تعمل كآلية لتقليل التباين. حين تحسب التدرّج عند موضع مُنعَّم ينخفض الضجيج الفعلي.
• الأسطح غير المحدّبة. قرب نقاط السرج والهِضاب المسطّحة، يساعد الزَّخَم في تجاوز المناطق التي تحتجز النزول التدرّجي النقي. والاستطلاع يمنع التذبذبات التي يُبديها الزَّخَم التقليدي قرب النهايات الصغرى الحادّة.
• نصيحة عملية: جدول الزَّخَم. في التعلّم العميق، قيمة ثابتة $\mu = 0.9$ تكفي لمعظم المهام. عند الضبط الدقيق أو الاقتراب من التقارب، رفعها إلى $\mu = 0.99$ قد يستخرج آخر نقطة دقة ممكنة. النظرية الأصلية تقترح جدولاً متصاعداً، وسَتسكيفر وزملاؤه أكّدوا ذلك تجريبياً.

نُشرت ورقة نيستيروف عام 1983 في وقائع أكاديمية العلوم السوفييتية (دوكلادي) — مقالة رياضية مختصرة وكثيفة. ظلّت لعقود حبيسة أوساط منظّري الأمثَلة. انتقالها إلى عالم التعلّم الآلي حدث عبر سلسلة من إعادات الاكتشاف والتكييف:

فكرة واحدة قدّمتها ورقة نيستيروف — احسب التدرّج عند نقطة استطلاعية بدل موقعك الحالي — وبرهنت أنها أفضل ما يمكن لأي أسلوب يعتمد على التدرّجات فقط. تلك الفكرة الواحدة تُسرّع تدريب كل شبكة عصبية تعمل اليوم على وجه الأرض. من مقالة بأربع صفحات في وقائع الرياضيات السوفييتية إلى قلب تدريب نماذج بتريليونات المعاملات: قلّ أن قطعت ورقة بحثية مسافة كهذه.