A Block Coordinate Descent Method for Nonsmooth Composite Optimization under Orthogonality Constraints

ملخص تقني: طريقة خوارزمية تنسيق الكتل (Block Coordinate Descent) للتحسين المركب غير السلس تحت قيود التعامد

بيان المشكلة
تتناول الورقة البحثية تحدي التحسين المركب غير السلس تحت قيود التعامد، والذي يُصاغ كالتالي:
$$\min_{X \in \mathbb{R}^{n \times r}} F(X) \triangleq f(X) + h(X), \quad \text{s.t. } X^T X = I_r$$
حيث $n \ge r$، و $f(X)$ هي دالة سلسة (قد تكون غير محدبة)، و $h(X)$ هي دالة "ملائمة، منخفضة نصف الاستمرارية، وقابلة للفصل عبر الإحداثيات" (proper, lower semicontinuous, coordinate-wise separable). مجموعة القيود هي ماني فولد ستيفل (Stiefel manifold) ويرمز لها بـ $\mathcal{M} = \text{St}(n, r)$. يضم هذا الإطار تطبيقات حيوية في التعلم الإحصائي وعلوم البيانات، بما في ذلك تحليل المكونات الرئيسية (PCA) المتناثر مع تنظيم $\ell_0$ أو $\ell_1$، و PCA غير السالب، وتدريب الشبكات العصبية العميقة ذات القيود المتعامدة، وتعلم القواميس (Dictionary Learning).

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

المنهجية: خوارزمية OBCD
يقترح المؤلفون خوارزمية OBCD (تنسيق الكتل المتعامد - Orthogonal Block Coordinate Descent)، وهي طريقة "جدوى" (feasible method) تقوم بتحديث $k$ من صفوف مصفوفة الحل $X$ في آن واحد، حيث $k \ge 2$.

1. مخطط التحديث الحافظ للقيود:
   بدلاً من الإسقاط على الماني فولد أو استخدام عمليات الارتداد (retractions)، تستخدم OBCD قاعدة تحديث محددة تحافظ على التعامد عن طريق البناء. بالنسبة لمجموعة عمل من مؤشرات الصفوف $B$ (حجمها $k$)، يتم تعريف التحديث كالتالي:
   $$X^{t+1} = X^t + U_B (V - I_k) U_B^T X^t$$
   حيث $U_B$ تختار الصفوف في $B$، و $V \in \text{St}(k, k)$ هي مصفوفة متعامدة تحل مسألة فرعية. يثبت التمهيد (Lemma 2.1) أنه إذا كانت $X^t$ تحقق شرط الجدوى، فإن $X^{t+1}$ تظل تحقق الشرط لأي $V \in \text{St}(k, k)$.

2. صياغة المسألة الفرعية:
   في كل تكرار، تحل OBCD مسألة فرعية صغيرة النطاق فوق ماني فولد ستيفل ذي أبعاد $k \times k$. باستخدام نهج "التعظيم-التقليل" (Majorization-Minimization - MM)، يتم تقريب الجزء السلس $f(X)$ بدالة بديلة تربيعية، بينما يتم الإبقاء على الجزء غير السلس $h(X)$ كما هو. المسألة الفرعية الناتجة هي:
   $$\bar{V}_t \in \arg\min_{V \in \text{St}(k, k)} \left( \frac{1}{2} \|V - I_k\|_{\tilde{Q}}^2 + \langle V, P \rangle + h(V Z) \right)$$
   حيث $Z = U_B^T X^t$، و $P$ يتضمن تدرج $f$، و $\tilde{Q}$ هي مصفوفة موجبة محددة مشتقة من هيسيان (Hessian) الدالة $f$ أو من بديل قياسي (scalar proxy).

3. حل المسائل الفرعية:

• للقيمة العامة $k$: تفترض الورقة إمكانية حل المسألة الفرعية بدقة أو بكفاءة (على سبيل المثال، عبر هياكل صديقة لعمليات التقريب القريب - proximal-friendly).
• الحالة $k=2$: يقدم المؤلفون طريقة مبتكرة تسمى طريقة البحث عن نقاط الكسر (Breakpoint Search Method - BSM). من خلال تمثيل المصفوفات المتعامدة $2 \times 2$ باستخدام دورات جيفنز (Givens rotations $V^{rot}_\theta$) وانعكاسات جاقوبي (Jacobi reflections $V^{ref}_\theta$)، يتم اختزال المسألة الفرعية إلى تحسين أحادي البعد على المعامل $\theta$. تحدد BSM جميع نقاط الكسر (النقاط الحرجة) لدالة الهدف (بما في ذلك تلك الناشئة عن الجزء غير السلس $h$) لإيجاد المثلى العالمية.

4. اختيار مجموعة العمل:
   تدعم الخوارزمية استراتيجيات الاختيار العشوائي أو الدوري لمجموعة العمل $B$.

