Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization

Abstract

Stochastic Gradient Descent (SGD) has become popular for solving large scale supervised machine learning optimization problems such as SVM, due to their strong theoretical guarantees. While the closely related Dual Coordinate Ascent (DCA) method has been implemented in various software packages, it has so far lacked good convergence analysis. This paper presents a new analysis of Stochastic Dual Coordinate Ascent (SDCA) showing that this class of methods enjoy strong theoretical guarantees that are comparable or better than SGD. This analysis justifies the effectiveness of SDCA for practical applications.

References in corpus (1)

• Block-Coordinate Frank-Wolfe Optimization for Structural SVMs

Cited by in corpus (53)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• A Survey on Distributed Machine Learning
• Non-convex Optimization for Machine Learning
• Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attacks
• Gradient Sparsification for Communication-Efficient Distributed Optimization
• A Survey of Stochastic Simulation and Optimization Methods in Signal Processing
• Mini-Batch Primal and Dual Methods for SVMs
• Proximal Stochastic Dual Coordinate Ascent
• Linear Support Tensor Machine: Pedestrian Detection in Thermal Infrared Images
• Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• Concentration inequalities for sampling without replacement
• Central Server Free Federated Learning over Single-sided Trust Social Networks
• A Coordinate Descent Primal-Dual Algorithm with Large Step Size and Possibly Non Separable Functions
• Fast and Simple PCA via Convex Optimization
• Supervised Learning Under Distributed Features
• Smooth minimization of nonsmooth functions with parallel coordinate descent methods
• Distributed Mini-Batch SDCA
• The Practicality of Stochastic Optimization in Imaging Inverse Problems
• Preference Completion: Large-scale Collaborative Ranking from Pairwise Comparisons
• Spectral Learning on Matrices and Tensors
• Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data
• Accelerated Variance Reduced Stochastic ADMM
• Stochastic Multi-Dimensional Deconvolution
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization
• Backtracking Spatial Pyramid Pooling (SPP)-based Image Classifier for Weakly Supervised Top-down Salient Object Detection
• Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems
• BROADCAST: Reducing Both Stochastic and Compression Noise to Robustify Communication-Efficient Federated Learning
• Fine-Grained Visual Categorization via Multi-stage Metric Learning
• Efficient Distributed Hessian Free Algorithm for Large-scale Empirical Risk Minimization via Accumulating Sample Strategy
• Federated Optimization of Smooth Loss Functions
• A Randomized Nonmonotone Block Proximal Gradient Method for a Class of Structured Nonlinear Programming
• Machine learning phases of active matter
• Stochastic Second-Order Optimization via von Neumann Series
• Stochastic subGradient Methods with Linear Convergence for Polyhedral Convex Optimization
• Analysis of regularized federated learning
• Improved Optimization of Finite Sums with Minibatch Stochastic Variance Reduced Proximal Iterations
• Randomized Block Subgradient Methods for Convex Nonsmooth and Stochastic Optimization
• Learning with risks based on M-location
• On the Convergence of SARAH and Beyond
• Noisy Accelerated Power Method for Eigenproblems with Applications
• Distributed Block-diagonal Approximation Methods for Regularized Empirical Risk Minimization
• A Stochastic Variance Reduced Nesterov's Accelerated Quasi-Newton Method
• Towards Making High Dimensional Distance Metric Learning Practical
• Stochastic Variance Reduction Gradient for a Non-convex Problem Using Graduated Optimization
• Hybrid Acceleration Scheme for Variance Reduced Stochastic Optimization Algorithms
• Memory Augmented Optimizers for Deep Learning
• On Linear Learning with Manycore Processors
• Data Sampling Strategies in Stochastic Algorithms for Empirical Risk Minimization
• Tight Lower Complexity Bounds for Strongly Convex Finite-Sum Optimization
• Regularized ERM on random subspaces
• Randomized Smoothing SVRG for Large-scale Nonsmooth Convex Optimization
• Training L1-Regularized Models with Orthant-Wise Passive Descent Algorithms