提出首个适用于广义鞍点问题的线性收敛算法与下界
On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms
- 构建了更通用的复杂度下界，覆盖已有结果
- 首次实现梯度与矩阵乘法复杂度同时最优
- 适合研究优化算法理论性能的研究者
我们重新审视光滑凸-凹双线性耦合鞍点问题：min_x max_y f(x) + ⟨y, Bx⟩ - g(y)。当f(x)和g(y)均为仿射或强凸时，已有梯度评估与矩阵-向量乘法的下界及匹配的最优算法，且可实现线性收敛（迭代次数与log(1/ε)成正比）。但具备线性收敛性的双线性耦合鞍点问题范围更广，可包含光滑非强凸函数。本文首次为该类问题建立下界并设计匹配的线性收敛算法。所提下界更具普遍性，涵盖并统一现有成果。算法通过分离复杂度机制，首次实现梯度评估与矩阵-向量乘法复杂度的同步最优，达到当前最优理论性能。
原文摘要 · Abstract (English)
We revisit the smooth convex-concave bilinearly-coupled saddle-point problem of the form $\min_x\max_y f(x) + \langle y,\mathbf{B} x\rangle - g(y)$. In the highly specific case where each of the functions $f(x)$ and $g(y)$ is either affine or strongly convex, there exist lower bounds on the number of gradient evaluations and matrix-vector multiplications required to solve the problem, as well as matching optimal algorithms. A notable aspect of these algorithms is that they are able to attain linear convergence, i.e., the number of iterations required to solve the problem is proportional to $\log(1/ε)$. However, the class of bilinearly-coupled saddle-point problems for which linear convergence is possible is much wider and can involve smooth non-strongly convex functions $f(x)$ and $g(y)$. Therefore, we develop the first lower complexity bounds and matching optimal linearly converging algorithms for this problem class. Our lower complexity bounds are much more general, but they cover and unify the existing results in the literature. On the other hand, our algorithm implements the separation of complexities, which, for the first time, enables the simultaneous achievement of both optimal gradient evaluation and matrix-vector multiplication complexities, resulting in the best theoretical performance to date.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。