Fetching the paper…
Reading the bibliography…
The total complexity (measured as the total number of gradient computations) of a stochastic first-order optimization algorithm that finds a first-order stationary point of a finite-sum smooth nonconvex objective function $F(w)=\frac{1}{n} \sum_{i=1}^n f_i(w)$ has been proven to be at least $\Omega(\sqrt{n}/\epsilon)$ for $n \leq \mathcal{O}(\epsilon^{-2})$ where $\epsilon$ denotes the attained accuracy $\mathbb{E}[ \|\nabla F(\tilde{w})\|^2] \leq \epsilon$ for the outputted approximation $\tilde{w}$ (Fang et al., 2018).
A stochastic approximation method
Herbert Robbins and Sutton Monro · 1951
Earlier work this paper cites.
Introductory lectures on convex optimization : a basic course
Yurii Nesterov · 2004
Earlier work this paper cites.
LIBSVM: A library for support vector machines
Chih-Chung Chang and Chih-Jen Lin · 2011
Earlier work this paper cites.
Pegasos: Primal estimated sub-gradient solver for SVM
Shai Shalev-Shwartz, Yoram Singer, Nathan Srebro, and Andrew Cotter · 2011
Earlier work this paper cites.
A stochastic gradient method with an exponential convergence rate for finite training sets
Nicolas Le Roux, Mark Schmidt, and Francis Bach · 2012
Earlier work this paper cites.
Accelerating stochastic gradient descent using predictive variance reduction
Rie Johnson and Tong Zhang · 2013
Earlier work this paper cites.
Semi-stochastic gradient descent methods
Jakub Konečný and Peter Richtárik · 2013
Earlier work this paper cites.
Optimization with first-order surrogate functions
Julien Mairal · 2013
Earlier work this paper cites.
Stochastic dual coordinate ascent methods for regularized loss
Shai Shalev-Shwartz and Tong Zhang · 2013
Cited alongside, same era.
SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien · 2014
Cited alongside, same era.
Optimization methods for large-scale machine learning
Léon Bottou, Frank E Curtis, and Jorge Nocedal · 2016
Cited alongside, same era.
Stochastic variance reduction for nonconvex optimization
Sashank J. Reddi, Ahmed Hefny, Suvrit Sra, Barnabás Póczos, and Alexander J. Smola · 2016
Cited alongside, same era.
Minimizing finite sums with the stochastic average gradient
Mark Schmidt, Nicolas Le Roux, and Francis Bach · 2016
Cited alongside, same era.
Non-convex finite-sum optimization via SCSG methods
Lihua Lei, Cheng Ju, Jianbo Chen, and Michael I Jordan · 2017
Later among the works it cites.
SARAH: A novel method for machine learning problems using stochastic recursive gradient
Lam M. Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč · 2017
Later among the works it cites.
Stochastic recursive gradient algorithm for nonconvex optimization
Lam M. Nguyen, Jie Liu, Katya Scheinberg, and Martin Takác · 2017
Later among the works it cites.
Spider: Near-optimal non-convex optimization via stochastic path integrated differential estimator
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang · 2018
Later among the works it cites.
SGD and Hogwild! convergence without the bounded gradients assumption
Lam Nguyen, Phuong Ha Nguyen, Marten van Dijk, Peter Richtarik, Katya Scheinberg, and Martin Takac · 2018
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Zeyuan Allen-Zhu · 2017
Cited alongside, same era.
Natasha: Faster non-convex stochastic optimization via strongly non-convex parameter
Zeyuan Allen-Zhu · 2017
Cited alongside, same era.
Spiderboost: A class of faster variance-reduced algorithms for nonconvex optimization
Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh · 2018
Later among the works it cites.
Stochastic nested variance reduction for nonconvex optimization
Dongruo Zhou, Pan Xu, and Quanquan Gu · 2018
Later among the works it cites.