المساهمات النظرية
تقدم الورقة تحليلاً نظرياً صارماً فيما يتعلق بالأمثلية والتقارب:

• اكتمال مخطط التحديث: يثبت المؤلفون أن مخطط التحديث المعتمد على الصفوف هو مخطط كامل. وتحديداً، يمكن الوصول إلى أي نقطة على ماني فولد ستيفل من أي نقطة أخرى قابلة للتحقق عبر تسلسل من تحديثات $k$-row (النظرية 3.1، الاستنتاج 3.2).
• شروط أمثلية أقوى: تُعرف الورقة نقاط الثبات الكلية للكتلة-$k$ (Global Block-$k$ Stationary Points - BSk-points). تكون النقطة "نقطة ثبات" إذا تعذر إجراء أي تحسين من خلال تحسين أي كتلة مكونة من $k$ من الصفوف. يضع المؤلفون تسلسلاً هرمياً للأمثلية:
  $$\{\text{Global Optima}\} \subseteq \{\text{BSk-points}\} \subseteq \{\text{BS(k+1)-points}\} \subseteq \{\text{Critical Points}\}$$
  وهذا يعني أن نقاط BSk (حيث $k \ge 2$) تحقق شرط أمثلية أقوى بصرامة من النقاط الحرجة القياسية، مما يسمح نظرياً للخوارزمية بالهروب من النهايات الصغرى المحلية الرديئة التي تحجز الطرق القياسية.
• تعقيد التكرار:
  • تجد OBCD نقطة ثبات $\epsilon$-block-$k$ بتعقيد تكراري قدره $O(1/\epsilon)$.
  • تحت فرضية متباينة كورديكا-لوجاتز (Kurdyka–Łojasiewicz - KL)، تثبت الورقة معدلات تقارب غير إرغودية (لآخر تكرار). اعتماداً على أس $KL$ (الرمز $\sigma$)، يكون التقارب منتهياً ($\sigma=0$)، أو خطياً ($\sigma \in (0, 1/2]$)، أو تحت خطي ($\sigma \in (1/2, 1)$).

النتائج التجريبية
قام المؤلفون بتقييم OBCD على تحليل المكونات الرئيسية المتناثر مع تنظيم $L_0$، و $L_1$، و PCA غير السالب باستخدام مجموعات بيانات واقعية (مثل MNIST، و Gisette، و 20News) وبيانات اصطناعية.

• الأداء: تتفوق OBCD باستمرار على الخطوط المرجعية الحديثة، بما في ذلك Linearized ADMM (LADMM)، و Riemannian ADMM (RADMM)، و Penalty-based Splitting Method (PSM)، و Manifold Proximal Gradient (ManPG).
• قيم الهدف: من حيث قيمة الهدف النهائية، تحقق OBCS قيمًا أقل من الطرق المنافسة، وغالبًا ما تهرب من النهايات الصغرى المحلية التي تعلق فيها الطرق الأخرى.
• الكفاءة: بينما قد تتطلب طرق التدرج الكامل تكرارات أقل، فإن التكلفة المنخفضة لكل تكرار في OBCD (تحديثات التدرج الجزئي) تؤدي إلى أداء متفوق عند قياسها بوقت وحدة المعالجة المركزية (CPU time).
• الجدوى: على عكس بعض الطرق غير الممكنة (Infeasible methods) (مثل بعض طرق التقسيم)، تحافظ OBCD على التعامد الصارم (واللا-سلبية في نسخة PCA غير السالبة) طوال عملية التحسين.

الأهمية والادعاءات
تزعم الورقة أن OBCD تقدم تقدماً كبيراً من خلال الجمع بين الكفاءة الحسابية والضمانات النظرية القوية. تكمن أهميتها الأساسية في:

1. التعامل مع عدم السلاسة: إنها تعالج بفعالية الأهداف غير السلسة عبر الإحداثيات تحت قيود التعامد، وهو إطار تعاني فيه العديد من طرق تحسين الماني فولد.
2. أمثلية أقوى: من خلال استخدام تحديثات الكتل ($k \ge 2$)، تستهدف الطريقة نقاط BSk، والتي تعد نظرياً متفوقة على النقاط الحرجة القياسية، مما يوفر آلية لتجنب النهايات الصغرى المحلية دون المستوى المطلوب.
3. الجدوى: هي طريقة "جدوى صارمة"، مما يضمن استيفاء القيود في كل تكرار، على عكس طرق التقسيم القائمة على العقوبة أو الطرق غير الممكنة.
4. الكفاءة العملية: تم تصميم الخوارزمية للمشاكل واسعة النطاق حيث تكون حسابات التدرج الكامل مكلفة للغاية، مما يوفر بديلاً قابلاً للتوسع مع خصائص تقارب مثبتة.