樂觀梯度下降上升法於相對利普希茨條件下求解最佳化問題之研究

Abstract

本研究從[10]所提出的相對利普希茨觀點出發，提出兩種基於樂觀梯度下降上升法（Optimistic Gradient Descent Ascent Method, OGDA）的演算法，分別對應於一般最佳化問題與有限總和最佳化問題。

第一個演算法針對光滑且強凸的目標函數，透過Fenchel共軛轉換將原問題改寫為鞍點問題，再把OGDA詮釋為近端算法（Proximal Point）的一種變形。我們證明此方法可達到一階方法中最佳的迭代複雜度O(√(L/μ)log(1/ε))。

第二個演算法設計於有限總和形式的最佳化問題中，每次迭代僅隨機抽取一個光滑的子函數進行更新。我們構造了一種隨機版本的OGDA，並證明在各子函數具有不同平滑常數L_i的情況下，仍能達到收斂速率O((n+(Σ_{i=1}^n √(L_i))/√(nμ))*log((γε_0)/ε))，其中γ:=1+(Σ_{i=1}^n L_i)/(nμ)。

最後，我們設計問題進行實驗驗證。結果顯示提出的OGDA變體具加速收斂效果。

In this research, we develop and analyze two variants of the Optimistic Gradient Descent Ascent (OGDA) algorithm through the lens of relative Lipschitzness, a structural condition introduced by [10]. We first consider the setting of Lipschitz gradient and strongly convex minimization problems and reformulate them as structured convex-concave saddle-point problems using Fenchel duality. Within this formulation, we show that OGDA achieves the optimal iteration complexity of O(√(L/μ)log(1/ε)).

Inspired by the finite-sum framework studied in [16], the second algorithm targets the finite-sum setting, where the objective function is expressed as an average of n convex component functions with Lipschitz continuous gradients. We develop a new algorithm based on OGDA, mirroring the structure used in the single-function setting. Our analysis demonstrates that in the finite-sum case, the proposed method achieves a convergence rate of O((n+(Σ_{i=1}^n √(L_i))/√(nμ))*log((γε_0)/ε)), where γ:=1+(Σ_{i=1}^n L_i)/(nμ).

Finally, we validate the effectiveness of our approach through numerical experiments.