# Adaptive and Stratified Subsampling for High-Dimensional Robust Estimation

arXiv: https://arxiv.org/abs/2410.12367 · HTML: https://mlsanity.com/paper/2410.12367/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 20 references that are in the map.
- First posted on arXiv 16 Oct 2024.

## Builds on (most cited first, 9 of 9)

- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Confidence Intervals and Hypothesis Testing for High-Dimensional Regression](https://mlsanity.com/paper/1306.3171/) (2013)
- [Adaptive Huber Regression](https://mlsanity.com/paper/1706.06991/) (2017)
- [Robust regression with covariate filtering: Heavy tails and adversarial contamination](https://mlsanity.com/paper/2009.12976/) (2020)
- [Challenges of Big Data Analysis](https://mlsanity.com/paper/1308.1479/) (2013)
- [A Statistical Perspective on Algorithmic Leveraging](https://mlsanity.com/paper/1306.5362/) (2013)
- [High-Dimensional Inference: Confidence Intervals, p-Values and R-Software hdi](https://mlsanity.com/paper/1408.4026/) (2014)
- [Modern Subsampling Methods for Large-Scale Least Squares Regression](https://mlsanity.com/paper/2105.01552/) (2021)
- [Robust and sparse estimation methods for high dimensional linear and logistic regression](https://mlsanity.com/paper/1703.04951/) (2017)

## Abstract (arXiv)

We study robust high-dimensional sparse regression under finite-variance heavy-tailed noise, epsilon-contamination, and alpha-mixing dependence via two subsampling estimators: Adaptive Importance Sampling (AIS) and Stratified Sub-sampling (SS). Under sub-Gaussian design whose scopeis precisely delimited and finite-variance noise, a subsample of size m achieves the minimax-optimal rate. We close the theory-algorithm gap: Theorem 4.6 applies to AIS at termination conditional on stabilized weights (Proposition 4.1), and SS fits the median-of-means M-estimation framework of Lecue and Lerasle (Proposition 4.3). The de-biasing step is fully specified via the nodewise-Lasso precision estimator under a new sparse-precision assumption, yielding valid coordinate-wise CIs (Theorem 4.14). The alpha-mixing extension uses a calendar-time block protocol that guarantees temporal separation (Theorem 4.12). Empirically, AIS achieves 3.10 times lower error than uniform subsampling at 20% contamination, and 29.5% lower test MSE on Riboflavin (p=4,088 and n=71).