Asymptotics of the Bootstrap via Stability with Applications to Inference with Model Selection

Morgane Austern, Vasilis SyrgkanisNeurIPS 2021 · OpenReview

Executive Summary

The empirical bootstrap is a ubiquitous tool for estimating uncertainty, but its theoretical guarantees often fail in modern machine learning pipelines involving model selection and ensemble learning. This paper introduces a new theoretical framework that shifts the focus to "stability"—how much an estimator changes when a single data point is modified—to extend bootstrap guarantees to these complex statistics.

Introduction

The empirical bootstrap is often considered the "Swiss Army knife" of statistics. To find the confidence interval of an estimator, practitioners resample their data with replacement many times to observe the estimator's variance. However, while widely used in machine learning, its theoretical guarantees are surprisingly thin for modern applications.

Classical proofs typically require the estimator to be "smooth" (Hadamard differentiable) or asymptotically normal. Modern ML pipelines, however, frequently involve non-linear steps like model selection, hyperparameter tuning, or "stacking" multiple models. These processes can be non-Gaussian and "jagged," leaving researchers unsure if their bootstrap-based confidence intervals are trustworthy. This paper bridges that gap by providing general conditions for bootstrap consistency that do not rely on Gaussianity.

Methodology: A Stability-Based Approach

Moving away from classical differentiation approaches, the authors employ a stability-based framework derived from a generalized Lindenberg method (a technique originally used to prove Central Limit Theorems). Key technical components include:

  • $C^3$-Approximability: The statistic is assumed to be approximable by a three-times differentiable function, with specific bounds on its first-, second-, and third-order derivatives. This acts as a "stability" requirement, ensuring the estimator does not react too violently to the change of a single observation.
  • Metric Consistency: A specific probability metric ($d_{\mathcal{F}}$) is used to measure the distance between the true distribution of the estimator and the distribution generated by the bootstrap.
  • Centered Bootstrap: The authors identify that when the mean of the observations is unknown, the standard bootstrap can fail. They propose a "centered" version of the bootstrap to restore consistency.

Key Insights

  • Stability Yields Consistency: The core insight is that if an estimator is stable (i.e., its derivatives with respect to individual data points are well-behaved), the bootstrap will work, even if the final distribution is not Gaussian.
  • The "Centering" Problem: The discovery that the standard bootstrap is not always consistent when the underlying data's mean is unknown is critical for practitioners who might be overconfident in out-of-the-box bootstrap intervals.
  • Broad Applicability: Unlike previous breakthroughs tailored to specific statistics (like the Lasso), this framework is highly general. If an ML algorithm can be shown to be "stable" in a $C^3$ sense, these bootstrap guarantees apply.

Results and Applications

As a theoretical paper, the study focuses on mathematical proofs rather than empirical benchmarking on specific datasets. The authors provide rigorous proofs for two classes of applications: two-sample kernel tests after a kernel selection process, and smooth stacked ensemble estimators.

  • Convergence Rates: The paper provides explicit rates at which the bootstrap distribution converges to the true distribution (e.g., $O(n^{-1/3})$ or $O(n^{-1/2})$, depending on the order of the derivatives).
  • Guaranteed Coverage: The authors prove that for stable estimators, the bootstrap can be used to build confidence intervals with guaranteed asymptotic coverage.
  • Validation of ML Pipelines: The theory successfully proves that the bootstrap is valid for complex tasks, such as selecting the best kernel for a hypothesis test and then running that test on the same data, or estimating the risk of a stacked ensemble of models.

Limitations and Future Directions

  • Verifying Smoothness: The primary hurdle for practitioners is verifying the $C^3$-approximability condition. For highly complex or "black-box" algorithms, calculating or bounding these third-order derivatives can be mathematically daunting.
  • Non-Smooth Selection: The theory relies on smooth versions of estimators. If a model selection process is highly discrete or "hard" (e.g., a hard threshold jumping from 0 to 1), the current stability conditions might not be met.
  • Future Work: The authors suggest extending these techniques to more complex data dependencies, such as time-series or networked data, where the independent and identically distributed (i.i.d.) assumption does not hold.

Summary updated

Abstract

One of the most commonly used methods for forming confidence intervals is the empirical bootstrap, which is especially expedient when the limiting distribution of the estimator is unknown. However, despite its ubiquitous role in machine learning, its theoretical properties are still not well understood. Recent developments in probability have provided new tools to study the bootstrap method. However, they have been applied only to specific applications and contexts, and it is unclear whether these techniques are applicable to the understanding of the consistency of the bootstrap in machine learning pipelines. In this paper, we derive general stability conditions under which the empirical bootstrap estimator is consistent and quantify the speed of convergence. Moreover, we propose alternative ways to use the bootstrap method to build confidence intervals with coverage guarantees. Finally, we illustrate the generality and tightness of our results by examples of interest for machine learning including for two-sample kernel tests after kernel selection and the empirical risk of stacked estimators.
BibTeX
@inproceedings{austern2021asymptotics,
  author = {Morgane Austern and Vasilis Syrgkanis},
  title = {{Asymptotics of the Bootstrap via Stability with Applications to Inference with Model Selection}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=oaIa8kTLjmP},
}
Figure