Timezone: »
Importance sampling is a promising strategy for improving the convergence rate of stochastic gradient methods. It is typically used to precondition the optimization problem, but it can also be used to reduce the variance of the gradient estimator. Unfortunately, this latter point of view has yet to lead to practical methods that provably improve the asymptotic error of stochastic gradient methods. In this work, we propose stochastic reweighted gradient descent (SRG), a stochastic gradient method based solely on importance sampling that can reduce the variance of the gradient estimator and improve on the asymptotic error of stochastic gradient descent (SGD) in the strongly convex and smooth case. We show that SRG can be extended to combine the benefits of both importance-sampling-based preconditioning and variance reduction. When compared to SGD, the resulting algorithm can simultaneously reduce the condition number and the asymptotic error, both by up to a factor equal to the number of component functions. We demonstrate improved convergence in practice on regularized logistic regression problems.
Author Information
Ayoub El Hanchi (University of Toronto)
David Stephens (McGill University)

I am Professor, Department of Mathematics and Statistics, McGill University, Montreal, Canada. My interests are in Bayesian theory and computation.
Chris Maddison (University of Toronto)
Related Events (a corresponding poster, oral, or spotlight)
-
2022 Spotlight: Stochastic Reweighted Gradient Descent »
Tue. Jul 19th 05:50 -- 05:55 PM Room Room 318 - 320
More from the Same Authors
-
2022 : Contrastive Learning Can Find An Optimal Basis For Approximately Invariant Functions »
Daniel D. Johnson · Daniel D. Johnson · Ayoub El Hanchi · Ayoub El Hanchi · Chris Maddison · Chris Maddison -
2022 Poster: Augment with Care: Contrastive Learning for Combinatorial Problems »
Haonan Duan · Pashootan Vaezipoor · Max Paulus · Yangjun Ruan · Chris Maddison -
2022 Poster: Learning to Cut by Looking Ahead: Cutting Plane Selection via Imitation Learning »
Max Paulus · Giulia Zarpellon · Andreas Krause · Laurent Charlin · Chris Maddison -
2022 Spotlight: Augment with Care: Contrastive Learning for Combinatorial Problems »
Haonan Duan · Pashootan Vaezipoor · Max Paulus · Yangjun Ruan · Chris Maddison -
2022 Spotlight: Learning to Cut by Looking Ahead: Cutting Plane Selection via Imitation Learning »
Max Paulus · Giulia Zarpellon · Andreas Krause · Laurent Charlin · Chris Maddison -
2022 Poster: Bayesian Nonparametrics for Offline Skill Discovery »
Valentin Villecroze · Harry Braviner · Panteha Naderian · Chris Maddison · Gabriel Loaiza-Ganem -
2022 Spotlight: Bayesian Nonparametrics for Offline Skill Discovery »
Valentin Villecroze · Harry Braviner · Panteha Naderian · Chris Maddison · Gabriel Loaiza-Ganem -
2021 Poster: Improving Lossless Compression Rates via Monte Carlo Bits-Back Coding »
Yangjun Ruan · Karen Ullrich · Daniel Severo · James Townsend · Ashish Khisti · Arnaud Doucet · Alireza Makhzani · Chris Maddison -
2021 Oral: Improving Lossless Compression Rates via Monte Carlo Bits-Back Coding »
Yangjun Ruan · Karen Ullrich · Daniel Severo · James Townsend · Ashish Khisti · Arnaud Doucet · Alireza Makhzani · Chris Maddison -
2021 Poster: Oops I Took A Gradient: Scalable Sampling for Discrete Distributions »
Will Grathwohl · Kevin Swersky · Milad Hashemi · David Duvenaud · Chris Maddison -
2021 Oral: Oops I Took A Gradient: Scalable Sampling for Discrete Distributions »
Will Grathwohl · Kevin Swersky · Milad Hashemi · David Duvenaud · Chris Maddison -
2020 : Q&A: Chris Maddison »
Chris Maddison · Jessica Forde · Jesse Dodge -
2020 : Invited Talk: Chris Maddison »
Chris Maddison