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.
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:
- Gaussian Rewards: Standard "clean" data.
- Huber Contaminated Rewards: 95% Gaussian data mixed with 5% Cauchy noise (extreme outliers).
- 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.
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