In this paper, we propose a novel stochastic gradient estimator---ProbAbilistic Gradient Estimator (PAGE) ---for nonconvex optimization. PAGE is easy to implement as it is designed via a small adjustment to vanilla SGD: in each iteration, PAGE uses the vanilla minibatch SGD update with probability p  or reuses the previous gradient with a small adjustment, at a much lower computational cost, with probability 1-p  . We give a simple formula for the optimal choice of p . We prove tight lower bounds for nonconvex}{\epsilon^2}) for nonconvex finite-sum } problems, which are of independent interest. Moreover, we prove matching upper bounds both in the}{\epsilon^2}) for nonconvex online problems, where b:= \min\{\sigma^2{\epsilon^2}, n\}. Then, we show that PAGE obtains the optimal convergence results O(n+\sqrt{n}{\epsilon^2}) (} finite-sum }{\epsilon^2}) (online) matching our lower bounds for both nonconvex finite-sum } and online regimes, which establish that PAGE is an optimal method . Besides, we  show that for nonconvex functions satisfying the Polyak-\L{}ojasiewicz (PL) condition, PAGE can automatically switch to a faster linear convergence rate {\epsilon})} . Finally, we conduct several deep learning experiments (e.g., LeNet, VGG, ResNet) on real datasets in PyTorch , and the results demonstrate that PAGE not only converges much faster than SGD in training but also achieves the higher test accuracy, validating our theoretical results and confirming the practical superiority of PAGE.
In this paper, we propose a novel stochastic gradient estimator -- ProbAbilistic Gradient Estimator (PAGE) -- for nonconvex optimization. PAGE is easy to implement as it is designed via a small adjustment to vanilla SGD: in each iteration, PAGE uses the vanilla minibatch SGD update with probability p _t or reuses the previous gradient with a small adjustment, at a much lower computational cost, with probability 1-p _t . We give a simple formula for the optimal choice of p _t. Moreover, we prove the first tight lower bound \Omega(n+\frac{\sqrt{n}{\epsilon^2}) for nonconvex finite-sum } problems, which also leads to a tight lower bound \Omega(b+\frac{\sqrt{b}{\epsilon^2}) for nonconvex online problems, where b:= \min\{\sigma^2{\epsilon^2}, n\}. Then, we show that PAGE obtains the optimal convergence results O(n+\sqrt{n}{\epsilon^2}) (} finite-sum ) and O(b+\frac{\sqrt{b}{\epsilon^2}) (online) matching our lower bounds for both nonconvex finite-sum } and online problems . Besides, we also show that for nonconvex functions satisfying the Polyak-\L{}ojasiewicz (PL) condition, PAGE can automatically switch to a faster linear convergence rate O(\cdot\log \frac{1{\epsilon})} . Finally, we conduct several deep learning experiments (e.g., LeNet, VGG, ResNet) on real datasets in PyTorch showing that PAGE not only converges much faster than SGD in training but also achieves the higher test accuracy, validating the optimal theoretical results and confirming the practical superiority of PAGE.
R
estimator---ProbAbilistic
estimator -- ProbAbilistic
R
---for
-- for
A
_t
A
_t
R
. We prove tight lower bounds for nonconvex
_t. Moreover, we prove the first tight lower bound \Omega(n+\frac{\sqrt{n
R
are of independent interest. Moreover, we prove matching upper bounds both in the
also leads to a tight lower bound \Omega(b+\frac{\sqrt{b
A
) and O(b+\frac{\sqrt{b
R
regimes, which establish that PAGE is an optimal method
problems
A
also
A
O(\cdot\log \frac{1
R
, and the results demonstrate
showing
R
our
the optimal