An Accelerated Communication-Efficient Primal-Dual Optimization Framework for Structured Machine Learning

2017-11-14 · Chenxin Ma, Martin Jaggi, Frank E. Curtis, Nathan Srebro, Martin Takáč

Distributed optimization algorithms are essential for training machine learning models on very large-scale datasets. However, they often suffer from communication bottlenecks. Confronting this issue, a communication-efficient primal-dual coordinate ascent framework (CoCoA) and its improved variant CoCoA+ have been proposed, achieving a convergence rate of $\mathcal{O}(1/t)$ for solving empirical risk minimization problems with Lipschitz continuous losses. In this paper, an accelerated variant of CoCoA+ is proposed and shown to possess a convergence rate of $\mathcal{O}(1/t^2)$ in terms of reducing suboptimality. The analysis of this rate is also notable in that the convergence rate bounds involve constants that, except in extreme cases, are significantly reduced compared to those previously provided for CoCoA+. The results of numerical experiments are provided to show that acceleration can lead to significant performance gains.

📄 PDF Abstract BibTeX arXiv:1711.05305

Code (1)

schemmy/CoCoA-Experiments 공식 구현

Tasks

BIG-bench Machine Learning Distributed Optimization

Accelerating Distributed Optimization: A Primal-Dual Perspective on Local Steps

2024-07-02 · Junchi Yang, Murat Yildirim, Qiu Feng

In distributed machine learning, efficient training across multiple agents with different data distributions poses significant challenges. Even with a centralized coordinator, current algorithms that achieve optimal comm…

Distributed Optimization

Accelerated Primal-Dual Policy Optimization for Safe Reinforcement Learning

2018-02-19 · Qingkai Liang, Fanyu Que, Eytan Modiano

Constrained Markov Decision Process (CMDP) is a natural framework for reinforcement learning tasks with safety constraints, where agents learn a policy that maximizes the long-term reward while satisfying the constraints…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Safe Reinforcement Learning

Accelerated Primal-Dual Algorithms for Distributed Smooth Convex Optimization over Networks

2019-10-23 · Jinming Xu, Ye Tian, Ying Sun, Gesualdo Scutari

This paper proposes a novel family of primal-dual-based distributed algorithms for smooth, convex, multi-agent optimization over networks that uses only gradient information and gossip communications. The algorithms can …

Distributed Optimization

Unrolled Neural Networks for Constrained Optimization

2026-01-24 · Samar Hadou, Alejandro Ribeiro arxiv

In this paper, we develop unrolled neural networks to solve constrained optimization problems, offering accelerated, learnable counterparts to dual ascent (DA) algorithms. Our framework, termed constrained dual unrolling…

On Principled Local Optimization Methods for Federated Learning

2024-01-24 · Honglin Yuan

Federated Learning (FL), a distributed learning paradigm that scales on-device learning collaboratively, has emerged as a promising approach for decentralized AI applications. Local optimization methods such as Federated…

Federated Learning