An accelerated communication-efficient primal-dual optimization framework for structured machine learning

DOI10.1080/10556788.2019.1650361MaRDI QIDQ5859008zbMATH OpenOpenAlexWikidataFDO

Authors Chenxin Ma, Martin Jaggi, Nathan Srebro, M. Takáč, Frank E. Curtis

Publication date 15 April 2021

Published in Optimization Methods \& Software (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.05305

zbMATH Keywords

accelerated methodsdistributed optimizationmachine learningnonlinear optimizationnonsmooth optimization

Mathematics Subject Classification ID

Convex programming (90C25)

Abstract: 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 $mathcalO(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 $mathcalO(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.

Recommendations

• scientific article; zbMATH DE number 6982986
• Optimal convergence rates for convex distributed optimization in networks
• Distributed block-diagonal approximation methods for regularized empirical risk minimization
• A general distributed dual coordinate optimization framework for regularized loss minimization
• On convergence rate of distributed stochastic gradient algorithm for convex optimization with inequality constraints

Cites work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Accelerated, parallel, and proximal coordinate descent
• Adaptive subgradient methods for online learning and stochastic optimization
• Algorithm 778: L-BFGS-B
• Asynchronous stochastic coordinate descent: parallelism and convergence properties
• Communication-efficient distributed optimization of self-concordant empirical loss
• Distributed optimization with arbitrary local solvers
• Gradient methods for minimizing composite functions
• scientific article; zbMATH DE number 6982986 (Why is no real title available?)
• scientific article; zbMATH DE number 3365044 (Why is no real title available?)
• Stochastic dual coordinate ascent methods for regularized loss minimization

Cited in

(6)

• Fast and safe: accelerated gradient methods with optimality certificates and underestimate sequences
• Distributed optimization for degenerate loss functions arising from over-parameterization
• Communication-efficient distributed multi-task learning with matrix sparsity regularization
• Distributed Learning with Sparse Communications by Identification
• Adaptive pruning-based Newton's method for distributed learning
• Distributed learning with compressed gradient differences

Describes a project that uses

Uses Software

• L-BFGS
• CoCoA
• HOGWILD
• L-BFGS-B
• LBFGS-B
• AdaGrad

This page was built for publication: An accelerated communication-efficient primal-dual optimization framework for structured machine learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5859008)