Bootstrapping Max Statistics in High Dimensions: Near-Parametric Rates Under Weak Variance Decay and Application to Functional Data Analysis

Miles E. Lopes, Zhenhua Lin, Hans-Georg MuellerarXiv 2018 · arXiv

Abstract

In high-dimensional statistics, the bootstrap is a vital tool for approximating the distributions of max statistics, such as the coordinate-wise maximum of a sample average. While existing theory suggests a slow convergence rate of $n^{-1/6}$, practitioners often observe much better performance. This paper resolves this discrepancy by demonstrating that if the coordinate-wise variances of the observations exhibit even weak decay, the bootstrap approximation achieves a near-parametric rate of $n^{-1/2}$. Crucially, this rate is dimension-free, holding regardless of the number of features $p$. We apply these findings to functional and multinomial data, showing significant improvements in statistical power and reliability.

Introduction

Modern statistical inference frequently involves "high-dimensional" data where the number of features $p$ significantly exceeds the number of observations $n$. A central task in this regime is estimating the distribution of a max statistic—the maximum value across all coordinates of a sample average. These statistics are essential for constructing simultaneous confidence intervals and conducting multiple hypothesis testing.

Historically, the theoretical understanding of bootstrapping these statistics was pessimistic. Established convergence rates (in Kolmogorov distance) typically scaled like $n^{-1/6}$, suggesting that very large samples were required for accurate inference. However, this did not align with the robust performance seen in practice. This paper identifies variance decay as the structural property that bridges this gap, explaining why the bootstrap is more efficient than previously theorized.

The Problem: The $n^{-1/6}$ Bottleneck

Standard bootstrap methods for high-dimensional max statistics are often analyzed under the assumption that all coordinates are equally important. In such a "worst-case" scenario, the complexity of the distribution grows with the dimension $p$, leading to the slow $n^{-1/6}$ rate. This rate is a byproduct of the need to account for all $p$ coordinates simultaneously, which becomes increasingly difficult as $p$ grows relative to $n$.

Methods: Partial Standardization and the $M$ Statistic

The authors introduce a novel framework to exploit the natural variance structure of data. A common practice in statistics is to standardize variables to have unit variance. However, the authors argue that full standardization is counterproductive because it destroys the variance decay that simplifies the problem.

The $M$ Statistic

To balance the benefits of standardization with the advantages of variance decay, the authors propose a new statistic, $M$, defined using a fractional power of the variances $(\sigma_j^{\tau_n})$. This partial standardization allows the method to "blend" the two approaches. By choosing an appropriate $\tau_n$, the statistic maintains the ordering of variances while ensuring that no single coordinate dominates the calculation too early.

Multiplier Bootstrap

The researchers apply a multiplier bootstrap procedure to this $M$ statistic. The core theoretical innovation lies in proving that when variances decay, the "maximizing index"—the specific coordinate that produces the maximum value—is likely to reside within a small, manageable subset of features. This "localization" effect effectively transforms a high-dimensional problem into a low-dimensional one, allowing the application of powerful tools like Bentkus’ multivariate Berry-Esseen theorem to achieve faster convergence rates.

Key Insights: Dimension-Free Convergence

The most striking result of this research is the emergence of dimension-free rates. The authors prove that the Kolmogorov distance between the true distribution and the bootstrap distribution is bounded by $cn^{-1/2+\delta}$ with high probability. This rate is independent of $p$, meaning the bootstrap remains highly accurate whether the data has 1,000 or 1,000,000 features, provided the variances decay.

Furthermore, the decay required to trigger this improvement is remarkably weak. The authors suggest a "phase transition" at $\alpha = 0$. If all variances are equal ($\alpha = 0$), the slow $n^{-1/6}$ rate applies. However, as soon as any decay is present ($\alpha > 0$), the rate jumps toward the near-parametric $n^{-1/2}$.

Applications to Functional Data

The theoretical findings were validated using synthetic functional data. By simulating i.i.d. samples from a Gaussian process with a Matérn covariance function, the authors generated Fourier coefficients that naturally exhibit variance decay.

In these simulations, the partially standardized bootstrap method outperformed existing approaches, such as the Choi and Reimherr (2018) method. It demonstrated significantly higher statistical power in detecting differences in the shape or scale of mean functions. Moreover, the method remained "honest," respecting nominal Type I error rates (e.g., achieving an actual error of approximately 5.7% for a 5% significance level at $n=200$).

Conclusion and Future Directions

This work provides a theoretical foundation for the empirical success of the bootstrap in high dimensions. By recognizing that variance decay localizes the max statistic, the authors show that the "effective dimension" of many problems is much smaller than the nominal dimension $p$.

While the current study focuses on max statistics, future research may explore whether similar variance decay benefits apply to other high-dimensional metrics, such as $L_p$ norms or quadratic forms. Additionally, while the authors provide heuristics for selecting the partial standardization parameter $\tau_n$, more formal data-driven selection rules remain an area for further development.

Summary updated

Abstract

In recent years, bootstrap methods have drawn attention for their ability to approximate the laws of max statistics in high-dimensional problems. A leading example of such a statistic is the coordinate-wise maximum of a sample average of $n$ random vectors in $\mathbb{R}^p$. Existing results for this statistic show that the bootstrap can work when $n\ll p$, and rates of approximation (in Kolmogorov distance) have been obtained with only logarithmic dependence in $p$. Nevertheless, one of the challenging aspects of this setting is that established rates tend to scale like $n^{-1/6}$ as a function of $n$. The main purpose of this paper is to demonstrate that improvement in rate is possible when extra model structure is available. Specifically, we show that if the coordinate-wise variances of the observations exhibit decay, then a nearly $n^{-1/2}$ rate can be achieved, independent of $p$. Furthermore, a surprising aspect of this dimension-free rate is that it holds even when the decay is very weak. Lastly, we provide examples showing how these ideas can be applied to inference problems dealing with functional and multinomial data.
BibTeX
@misc{lopes2018bootstrapping,
  author = {Miles E. Lopes and Zhenhua Lin and Hans-Georg Mueller},
  title = {{Bootstrapping Max Statistics in High Dimensions: Near-Parametric Rates Under Weak Variance Decay and Application to Functional Data Analysis}},
  year = {2018},
  eprint = {1807.04429},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1807.04429},
}
Figure