SVRG meets AdaGrad: painless variance reduction

DOI10.1007/S10994-022-06265-XMaRDI QIDQ6097116zbMATH OpenOpenAlexFDO

Authors Benjamin Dubois-Taine, Sharan Vaswani, Reza Babanezhad, Mark Schmidt, Simon Lacoste-Julien

Publication date 12 June 2023

Published in Machine Learning (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.09645

zbMATH Keywords

adaptive gradient methodsconvex optimizationstochastic optimizationvariance reduction

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Abstract: Variance reduction (VR) methods for finite-sum minimization typically require the knowledge of problem-dependent constants that are often unknown and difficult to estimate. To address this, we use ideas from adaptive gradient methods to propose AdaSVRG, which is a more robust variant of SVRG, a common VR method. AdaSVRG uses AdaGrad in the inner loop of SVRG, making it robust to the choice of step-size. When minimizing a sum of n smooth convex functions, we prove that a variant of AdaSVRG requires $ildeO(n+1/epsilon)$ gradient evaluations to achieve an $O(epsilon)$-suboptimality, matching the typical rate, but without needing to know problem-dependent constants. Next, we leverage the properties of AdaGrad to propose a heuristic that adaptively determines the length of each inner-loop in AdaSVRG. Via experiments on synthetic and real-world datasets, we validate the robustness and effectiveness of AdaSVRG, demonstrating its superior performance over standard and other "tune-free" VR methods.

Cites work

• Adaptive subgradient methods for online learning and stochastic optimization
• Exact and inexact subsampled Newton methods for optimization
• scientific article; zbMATH DE number 7306906 (Why is no real title available?)
• Introductory lectures on convex optimization. A basic course.
• Just interpolate: kernel ``ridgeless regression can generalize
• Katyusha: the first direct acceleration of stochastic gradient methods
• Minimization of functions having Lipschitz continuous first partial derivatives
• Minimizing finite sums with the stochastic average gradient
• Stochastic dual coordinate ascent methods for regularized loss minimization
• Theory of Classification: a Survey of Some Recent Advances
• Two-Point Step Size Gradient Methods

Cited in

(4)

• Batching Adaptive Variance Reduction
• An adaptive stochastic gradient algorithm based on FISTA for convex optimization
• On the improvement of the Barzilai-Borwein step size in variance reduction methods
• Stochastic Polyak stepsize for SGD with variance reduction and momentum

This page was built for publication: SVRG meets AdaGrad: painless variance reduction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6097116)