Distributed Optimization

Follow this topic Ask about this topic

Distributed optimization studies how multiple machines, clients, or robots can solve a shared problem using local data and limited communication. Common approaches include consensus and decentralized gradient methods, local or federated SGD, ADMM and primal-dual algorithms, and asynchronous updates; communication can be reduced through compression, quantization, or less frequent synchronization. These methods support settings from large-model training and statistical learning to robot coordination, energy systems, and networked control. A central challenge is balancing communication and computation against convergence when data and worker speeds differ, messages are delayed, or participants may be unreliable or adversarial.

Latest papers

92 papers11 papers in the last four weeks, up 267% on the four weeks before. 0.1% of all new papers.

On the Relationship Between CoCoA and ADMM for Distributed Empirical Risk Minimization
Feb 1, 2025Runxiong Wu, Andi WangPrimal-Dual Optimization Distributed Optimization
Department of Industrial & Systems Engineering University of Wisconsin–Madison
The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication
May 19, 2024Kumar Kshitij Patel, Margalit Glasgow, Ali Zindari +5Communication-Efficient Distributed Training Distributed Optimization
Toyota Technological Institute, Chicago · Stanford University · CISPA Helmholtz Center +1

Feb 1, 2025J/K move · Enter open · S save

On the Relationship Between CoCoA and ADMM for Distributed Empirical Risk Minimization

Runxiong Wu, Andi Wang

Department of Industrial & Systems Engineering University of Wisconsin–Madison

Primal-Dual Optimization Distributed Optimization Alternating Direction Method of Multipliers Empirical Risk Minimization

Open paper AskPDF arXiv

Distributed empirical risk minimization (ERM) is often studied through two influential yet seemingly separate families of methods: CoCoA-type algorithms, derived from distributed dual coordinate ascent, and ADMM-type algorithms, derived from consensus and proximal splitting. In this paper, we investigate the connection of the two types of algorithms from a unified primal-dual perspective. We show that consensus ADMM, linearized consensus ADMM, two distributed proximal ADMM variants, and ridge-regularized CoCoA can all be written in a common update form involving a global primal variable and block dual variables. This reformulation makes several previously hidden connections explicit: For ridge-regularized ERM, CoCoA coincides with a particular proximal ADMM scheme at the level of the dual update. Moreover, consensus ADMM on the primal problem is equivalent to proximal ADMM on the dual problem under an explicit parameter mapping together with a sign reversal of the saddle objective; similar correspondences also hold for the linearized variants. These results indicates that the ADMM-type algorithms, when fine tuned, performs at least as good as CoCoA, under ridge regularized ERM problems. The unified view also yields a natural primal-dual gap stopping criterion for consensus ADMM and a unified

O(1/T)

ergodic convergence analysis for the ADMM-type methods. Experiments on synthetic regression problems and real SVM datasets support the predicted relationships, clarify the role of tuning parameters, and show that suitably tuned ADMM variants can outperform CoCoA in the ridge-regularized setting.

Latest papers

On the Relationship Between CoCoA and ADMM for Distributed Empirical Risk Minimization

The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication