Quantile-based Loss Filtering for Outlier-Robust Stochastic Gradient Descent
Abstract
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 (QkL-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.
Related
- A Rate Transfer Method: Convergence Rates in Stochastic Gradient Descent via Stochastic Calculus
- Convergence rate of stochastic gradient descent under Łojasiewicz type condition and polynomially controlled noise
- Exact Theory and Optimal Stepsizes for Stochastic Gradient Descent in Smooth Convex Minimization
- Continuous Delayed-Memory Stochastic Gradient Descent and Continuous-Time Reinforcement Learning from History of Astrophysical Time Series Studies
- Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent
BibTeX
@misc{haddock2026quantilebased,
title = {{Quantile-based Loss Filtering for Outlier-Robust Stochastic Gradient Descent}},
author = {Jamie Haddock and Anna Ma and Elizaveta Rebrova},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.13040},
eprint = {2609.13040},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.13040},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantile-based Loss Filtering for Outlier-Robust Stochastic Gradient Descent
AU - Jamie Haddock
AU - Anna Ma
AU - Elizaveta Rebrova
PY - 2026
DA - 2026/09/11
PB - arXiv
DO - 10.48550/arxiv.2609.13040
UR - https://arxiv.org/abs/2609.13040
AB - 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 (QkL-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.
ER -