# Markov subsampling based Huber Criterion

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 47 references that are in the map.
- First posted on arXiv 12 Dec 2021.

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

- [Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates](https://mlsanity.com/paper/1305.5029/) (2013)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [Adaptive Huber Regression](https://mlsanity.com/paper/1706.06991/) (2017)
- [An Alternative Probabilistic Interpretation of the Huber Loss](https://mlsanity.com/paper/1911.02088/) (2019)
- [On Fast Leverage Score Sampling and Optimal Learning](https://mlsanity.com/paper/1810.13258/) (2018)
- [A Statistical Perspective on Algorithmic Leveraging](https://mlsanity.com/paper/1306.5362/) (2013)
- [Statistical consistency and asymptotic normality for high-dimensional robust M-estimators](https://mlsanity.com/paper/1501.00312/) (2015)
- [Gradient Sampling Methods for Nonsmooth Optimization](https://mlsanity.com/paper/1804.11003/) (2018)
- [Optimal Distributed Subsampling for Maximum Quasi-Likelihood Estimators with Massive Data](https://mlsanity.com/paper/2005.10435/) (2020)
- [Fast and Robust Least Squares Estimation in Corrupted Linear Models](https://mlsanity.com/paper/1406.3175/) (2014)
- [Gradient-based Sampling: An Adaptive Importance Sampling for Least-squares](https://mlsanity.com/paper/1803.00841/) (2018)
- [More Efficient Estimation for Logistic Regression with Optimal Subsample](https://mlsanity.com/paper/1802.02698/) (2018)
- [Adaptive Huber Regression on Markov-dependent Data](https://mlsanity.com/paper/1904.09027/) (2019)

## Abstract (arXiv)

Subsampling is an important technique to tackle the computational challenges brought by big data. Many subsampling procedures fall within the framework of importance sampling, which assigns high sampling probabilities to the samples appearing to have big impacts. When the noise level is high, those sampling procedures tend to pick many outliers and thus often do not perform satisfactorily in practice. To tackle this issue, we design a new Markov subsampling strategy based on Huber criterion (HMS) to construct an informative subset from the noisy full data; the constructed subset then serves as a refined working data for efficient processing. HMS is built upon a Metropolis-Hasting procedure, where the inclusion probability of each sampling unit is determined using the Huber criterion to prevent over scoring the outliers. Under mild conditions, we show that the estimator based on the subsamples selected by HMS is statistically consistent with a sub-Gaussian deviation bound. The promising performance of HMS is demonstrated by extensive studies on large scale simulations and real data examples.