Quantile-based Loss Filtering for Outlier-Robust Stochastic Gradient Descent
Jamie Haddock, Anna Ma, Elizaveta Rebrova
cs.LG · math.NA
Quick verdict
QkL-SGD unifies min-k-loss and SGD via quantile loss filtering with linear convergence guarantees; solid theory, but headline experiments use oracle q and k=m.
Summary
The paper introduces Quantile-k-Loss SGD (QkL-SGD), a two-parameter robust sampling framework for finite-sum optimization with corrupted components. At each iteration it samples k component losses, forms the lower empirical q-quantile set, and updates using an index drawn uniformly from that set; q=1/k recovers min-k-loss SGD and q=1 recovers standard SGD. Under convexity, smoothness, and subset strong convexity of good components, Theorem 1 proves linear convergence to the uncorrupted minimizer when the sample size is governed by the number of corruptions s and a subset strong-convexity threshold rather than m, improving on the O(m) requirement of prior subsampled quantile-Kaczmarz analyses. A complementary small-sample bound (Theorem 2) covers any k, with rate set by the outlier-selection probability and expected good-step curvature, made explicit under hard loss separation via Hoeffding bounds. Experiments on noiseless and noisy polynomial regression, regularized logistic regression, and hinge loss (m=200, 10,000 iterations, 100-trial averages) show intermediate quantiles outperform both SGD and min-k-loss SGD, which stalls by repeatedly selecting nearly solved components; the best q lies near the clean fraction 1−β. Limitations: headline experiments use k=m full-loss screening and the oracle q=1−β, three of four models violate the zero-good-loss assumption, the contraction condition is never quantitatively verified, and no adaptive quantile is proposed. Code is public.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 2
● low 3
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- QkL-SGD is a two-parameter loss-filtering family for general finite-sum objectives that contains min-k-loss SGD (q=1/k) and standard SGD (q=1) as endpoints.
- Under convexity, smoothness, and subset strong convexity, QkL-SGD converges linearly to the uncorrupted minimizer with sample size governed by the corruption count s and a subset threshold rather than m (Theorem 1), improving the O(m) requirement of prior subsampled quantile-Kaczmarz analyses.
- A complementary probabilistic bound covers any sample size k, with rate determined by the outlier-selection probability and expected good-step curvature, explicit under hard loss separation via Hoeffding bounds (Theorem 2, Proposition 2, Corollaries 1–2).
- Empirically, intermediate quantiles outperform both standard SGD and min-k-loss SGD — the latter stalls by repeatedly selecting nearly solved components — with best performance near the clean fraction q=1−β across polynomial regression, logistic regression, and hinge loss.
Strengths
Unifying two-parameter framework with clean endpoint recovery
Section 2 defines QkL-SGD so q=1/k reduces exactly to min-k-loss SGD (Shah et al. 2020) and q=1 to standard SGD, making the robustness–progress tradeoff an explicit design axis; the analysis does not require the accepted bag to be clean, which is more honest than most trimming analyses.
Genuine sample-size improvement over prior quantile-Kaczmarz theory
Theorem 1 needs k ≳ max((s+r_sc)/q, s/(1−q)) — governed by corruption count s and subset strong-convexity threshold r_sc — whereas subsampled quantile-RK guarantees (Haddock et al. 2023, 2022) required O(m); the paper states this contrast explicitly in Section 2.1.
Transparent theory–experiment bookkeeping
Consistent empirical story across four objective classes with cost-matched comparison
Public code with fully specified synthetic setups
Weaknesses
Headline experiments live in the least interesting regime
Oracle quantile throughout the main experiments
Contraction condition never verified quantitatively
Zero-good-loss assumption fails in 3 of 4 models; horizon only conjectured
Polish and proof-typography defects
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper studies finite-sum minimization min (1/m)Σf_i(x) when an unknown subset O of components is corrupted; the target is the minimizer of the clean objective F_G. The proposed QkL-SGD samples k component losses per iteration, accepts those at or below the empirical q-quantile (the bag B_t), and updates with the gradient of one uniformly chosen accepted index. The family spans min-k-loss SGD (q=1/k, Shah et al. 2020) and standard SGD (q=1). Four claims are made: (1) a two-parameter unifying framework; (2) deterministic linear convergence (Theorem 1) with sample size governed by corruption count s and subset strong-convexity threshold r_sc rather than m; (3) a complementary small-sample bound for any k (Theorem 2), made explicit under hard loss separation (Proposition 2, Corollaries 1–2); (4) empirical superiority of intermediate quantiles over both endpoints. All four are supported at the level stated; claim (2) is the clearest advance, relaxing the O(m) sample size required by subsampled quantile-Kaczmarz guarantees (Haddock et al. 2023, 2022).
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is Quantile-k-Loss SGD (QkL-SGD)?
QkL-SGD is a robust variant of stochastic gradient descent for datasets where some training examples are corrupted. Each iteration it samples k examples, computes their current losses, keeps only those at or below the empirical q-quantile of the sampled losses, and takes a gradient step on one example chosen uniformly from that low-loss set. Choosing q=1/k recovers min-k-loss SGD; choosing q=1 recovers ordinary SGD. Intermediate q values balance outlier avoidance against optimization progress.
When does QkL-SGD provably converge, and how large must the sample k be?
Two regimes are proved. (1) Deterministic: if each iteration's sample of size k exceeds the corruption count s with slack both below and above the quantile (roughly k ≳ max((s+r_sc)/q, s/(1−q)), where r_sc is a subset strong-convexity threshold), Theorem 1 gives linear convergence to the clean-data minimizer — notably without requiring k to scale with the full dataset size m. (2) Small-sample: Theorem 2 covers any k, with a rate and error floor determined by the probability of selecting an outlier and the expected curvature of good steps; under hard loss separation these become explicit exponential bounds in k.
Does QkL-SGD require knowing the fraction of corrupted data?
The method itself takes any quantile q, but the paper's main experiments set q=1−β using the true corruption fraction β, which is an oracle choice. Sensitivity experiments sweeping q on a 0.1 grid show the best q lies close to 1−β, and that underestimating β tends to hurt less than overestimating it in the logistic case. No adaptive method for estimating q from data is proposed; this is left as a practical gap.
Why does min-k-loss SGD stall in the paper's experiments, and where is the code?
The authors observe that minimum-loss selection repeatedly picks nearly solved components whose gradients are almost zero, so updates become negligible and both loss and parameter error plateau early. Intermediate quantiles keep some worst-case protection while selecting components that still make progress. Code for all experiments is publicly available at github.com/jamiehadd/QuantileSGD.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Mathematical notation is partially garbled by PDF extraction (e.g., the radical and fraction structure in χ's definition and some quantile expressions), so exact constant definitions were verified structurally rather than symbol-by-symbol; argument flow is unambiguous.
- Figure images are not present in the extraction (only captions and descriptive text), so convergence-rate judgments rely on the authors' descriptions rather than direct inspection of the plots.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.