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. Moreover, we prove matching upper bounds both in the}{\epsilon^2}) for nonconvex online problems, where b:= \min\{\sigma^2{\epsilon^2}, n\}.
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 . We prove tight lower bounds for nonconvex}{\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\}.