Bounding the expected run-time of nonconvex optimization with early stopping

Thomas Flynn, Kwangmin Yu, Abid Malik, Nicholas D'Imperio, Shinjae Yoo

Abstract

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.

Introduction

In the practical application of machine learning, training rarely continues until the training loss reaches a global minimum. Instead, practitioners rely on early stopping—monitoring a validation set and terminating the process when performance plateaus or a specific criterion is met. Despite its ubiquity, standard optimization theory for nonconvex functions (such as deep neural networks) often ignores this heuristic. Most theoretical analyses assume a fixed number of iterations or utilize the "Randomized Stochastic Gradient" (RSG) method, where a final model is selected at random from the iteration history.

Presented at UAI 2020, this research provides a non-asymptotic theoretical bridge between the heuristic of early stopping and rigorous nonconvex optimization theory. The authors provide the first bounds on the expected run-time (measured in iterations and gradient calls) for several popular algorithms—SGD, Decentralized SGD (DSGD), and SVRG—when using a gradient-based early stopping rule.

The Early Stopping Framework

The paper analyzes a specific, mathematically grounded stopping rule: terminate optimization the first time the norm of the gradient of a validation function falls below a threshold $\epsilon$.

To analyze this rule, the authors address three primary challenges:

  1. Stochastic Stopping Times: Because the stopping time is a random variable, the authors employ the Optional Stopping Theorem and martingale theory to calculate its expected value.
  2. Algorithm Unification: They model various algorithms under a "Biased SGD" framework. For instance, in Decentralized SGD, the "bias" represents the lag in synchronization between local nodes. By introducing a geometric drift condition, they bound how this bias evolves, allowing for a unified proof strategy.
  3. The Training-Validation Gap: To quantify the difference between the training function ($f_T$) and the validation function ($f_V$), the authors use the $L_1$-Wasserstein distance between the data distributions. This allows them to prove that if the datasets are sufficiently similar, their gradients will behave similarly, ensuring the stopping rule on the validation set is meaningful for the training objective.

Key Theoretical Results

Expected Run-Time Bounds

The authors demonstrate that early stopping does not degrade the theoretical complexity of these algorithms compared to their fixed-iteration counterparts:

  • SGD: The expected number of iterations to find an $\epsilon$-stationary point is $O(1/\epsilon^2)$. This matches the standard rate for randomized methods but explicitly incorporates the gap between training and validation sets.
  • SVRG: For the Stochastic Variance Reduced Gradient algorithm, the expected number of Incremental First-order Oracle (IFO) calls is $O(n_T^{5/3}/\epsilon + n_T)$.
  • The Cost of Monitoring: For SGD, the expected number of gradient evaluations increases quadratically with the "epoch length" (the frequency of validation checks). This highlights a theoretical trade-off between the overhead of frequent validation and the total computational work.

Generalization Properties

A critical contribution of this work is linking the optimization stopping criterion to generalization. The authors provide a formula (Corollary 22) that relates the expected gradient norm on the true underlying distribution to the stopping threshold $\epsilon$ and the number of training samples $n_T$. This ensures that stopping based on a validation gradient is a mathematically sound proxy for reaching a stationary point of the true distribution.

Limitations and Future Directions

While this work provides a foundational step in theorizing early stopping, several challenges remain:

  • Step-size Constraints: The analysis for SGD requires a small step-size $\eta$ that scales inversely with the epoch length. It remains unclear if this is a fundamental requirement or a mathematical artifact of the proof.
  • High-Dimensional Data: The generalization bounds rely on Wasserstein concentration results, which are subject to the "curse of dimensionality." In very high-dimensional spaces, the number of samples required for these bounds to be tight may be extremely large.
  • Gradient vs. Loss Criteria: The study focuses on the gradient norm as a stopping criterion. In practice, many practitioners stop based on the loss value or accuracy. Extending this rigorous framework to loss-based stopping in nonconvex settings remains an open problem.

Conclusion

By treating early stopping as a formal stopping rule within a biased SGD framework, this paper provides a much-needed theoretical justification for a common practice. It confirms that for a variety of stochastic gradient methods, stopping based on a validation set provides strong guarantees on both the expected run-time and the quality of the resulting solution relative to the true data distribution.

Summary updated

Abstract

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.
BibTeX
@inproceedings{flynn2020bounding,
  author = {Thomas Flynn and Kwangmin Yu and Abid Malik and Nicholas D'Imperio and Shinjae Yoo},
  title = {{Bounding the expected run-time of nonconvex optimization with early stopping}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=tFPJVzQCrtM},
}
Figure