Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
From MaRDI portal
Publication:5962715
DOI10.1007/S10107-014-0839-0zbMATH Open1342.90103arXiv1309.2375OpenAlexW2118545728MaRDI QIDQ5962715FDOQ5962715
Authors: Shai Shalev-Shwartz, Tong Zhang 
Publication date: 23 February 2016
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: We introduce a proximal version of the stochastic dual coordinate ascent method and show how to accelerate the method using an inner-outer iteration procedure. We analyze the runtime of the framework and obtain rates that improve state-of-the-art results for various key machine learning optimization problems including SVM, logistic regression, ridge regression, Lasso, and multiclass SVM. Experiments validate our theoretical findings.
Full work available at URL: https://arxiv.org/abs/1309.2375
Recommendations
- Stochastic dual coordinate ascent methods for regularized loss minimization
- An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization
- Accelerated, parallel, and proximal coordinate descent
- A general distributed dual coordinate optimization framework for regularized loss minimization
- Accelerated iterative regularization via dual diagonal descent
- Stochastic primal-dual coordinate method for regularized empirical risk minimization
- Projection-Based Regularized Dual Averaging for Stochastic Optimization
- Dual coordinate ascent methods for non-strictly convex minimization
- Accelerated Bregman proximal gradient methods for relatively smooth convex optimization
Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Stochastic programming (90C15)
Cites Work
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- Pegasos: primal estimated sub-gradient solver for SVM
- Smooth minimization of non-smooth functions
- Gradient methods for minimizing composite functions
- Understanding Machine Learning
- Smooth Optimization with Approximate Gradient
- First-order methods of smooth convex optimization with inexact oracle
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Dual averaging methods for regularized stochastic learning and online optimization
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Accelerated, Parallel, and Proximal Coordinate Descent
- Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework
- Title not available (Why is that?)
- Sparse online learning via truncated gradient
- Trading accuracy for sparsity in optimization problems with sparsity constraints
- 10.1162/15324430260185628
- Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
- Efficient online and batch learning using forward backward splitting
- Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
- Exponentiated gradient algorithms for conditional random fields and max-margin Markov networks
- On the dual formulation of regularized linear systems with convex risks
Cited In (74)
- Title not available (Why is that?)
- Random Gradient Extrapolation for Distributed and Stochastic Optimization
- Title not available (Why is that?)
- An accelerated variance reducing stochastic method with Douglas-Rachford splitting
- On optimal probabilities in stochastic coordinate descent methods
- A Randomized Nonmonotone Block Proximal Gradient Method for a Class of Structured Nonlinear Programming
- Primal-dual block-proximal splitting for a class of non-convex problems
- On the Convergence of Stochastic Primal-Dual Hybrid Gradient
- A generic coordinate descent solver for non-smooth convex optimisation
- Dual coordinate descent methods for logistic regression and maximum entropy models
- Title not available (Why is that?)
- On the Complexity Analysis of the Primal Solutions for the Accelerated Randomized Dual Coordinate Ascent
- Randomized smoothing variance reduction method for large-scale non-smooth convex optimization
- On the Adaptivity of Stochastic Gradient-Based Optimization
- Kalman-Based Stochastic Gradient Method with Stop Condition and Insensitivity to Conditioning
- A new accelerated algorithm for ill-conditioned ridge regression problems
- Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization
- Title not available (Why is that?)
- Generalized stochastic Frank-Wolfe algorithm with stochastic ``substitute gradient for structured convex optimization
- An optimal randomized incremental gradient method
- Stochastic primal dual fixed point method for composite optimization
- An accelerated directional derivative method for smooth stochastic convex optimization
- A unified convergence analysis of stochastic Bregman proximal gradient and extragradient methods
- Provable accelerated gradient method for nonconvex low rank optimization
- Block-proximal methods with spatially adapted acceleration
- Convergence rates of accelerated proximal gradient algorithms under independent noise
- On the complexity analysis of randomized block-coordinate descent methods
- A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization
- Surpassing Gradient Descent Provably: A Cyclic Incremental Method with Linear Convergence Rate
- Importance sampling in signal processing applications
- Block mirror stochastic gradient method for stochastic optimization
- Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
- Parallel decomposition methods for linearly constrained problems subject to simple bound with application to the SVMs training
- The complexity of primal-dual fixed point methods for ridge regression
- Title not available (Why is that?)
- An Accelerated Randomized Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
- Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent
- An Optimal High-Order Tensor Method for Convex Optimization
- Optimization in high dimensions via accelerated, parallel, and proximal coordinate descent
- Faster convergence of a randomized coordinate descent method for linearly constrained optimization problems
- On Faster Convergence of Cyclic Block Coordinate Descent-type Methods for Strongly Convex Minimization
- Dual averaging methods for regularized stochastic learning and online optimization
- Bundle methods for regularized risk minimization
- Title not available (Why is that?)
- Accelerated, Parallel, and Proximal Coordinate Descent
- Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
- Distributed block-diagonal approximation methods for regularized empirical risk minimization
- High-dimensional model recovery from random sketched data by exploring intrinsic sparsity
- Top-\(k\) multi-class SVM using multiple features
- Variance reduction for root-finding problems
- Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice
- An Inexact Variable Metric Proximal Point Algorithm for Generic Quasi-Newton Acceleration
- Accelerated Methods for NonConvex Optimization
- Title not available (Why is that?)
- Linear convergence of cyclic SAGA
- Title not available (Why is that?)
- A stochastic extra-step quasi-Newton method for nonsmooth nonconvex optimization
- Title not available (Why is that?)
- A Smooth Inexact Penalty Reformulation of Convex Problems with Linear Constraints
- A new randomized primal-dual algorithm for convex optimization with fast last iterate convergence rates
- An extragradient-based alternating direction method for convex minimization
- Title not available (Why is that?)
- An Optimal Algorithm for Decentralized Finite-Sum Optimization
- Title not available (Why is that?)
- A dual-based stochastic inexact algorithm for a class of stochastic nonsmooth convex composite problems
- An accelerated stochastic mirror descent method
- An aggressive reduction on the complexity of optimization for non-strongly convex objectives
- Title not available (Why is that?)
- A safe double screening strategy for elastic net support vector machine
- Active Subspace of Neural Networks: Structural Analysis and Universal Attacks
- An inexact primal-dual smoothing framework for large-scale non-bilinear saddle point problems
- Unifying framework for accelerated randomized methods in convex optimization
- Support vector machine in big data: smoothing strategy and adaptive distributed inference
- Title not available (Why is that?)
Uses Software
This page was built for publication: Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5962715)
