Quantile based gradient method improves robustness to outliers in training
Quantile-based Loss Filtering for Outlier-Robust Stochastic Gradient Descent
Machine Learning
Summary
Training machine learning models often involves adjusting parameters step by step using the data, but some data points can be wrong or misleading (called outliers). The authors study a new way to pick which pieces of data to learn from, focusing on those with losses in a certain low to medium range, rather than just the smallest losses or random picks. This method is more robust to bad data points, converges reliably, and performs better than some previous approaches on common problems like regression and classification. Their analysis shows how the method works well even with few or many outliers.
What this means in practice
- •For machine learning engineers: Improve training of models on noisy datasets by selecting updates based on intermediate loss quantiles to reduce impact of corrupted data points.
- •For data scientists: Develop more reliable regression and classification models when data contains outliers by applying quantile-based gradient filtering during training.
Authors
Jamie Haddock, Anna Ma, Elizaveta Rebrova
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 (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.