A nonasymptotic law of iterated logarithm for robust online estimators

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

Abstract

This paper introduces the first non-asymptotic law of iterated logarithm (LIL) for general M-estimators, providing "any-time" deviation bounds that hold for all sample sizes simultaneously. By leveraging the curvature of population risk and sub-Gaussian concentration, the authors develop robust estimators capable of handling heavy-tailed noise and outliers. The theoretical framework is applied to multi-arm bandit problems, where a novel "Median lil'UCB" algorithm demonstrates superior performance and 100% success rates in contaminated environments where traditional mean-based methods fail.

Introduction

In statistics, the Law of Iterated Logarithm (LIL) describes the fluctuations of a sample average over time. While the Central Limit Theorem characterizes the distribution at a specific large $n$, the LIL provides a bound that holds for all large $n$ simultaneously. However, classical LIL results suffer from two primary limitations: they are asymptotic, failing to describe behavior during the initial "burn-in" period, and they are typically restricted to sample means, which are highly sensitive to outliers.

In fields like online learning and multi-arm bandits, "any-time" guarantees are essential—bounds must be valid from the very first sample and remain so as data accumulates. Standard fixed-time bounds (like Hoeffding’s inequality) can be adapted for any-time use via naive union bounds, but this approach results in mathematically loose and practically inefficient guarantees.

Methods and Theoretical Framework

The authors bridge this gap by developing a non-asymptotic LIL for M-estimators—a broad class of estimators defined as minimizers of a loss function (e.g., the median minimizes absolute loss). The derivation relies on the local curvature of the population risk and the Lipschitz continuity of the loss function.

Key technical contributions include:

  • Uniform Concentration: Utilizing sub-Gaussian concentration inequalities to create tight bounds that do not decay prematurely as $n$ grows.
  • Multivariate Extension: Extending the theory to $d$-dimensional penalized M-estimators, such as Lasso or Ridge regression.
  • Tightness: The proposed LIL bound is significantly tighter than the common practice of applying a union bound over standard concentration inequalities, especially as the sample size increases.
Comparison of the proposed LIL bound versus a naive union bound (UB) across sample sizes.

Robust Multi-Arm Bandits

The theoretical framework is applied to the Best Arm Identification (BAI) task in multi-arm bandits. The authors propose the Median lil'UCB algorithm, which replaces the standard sample mean with a robust median estimator and utilizes the new LIL bound to define the "confidence width" for the Upper Confidence Bound (UCB) logic.

To evaluate robustness, the algorithm was tested against three reward distributions:

  1. Gaussian Rewards: Standard "clean" data.
  2. Huber Contaminated Rewards: 95% Gaussian data mixed with 5% Cauchy noise (extreme outliers).
  3. Student’s t-distribution ($df=2$): A heavy-tailed distribution with infinite variance.

Key Results

Empirical results demonstrate that the Median lil'UCB algorithm achieved a 100% success rate across all scenarios. In contrast, the standard mean-based lil'UCB dropped to a 64.5% success rate when faced with Huber contamination.

Sample complexity (number of pulls) for best arm identification across different reward distributions.

As shown in the figure above, while the median-based approach requires slightly more samples in clean Gaussian data, its sample complexity remains remarkably stable in the presence of outliers. Conversely, the standard mean-based approach (lil'UCB Huber) becomes highly unreliable and inefficient when noise is introduced.

Conclusion and Future Work

This work establishes that robustness in online estimation does not necessarily come at a high theoretical cost. By using well-behaved loss functions, one can achieve LIL-style guarantees even for data that is not sub-Gaussian. Future research directions include relaxing curvature assumptions to local regions near the optimal point, applying these bounds to sequential estimators like Online Gradient Descent, and exploring high-dimensional settings where the number of features $d$ exceeds the sample size $n$.

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 nonasymptotic 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 parametric 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{brunel2020nonasymptotic,
  author = {Victor-Emmanuel Brunel and Arnak S. Dalalyan and Nicolas Schreuder},
  title = {{A nonasymptotic law of iterated logarithm for robust online estimators}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=g4kJmcpayec},
}
Figure