Coordinate Descent with Arbitrary Sampling II: Expected Separable Overapproximation
arXiv:1412.8063
Abstract
The design and complexity analysis of randomized coordinate descent methods, and in particular of variants which update a random subset (sampling) of coordinates in each iteration, depends on the notion of expected separable overapproximation (ESO). This refers to an inequality involving the objective function and the sampling, capturing in a compact way certain smoothness properties of the function in a random subspace spanned by the sampled coordinates. ESO inequalities were previously established for special classes of samplings only, almost invariably for uniform samplings. In this paper we develop a systematic technique for deriving these inequalities for a large class of functions and for arbitrary samplings. We demonstrate that one can recover existing ESO results using our general approach, which is based on the study of eigenvalues associated with samplings and the data describing the function.
29 pages, 0 figures
References in corpus (10)
- Parallel Coordinate Descent for L1-Regularized Loss Minimization
- Mini-Batch Primal and Dual Methods for SVMs
- Stochastic Optimization with Importance Sampling
- Randomized Dual Coordinate Ascent with Arbitrary Sampling
- Smooth minimization of nonsmooth functions with parallel coordinate descent methods
- An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
- Inexact Coordinate Descent: Complexity and Preconditioning
- On the Complexity Analysis of Randomized Block-Coordinate Descent Methods
- On Optimal Probabilities in Stochastic Coordinate Descent Methods
- Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties
Cited by in corpus (8)
- Stochastic Dual Ascent for Solving Linear Systems
- Importance Sampling for Minibatches
- Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
- Breaking Locality Accelerates Block Gauss-Seidel
- Sketch and Project: Randomized Iterative Methods for Linear Systems and Inverting Matrices
- Stochastic Second-Order Optimization via von Neumann Series
- Accelerated Variance Reduced Block Coordinate Descent
- Faster Convergence of a Randomized Coordinate Descent Method for Linearly Constrained Optimization Problems