A nonasymptotic law of iterated logarithm for general M-estimators

Arnak S. Dalalyan, Nicolas Schreuder, Victor-Emmanuel Brunel

Abstract: M-estimators are ubiquitous in machine learning and statistical learning theory. They are used both for defining prediction strategies and for evaluating their precision. In this paper, we propose the first non-asymptotic ’any-time’ deviation bounds for general M-estimators, where ’any-time’ means that the bound holds with a prescribed probability for every sample size. These bounds are non-asymptotic versions of the law of iterated logarithm. They are established under general assumptions such as Lipschitz continuity of the loss function and (local) curvature of the population risk. These conditions are satisfied for most examples used in machine learning, including those ensuring robustness to outliers and to heavy tailed distributions. As an example of application, we consider the problem of best arm identification in a stochastic multi-arm bandit setting. We show that the established bound can be converted into a new algorithm, with provably optimal theoretical guarantees. Numerical experiments illustrating the validity of the algorithm are reported.

Introduction

In statistical learning, the Law of Large Numbers (LLN) and Central Limit Theorem (CLT) characterize the average behavior of estimators as data accumulates. Between these lies the Law of Iterated Logarithm (LIL), which provides a tighter envelope for estimator fluctuations. However, classical LIL results are typically asymptotic, describing behavior only as the sample size $n \to \infty$.

For "any-time" applications—such as online learning, adaptive clinical trials, or sequential testing—where stopping rules depend on the observed data, we require non-asymptotic bounds valid for every $n$. While such bounds have been established for the sample mean, they were previously missing for the broader class of M-estimators. This gap is significant because the sample mean is fragile; a single outlier can compromise its accuracy. This work provides robust "any-time" guarantees for estimators like the median and Huber estimator to handle real-world, heavy-tailed data.

Theoretical Framework: Non-asymptotic Any-time Bounds

We derive new theoretical upper bounds for the deviation of an M-estimator from its true population parameter. These bounds are valid across all possible sample sizes simultaneously, avoiding the over-conservatism of naive union bounds.

Ratio of the proposed non-asymptotic bound to the asymptotic LIL as a function of sample size.

The framework relies on three technical pillars:

  1. Convexity: The loss function must be convex.
  2. Local Curvature: The population risk must exhibit quadratic growth near its minimum.
  3. Sub-Gaussian Increments: Variations in the loss function must have well-behaved tails.

By satisfying these conditions, we show that robustness is essentially "free" from a theoretical standpoint: LIL-style guarantees for the median are structurally identical to those for the mean, without sacrificing any-time validity.

Application: Robust Best Arm Identification

To demonstrate the utility of these bounds, we consider the best arm identification problem in a stochastic multi-armed bandit setting. We introduce the Med-lilUCB algorithm, a median-based variant of the standard lilUCB. This algorithm is designed to remain effective even when reward distributions are contaminated or heavy-tailed.

Experimental Evaluation

We compared Med-lilUCB against the standard mean-based lilUCB using synthetic simulations under three reward processes: Gaussian (clean), Contaminated Gaussian (95% normal mixed with 5% heavy-tailed Cauchy outliers), and Student-t (heavy-tailed data with infinite variance).

Key Results: * Robustness: Med-lilUCB achieved 100% success in identifying the best arm across all scenarios, including heavy-tailed and contaminated data. * Failure of Standard Methods: The vanilla lilUCB performed well on Gaussian data but its accuracy plummeted to 44% under contamination and 60% with Student-t distributions. * Optimality: The algorithm's sample complexity is proven to be order-optimal, matching the best possible theoretical performance for reaching a specified confidence level.

Conclusion and Future Work

This paper establishes the first non-asymptotic LIL for general M-estimators, providing a rigorous foundation for robust sequential decision-making. Future research will focus on extending these results to multivariate settings with only local curvature and improving the scaling of these bounds in high-dimensional feature spaces where the number of parameters exceeds the sample size.

Summary updated

Abstract

M-estimators are ubiquitous in machine learning and statistical learning theory. They are used both for defining prediction strategies and for evaluating their precision. In this paper, we propose the first non-asymptotic ’any-time’ deviation bounds for general M-estimators, where ’any-time’ means that the bound holds with a prescribed probability for every sample size. These bounds are non-asymptotic versions of the law of iterated logarithm. They are established under general assumptions such as Lipschitz continuity of the loss function and (local) curvature of thepopulation risk. These conditions are satisfied for most examples used in machine learning, including those ensuring robustness to outliers and to heavy tailed distributions. As an example of application, we consider the problem of best arm identification in a stochastic multi-arm bandit setting. We show that the established bound can be converted into a new algorithm, with provably optimal theoretical guarantees. Numerical experiments illustrating the validity of the algorithm are reported.
BibTeX
@inproceedings{dalalyan2020nonasymptotic,
  author = {Arnak S. Dalalyan and Nicolas Schreuder and Victor-Emmanuel Brunel},
  title = {{A nonasymptotic law of iterated logarithm for general M-estimators}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=g4kJmcpayec},
}
Figure