On the adaptivity of stochastic gradient-based optimization
From MaRDI portal
Abstract: Stochastic-gradient-based optimization has been a core enabling methodology in applications to large-scale problems in machine learning and related areas. Despite the progress, the gap between theory and practice remains significant, with theoreticians pursuing mathematical optimality at a cost of obtaining specialized procedures in different regimes (e.g., modulus of strong convexity, magnitude of target accuracy, signal-to-noise ratio), and with practitioners not readily able to know which regime is appropriate to their problem, and seeking broadly applicable algorithms that are reasonably close to optimality. To bridge these perspectives it is necessary to study algorithms that are adaptive to different regimes. We present the stochastically controlled stochastic gradient (SCSG) method for composite convex finite-sum optimization problems and show that SCSG is adaptive to both strong convexity and target accuracy. The adaptivity is achieved by batch variance reduction with adaptive batch sizes and a novel technique, which we referred to as geometrization, which sets the length of each epoch as a geometric random variable. The algorithm achieves strictly better theoretical complexity than other existing adaptive algorithms, while the tuning parameters of the algorithm only depend on the smoothness parameter of the objective.
Recommendations
- Adaptivity of stochastic gradient methods for nonconvex optimization
- Adaptive sampling strategies for stochastic optimization
- Adaptive subgradient methods for online learning and stochastic optimization
- Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression
- Adaptive gradient-free method for stochastic optimization
Cites work
- Accelerate stochastic subgradient method by leveraging local growth condition
- Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
- Acceleration of Stochastic Approximation by Averaging
- Adaptive subgradient methods for online learning and stochastic optimization
- An optimal method for stochastic composite optimization
- Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization
- Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization
- Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression
- Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization
- Introductory lectures on convex optimization. A basic course.
- Katyusha: the first direct acceleration of stochastic gradient methods
- Martingales with values in uniformly convex spaces
- Mirror descent and nonlinear projected subgradient methods for convex optimization.
- Nemirovski's inequalities revisited
- New method of stochastic approximation type
- On the uniform convexity of L^p and l^p
- Robust Stochastic Approximation Approach to Stochastic Programming
- Solving variational inequalities with stochastic mirror-prox algorithm
- Universal gradient methods for convex optimization problems
Cited in
(18)- ASD+M: automatic parameter tuning in stochastic optimization and on-line learning
- Adaptivity of stochastic gradient methods for nonconvex optimization
- On the Value of Objective Function Adaptation in Online Optimisation
- Adaptive gradient-free method for stochastic optimization
- Learning rate adaptation in stochastic gradient descent.
- Improving the stochastically controlled stochastic gradient method by the bandwidth-based stepsize
- Adaptive sequential machine learning
- Variance reduction on general adaptive stochastic mirror descent
- Nonlinear Gradient Mappings and Stochastic Optimization: A General Framework with Applications to Heavy-Tail Noise
- The importance of better models in stochastic optimization
- An adaptive gradient method with energy and momentum
- Stochastic ADMM with batch size adaptation for nonconvex nonsmooth optimization
- Bolstering stochastic gradient descent with model building
- A multivariate adaptive gradient algorithm with reduced tuning efforts
- Adaptive sampling strategies for stochastic optimization
- Convergence results on stochastic adaptive learning
- On the improvement of the Barzilai-Borwein step size in variance reduction methods
- Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression
This page was built for publication: On the adaptivity of stochastic gradient-based optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5114394)
