This work examines the convergence of stochastic gradient algorithms that use early stopping based on a validation function, wherein optimization ends when the magnitude of a validation function gradient drops below a threshold. We derive conditions that guarantee this stopping rule is well-defined and analyze the expected number of iterations and gradient evaluations needed to meet this criteria. The guarantee accounts for the distance between the training and validation sets, measured with the Wasserstein distance. We develop the approach for stochastic gradient descent (SGD), allowing for biased update directions subject to a Lyapunov condition. We apply the approach to obtain new bounds on the expected running time of several algorithms, including Decentralized SGD (DSGD), a variant of decentralized SGD, known as Stacked SGD, and the stochastic variance reduced gradient (SVRG) algorithm. Finally, we consider the generalization properties of the iterate returned by early stopping.
The paper studies the problem of the number of first-order-oracle calls for the SGD type of algorithms to find a stationary point of the objective function. The main results in the paper are built upon a new, general framework to analyze the SGD type of algorithms.
The main framework can be summarized as follows: At each iteration, the algorithm receives h_t, a (potentially biased) estimator of the gradient at a given point x_t, and performs a simple update x_{t + 1} = x_t - \eta * h_t. The framework says that as long as the norm (V_t) of \Delta_t = h_t - v_t (where v_t is an unbiased estimator of the true gradient with bounded variance) satisfies a particular Lyapunov-type inequality, then the algorithm can find an epsilon-stationary point as long as epsilon is not too small. 
The analysis of the framework is quite standard, one only needs to write the decrement in function value at each iteration into the following three terms: the norm of the true gradient of the function, \delta_t: the difference between v_t and the true gradient (so E[\delta_t] = 0) and \Delta_t: the difference between the received gradient h_t and v_t.
The authors showed some application of this framework in Stacked SGD and decentralized SGD. The main intuitions of these applications are (1). \Delta_t comes from the synchronization difference of the nodes when computing the gradient. (2). The shrinking of V_t is due to the  (better) synchronization at each iteration. (3). The increment of V_t is due to the gradient update. 
Overall, I find the general framework quite interesting and potentially useful for future research and could be used as a guide for choosing the proper algorithm in distributed computation.  The bounds in this paper are also in principle tight. The only question I have about this result is the dependency of m (the number of iterations between each evaluation of the gradient norm of the underlying function). (1). How can this (the evaluation of the gradient norm of the underlying function)) be done in a decentralized environment? What is the computation overhead?  (For example in DSGD, how can we compute \bar{x}_t?) (2). It seems that the computation cost (number of IFO) scales quadratically with respect to m. What is the intuition for this scaling? It appears to me that the scaling should be linear or better (the worst case is that within the "m" iterations, only one iteration has gradient >= epsilon). The authors should elaborate more on this point.