Coordinate descent with arbitrary sampling. II: Expected separable overapproximation.
From MaRDI portal
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.
Recommendations
- Coordinate descent with arbitrary sampling. I: Algorithms and complexity.
- A randomized coordinate descent method with volume sampling
- On the complexity analysis of randomized block-coordinate descent methods
- Accelerated, parallel, and proximal coordinate descent
- Inexact coordinate descent: complexity and preconditioning
Cites work
- A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints
- Accelerated, parallel, and proximal coordinate descent
- An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization
- Asynchronous stochastic coordinate descent: parallelism and convergence properties
- Convergence of a block coordinate descent method for nondifferentiable minimization
- Coordinate descent algorithms
- Efficiency of coordinate descent methods on huge-scale optimization problems
- scientific article; zbMATH DE number 635657 (Why is no real title available?)
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- On the convergence of block coordinate descent type methods
- Parallel coordinate descent methods for big data optimization
- Separable approximations and decomposition methods for the augmented Lagrangian
Cited in
(19)- Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
- Stochastic quasi-gradient methods: variance reduction via Jacobian sketching
- Fastest rates for stochastic mirror descent methods
- Parallel random block-coordinate forward-backward algorithm: a unified convergence analysis
- Restarting the accelerated coordinate descent method with a rough strong convexity estimate
- Empirical risk minimization: probabilistic complexity and stepsize strategy
- Coordinate descent with arbitrary sampling. I: Algorithms and complexity.
- Optimization in high dimensions via accelerated, parallel, and proximal coordinate descent
- On optimal probabilities in stochastic coordinate descent methods
- A randomized coordinate descent method with volume sampling
- scientific article; zbMATH DE number 6982318 (Why is no real title available?)
- On the complexity of parallel coordinate descent
- L-SVRG and L-Katyusha with arbitrary sampling
- A discrete dynamics approach to sparse calculation and applied in ontology science
- Faster convergence of a randomized coordinate descent method for linearly constrained optimization problems
- Convergence analysis of inexact randomized iterative methods
- Local linear convergence of proximal coordinate descent algorithm
- Laplacian-based semi-supervised learning in multilayer hypergraphs by coordinate descent
- EF21 with bells \& whistles: six algorithmic extensions of modern error feedback
This page was built for publication: Coordinate descent with arbitrary sampling. II: Expected separable overapproximation.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2829566)
