RECORD
Reducing the variance in online optimization by transporting past gradients
Machine Learning · Submitted 8 Jun 2019
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We show experimentally that it achieves state-of-the-art results on a wide range of architectures and benchmarks.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Most stochastic optimization methods use gradients once before discarding them. While variance reduction methods have shown that reusing past gradients can be beneficial when there is a finite number of datapoints, they do not easily extend to the online setting. One issue is the staleness due to using past gradients. We propose to correct this staleness using the idea of implicit gradient transport (IGT) which transforms gradients computed at previous iterates into gradients evaluated at the current iterate without using the Hessian explicitly. In addition to reducing the variance and bias of our updates over time, IGT can be used as a drop-in replacement for the gradient estimate in a number of well-understood methods such as heavy ball or Adam. We show experimentally that it achieves state-of-the-art results on a wide range of architectures and benchmarks. Additionally, the IGT gradient estimator yields the optimal asymptotic convergence rate for online stochastic optimization in the restricted setting where the Hessians of all component functions are equal.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Most stochastic optimization methods use gradients once before discarding them. | background 1.00 | 0.05 | 0.02 | asserted 1.00 |
| s1 | While variance reduction methods have shown that reusing past gradients can be beneficial when there is a finite number of datapoints, they do not easily extend to the online setting. | gap 0.78 | 0.05 | 0.04 | asserted 0.99 |
| s2 | One issue is the staleness due to using past gradients. | background 0.71 | 0.07 | 0.02 | asserted 0.98 |
| s3 | We propose to correct this staleness using the idea of implicit gradient transport (IGT) which transforms gradients computed at previous iterates into gradients evaluated at the current iterate without using the Hessian explicitly. | method 0.62 | 0.87 | 0.22 | asserted 0.97 |
| s4 | In addition to reducing the variance and bias of our updates over time, IGT can be used as a drop-in replacement for the gradient estimate in a number of well-understood methods such as heavy ball or Adam. | contribution 0.59 | 0.75 | 0.24 | asserted 0.69 |
| s5 | We show experimentally that it achieves state-of-the-art results on a wide range of architectures and benchmarks. | result 1.00 | 0.95 | 0.34 | asserted 1.00 |
| s6 | Additionally, the IGT gradient estimator yields the optimal asymptotic convergence rate for online stochastic optimization in the restricted setting where the Hessians of all component functions are equal. | result 0.98 | 0.88 | 0.16 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Most stochastic optimization methods use gradients once before discarding them. While variance reduction methods have shown that reusing past gradients can be beneficial when there is a finite number of datapoints, they do not easily extend to the online setting. One issue is the staleness due to using past gradients. We propose to correct this staleness using the idea of implicit gradient transport (IGT) which transforms gradients computed at previous iterates into gradients evaluated at the current iterate without using the Hessian explicitly. In addition to reducing the variance and bias of our updates over time, IGT can be used as a drop-in replacement for the gradient estimate in a number of well-understood methods such as heavy ball or Adam. We show experimentally that it achieves state-of-the-art results on a wide range of architectures and benchmarks. Additionally, the IGT gradient estimator yields the optimal asymptotic convergence rate for online stochastic optimization in the restricted setting where the Hessians of all component functions are equal.
Human review
How the literature uses it
4 arXiv papers cite this in 7 sentences
Papers citing it · 5 sentences without a confident label
Builds on it 1 paper
-
This significantly extends the prior results of [ref] , which hold only on convex quadratic objectives with constant Hessian, and helps realize the theoretical potential of the implicit gradient transport idea.
Momentum Improves Normalized SGD · Faster Convergence with Second-Order Smoothness · 0.99
Uses its method or tool 1 paper
-
Specifically, we use implicit gradient transport [ref] , as implemented by [ref] in their NIGT algorithm.
High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails · Second-Order Smooth Losses · 1.00
What it cites · 8 sentences without a confident label
Uses the method or tool of 1 paper
-
To this end, we shall use anytime tail averaging [ref] , named in reference to the tail averaging technique used in optimization [ref] .
Anytime Tail Averaging · IGT and Anytime Tail Averaging · 0.98
Cites as background 2 papers
-
Another line of work reduces variance by averaging iterates [ref] .
A simpler approach to obtaining an O(1/t) convergence rate for the projected stochastic subgradient method · Introduction · 0.93
-
Another line of work reduces variance by averaging iterates [ref] .
Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains · Introduction · 0.93
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.