Unified analysis of stochastic gradient methods for composite convex and smooth optimization
From MaRDI portal
Abstract: We present a unified theorem for the convergence analysis of stochastic gradient algorithms for minimizing a smooth and convex loss plus a convex regularizer. We do this by extending the unified analysis of Gorbunov, Hanzely & Richt'arik (2020) and dropping the requirement that the loss function be strongly convex. Instead, we only rely on convexity of the loss function. Our unified analysis applies to a host of existing algorithms such as proximal SGD, variance reduced methods, quantization and some coordinate descent type methods. For the variance reduced methods, we recover the best known convergence rates as special cases. For proximal SGD, the quantization and coordinate type methods, we uncover new state-of-the-art convergence rates. Our analysis also includes any form of sampling and minibatching. As such, we are able to determine the minibatch size that optimizes the total complexity of variance reduced methods. We showcase this by obtaining a simple formula for the optimal minibatch size of two variance reduced methods ( extit{L-SVRG} and extit{SAGA}). This optimal minibatch size not only improves the theoretical total complexity of the methods but also improves their convergence in practice, as we show in several experiments.
Recommendations
- A smoothing stochastic gradient method for composite optimization
- Stochastic Methods for Composite and Weakly Convex Optimization Problems
- A unified convergence analysis of stochastic Bregman proximal gradient and extragradient methods
- A hybrid stochastic optimization framework for composite nonconvex optimization
- Inexact proximal stochastic gradient method for convex composite optimization
- A unified analysis of stochastic gradient‐free Frank–Wolfe methods
- General convergence analysis of stochastic first-order methods for composite optimization
- A stochastic Nesterov's smoothing accelerated method for general nonsmooth constrained stochastic composite convex optimization
- Conditional gradient type methods for composite nonlinear and stochastic optimization
- Stochastic generalized gradient method for nonconvex nonsmooth stochastic optimization
Cites work
- A Stochastic Approximation Method
- Convergence rates for deterministic and stochastic subgradient methods without Lipschitz continuity
- Coordinate descent algorithms
- Efficiency of coordinate descent methods on huge-scale optimization problems
- First-order methods in optimization
- High-dimensional Ising model selection using \(\ell _{1}\)-regularized logistic regression
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- Katyusha: the first direct acceleration of stochastic gradient methods
- Minimizing finite sums with the stochastic average gradient
- On perturbed proximal gradient algorithms
- Regularization and Variable Selection Via the Elastic Net
- Robust Stochastic Approximation Approach to Stochastic Programming
- Stochastic distributed learning with gradient quantization and double-variance reduction
- Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
- Stochastic quasi-gradient methods: variance reduction via Jacobian sketching
- Understanding machine learning. From theory to algorithms
Cited in
(7)- General convergence analysis of stochastic first-order methods for composite optimization
- scientific article; zbMATH DE number 7626722 (Why is no real title available?)
- A framework of convergence analysis of mini-batch stochastic projected gradient methods
- Variable metric proximal stochastic gradient methods with additional sampling
- Zeroth-order proximal clipped gradient method with shifts for distributed stochastic composite optimization problems with infinite variance
- On the application of explicit Runge-Kutta methods to the construction of stochastic gradient descent methods for convex optimization
- Application of stochastic gradient method with momentum inspired by explicit stabilized Runge-Kutta method in unconstrained convex optimization
This page was built for publication: Unified analysis of stochastic gradient methods for composite convex and smooth optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6086133)
