Before revision:  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.
After revision:  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 _t. Moreover, we prove the first tight lower bound \Omega(n+\frac{\sqrt{n}{\epsilon^2}) for nonconvex finite-sum } problems, which are of independent interest.