On the complexity of a simple primal-dual coordinate method

• 成果类型: Article; Early Access
• 署名作者: Alacaoglu, Ahmet; Cevher, Volkan; Wright, Stephen J.
• 署名单位: University of British Columbia; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University of Wisconsin System; University of Wisconsin Madison
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02247-8
• 发表日期: 2025
• 关键词: algorithm; gradient; CONVERGENCE

摘要

We prove new complexity bounds for the primal-dual algorithm with random extrapolation and coordinate descent (PURE-CD), which has been shown to obtain promising practical performance for solving convex-concave min-max problems with bilinear coupling and dual separability. Such problems arise in many machine learning contexts, including empirical risk minimization, matrix games, and image processing. Our results either match or improve the best-known complexities of first-order algorithms for dense and sparse (strongly)-convex-(strongly)-concave problems with bilinear coupling.