Timezone: »

 
Poster
Stochastic Reweighted Gradient Descent
Ayoub El Hanchi · David Stephens · Chris Maddison

Tue Jul 19 03:30 PM -- 05:30 PM (PDT) @ Hall E #633
in Poster Session 1 »

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.

Keywords: Optimization · OPT: Stochastic

Author Information

Ayoub El Hanchi (University of Toronto)
David Stephens (McGill University)
David Stephens

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)

More from the Same Authors