Abstract
The problem of linear predictions has been extensively studied for the past century under pretty generalized frameworks. Recent advances in the robust statistics literature allow us to analyze robust versions of classical linear models through the prism of Median of Means (MoM). Combining these approaches in a piecemeal way might lead to ad-hoc procedures, and the restricted theoretical conclusions that underpin each individual contribution may no longer be valid. To meet these challenges coherently, in this study, we offer a unified robust framework that includes a broad variety of linear prediction problems on a Hilbert space, coupled with a generic class of loss functions. Notably, we do not require any assumptions on the distribution of the outlying data points ($\mathcal{O}$) nor the compactness of the support of the inlying ones ($\mathcal{I}$). Under mild conditions on the dual norm, we show that for misspecification level $\epsilon$, these estimators achieve an error rate of $O(\max\left\{|\mathcal{O}|^{1/2}n^{-1/2}, |\mathcal{I}|^{1/2}n^{-1} \right\}+\epsilon)$, matching the best-known rates in literature. This rate is slightly slower than the classical rates of $O(n^{-1/2})$, indicating that we need to pay a price in terms of error rates to obtain robust estimates. Additionally, we show that this rate can be improved to achieve so-called "fast rates" under additional assumptions.
Introduction
Classical machine learning relies heavily on Empirical Risk Minimization (ERM), which minimizes average error across training data. However, the average is notoriously sensitive to outliers. Corrupted labels, adversarial attacks, or extreme measurement errors can cause standard ERM models to skew heavily, ruining predictions for clean data. While robust alternatives exist, they are often algorithm-specific or lack finite-sample theoretical guarantees. This study proposes a unified theoretical framework to robustify a broad family of linear models while providing rigorous mathematical bounds on performance.
Methodology: Quantile of Means
The core technique generalizes the Median of Means (MoM) philosophy to a "Quantile of Means" approach. The dataset is randomly partitioned into $K$ equal-sized blocks. Instead of minimizing the overall average loss, the algorithm computes the empirical risk for each block and minimizes the $q$-th quantile of these block averages (typically $q=0.5$ for the median). Since outliers only corrupt a fraction of blocks, the quantile block remains representative of the true distribution. This quantile loss can be optimized using standard convex optimization methods like gradient descent or Newton's method.
Theoretical Guarantees
A key contribution of this work is the establishment of theoretical guarantees without assumptions on outlier distribution or support compactness of inliers.
- Zero Assumptions on Outliers: Guarantees hold even for unboundedly large or dependent outliers, provided inliers have finite variance.
- Robustness Trade-off: Robustness comes at a slight cost to learning rates. While classical models converge at $O(1/\sqrt{n})$, the MoM approach is slightly slower, scaling with the number of partitions $K$.
- Fast Rates: The authors prove that MoM estimators can achieve "fast rates" of $O(1/n)$ under conditions like strong convexity, bridging the gap between classical and robust learning theory.
- Graceful Degradation: The framework accounts for model misspecification $\epsilon$, where the error bound increases proportionally without the framework collapsing.
Key Results and Empirical Evaluation
The authors prove an error rate of $O(\max\{|O|^{1/2}n^{-1/2}, |I|^{1/2}n^{-1}\} + \epsilon)$, matching state-of-the-art results in robust statistics. Computationally, the per-iteration complexity of robust gradient descent is lower than standard ERM because gradients are computed only on the "median" block.
Simulation results for binary classification with heavy-tailed outliers validate these findings. As shown in the comparison above, while both models show decreasing error on a log scale as the number of inliers increases, the standard logistic regression model maintains errors several orders of magnitude higher than the MoM version. The MoM estimator effectively ignores outliers, maintaining a stable, low-error trajectory.
Conclusion and Future Directions
The framework requires that outliers grow slower than the total dataset size ($|O| = o(n)$). If outliers constitute a large constant fraction, the bounds become less meaningful. Additionally, performance is sensitive to the choice of quantile $q$. Future research directions include exploring "super-fast" rates, establishing min-max lower bounds, and extending the framework to high-dimensional sparse models like robust Lasso.
Summary updated