# Quantile-based Loss Filtering for Outlier-Robust Stochastic Gradient Descent

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 43 references that are in the map.
- First posted on arXiv 11 Sep 2026.

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

- [Co-teaching: Robust Training of Deep Neural Networks with Extremely Noisy Labels](https://mlsanity.com/paper/1804.06872/) (2018)
- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [DivideMix: Learning with Noisy Labels as Semi-supervised Learning](https://mlsanity.com/paper/2002.07394/) (2020)
- [MentorNet: Learning Data-Driven Curriculum for Very Deep Neural Networks on Corrupted Labels](https://mlsanity.com/paper/1712.05055/) (2017)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018)
- [Learning from History for Byzantine Robust Optimization](https://mlsanity.com/paper/2012.10333/) (2020)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping](https://mlsanity.com/paper/2005.10785/) (2020)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Byzantine Stochastic Gradient Descent](https://mlsanity.com/paper/1803.08917/) (2018)
- [Robust Estimation via Robust Gradient Estimation](https://mlsanity.com/paper/1802.06485/) (2018)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [Zeno++: Robust Fully Asynchronous SGD](https://mlsanity.com/paper/1903.07020/) (2019)
- [Robust Regression via Hard Thresholding](https://mlsanity.com/paper/1506.02428/) (2015)
- [Choosing the Sample with Lowest Loss makes SGD Robust](https://mlsanity.com/paper/2001.03316/) (2020)
- [Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression](https://mlsanity.com/paper/1903.08192/) (2019)
- [Online Robust Regression via SGD on the l1 loss](https://mlsanity.com/paper/2007.00399/) (2020)
- [Stochastic gradient descent for streaming linear and rectified linear systems with adversarial corruptions](https://mlsanity.com/paper/2403.01204/) (2024)
- [Quantile Randomized Kaczmarz Algorithm with Whitelist Trust Mechanism](https://mlsanity.com/paper/2602.12483/) (2026)

## Abstract (arXiv)

We study loss-based filtering for finite-sum optimization with a subset of corrupted component functions whose gradients may be highly unreliable. Motivated by minimum-loss-based SGD (min-k-loss) and quantile-based methods for corrupted linear systems, we propose and analyze a general loss-filtering framework -- Quantile-(k)-Loss SGD (Q(k)L-SGD) -- that samples (k) component losses at each iteration and updates using an index chosen uniformly from the lower empirical (q)-quantile. We prove linear convergence of this family of methods under standard convexity assumptions, requiring the sample size to scale with the number of corruptions and a subset strong-convexity threshold. For the cases when large enough sampling is impossible or undesirable, we give a complementary small-sample probabilistic analysis that covers any sample size k and the convergence behavior depends on the probability of selecting an outlier and on the curvature of the selected good step. Experiments on polynomial regression, regularized logistic regression, and regularized hinge loss show that intermediate quantiles often outperform both standard SGD and min-(k)-loss SGD. In particular, min-(k) often stalls by repeatedly selecting nearly solved components, while intermediate quantiles retain robustness and produce more informative updates.