← Back to papers
2022 JMLR JMLR 2022

On Biased Stochastic Gradient Estimation

Abstract

We present a uniform analysis of biased stochastic gradient methods for minimizing convex, strongly convex, and non-convex composite objectives, and identify settings where bias is useful in stochastic gradient estimation. The framework we present allows us to extend proximal support to biased algorithms, including SAG and SARAH, for the first time in the convex setting. We also use our framework to develop a new algorithm, Stochastic Average Recursive GradiEnt (SARGE), that achieves the oracle complexity lower-bound for non-convex, finite-sum objectives and requires strictly fewer calls to a stochastic gradient oracle per iteration than SVRG and SARAH. We support our theoretical results with numerical experiments that demonstrate the benefits of certain biased gradient estimators. [abs] [ pdf ][ bib ] © JMLR 2022. (edit, beta)

🐣 Hot Topic Early Bird — non-convex optimization
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Reinforcement Learning
🌉 Interdisciplinary Bridge — Deep Learning and Machine Learning and Mathematics & Optimization

Authors

Derek Driggs , Jingwei Liang , Carola-Bibiane Schönlieb

Topics

Machine Learning > Optimization & Theory > Neural Network Optimization Machine Learning > Optimization & Theory > Optimization Mathematics & Optimization > Optimization > Stochastic Methods Machine Learning > Optimization & Theory > Stochastic Methods Machine Learning > Core Methods > Optimization Deep Learning > Optimization & Theory > Optimization

Keywords

stochastic gradient stochastic gradient descent non-convex optimization oracle complexity gradient estimator
Download PDF

Related papers

Prior Adaptive Semi-supervised Learning with Application to EHR Phenotyping 2022
LinCDE: Conditional Density Estimation via Lindsey's Method 2022
Causal Classification: Treatment Effect Estimation vs. Outcome Prediction 2022
Provable Tensor-Train Format Tensor Completion by Riemannian Optimization 2022
Power Iteration for Tensor PCA 2022