PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Jamie Haddock, Anna Ma, Elizaveta Rebrova

arXiv:2609.13040v1cs.LGcs.NAmath.NA

TL;DR

Corrupted component gradients can distort finite-sum SGD, motivating methods that target the uncorrupted objective. The paper proposes QkL-SGD, which filters sampled components by loss quantile, and analyzes both deterministic and small-sample probabilistic convergence. It reports empirical effectiveness across several optimization problems and corruption models.

  • Problem

    Corrupted component gradients can substantially distort SGD updates, while the objective of interest is the minimizer of the uncorrupted components.

    Source: §1 · pp. 1–2

  • Method

    QkL-SGD samples component losses and selects an update index from the lower empirical quantile, with q and k controlling the sampling rule.

    Source: §1 · p. 3

  • Results

    The analysis establishes deterministic and probabilistic guarantees, and experiments show effectiveness across several machine-learning and optimization problems under varied corruption models.

    Source: §1 · p. 3, §4 · p. 35

  • Takeaways & Limitations

    The framework makes the trade-off between outlier avoidance, progress on selected good components, and screening cost explicit through q and k.

    Source: §1 · p. 3

    QkL-SGD evaluates k losses to choose one update index; using accepted-set gradients, momentum, or variance reduction remains future work.

    Source: §4 · p. 35

Abstract

from arXiv · show

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.

1 Introduction

The paper studies finite-sum optimization when corrupted component gradients can distort SGD, targeting the minimizer of the uncorrupted objective. It introduces QkL-SGD, analyzes deterministic and small-sample probabilistic regimes, and positions the method among loss- and residual-based approaches.

1 Introduction

  • QkL-SGD samples k component losses and uniformly selects an update index from those at or below the empirical q-quantile, without requiring the accepted set to be clean.The parameter q controls the accepted fraction, while k controls how many losses are screened.Source: §1 · pp. 2–3
  • The deterministic analysis establishes linear convergence when sampling and subset strong-convexity conditions hold, with required sample size governed by corruptions and the subset threshold.In some sublinear-corruption regimes, k can be o(m), improving sample-size dependence over earlier subsampled quantile analyses in linear settings [Haddock et al., 2023].Source: §1 · p. 3
  • When deterministic counting conditions fail, a small-sample convergence bound depends on outlier-selection probability and the expected curvature of a selected good step.Under warm-start conditions, these quantities yield an explicit robustness–progress trade-off in q and k.Source: §1 · p. 3
  • Intermediate quantiles often outperform standard SGD and min-k-loss SGD across polynomial regression, regularized logistic regression, and regularized hinge loss, with the best q depending on the problem and corruption.The cited evaluation also varies q and k to illustrate parameter dependence predicted by the analysis.Source: §1 · p. 3

1.1 Background and related work

  • QkL-SGD extends loss- and residual-based selection beyond linear systems and the minimum-loss endpoint, making q and k explicit design parameters.For squared residuals, residual-quantile selection is equivalent to loss-quantile selection; QkL-SGD extends that connection to general finite-sum objectives.Source: §1 · p. 3, §1.1 · pp. 5–6

1.2 Notation

  • The method recomputes the eligible lower-tail set from current sampled losses each iteration; q=1/k gives min-k-loss SGD, while q=1 recovers uniform component sampling.The sample size k and quantile q are chosen so qk is an integer.Source: §1.2 · p. 6

2 Framework: Quantile-k-loss SGD

This section presents QkL-SGD, which selects an update uniformly from the sampled lower empirical loss quantile and recomputes that quantile each iteration. It analyzes convergence for large samples with deterministic guarantees and for smaller samples probabilistically, including explicit quantile-dependent convergence and error bounds under hard loss separation.

2 Framework: Quantile-k-loss SGD

  • The accepted set is recomputed from current losses each iteration, and q interpolates between min-k-loss SGD at q = 1/k and standard uniform-sampling SGD at q = 1.Intermediate q values select uniformly from the eligible lower-quantile set.Source: §2 · p. 6

2.1 Analysis for the sample size larger than the number of corruptions

  • Under the stated assumptions, QkL-SGD converges linearly in expectation to the uncorrupted objective’s minimizer, with contraction governed by accepted-outlier probability and error inflation from corrupted steps.The result applies when the accepted good set meets the subset strong-convexity threshold and the structural and step-size conditions hold.Source: §2.1 · pp. 7, 9, 14
  • The sample size need only scale with the outlier count and subset strong-convexity threshold, not the full dataset size; accepted and rejected sets must each retain good components.The required slack is τ = qk − s > 0 in the accepted set and ν = k − qk − s > 0 above the quantile threshold.Source: §2.1 · pp. 8–9
  • When s > 0, the deterministic assumptions exclude q = 1/k; min-k can be slow, and batches containing only outliers can force arbitrarily harmful corrupt-gradient steps.This obstruction can occur when s ≥ k, with positive probability under uniform sampling without replacement.Source: §2.1 · p. 9

