Proximal Stochastic Dual Coordinate Ascent

Abstract

We introduce a proximal version of dual coordinate ascent method. We demonstrate how the derived algorithmic framework can be used for numerous regularized loss minimization problems, including ${\ell }_1$ regularization and structured output SVM. The convergence rates we obtain match, and sometimes improve, state-of-the-art results.

References in corpus (2)

• Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
• Block-Coordinate Frank-Wolfe Optimization for Structural SVMs

Cited by in corpus (42)

• A Universal Catalyst for First-Order Optimization
• Block-Coordinate Frank-Wolfe Optimization for Structural SVMs
• Optimization with First-Order Surrogate Functions
• Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization
• Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport
• Stochastic Optimization with Importance Sampling
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Randomized Dual Coordinate Ascent with Arbitrary Sampling
• The proximal point method revisited
• Stochastic Dual Coordinate Ascent with Adaptive Probabilities
• Linear Convergence of Variance-Reduced Stochastic Gradient without Strong Convexity
• On the Adaptivity of Stochastic Gradient-Based Optimization
• Importance Sampling for Minibatches
• On the Complexity Analysis of Randomized Block-Coordinate Descent Methods
• On Optimal Probabilities in Stochastic Coordinate Descent Methods
• Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
• Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning
• Breaking the Nonsmooth Barrier: A Scalable Parallel Method for Composite Optimization
• Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method
• Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice
• A Randomized Nonmonotone Block Proximal Gradient Method for a Class of Structured Nonlinear Programming
• Riemannian stochastic variance reduced gradient on Grassmann manifold
• Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives
• Stochastic Dual Coordinate Ascent with Alternating Direction Multiplier Method
• Cyanure: An Open-Source Toolbox for Empirical Risk Minimization for Python, C++, and soon more
• A Stochastic Penalty Model for Convex and Nonconvex Optimization with Big Constraints
• Distributed Block-diagonal Approximation Methods for Regularized Empirical Risk Minimization
• Generalized Stochastic Frank-Wolfe Algorithm with Stochastic "Substitute" Gradient for Structured Convex Optimization
• Data Sampling Strategies in Stochastic Algorithms for Empirical Risk Minimization
• A Distributed Quasi-Newton Algorithm for Primal and Dual Regularized Empirical Risk Minimization
• Label and Sample: Efficient Training of Vehicle Object Detector from Sparsely Labeled Data
• SGD with Variance Reduction beyond Empirical Risk Minimization
• Empirical study of PROXTONE and PROXTONE${}^{+}$ for Fast Learning of Large Scale Sparse Models
• Randomized Smoothing SVRG for Large-scale Nonsmooth Convex Optimization
• A generic coordinate descent solver for nonsmooth convex optimization
• Online and Stochastic Universal Gradient Methods for Minimizing Regularized Hölder Continuous Finite Sums
• Stochastic primal dual fixed point method for composite optimization
• A Stochastic Variance Reduced Primal Dual Fixed Point Method For Linearly Constrained Separable Optimization
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
• The Lingering of Gradients: Theory and Applications
• Random constraint sampling and duality for convex optimization
• Proximal Stochastic Newton-type Gradient Descent Methods for Minimizing Regularized Finite Sums