# SVRG literature survey

- Variance reduction:
Three different proof techniques.

SVRG: https://papers.nips.cc/paper/4937-accelerating-stochastic-gradient-descent-using-predictive-variance-reduction.pdf

SAGA:
http://www.iro.umontreal.ca/~slacoste/research/pubs/defazio-NIPS14-SAGA.pdf

SARAH:
https://arxiv.org/abs/1703.00102

See the VR review (still a draft. Do not circulate) I sent you on Slack.

Automatic step-size tuning for VR methods:
Barzilai-Borwen step with SVRG https://arxiv.org/abs/1605.04131

A Class of Stochastic Variance Reduced Methods with an Adaptive Stepsize (http://www.optimization-online.org/DB_HTML/2019/04/7170.html)
- proposes to set the stepsize in SVRG and SARAH by estimating the smoothness constant at each outer loop iteration.
- achieves linear convergence for SC smooth problems, but still requires the knowledge of $L$ to set the inner loop size $m$. Maybe explore the loopless variant?

Automatic step-sizes for interpolation
Stochastic line-search https://arxiv.org/abs/1905.09997
Stochastic Polyak step https://arxiv.org/abs/2002.10542

Using statistical estimators to detect reduction in variance
Using Statistics to Automate Stochastic Optimization(http://papers.nips.cc/paper/9150-using-statistics-to-automate-stochastic-optimization)
- Statistical test to reduce the stepsize in SGD with momentum. Not much theory, good practical results.

Statistical Adaptive Stochastic Gradient Methods(https://arxiv.org/abs/2002.10597)
- Follows the previous paper.
- again, (simpler) statistical test to reduce the step size that applies to classic SGD and SGD with momentum.
- Uses smooth stochastic line search to set initial learning rate
- good experimental results

Robust Learning Rate Selection for Stochastic Optimization via Splitting Diagnostic(https://arxiv.org/abs/1910.08597)
- proposes to reduce the step size in SGD by running two threads of SGD and doing a statistical test
- weird theory, seems to work well in practice.

Loopless SVRG and Katyusha with arbitrary sampling
https://arxiv.org/abs/1906.01481

Our initial failed attempt at incorporating line-search in SVRG: https://www.overleaf.com/9187184292fntqjnchkzsf

Boosting First-order Methods by Shifting Objective: New Schemes with Faster Worst Case Rates (https://arxiv.org/abs/2005.12061)

A Stochastic Line Search Method with Convergence Rate Analysis (https://arxiv.org/pdf/1807.07994.pdf)
- proposes Armijo line search to stochastic setting.
- gives bounds in probability for nonconvex, convex and SC
- hard to read

Stop Wasting My Gradients: Practical SVRG (https://arxiv.org/pdf/1511.01942.pdf)

Almost Tune-Free Variance Reduction(https://arxiv.org/pdf/1908.09345.pdf)
- new averaging schemes for SVRG and SARAH, with theoretical guarantees for SC case.
- shows that avereging schemes also give linear convergence for BB-SVRG and BB-SARAH. Still requires to know L and $\mu$ for inner loop size.
- proposes tune-free SVRG and SARAH. No theory on that. Seems to do well on experiments.

Towards closing the gap between the theory and
practice of SVRG (https://papers.nips.cc/paper/8354-towards-closing-the-gap-between-the-theory-and-practice-of-svrg.pdf)
- Convergence of SVRG under arbitrary sampling and with optimal batch size and step size.
- Linear convergence proof for $m = n$ and without averaging
- proposes loopless variant that starts with big step size when snapshot is updated, then slowly decreases it. Linear convergence proof. Still requires knowledge of $L$ to set initial step size.

A Simpler Approach to Accelerated Stochastic Optimization: Iterative
Averaging Meets Optimism (https://proceedings.icml.cc/static/paper_files/icml/2020/6589-Paper.pdf)
- provides accelerated rate (O($1/T^2$)) for variant of SVRG in the convex case. Still requires knowledge of $L$. No experiments.

A Modular Analysis of Adaptive (Non-)Convex Optimization: Optimism,Composite Objectives, Variance Reduction, and Variational Bounds (https://arxiv.org/pdf/1709.02726.pdf)
- General analysis of stochastic algorithms through the lens of online optimization.
- Gets as a byproduct, sublinear convergence of slight variant of SVRG in the convex case. Still requires knowledge of $L$. No experiments.

Adaptive Sampling Strategies for Stochastic Optimization (https://arxiv.org/pdf/1710.11258.pdf)
- Proposes inner product test to ensure the batch size is large enough to ensure descent direction for constant step size SGD.
- Obtains linear and sublinear convergence for SC and convex objectives, respectively.
- No bound on the batch size, which seems to grow fast in the experiments.
- Experiments do not compare to classic SGD.

Momentum-Based Variance Reduction in Non-Convex SGD (https://arxiv.org/pdf/1905.10018.pdf)
- proposes STORM, which looks like Adagrad with momentum.
- obtains $O(1/\sqrt{T} + \frac{\sigma^{1/3}}{T^{1/3}})$ rate for non-convex smooth , where $\sigma^2$ is the variance in the gradients
- Still requires knowledge of $L$ to set initial parameters

AdaGrad stepsizes: sharp convergence over nonconvex
landscapes, from any initialization (https://arxiv.org/pdf/1806.01811.pdf)
- shows $O(\frac{log(T)}{\sqrt{T}})$ rate for stochastic Adagrad in non convex setting
- $O(1/T)$ rate for deterministic Adagrad in non convex setting.

Linear Convergence of Adaptive Stochastic Gradient Descent (https://arxiv.org/pdf/1908.10525.pdf)
- convergence analysis of Adagrad-norm under SC or PL, assuming interpolation and weird probability assumption on bound on stochastic gradient norm.
- two-phased analysis with linear convergence in the second phase only.

Online to Offline Conversions, Universality and
Adaptive Minibatch Sizes (https://arxiv.org/pdf/1705.10499.pdf)
- Analysis of Adagrad and variants in the deterministic and stochastic settings.
- Gives $O(\frac{log^2 T}{T})$ rate for stochastic Adagrad on SC smooth objectives, requiring only the knowledge of the SC constant.

https://arxiv.org/pdf/1802.04715.pdf
https://arxiv.org/pdf/1809.02864.pdf
https://arxiv.org/pdf/1905.10018.pdf
https://arxiv.org/pdf/1903.00974.pdf