2.2 Analysis for the sample size smaller than the number of corruptions

  • At smaller, even constant, sample sizes, convergence is analyzed probabilistically by requiring bounded outlier-selection probability, sufficient expected curvature from good steps, and bounded corrupted updates.Theorem 2 gives meaningful convergence when outlier-selection probability is sufficiently small; the analysis also motivates these assumptions through geometric separation of outlier and uncorrupted losses.Source: §2.2 · pp. 14–15
  • Theorem 2’s additive error term arises from selected corrupted updates that may remain nonzero near x*; if outliers weaken near x*, the result becomes exact linear contraction to zero.The exact-contraction condition is described as absorbing the corrupted-step contribution into the multiplicative term.Source: §2.2 · p. 16
  • The monotone subset-curvature profile provides an admissible good-step curvature bound, but random accepted good sets can fall below the strong-convexity threshold, leaving some iterations without a contraction guarantee.In the deterministic large-sample regime, the profile recovers the earlier curvature lower bound; in the general small-sample regime, accepted sets may be smaller than that threshold.Source: §2.2 · p. 17

2.2.1 Interpretation under large separation regime

  • Under hard separation, the outlier-selection probability is bounded through the chance of sampling fewer than qk good indices, while qk ≥ rsc and q < pG give a good-step curvature bound.The curvature bound uses the subset-curvature profile at qk.Source: §2.2.1 · pp. 18–19
  • Under hard separation, Corollary 2 gives explicit multi-iteration convergence and limiting-error bounds for any quantile using uniform bounds in εq,k and µ(qk).This replaces state-dependent quantities with explicit bounds and makes the tradeoff between avoiding outliers and making progress on good steps interpretable.Source: §2.2.1 · pp. 19–20
  • At fixed q < pG, increasing k decreases the outlier-selection bound exponentially and makes the curvature factor nondecreasing, improving the guaranteed convergence behavior when κq,k < 1.The improvement comes at the cost of more loss evaluations per iteration.Source: §2.2.1 · p. 20
  • At fixed k, decreasing q lowers outlier-selection and additive-error bounds but may also reduce good-step curvature, trading robustness for potentially slower progress.The effect on the multiplicative rate and limiting-error bound depends on the balance between those changes.Source: §2.2.1 · p. 20

3 Experiments

The experiments test QkL-SGD across finite-sum objectives beyond linear regression, including settings that stress the theory’s assumptions. Comparisons with SGD and min-k-loss SGD examine both loss-filtering choices and sample-size effects.

3 Experiments

  • Experiments cover polynomial regression, regularized logistic regression, and regularized hinge loss, including settings where one or more deterministic-theory assumptions fail.The evaluation includes noisy observations and corruption models beyond the exact theoretical assumptions.Source: §3 · pp. 20–21
  • With k = m, QkL-SGD and min-k-loss SGD are compared with standard SGD per iteration to isolate the loss-based selection rule.Min-k-loss SGD selects the sampled component with the smallest loss.Source: §3 · p. 21
  • Fixed-quantile experiments use q = 1 −β, while varying-q experiments test sensitivity to misspecifying that choice.The sample-size study compares methods by total component-loss evaluations across iterations.Source: §3 · p. 21

3.1 Noiseless Polynomial Regression

The noiseless degree-3 polynomial regression experiments test robustness to corrupted responses in a setting satisfying the stated model assumptions. They compare QkL-SGD with SGD and min-k-loss SGD, and vary q to assess its effect.

3.1 Noiseless Polynomial Regression

  • The noiseless task fits degree-3 polynomials to 200 samples, with outlier responses perturbed by large additive corruption drawn from N(0, 100).The uncorrupted polynomial has zero optimal loss, and the stated model assumptions hold.Source: §3.1 · pp. 21–22

3.1.1 Various outlier settings

  • With 5% and 10% corrupted responses, QkL-SGD converges faster and reaches lower final relative loss and parameter error than SGD, while min-k-loss SGD stagnates early.At both corruption levels, QkL-SGD’s learned polynomial remains close to the clean polynomial; the SGD fit is visibly distorted.Source: §3.1.1 · p. 22, Figure 1 · p. 23

3.1.2 Varying q with fixed corruption fraction β

  • Across corruption fractions β = 0.1, 0.2, 0.3, and 0.4, the q values yielding the lowest relative loss and error are near 1 −β.For larger β, quantiles slightly above 1 −β can be optimal; results are averaged over 100 independent trials.Source: §3.1.2 · pp. 22–23, Figure 1 · p. 23

3.2 Polynomial Regression

The noisy polynomial regression experiments assess QkL-SGD under response noise and additional large corruptions, a setting where Assumption 2.I fails. They compare methods at fixed quantiles and examine sensitivity to q.

3.2 Polynomial Regression

  • The noisy-response setting violates Assumption 2.I, while retaining the other stated model assumptions for the polynomial regression loss.The experiments add noise sampled from N(0, 0.32) to responses before introducing outliers.Source: §3.2 · pp. 23–24

3.2.1 Various outlier settings

  • With 5% and 10% corrupted responses, QkL-SGD achieves faster convergence and lower final relative loss and squared error than SGD, while min-k-loss SGD stagnates.The learned polynomial remains close to the clean polynomial despite corruption, while the SGD fit deviates.Source: §3.2.1 · p. 24, Figure 3 · p. 25

