Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling

Abstract

Accelerated coordinate descent is widely used in optimization due to its cheap per-iteration cost and scalability to large-scale problems. Up to a primal-dual transformation, it is also the same as accelerated stochastic gradient descent that is one of the central methods used in machine learning. In this paper, we improve the best known running time of accelerated coordinate descent by a factor up to $\sqrt{n}$. Our improvement is based on a clean, novel non-uniform sampling that selects each coordinate with a probability proportional to the square root of its smoothness parameter. Our proof technique also deviates from the classical estimation sequence technique used in prior work. Our speed-up applies to important problems such as empirical risk minimization and solving linear systems, both in theory and in practice.

same result, but polished writing

References in corpus (9)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection
• A geometric alternative to Nesterov's accelerated gradient descent
• Stochastic Dual Ascent for Solving Linear Systems
• Optimal Black-Box Reductions Between Optimization Objectives
• Randomized Dual Coordinate Ascent with Arbitrary Sampling
• Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
• Stochastic Dual Coordinate Ascent with Adaptive Probabilities
• Exploiting the Structure: Stochastic Gradient Methods Using Raw Clusters

Cited by in corpus (53)

• Variance Reduction for Faster Non-Convex Optimization
• Optimal Client Sampling for Federated Learning
• Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization
• A Primer on Coordinate Descent Algorithms
• Hamiltonian Descent Methods
• Minimizing the Maximal Loss: How and Why?
• The Practicality of Stochastic Optimization in Imaging Inverse Problems
• An Accelerated Directional Derivative Method for Smooth Stochastic Convex Optimization
• On the Complexity of Approximating Multimarginal Optimal Transport
• Privacy Preserving Randomized Gossip Algorithms
• Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition
• Accelerating Greedy Coordinate Descent Methods
• Alternating Randomized Block Coordinate Descent
• Breaking Locality Accelerates Block Gauss-Seidel
• Stochastic Subspace Descent
• Robust Training in High Dimensions via Block Coordinate Geometric Median Descent
• A Convergence Analysis for A Class of Practical Variance-Reduction Stochastic Gradient MCMC
• Accelerating Asynchronous Algorithms for Convex Optimization by Momentum Compensation
• About accelerated randomized methods
• Personalized Federated Learning: A Unified Framework and Universal Optimization Techniques
• Online Variance Reduction for Stochastic Optimization
• Leverage Score Sampling for Faster Accelerated Regression and ERM
• Adaptive Task Sampling for Meta-Learning
• Convergence Analysis of Block Coordinate Algorithms with Determinantal Sampling
• Linear convergence of SDCA in statistical estimation
• Faster Principal Component Regression and Stable Matrix Chebyshev Approximation
• Global Riemannian Acceleration in Hyperbolic and Spherical Spaces
• Efficiency of Coordinate Descent Methods For Structured Nonconvex Optimization
• Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip
• Explicit Regularization of Stochastic Gradient Methods through Duality
• How Does Momentum Help Frank Wolfe?
• Acceleration of Primal-Dual Methods by Preconditioning and Simple Subproblem Procedures
• Improving SAGA via a Probabilistic Interpolation with Gradient Descent
• A Stochastic Penalty Model for Convex and Nonconvex Optimization with Big Constraints
• An adaptive proximal point algorithm framework and application to large-scale optimization
• SGD with Coordinate Sampling: Theory and Practice
• Stochastic Spectral and Conjugate Descent Methods
• Searching equillibriums in large transport networks
• Variance Reduced Coordinate Descent with Acceleration: New Method With a Surprising Application to Finite-Sum Problems
• Reducing Runtime by Recycling Samples
• A stochastic subspace approach to gradient-free optimization in high dimensions
• Markov Chain Block Coordinate Descent
• Accelerated Randomized Coordinate Descent Algorithms for Stochastic Optimization and Online Learning
• An Analysis of Asynchronous Stochastic Accelerated Coordinate Descent
• Coordinate Methods for Accelerating ${\ell }_{\infty }$ Regression and Faster Approximate Maximum Flow
• Optimal First-Order Algorithms as a Function of Inequalities
• A Geometric Structure of Acceleration and Its Role in Making Gradients Small Fast
• Safe Adaptive Importance Sampling
• A generic coordinate descent solver for nonsmooth convex optimization
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
• Acceleration of SVRG and Katyusha X by Inexact Preconditioning
• Computing the Best Approximation Over the Intersection of a Polyhedral Set and the Doubly Nonnegative Cone
• A Simple and Fast Coordinate-Descent Augmented-Lagrangian Solver for Model Predictive Control