On the Complexity of a Practical Primal-Dual Coordinate Method

We prove complexity bounds for the primal-dual algorithm with random extrapolation and coordinate descent (PURE-CD), which has been shown to obtain good practical performance for solving convex-concave min-max problems with bilinear coupling. Our complexity bounds either match or improve the best-known results in the literature for both dense and sparse (strongly)-convex-(strongly)-concave problems.

math.OC cs.LG stat.ML Stochastic Gradient Optimization Techniques Sparse and Compressive Sensing Techniques Machine Learning and Algorithms

View graph Source

Paper

Similar papers

Random extrapolation for primal-dual coordinate descentAhmet Alacaoglu, Olivier Fercoq, Volkan Cevher2020 · Infoscience (Ecole Polytechnique Fédérale de Lausanne) In Library

Random extrapolation for primal-dual coordinate descentAhmet Alacaoglu, Olivier Fercoq, Volkan Cevher2020 · arXiv (Cornell University) · 21 citations In Library

Linear Convergence of Randomized Primal-Dual Coordinate Method for Large-scale Linear Constrained Convex ProgrammingDaoli Zhu, Lei Zhao2020 · International Conference on Machine Learning · 7 citations In Library

On the Complexity Analysis of the Primal Solutions for the Accelerated Randomized Dual Coordinate AscentHuan Li, Zhouchen Lin2018 · Journal of machine learning research · 8 citations In Library

Random block coordinate methods for inconsistent convex optimisation problemsMathias Staudigl, Paulin Jacquot2022 · arXiv (Cornell University) In Library

Efficient Methods for Min-Max Optimization with Dual-Linear CouplingRonak Mehta, Jelena Diakonikolas, Zaïd Harchaoui2025 · arXiv (Cornell University) In Library

Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk MinimizationYuchen Zhang, Xiao Lin2014 · International Conference on Machine Learning · 271 citations In Library

Exponential Convergence of Primal–Dual Dynamics Under General Conditions and Its Application to Distributed OptimizationLuyao Guo, Xinli Shi, Jinde Cao et al.2022 · IEEE Transactions on Neural Networks and Learning Systems · 11 citations In Library

A New Randomized Primal-Dual Algorithm for Convex Optimization with Optimal Last Iterate RatesQuoc Tran-Dinh, Deyi Liu2020 · arXiv (Cornell University) In Library

Coordinate Methods for Matrix GamesYair Carmon, Yujia Jin, Aaron Sidford et al.2020 In Library

Source of record

arXiv

44B

Welcome.

This panel sticks with you. Pick anything below and it opens right beside it, so you can dig through 60,000-plus records without ever losing your spot here.

Travel 44B

LibraryPapers, policy, standards, statute LabsEvery organization building AI ModelsIntelligence, price, and speed BenchmarksThe evaluation catalog IncidentsAI failures and harms SearchOne field across everything DashboardThe state of AI accountability in NY 44B RegistryThe Art. 44-B compliance portal