Bounding the expected run-time of nonconvex optimization with early
  stopping
  This work examines the convergence of stochastic gradient-based optimization
algorithms that use early stopping based on a validation function. The form of
early stopping we consider is that optimization terminates when the norm of the
gradient of a validation function falls below a threshold. We derive conditions
that guarantee this stopping rule is well-defined, and provide bounds on the
expected number of iterations and gradient evaluations needed to meet this
criterion. The guarantee accounts for the distance between the training and
validation sets, measured with the Wasserstein distance. We develop the
approach in the general setting of a first-order optimization algorithm, with
possibly biased update directions subject to a geometric drift condition. We
then derive bounds on the expected running time for early stopping variants of
several algorithms, including stochastic gradient descent (SGD), decentralized
SGD (DSGD), and the stochastic variance reduced gradient (SVRG) algorithm.
Finally, we consider the generalization properties of the iterate returned by
early stopping.
