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 machine learning practice, early stopping is a ubiquitous technique used to prevent overfitting and reduce computational costs. Despite its widespread adoption, a significant gap exists between empirical practice and theoretical understanding. Most optimization theory assumes a fixed number of iterations or the selection of a random iterate as the final output. This paper bridges this gap by providing a non-asymptotic analysis of the expected running time for nonconvex optimization algorithms employing a validation-based stopping criterion.

The core challenge addressed is the discrepancy between the training objective and the validation objective. If the validation set is not representative of the training set, the algorithm might terminate prematurely or fail to terminate at all. This research quantifies how the similarity between these datasets and the frequency of validation checks (epoch length) influence the expected runtime and the quality of the resulting solution.

Methods

The authors analyze three prominent algorithms: Stochastic Gradient Descent (SGD), Decentralized SGD (DSGD), and Stochastic Variance Reduced Gradient (SVRG). The analysis relies on three key technical pillars:

  1. Wasserstein Distance: The 1-Wasserstein distance ($d_1$) is employed to measure the distributional shift between training and validation data. This metric allows for bounding the deviation of the validation gradient from the training gradient.
  2. Geometric Drift Condition: To handle biased algorithms like DSGD—where individual nodes possess different local data—the authors model the error as a "geometric drift." This captures the dynamics of local iterates as they diverge from and contract toward the global average.
  3. Stopping Time Analysis: The stopping time $\tau(\epsilon)$ is treated as a random variable. Using tools from stochastic process theory, such as the Optional Stopping Theorem, the authors derive bounds on its expected value.

The following algorithm block demonstrates how these principles are applied to the decentralized setting, showing the integration of the validation-based stopping rule within the training loop.

Algorithm 1: Decentralized SGD with Early Stopping.

Key Insights

The theoretical framework yields several significant insights into the behavior of early stopping:

  • Computational Efficiency of SVRG: In SVRG, a full gradient is computed at the start of each epoch. Utilizing this gradient for the stopping criterion introduces no additional computational overhead, making early stopping "free" in this context.
  • Impact of Epoch Length: For standard SGD, the expected number of gradient evaluations scales quadratically with the epoch length $m$. This reveals a critical trade-off: infrequent validation checks can significantly inflate the total computational work.
  • Decentralized Bias Management: By treating DSGD as a biased version of SGD, the authors show that the communication network's mixing rate acts as a contraction factor. This ensures that the bias remains bounded, allowing for a runtime analysis comparable to the centralized case.
  • Generalization and Concentration: Combining optimization bounds with Wasserstein concentration inequalities, the study demonstrates how the training set size ($n_T$) affects the final solution's quality relative to the underlying data distribution.

Key Results

The paper establishes "Expected Run-Time" bounds for a target accuracy $\epsilon$:

  • SGD: The expected number of iterations is $O(m^2 / \epsilon^2)$.
  • SVRG: The expected number of Incremental First-order Oracle (IFO) calls is $O(n_T^{5/3}/\epsilon + n_T)$.
  • Stationarity Guarantee: Upon termination, the training gradient norm is bounded by $\sqrt{\epsilon} + G d_1(\mu_V, \mu_T)$. This result explicitly links the solution quality to the representativeness of the validation set ($d_1$).

Conclusion and Future Work

While this work provides a rigorous foundation for early stopping, several avenues for future research remain. The current analysis for SGD requires the step-size to scale inversely with the epoch length $m$; relaxing this constraint is an open question. Additionally, the generalization bounds are subject to the "curse of dimensionality" inherent in Wasserstein distances, suggesting that bounding the gap in high-dimensional spaces remains challenging. Finally, reducing the $O(m^2)$ complexity for SGD to $O(m)$ would further refine our understanding of optimal validation frequencies.

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