用算子理论分析双线性鞍点问题，证明多类算法线性收敛。
Contractivity and linear convergence in bilinear saddle-point problems: An operator-theoretic approach
- 基于单调算子理论，统一分析多种一阶原始对偶算法
- 在满足秩条件时，算法具有线性收敛性，收敛速率更优
- 适合研究优化算法收敛性的学者与工程应用者参考
我们研究凸-凹双线性鞍点问题：$\min_x \max_y f(x) + y^\top Ax - g(y)$，其中 $f$ 与 $g$ 可能均、仅一个或均不强凸，且矩阵 $A$ 满足适当的秩条件。该问题的解是许多机器学习任务的核心。通过采用单调算子理论工具，我们系统地证明了包括Chambolle-Pock方法在内的多种一阶原始对偶算法的收缩性（从而实现线性收敛）。该方法给出简洁证明，并获得比已有结果更优的新收敛保证和更紧的界。
原文摘要 · Abstract (English)
We study the convex-concave bilinear saddle-point problem $\min_x \max_y f(x) + y^\top Ax - g(y)$, where both, only one, or none of the functions $f$ and $g$ are strongly convex, and suitable rank conditions on the matrix $A$ hold. The solution of this problem is at the core of many machine learning tasks. By employing tools from monotone operator theory, we systematically prove the contractivity (in turn, the linear convergence) of several first-order primal-dual algorithms, including the Chambolle-Pock method. Our approach results in concise proofs, and it yields new convergence guarantees and tighter bounds compared to known results.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。