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

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.