3.2.2 Varying q with fixed corruption fraction β

  • Across β = 0.1, 0.2, 0.3, and 0.4, q near 1 −β yields the lowest relative loss and error, but relative error is sensitive to q when accuracy matters.Relative loss values remain similar for quantiles near the optimum; results average 100 independent trials.Source: §3.2.2 · pp. 24–25

3.3 Regularized Logistic Regression

The logistic-regression experiments test QkL-SGD under label corruption in a smooth, nonquadratic classification model where individual good losses do not vanish at the clean-data reference. Across the tested corruption settings, QkL-SGD outperforms standard SGD, while full-sample min-k-loss SGD often stalls; the best quantile is approximately 1−β.

3.3 Regularized Logistic Regression

  • The experiments use smooth, regularized logistic regression with randomly flipped labels; individual good losses need not vanish at the clean-data reference.The model’s quadratic regularizer makes every nonempty good-subset objective λ/m-strongly convex.Source: §3.3 · pp. 25, 27

3.3.1 Various outlier settings

  • Across 1% and 10% label-flip settings, QkL-SGD beats SGD on good-set loss and parameter error, while full-sample MkL-SGD stalls.The tests include corruption in both classes and corruption concentrated in the positive class.Source: §3.3.1 · pp. 27–28

3.3.2 Varying q with fixed corruption fraction β

  • Across corruption fractions β=0.1–0.4, the best q is approximately 1−β; slight undershooting beats even slight overestimation.The comparison uses final relative loss and parameter error over 10,000 iterations, averaged across 100 trials.Source: §3.3.2 · pp. 28–29, Figure 6 · p. 29

3.4 Regularized Hinge Loss

The hinge-loss experiments assess label-corruption robustness for a regularized, nonsmooth classification objective. QkL-SGD performs well across the tested corruption settings, while min-k-loss SGD can stagnate; the quantile giving the best results is approximately 1−β.

3.4 Regularized Hinge Loss

  • The ℓ2-regularized hinge loss is nonsmooth, so Assumptions 2.I and 2.III fail, while 2.II and 2.IV hold.Its regularization makes every nonempty good-subset objective λ/m-strongly convex.Source: §3.4 · pp. 29–30

3.4.1 Various outlier settings

  • With 5% corruption, QkL-SGD beats SGD and MkL-SGD on both loss and error; at 1%, its error and boundary improve more clearly than its loss.The 5% tests include corruption from both classes and corruption confined to one class; at 1%, MkL-SGD’s relative loss increases and its error stagnates.Source: §3.4.1 · p. 30

3.4.2 Varying q with fixed corruption fraction β

  • Across corruption fractions β=0.1–0.4, the q producing the lowest final relative loss and error is approximately 1−β.The reported values are averages over 100 independent trials.Source: §3.4.2 · p. 32, Figure 8 · p. 32

3.5 Varying Sample Size k

The experiments vary the fraction of component losses sampled and compare small-sample min-k-loss SGD with QkL-SGD by cumulative loss evaluations. Smaller samples can increase QkL-SGD’s variance, while larger sample fractions generally favor QkL-SGD over min-k-loss SGD; in several small-sample comparisons, QkL-SGD eventually reaches lower loss or error.

3.5.1 Sample Fraction α

  • Across regression and classification tests, smaller sampling fractions can increase QkL-SGD’s variance, while it often achieves lower loss and error than MkL-SGD.In logistic regression and hinge loss, MkL-SGD suffers at large sampling fractions; QkL-SGD can suffer when the fraction is too small.Source: §3.5.1 · pp. 32–33
  • Across four problem settings, QkL-SGD performs best at a larger α than MkL-SGD, though both generally perform best with α<1.Figure 10 reports averages and the minimum-to-maximum spread over 100 trials.Source: §3.5.1 · p. 33

3.5.2 Small Sample Size

  • Against MkL-SGD with k=2, 5, or 10, QkL-SGD eventually reaches lower values in logistic regression and hinge loss when compared by loss evaluations.On noisy polynomial regression, QkL-SGD achieves the lowest final relative error; in the noiseless case, MkL-SGD with k=5 has the lowest loss and error.Source: §3.5.2 · pp. 33, 35

4 Conclusions and Future Work

The paper presents quantile-based loss filtering as a framework for optimization on corrupted data, with deterministic and probabilistic guarantees and empirical results across multiple problems. It identifies fuller use of accepted samples and batch, momentum, and adaptive variants as open directions.

4 Conclusions and Future Work

  • QkL-SGD has deterministic guarantees when sample size scales with corruption size and probabilistic guarantees in the small-sample regime, with empirical effectiveness across several problems.The conclusion describes results across several machine-learning and optimization problems and corruption models.Source: §4 · p. 35
  • Open directions include using the accepted lower-tail set for multiple updates and developing batch, momentum, and adaptive variants with convergence theory.The method currently evaluates k losses to select a single update index.Source: §4 · p. 35
Loading 2609.13040v1…