Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise

ملخص تقني: التحسين غير المحدب وغير السلس من الدرجة صفر مع ضوضاء ثقيلة الذيل

صياغة المشكلة
تتناول هذه الورقة مشكلة التحسين العشوائي غير المقيد:
$$\min_{x \in \mathbb{R}^d} f(x) = \mathbb{E}_{\xi \sim P}[F(x; \xi)]$$
حيث أن دالة الهدف $f$ هي دالة غير محدبة (nonconvex) وغير سلسة (nonsmooth)، ولكنها مستمرة ليبشيتز (Lipschitz continuous). الإطار هو الدرجة صفر (zeroth-order)، مما يعني أن الخوارزمية لا تملك وصولاً إلا إلى تقييمات الدالة المشوبة بالضوضاء $F(x; \xi)$ بدلاً من التدرجات (gradients).

يمثل افتراض الضوضاء انحرافاً جوهرياً عن الأعمال السابقة. فبينما تعتمد معظم التحليلات الحالية على افتراض التباين المحدود (عزم الدرجة الثانية)، تعمل هذه الورقة تحت افتراض الضوضاء ثقيلة الذيل (heavy-tailed noise). وتحديداً، يحقق ثابت ليبشيتز $L(\xi)$ للدالة العشوائية المكونة شرط عزم الدرجة $p$ المحدود:
$$\mathbb{E}[L(\xi)^p] \leq L^p$$
حيث $p \in (1, 2]$. عندما تكون $p < 2$، قد يكون التباين غير محدود، مما يميز توزيعات ثقيلة الذيل (مثل توزيعات ليفي $\alpha$-stable) التي تُلاحظ بشكل شائع في تطبيقات تعلم الآلة الواقعية مثل تدريب الشبكات العصبية العميقة والتعلم التعزيزي.

المنهجية: خوارزمية ZOCOON
يقترح المؤلفون خوارزمية التحسين من الدرجة صفر عبر الإنترنت إلى غير المحدب (Zeroth-Order Clipped Online-to-Nonconvex) والتي تُعرف بـ ZOCOON. يدمج هذا الأسلوب ثلاثة مكونات أساسية:

1. إطار تحويل "من الإنترنت إلى غير المحدب" (Online-to-Nonconvex): بناءً على الإطار الذي وضعه كوتكوسكي وآخرون [9] والذي وسعه كورنووسكي وشامير [25]، تقوم الخوارزمية بتحويل مشكلة التعلم عبر الإنترنت إلى محلل تحسين غير محدب. يتضمن ذلك تشغيل سلسلة من التحديثات عبر جولات لإيجاد نقطة استقرار.
2. مُقدّر التدرج العشوائي بنقطتين: نظراً لعدم توفر التدرجات، تستخدم الخوارذية مُقدّراً من الدرجة صفر يعتمد على الدالة البديلة المُمهدة $f_{\delta'}(x)$. بالنسبة لنقطة $x$ واتجاه عشوائي $w$ على الكرة الوحدة، يكون المُقدّر هو:
   $$\hat{g}(x; w, \xi) = \frac{d}{2\delta'} (F(x + \delta'w; \xi) - F(x - \delta'w; \xi))w$$
   يوفر هذا تقديراً غير متحيز لتدرج الدالة المُمهدة.
3. قص التدرج (Gradient Clipping): للتخفيف من تأثير الضوضاء ثقيلة الذيل، تدمج الخوارزمية عامل قص (clipping operator) على مُقدّر التدرج. تستخدم خطوة التحديث $\hat{g}_{clipped} = \text{clip}(\hat{g}, \tau)$، حيث $\tau$ هو معامل العتبة. هذا يمنع التدرجات الكبيرة والمشوبة بالضوضاء من زعزعة استقرار عملية التحسين.

تعمل الخوارزمية في حقبات (epochs) مع عمليات إعادة تشغيل، وتخرج نقطة عشوائية منتظمة من مجموعة التكرارات المتوسطة لضمان ضمانات التقارب.

المساهمات الرئيسية والنتائج النظرية
تثبت الورقة ضمانات نظرية لإيجاد نقطة استقرار غولدشتاين $(\delta, \epsilon)$، وهي مفهوم مطور للاستقرار التقريبي للدوال غير السلسة المعرّف عبر التفاضل الفرعي لغولدشتاين $\delta$.

• تعقيد التقارب: تحقق خوارزمية ZOCOON نقطة استقرار $(\delta, \epsilon)$ بتعقيد أوراكل (oracle complexity) عشوائي من الدرجة صفر قدره:
  $$O\left( d^{\frac{p}{2(p-1)}} \delta^{-1} \epsilon^{-\frac{2p-1}{p-1}} \right)$$
  هذه النتيجة تتحقق في كل من التوقع وبالاحتمالية العالية.
• الاعتماد على البعد: يتطابق الاعتماد على البعد $d$ مع أفضل النتائج المعروفة للتحسين العشوائي من الدرجة صفر في الحالة المحدبة غير السلسة.
• الاعتماد على الدقة: يتوافق الاعتماد على معايير الدقة $\delta$ و $\epsilon$ مع أفضل خوارزميات الدرجة الأولى العشوائية المعروفة للمشاكل غير المحدبة وغير السلسة تحت الضوضاء ثقيلة الذيل.
• الامتداد للسلاسة: تمتد النتائج بشكل طبيعي إلى الحالة السلسة. من خلال ضبط $\delta = \epsilon/H$ (حيث $H$ هو ثابت السلاسة)، تحقق الطريقة نقطة استقرار $\epsilon$ بتعقيد يطابق أفضل طرق الدرجة الأولى العشوائية للتحسين غير المحدد السلس.

التحقق التجريبي
أُجريت تجارب عددية على مسائل SVM غير المحدبة ذات الجزاء (penalized SVM) باستخدام مجموعات بيانات واقعية (a9a, covtype, w8a) مع إضافة ضوضاء ثقيلة الذيل اصطناعياً (توزيع باريتو).

• النماذج المرجعية: تمت مقارنة ZOCOON بكل من GFM [26]، و GFM+ [5]، و ZOO2N [25].
• النتائج: حققت ZOCOON و ZOO2N تقارباً أسرع بكثير من GFM و GFM+. كما أظهرت ZOCON أداءً أكثر استقراراً من ZOO2N عبر معظم مجموعات البيانات، مما يؤكد فعالية آلية القص في التعامل مع الضوضاء ثقيلة الذيل.

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

• الأولى من نوعها: تُقدم ZOCOON كأول خوارزمية عشوائية فعالة من الدرجة صفر للتحسين غير المحدب وغير السلس تحت الضوضاء ثقيلة الذيل.
• المثالية: يشير المؤلفون إلى أن الاعتماد على $L$ و $\delta$ و $\epsilon$ يطابق الحد الأدنى الذي تم إثباته مؤخراً لهذه الفئة من المشاكل، مما يشير إلى أن الطريقة قريبة من المثالية فيما يتعلق بمعايير الدقة.
• القوة (Robustness): يوضح العمل أن قص التدرج، وهو تقنية شائعة في طرق الدرجة الأولى، يمكن تكييفه بنجاح مع أطر الدرجة صفر للتعامل مع التباين غير المحدود دون التضحية بالتعقيد المرتبط بالبعد.

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