A general distributed dual coordinate optimization framework for regularized loss minimization
From MaRDI portal
(Redirected from Publication:4637039)
Abstract: In modern large-scale machine learning applications, the training data are often partitioned and stored on multiple machines. It is customary to employ the "data parallelism" approach, where the aggregated training loss is minimized without moving data across machines. In this paper, we introduce a novel distributed dual formulation for regularized loss minimization problems that can directly handle data parallelism in the distributed setting. This formulation allows us to systematically derive dual coordinate optimization procedures, which we refer to as Distributed Alternating Dual Maximization (DADM). The framework extends earlier studies described in (Boyd et al., 2011; Ma et al., 2015a; Jaggi et al., 2014; Yang, 2013) and has rigorous theoretical analyses. Moreover with the help of the new formulation, we develop the accelerated version of DADM (Acc-DADM) by generalizing the acceleration technique from (Shalev-Shwartz and Zhang, 2014) to the distributed setting. We also provide theoretical results for the proposed accelerated version and the new result improves previous ones (Yang, 2013; Ma et al., 2015a) whose runtimes grow linearly on the condition number. Our empirical studies validate our theory and show that our accelerated approach significantly improves the previous state-of-the-art distributed dual coordinate optimization algorithms.
Recommendations
- Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
- Distributed block-diagonal approximation methods for regularized empirical risk minimization
- Stochastic primal-dual coordinate method for regularized empirical risk minimization
- scientific article; zbMATH DE number 6982986
- DSCOVR: randomized primal-dual block coordinate algorithms for asynchronous distributed optimization
Cites work
- A distributed block coordinate descent method for training l₁ regularized linear classifiers
- Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
- Adaptive restart for accelerated gradient schemes
- An efficient distributed learning algorithm based on effective local functional approximations
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- scientific article; zbMATH DE number 6982986 (Why is no real title available?)
- Introductory lectures on convex optimization. A basic course.
- On the limited memory BFGS method for large scale optimization
- Smooth minimization of non-smooth functions
- Sparse inverse covariance estimation with the graphical lasso
- Stochastic dual coordinate ascent methods for regularized loss minimization
Cited in
(9)- Communication-efficient distributed multi-task learning with matrix sparsity regularization
- Communication-efficient distributed optimization of self-concordant empirical loss
- Inexact successive quadratic approximation for regularized optimization
- scientific article; zbMATH DE number 6982986 (Why is no real title available?)
- DSCOVR: randomized primal-dual block coordinate algorithms for asynchronous distributed optimization
- GADMM: fast and communication efficient framework for distributed machine learning
- An accelerated communication-efficient primal-dual optimization framework for structured machine learning
- Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
- Distributed block-diagonal approximation methods for regularized empirical risk minimization
This page was built for publication: A general distributed dual coordinate optimization framework for regularized loss minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4637039)
