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

• URL: http://arxiv.org/abs/2609.13040v1
• Date: Fri, 11 Sep 2026 16:38:21 GMT
• Title: Quantile-based Loss Filtering for Outlier-Robust Stochastic Gradient Descent
• Abstract summary: We study loss-based finite-sum optimization with a subset of corrupted component functions.<n>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.
• Score: 2.0970533716091606
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• $Ω$: Operator-based Mixture Ensemble for Generative Assimilation [7.915816961228985]
  $$ is a scalable framework that integrates conditional Gaussian surrogate modeling, unsupervised score learning, and generative sampling.<n>$$ exploits closed-form conditional posterior distributions to analytically recover the high-dimensional unobserved component.<n>$$ is validated on several turbulent models with intermittency and extreme events, consistently improving posterior accuracy.
  arXiv  Detail & Related papers  (2026-06-18T20:19:44Z)
• Sharp Convergence Rates for Masked Diffusion Models [53.117058231393834]
  We develop a total-variation based analysis for the Euler method that overcomes limitations.<n>Our results relax assumptions on score estimation, improve parameter dependencies, and establish convergence guarantees.<n>Overall, our analysis introduces a direct TV-based error decomposition along the CTMC trajectory and a decoupling-based path-wise analysis for FHS.
  arXiv  Detail & Related papers  (2026-02-26T00:47:51Z)
• Stratified Sampling for Quasi-Probability Decompositions [0.0]
  Quasi-probability decompositions (QPDs) have proven essential in many quantum algorithms and protocols.<n>We develop a broad framework for accounting for and reducing this variance.<n> Numerical simulations of typical QPDs demonstrate constant-factor reductions in overall variance.
  arXiv  Detail & Related papers  (2026-02-11T17:46:40Z)
• Robust Stochastic Optimization via Gradient Quantile Clipping [6.2844649973308835]
  We introduce a quant clipping strategy for Gradient Descent (SGD) We use gradient new outliers as norm clipping chains. We propose an implementation of the algorithm using Huberiles.
  arXiv  Detail & Related papers  (2023-09-29T15:24:48Z)
• Boosting Differentiable Causal Discovery via Adaptive Sample Reweighting [62.23057729112182]
  Differentiable score-based causal discovery methods learn a directed acyclic graph from observational data. We propose a model-agnostic framework to boost causal discovery performance by dynamically learning the adaptive weights for the Reweighted Score function, ReScore.
  arXiv  Detail & Related papers  (2023-03-06T14:49:59Z)
• Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
  We introduce data structures for solving robust regression through gradient descent (SGD) Our algorithm effectively runs $T$ steps of SGD with importance sampling while using sublinear space and just making a single pass over the data.
  arXiv  Detail & Related papers  (2022-07-16T03:09:30Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  We propose a conditional gradient method (CGM) for minimizing convex finite-sum objectives formed as a sum of smooth and non-smooth terms. The proposed method, equipped with an average gradient (SAG) estimator, requires only one sample per iteration. Nevertheless, it guarantees fast convergence rates on par with more sophisticated variance reduction techniques.
  arXiv  Detail & Related papers  (2022-02-26T19:10:48Z)
• Learning Quantile Functions without Quantile Crossing for Distribution-free Time Series Forecasting [12.269597033369557]
  We propose the Incremental (Spline) Quantile Functions I(S)QF, a flexible and efficient distribution-free quantile estimation framework. We also provide a generalization error analysis of our proposed approaches under the sequence-to-sequence setting.
  arXiv  Detail & Related papers  (2021-11-12T06:54:48Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  Policy gradient (PG) is one of the most popular reinforcement learning (RL) problems. "vanilla" theoretical understanding of PG trajectory is one of the most popular methods for solving RL problems.
  arXiv  Detail & Related papers  (2021-07-23T19:38:17Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  We show that $O(k log L)$ samples suffice to guarantee that the signal is close to any vector that minimizes an amplitude-based empirical loss function. We adapt this result to sparse phase retrieval, and show that $O(s log n)$ samples are sufficient for a similar guarantee when the underlying signal is $s$-sparse and $n$-dimensional.
  arXiv  Detail & Related papers  (2021-06-29T12:49:54Z)
• Choosing the Sample with Lowest Loss makes SGD Robust [19.08973384659313]
  We propose a simple variant of the simple gradient descent (SGD) method in each step. Vanilla represents a new algorithm that is however effectively minimizing a non-current sum with the smallest loss. Our theoretical analysis of this idea for ML problems is backed up with small-scale neural network experiments.
  arXiv  Detail & Related papers  (2020-01-10T05:39:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.