Quantile-based Loss Filtering for Outlier-Robust Stochastic Gradient Descent
Quantile-k-Loss SGD filters corrupted component losses by quantile sampling, proving linear convergence while outperforming standard and min-k-loss SGD.
The paper proposes Quantile-k-Loss SGD (Q(k)L-SGD), a loss-filtering framework for finite-sum optimization with corrupted components that samples k losses per iteration and updates using an index from the lower empirical q-quantile. The authors prove linear convergence under standard convexity, requiring sample size to scale with the number of corruptions, plus a complementary small-sample probabilistic analysis. Experiments on polynomial regression, regularized logistic regression, and hinge loss show intermediate quantiles often outperform both standard SGD and min-k-loss SGD.
18