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

Introduction

Stochastic Gradient Descent (SGD) is a fundamental method for solving large-scale finite-sum optimization problems of the form

where each component function $f_i$ corresponds to an individual data point, measurement, or training example. A basic component-sampling SGD replaces the full gradient by the gradient of a randomly selected component:

This update is computationally cheap, but can be vulnerable to corrupted data: if a small fraction of the component functions are affected by mislabeled data, faulty measurements, adversarial perturbations, or system failures, then even rare corrupted updates can substantially distort the method’s trajectory. Ordinary mini-batching reduces stochastic variance, but it does not by itself remove this vulnerability when corrupted gradients can be very large; as a single corrupted component can dominate an averaged batch update.

Across robust regression and stochastic or distributed optimization, related methods use three broad, overlapping strategies. Some select, remove, or reweigh observations or candidate updates using losses, residuals, or gradient diagnostics [6, 36, 13]. Others construct a robust gradient estimate or aggregate, for example through robust mean estimation, coordinate-wise median, or trimmed mean [32, 43]. A third line limits the influence of an individual selected observation through a robust loss or bounded update, as in $\ell_1$-loss SGD and gradient clipping [31, 24, 15]. These approaches address different corruption models and target problems.

Our focus is on a finite-sum corruption model in which the index set $[m]$ is partitioned as

where $G$ denotes the uncorrupted, or Good components and $O$ denotes corrupted components, or Outliers. Our goal is not to minimize the corrupted objective $F$, but rather to approximate a minimizer of the uncorrupted objective

That is, we seek $\mathbf{x}^* \in\operatorname*{arg\,min}_{\mathbf{x}} F_G(\mathbf{x})$. The sets $G$ and $O$ are unknown to the algorithm, and we do not impose a stochastic model on how the corruptions are generated. Corrupted component gradients may therefore be highly unreliable or adversarially aligned, so even a single corrupted update can result in an arbitrarily perturbed iterate.

Rather than modifying the per-sample update or constructing a robust aggregate from candidate gradients, we use iteration-dependent loss filtering: current component losses are used to restrict which sampled indices are eligible for the next stochastic update, without permanently identifying or removing observations. The motivation is that, in many corrupted-measurement models, good losses become small near the target solution while severely corrupted losses remain comparatively large. Thus the lower tail of the current loss distribution can provide useful information about which components are more reliable candidates for an update – even before any closeness to the target solution.

To that end, we introduce Quantile-$k$-Loss SGD (QkL-SGD). At each iteration, the method samples a subset $S_t \subset[m]$ of size $k$, computes the sampled losses

and accepts those sampled indices whose losses lie at or below the empirical $q$-quantile. The update index is then chosen uniformly from this accepted lower-tail set. Importantly, QkL-SGD does not rely on the accepted lower tail being clean. Corrupted components may also be accepted, and our analysis shows that their effect can still be controlled.

This construction defines a two-parameter family of stochastic sampling rules, with $q \in(0,1]$ controlling the accepted fraction and $k$ controlling the number of losses screened at each iteration. The extreme choice $q = 1/k$ reduces to min-$k$-loss SGD [34], which selects a minimum-loss component from a sample of size $k$. Larger values of $q$ interpolate between this conservative choice and ordinary SGD, recovered when $q = 1$. Viewed as a family, QkL-SGD unifies these special cases and explains why intermediate quantiles can offer a better balance between robustness and optimization progress than either endpoint. Our main contributions are as follows:

• A quantile loss-filtering framework for robust SGD. We formulate and analyze QkL-SGD as a two-parameter family of loss-based stochastic sampling rules for general finite-sum objectives (see Section 2). The family contains min-$k$-loss SGD and the standard SGD sampling distribution as endpoints and extends quantile-based residual selection beyond linear least squares. Treating $q$ and $k$ as separate algorithmic parameters makes explicit the tradeoff between outlier avoidance, progress on selected good components, and screening cost.

• A deterministic guarantee. Under smoothness and convexity assumptions, we prove linear convergence of QkL-SGD (see Theorem 1). The required sample size is governed by the number of corruptions and by a subset strong-convexity threshold, rather than directly by the total number of component functions. No stochastic model for the outliers is required, and the accepted lower-tail set need not be clean: the empirical quantile threshold and deterministic counting conditions control the effect of accepted outliers. In some regimes where the number of corruptions is sublinear in $m$, this permits sample sizes $k=o(m)$, improving the sample-size dependence of earlier subsampled quantile analyses in the linear setting [19].

• A probabilistic small-sample guarantee. When the deterministic counting conditions fail, for example, if the afforded sample size $k$ is constant-order, we derive a complementary convergence bound. Its rate depends on two interpretable quantities: the probability of selecting an outlier and the expected curvature of a selected good step (see Theorem 2). Further, under warm-start conditions, we show that these quantities yield an explicit robustness–progress tradeoff in $q$ and $k$ (see Section 2.2.1).

• Numerical evaluation across models and corruption regimes. We evaluate QkL-SGD on polynomial regression, regularized logistic regression, and regularized hinge loss under several corruption models, including settings beyond the exact assumptions of our theory. Across these problems, intermediate quantiles often improve performance relative to standard SGD and min-$k$-loss SGD. Experiments varying $q$ and $k$ further illustrate the parameter dependence predicted by the analysis. The best quantile is problem- and corruption-dependent, with strong empirical performance often occurring near the clean-data fraction (see Section 3).

The remainder of the paper is organized as follows. Section 1.1 reviews related work, then Section 2 formally introduces the QkL-SGD framework. Sections 2.1 and 2.2 develop the two complementary theoretical regimes: a deterministic analysis based on sufficiently large samples and a probabilistic analysis for smaller samples, including an explicit specialization under loss separation. Section 3 evaluates the method across several objective classes and corruption models, and Section 4 concludes with a brief discussion of some natural future directions of this work.

Background and related work

Robust statistics and robust regression. Learning or estimating in the presence of a small fraction of unreliable data has a long history in robust statistics, dating back to classical works such as [40, 22]. In regression, this perspective led to methods such as least median of squares and least trimmed squares [33, 41], in which residuals determine which observations influence the fitted model. More recently, high-dimensional robust statistics has developed efficient algorithms for estimation under adversarial contamination, including robust mean estimation and robust regression [2, 28, 10, 13]. Work by Klivans et al. [27] gives polynomial-time algorithms for outlier-robust linear and polynomial regression under adversarial corruptions in examples and labels. These works primarily study the statistical problem of constructing a robust estimator from a corrupted sample. Our goal is different: we study an iterative SGD-type method whose individual updates may be corrupted, and we ask when loss-based sampling can avoid such corrupted updates.

Residual and loss trimming. An algorithmic use of residual information appears in robust regression through hard thresholding. TORRENT alternates between selecting observations with small residuals under the current iterate and updating the regressor on the resulting active set; for squared loss, this is a residual- or loss-trimming procedure [6]. Related methods include consistent robust regression and adaptive hard thresholding for response corruption [7, 39]. These methods use residuals to address response or right-hand-side corruption, but are formulated primarily for linear regression as threshold-and-refit procedures.

A related line of work studies iterative trimmed loss minimization. Shen and Sanghavi [36] propose a general framework that repeatedly selects low-loss samples and updates or retrains a model on the selected subset, while iterative least trimmed squares methods apply the same principle in linear and mixed linear regression [35]. Awasthi et al. [3] analyze iterative trimmed maximum likelihood for robust generalized linear models under adversarial corruptions, including label corruptions. These methods are close in spirit to $Q_{\mathrm{kL}}$-SGD because they use losses to select samples. $Q_{\mathrm{kL}}$-SGD turns this principle into a sampled, single-component stochastic update rule for general finite-sum objectives.

Robust gradient filtering, estimation, aggregation, and clipping. Another line of work uses gradient information to robustify stochastic or distributed optimization. SEVER uses the spectral structure of per-sample gradients to score and remove suspect sample functions [14], whereas robust gradient-estimation methods replace the ordinary empirical gradient by a robust estimate [32]. Byzantine-resilient methods select or aggregate candidate worker gradients [8, 1], including coordinate-wise median and trimmed-mean aggregation [43].

Related Byzantine-resilient methods use additional information to screen or stabilize candidate updates. For example, Zeno++ accepts asynchronous worker updates according to an estimated loss-descent score [42], while other approaches incorporate information across iterations, such as worker momentum, to address attacks coupled over time [26]. Gradient clipping and norm-based filtering instead limit the influence of individual large gradients [15, 16]. Thus, these methods use gradient information to filter, estimate, aggregate, score, or control candidate updates. In contrast, $Q_{\mathrm{kL}}$-SGD uses current component losses to determine which sampled components are eligible to generate the next stochastic update.

Robust losses and bounded-influence stochastic updates. A complementary line of work builds robustness into the per-sample loss or update itself. For online linear and ReLU regression, SGD on the $\ell_1$ loss limits the influence of the magnitude of a corrupted residual; combined with iterate averaging or decaying step sizes, this yields convergence guarantees under oblivious or Massart response corruption [31, 24]. The $Q_{\mathrm{kL}}$-SGD method retains a general component-loss formulation and modifies which sampled component is used for the update.

Small-loss sample selection in noisy-label learning. A broader noisy-label learning literature also uses small loss as a proxy for sample reliability. MentorNet learns a curriculum weighting rule that emphasizes examples whose labels are likely to be correct [25]; Co-teaching uses two networks to select small-loss examples for one another [20]; and DivideMix models the per-sample loss distribution to separate likely clean and noisy examples [29]. These are primarily deep-learning procedures specialized to noisy-label training, whereas QkL-SGD defines an explicit finite-sum stochastic sampling rule with convergence theory. Moreover, our main analysis does not require the accepted lower-tail set to be clean: accepted outliers are permitted and their effect is controlled through the empirical quantile threshold and deterministic counting conditions.

The next two paragraphs review the two closest technical predecessors of QkL-SGD.

Quantile randomized Kaczmarz and corrupted linear systems. For linear systems with corrupted right-hand sides, quantile-based randomized Kaczmarz methods select rows using residual quantiles in order to avoid corrupted equations. This line of work includes quantile randomized Kaczmarz and its subsampled or block variants [18, 38, 17, 23, 11, 19]. The linear least-squares setting is a special case of finite-sum optimization: for

an SGD step on one squared residual is

When the rows are normalized and $\eta= 1$, this is the randomized Kaczmarz update. Thus, for squared residual losses, residual-quantile selection is equivalent to loss-quantile selection, and QkL-SGD can be viewed as an extension of quantile-based Kaczmarz sampling to general finite-sum objectives.

Min-$k$-loss SGD. The closest nonlinear SGD method is min-$k$-loss SGD, which samples $k$ components and updates the current iterate using the gradient of a component attaining the smallest current loss [34]. That work develops landscape and convergence analyses for the minimum-loss rule under separation and noise assumptions. QkL-SGD generalizes min-$k$-loss SGD from the minimum to a general sampled quantile. The additional quantile parameter is important because minimum-loss selection can be highly conservative, especially when $k$ is moderate or large. Our analysis and experiments show that intermediate quantiles can retain substantial robustness while producing more informative updates.

Overall, the existing works give rich evidence that losses and residuals can provide useful signals for robust estimation and optimization. They show that robustness can be introduced at different stages of a stochastic method: by controlling which observations or candidate updates influence a step, by constructing a robust gradient estimate or aggregate, or by limiting the influence of each selected observation. QkL-SGD develops the first strategy using current component losses as the selection statistic while retaining an otherwise standard component-gradient update. Existing loss- and residual-based theory has focused on problem-specific trimming and refitting procedures, quantile selection in linear systems, or the minimum-loss endpoint of stochastic sampling. We analyze the full sampled lower-quantile family for general finite-sum objectives, treating $q$ and $k$ as separate design parameters and making explicit their tradeoff between outlier avoidance and optimization progress.

Notation

We write $[m] = \{1,\ldots,m\}$. The index set is partitioned as $[m] = G \cup O$, where $G$ is the good set and $O$ is the outlier set. For any nonempty $S \subseteq[m]$, define

In particular,

For a multiset $R = \{z_1,\ldots,z_k\}$, let

denote its order statistics. Throughout the paper, the sample size $k$ and quantile level $q \in(0,1]$ are chosen so that $qk \in\{1,\ldots,k\}$ is an integer. We denote the empirical $q$-quantile by

Thus $q = 1/k$ gives the minimum of the sample, while $q = 1$ gives the maximum.

At iteration $t$, $S_t \subset[m]$ denotes a uniformly sampled subset of size $k$. The lower-tail set at iteration $t$ is the set, or Bag of acceptable components, i.e., sampled components whose loss falls below the empirical quantile:

We also write

to denote the set of outlier and good components in $B_t$, respectively.

Framework: Quantile-$k$-loss SGD

Algorithm 1 formalizes QkL-SGD: at each iteration, the method restricts the eligible update indices to the lower empirical $q$-quantile of the losses in a uniformly sampled set.

Note that the accepted set $B_t$ is recomputed from the current losses at every iteration; the method does not permanently identify or remove outliers. The quantile parameter controls the size of the eligible set. When $q = 1/k$, QkL-SGD reduces to min-$k$-loss SGD, up to ties. When $q = 1$, every sampled index is eligible, and the resulting update index has the standard uniform component-sampling distribution of SGD. Intermediate values of $q$ interpolate between these two rules. The next sections develop the analysis showing when the accepted good components provide sufficient progress and when the effect of accepted outliers remains controlled.

Analysis for the sample size larger than the number of corruptions

In this section, we analyze QkL-SGD in the regime where the sample size $k$ is large relative to the number of corruptions $s$. Under this condition, we can guarantee deterministically that every sampled batch contains enough good components both below and above the quantile threshold. We first state the sampling and model assumptions (Assumptions 1 and 2), which require that the accepted lower-tail set contains at least $\tau= qk - s$ good indices and that the averaged objective over any sufficiently large good subset is strongly convex. Our main result, Theorem 1, then establishes linear convergence in expectation of the QkL-SGD iterates to the minimizer $\mathbf{x}^*$ of the uncorrupted objective, with a contraction rate governed by the probability $\rho$ of selecting an accepted outlier and the potential error inflation $\chi$ from a corrupted step.

Assumption 1. (Sampling and corruption regime.) Let $s := |O|$ be the number of outliers, $k$ be the sample size ($1 \le k \le m$), $q \in(0,1)$ be the quantile, and assume $qk$ is an integer. We assume that

Equivalently,

The first inequality ensures that the accepted lower-tail set contains enough good indices. The second inequality ensures that the quantile threshold can be controlled by good components above the threshold.

Before discussing Assumption 1 and its implications on the sample size, we first present additional model assumptions.

Assumption 2. (Model setting.) We adopt the following model assumptions on the component functions $f_i$.

I. Good-component regularity. For every $i \in G$, the function $f_i$ is convex and

where $\mathbf{x}^*$ minimizes the uncorrupted objective $F_G(\mathbf{x})$. II. Outlier nonnegativity. For every $i \in O$ and every $\mathbf{v} \in\mathbb{R}^{n}$,

III. Component smoothness. For every $i \in[m]$, the function $f_i$ has $L_i$-Lipschitz gradient, i.e.,

For sets $S \subseteq[m]$, we use the conventions

Note that in particular

IV. Subset strong convexity on good accepted sets. There exists integer $r_{\mathrm{sc}}$ such that $1 \le r_{\mathrm{sc}} \le\tau$, such that for every subset $S \subseteq G$ with $|S| \ge r_{\mathrm{sc}}$, the averaged objective $F_S$ is $\mu_S$-strongly convex, i.e.,

Furthermore, we denote the smallest strong convexity parameter over good sets of size at least $\tau$ by $\mu^*$

The role of the sample size $k$ is to ensure that, at every iteration, the accepted set contains enough good indices both (i) below the quantile threshold, so that the update step can sample from a sufficiently large good subset, and (ii) above the quantile threshold, so that the threshold itself can be controlled by good components. As a result, Assumption 1 requires the two conditions

The first condition is a result of the simple calculation

The latter condition is needed because, after removing up to $s$ outliers, there remain at least $\nu=k-qk-s>0$ good sampled indices above the threshold, which allows us to relate the loss quantile value and the error. In particular, we can view the terms $\tau$ and $\nu$ “slack in the accepted and rejected set,” where the “slack” is for the worst case (all corruptions in the accepted/rejected set).

Up to integer rounding, this means that the sample size should be chosen so that

This gives a practical rule for selecting $k$: it must be large enough to overcome the number of outliers $s$, and large enough so that the accepted good set reaches the subset strong convexity threshold $r_{\mathrm{sc}}$.

A useful point is that this requirement does not force $k$ to scale with the total number of components $m$. In earlier subsampled methods for the linear setting, such as Haddock et al. [19, 17], theoretical guarantees typically required taking a sample size of order $O(m)$. In contrast, the present result allows $k$ to be chosen in terms of the outlier level $s$ and the structural threshold $r_{\mathrm{sc}}$, which can be much smaller than $m$.

The present assumptions always exclude the extreme choice $q=1/k$ whenever $s>0$, since then

In other words, as soon as there is even one outlier, the proof requires an accepted set larger than a single index. This is also consistent with a basic robustness obstruction: if $s\ge k$, then the random sample $S_t$ can consist entirely of outliers, and under uniform sampling without replacement this happens with positive probability. This event is detrimental to the analysis since, in this case, every accepted index is corrupted, since

regardless of the quantile level $q$. Hence the update necessarily uses a corrupt gradient, and if those outlier gradients are very large or adversarially aligned, a single such step can be arbitrarily harmful. Practically, for moderate or large sample size $k$, the extreme choice $q=1/k$ (that is, selecting the smallest residual/loss) is typically too conservative and leads to unnecessarily slow progress. Thus both the theory and the practical behavior suggest choosing $k$ large enough to ensure robustness, without relying on the minimum-loss rule. We illustrate this tradeoff in the numerical experiments in Section 3.

For simplicity of analysis, we assume that $f_i(x^*)=0$ for $i\in G$. However, in general, this is not necessary, and we expect that a nonzero value of $f_i$ at $x^*$ will, at worst, introduce a convergence horizon. For example, see the analysis of QRK in the noisy least squares case [5, 12]. We note that our experiments in Sections 3.2, 3.3, and 3.4 support this hypothesis in and beyond the quadratic least-squares objective.

We now present our main result in this section, which illustrates that the QkL-SGD iterates converge to the solution of the optimization problem restricted to only good components under Assumptions 1 and 2.

Theorem 1. Suppose Assumptions 1 and 2 hold, and let $x_t$ denote the iterates of Algorithm 1. Assume moreover that $\mu^*$ satisfies the structural condition

where we denote

and choose the step size so that

Then

where

We first develop some auxiliary results to prove Theorem 1. Lemma 1 and Lemma 3 handle the case where the selected update index is an outlier, first by showing that the quantile can be bounded, and then by showing that any inflation in error can be controlled. Lemma 4 handles the case where the selected update index is good.

Lemma 1. Let $\mathbf{v}\in\mathbb{R}^n$ be an arbitrary fixed vector. Under Assumptions 1 and 2,

Proof. Let

Recall that $|S_t|=k$ and by definition of the empirical $q$-quantile, $\gamma=z_{(qk)}$ where the $\{z_{(j)}\}_{j=1}^{k}$ values are the order statistics of $\{f_i(\mathbf{v})\}_{i\in S_t}$, and at least $k-qk-s=\nu$ indices in $S_t\cap G$ satisfy

By outlier nonnegativity and by convexity plus good-set regularity for the good components, all sampled losses are nonnegative. Hence $\gamma\ge0$ and

Let us further bound the right-hand side. Using the descent inequality implied by the $L_i$-Lipschitz gradient assumption (Assumption 2.III), together with the good-component regularity at the point $\mathbf{x}^{*}$, we obtain for each $i\in G$

Summing over $i\in S_t\cap G$ yields

since $S_t\cap G\subseteq G$, $|S_t\cap G|\le k$, and by definition of $L_{G,k}^{*}$, $\sum_{i\in S_t\cap G}\frac{L_i}{2}\le L_{G,k}^{*}$. Combining (8), (9) and (10), we conclude that

$\square$

Lemma 2 is the standard self-bounding inequality for smooth nonnegative functions; see, e.g., [30].

Lemma 2. Let $f$ be a nonnegative differentiable function satisfying the descent inequality with constant $L > 0$, i.e.,

Then, for any $\mathbf{v} \in\mathbb{R}^{n}$,

Now, we combine Lemmas 1 and 2 to bound the increase in error caused by an iteration using an outlier component.

Lemma 3. Suppose Assumptions 1 and 2 hold, and let $\mathbf{x}_t$ denote the iterates of Algorithm 1. If the selected update index satisfies $i_t \in O_t = B_t \cap O$, then

where

Proof. Fix a realization of $S_t$ and suppose $i_t \in O_t$. Starting with $\lVert\mathbf{x}_{t+1} - \mathbf{x}^{*}\rVert$, we have

Since $i_t \in O_t \subseteq B_t$, Lemma 1 and Lemma 2 give

Thus,

Consequently,

Squaring both sides gives the claimed result. □

We now turn to the case that the sampled component is good.

Lemma 4. Suppose Assumptions 1 and 2 hold, and let $\mathbf{x}_t$ denote the iterates of Algorithm 1. Assume that the step size satisfies

Conditioned on the selected update index satisfying $i_t \in G_t$, the algorithm selects $i_t$ uniformly from $G_t$, and

where

Proof. Since conditional on $(x_t, S_t)$, the algorithm is uniform on $B_t$; then conditional on the event $i_t \in G_t$, it is uniform on $G_t$.

Recall that by (6) and Assumption 2 the number of good accepted indices is large enough for the subset strong convexity assumption to apply. Now fix $i_t \in G_t$. Since $i_t \in G$, Assumption 2 gives $\nabla f_{i_t}(x^*) = 0$. We have

where the last step holds by co-coercivity for convex $L_{i_t}$-smooth functions. Since $i_t \in G$, convexity implies

Using $L_{i_t} \le L_G^*$, we get

Now take expectation over the uniform choice of $i_t \in G_t$. Since

we have

Therefore

Since $\lvert G_t \rvert\ge\tau$ and $G_t \subseteq G$, the subset strong convexity assumption implies

Since $\eta\le2/L_G^*$, $2\eta- \eta^2 L_G^* \ge0$, and we conclude

This proves the claim.

We are now ready to prove the main Theorem 1. We will shorten

where the randomness is over the fresh sample set $S_t$ and the uniform choice of $i_t \in B_t$.

Proof. (Proof of Theorem 1)

Step 1 (Checking step size assumption). First, we check that the stated step-size bound indeed implies the admissibility condition. Recall that

is required in Lemma 4. Indeed, by (7), we have

and therefore

We note that

and so

and (11) is satisfied for the considered step sizes $\eta\in(0,\bar{\eta}]$.

Step 2 (A one-step bound). We now prove the one-step estimate. Given $(x_t,S_t)$, the sets $B_t$, $G_t$, and $O_t$ are deterministic, and the algorithm chooses $i_t$ uniformly from $B_t$. Therefore,

Now define

Since $|O_t|\le s$ and $|B_t|\ge qk$, we have

Also, conditional on $(x_t,S_t)$ and the event $i_t\in G_t$, the index $i_t$ is uniformly distributed on $G_t$; similarly, conditional on $(x_t,S_t)$ and the event $i_t\in O_t$, the selected index lies in $O_t$. Thus, with $r_O$ as defined in Lemma 3 and with $r_G$ as defined in Lemma 4, we can bound

Next, $r_O=(1+\eta\chi)^2\ge1$ and, since $\eta\le2/L_G^*$, $r_G=1-\eta\mu^*(2-\eta L_G^*)\le1$. Hence the function

is increasing on $[0,1]$. Using $p_t(S_t)\le\rho$, we obtain

Finally, taking conditional expectation over $S_t$ given $x_t$ yields

This proves the one-step bound.

Step 3 (Contraction guarantee). It remains to show that $\kappa_{\mathrm{rate}} < 1$. We have

Therefore

By the structural condition on $\mu^*$,

and by the assumed step-size bound,

Thus $\kappa_{\mathrm{rate}}-1<0$, or equivalently, $\kappa_{\mathrm{rate}}<1$. Taking total expectation in the one-step estimate and iterating gives

This completes the proof.

Analysis for the sample size smaller than the number of corruptions

The deterministic analysis above allows the sample size $k$ to be chosen in terms of the number of outliers $s$ and the subset strong convexity threshold $r_{\mathrm{sc}}$, rather than in terms of the full dataset size $m$. This is already an improvement over earlier subsampled robust methods in the linear setting [19, 17], whose guarantees typically required sample sizes of order $O(m)$.

We now consider a complementary regime in which the same algorithm, QkL-SGD, is used with even smaller sample sizes, possibly constant. In this regime, the deterministic counting arguments from the previous section are no longer enough to provide convergence guarantees: a random sample may contain too many outliers, or even only outliers, and the sample quantile need not reliably reflect the behavior of the uncorrupted gradients of the full dataset. On the other hand, in practice corrupted residuals often become comparatively larger later in the iterations as the method approaches the optimizer, as observed in [18, 37]. This observation has motivated quantile-based robust rules on small samples in both the linear [19] and nonlinear [34] settings, and there is also recent evidence that logarithmic sample sizes may suffice under additional assumptions [9].

Motivated by these observations, we consider a modified probabilistic model with two additional assumptions: (a) the probability that Algorithm 1 selects a corrupted index is bounded from above, and (b) second moments of the corrupted gradients cannot be arbitrarily large:

Assumption 3 (Small-sample probabilistic assumptions). Fix a region $\mathcal{R}\subseteq\mathbb{R}^n$ containing $x^*$, and suppose the iterates under consideration remain in $\mathcal{R}$. We assume the following.

I. Good-component regularity. For every $i\in G$,

and $f_i$ is convex and has $L_i$-Lipschitz gradient. II. Soft quantile separation. There exists $\pi_{q,k} \in[0,1)$ such that, for every $\mathbf{x} \in\mathbb{R}$,

where $i_t$ is the index selected by Algorithm 1. This assumption requires that the selected lower-tail quantile rule chooses a corrupted index with probability at most $\pi_{q,k}$.

III. Good-step expected curvature. Let $\mu_{q,k} \ge0$ be a uniform curvature lower bound such that, for every $\mathbf{x} \in\mathbb{R}$,

IV. Bounded corrupted updates. There exists $G_O < \infty$ such that, for every $\mathbf{x} \in\mathbb{R}$,

One can obtain meaningful convergence rates in the small-sample regime under probabilistic assumptions, that is, assuming the probability of sampling an outlier is sufficiently small. We first formulate and prove our next result, Theorem 2, and then discuss how rather strong probabilistic assumptions naturally appear from the geometric assumptions, such as that the outlier losses are large enough compared to the uncorrupt losses.

Theorem 2 (Small-sample convergence). Suppose Assumption 3 holds and the step size satisfies the standard condition $0 < \eta\le2/L_G^{*}$. Then

where

where where $L_G^{*} := \max_{i \in G} L_i$ and $\pi_{q,k}$ is an upper bound on the probability that Algorithm 1 selects an outlier at iteration $t$. Therefore, whenever the probability of selecting a corrupted component is small enough, that is,

we have $\kappa_{q,k} < 1$, and the theorem implies

with $\kappa_{q,k}^{t} \searrow0$ and $\frac{1-\kappa_{q,k}^{t}}{1-\kappa_{q,k}}b_{q,k} \nearrow\frac{b_{q,k}}{1-\kappa_{q,k}}$ as $t \to\infty$.

Proof. Let us denote

We first control the update conditioned on $i_t \in G_t$. Since $\nabla f_j(x^{*}) = 0$ for every $j \in G$,

For $i_t \in G_t$, convexity and $L_{i_t}$-smoothness imply co-coercivity:

Since $L_{i_t} \le L_G^*$, we obtain

Using the good-step expected curvature assumption gives

where

Next, condition on $i_t \in O_t$. By Cauchy–Schwarz, the bounded corrupted update assumption, and Jensen’s inequality,

Using $2ab \le a^2 + b^2$ with $a = \sqrt{D_t}$ and $b = \eta G_O$, we obtain

Therefore

Combining the two conditional estimates yields

Since $0 < \eta\le2/L_G^*$, we have $r_G^{\mathrm{prob}} \le1 < 2$. Thus the right-hand side is increasing in $p_t$. Using $p_t \le\pi_{q,k}$, we obtain

If $\kappa_{q,k} < 1$, taking total expectation and iterating this recursion yields

Remark 1. The additive term in Theorem 2 comes only from the possibility that a selected corrupted update may have nonvanishing magnitude even near $x^*$. In more benign local regimes, the selected outliers may also become weak near $x^*$. For example, if

then the corrupted-step contribution can be absorbed into the multiplicative term and the convergence result becomes an exact linear contraction, that is, $\mathbb{E}\lVert x_t - x^*\rVert^2 \to0$ as $t \to\infty$.

Unlike the deterministic large-sample regime, the accepted good set $G_t$ is random and need not exceed the subset strong-convexity threshold at every iteration. Additionally, the expected-curvature constant $\mu_{q,k}$ in Assumption 3.III can be difficult to verify directly, and its dependence on $q$ and $k$ is not transparent. We next use the same subset strong-convexity structure as in Section 2.1 to construct a monotone curvature profile that yields an explicit admissible value of $\mu_{q,k}$.

Proposition 1 (Subset curvature implies good-step expected curvature). Suppose Assumption 3.I–II holds. Recall that $G \subseteq[m]$ is the fixed set of good component indices and that $G_t = B_t \cap G$ is the set of accepted good indices at iteration $t$. Assume that there exists $r_{\mathrm{sc}} \in\{1,\ldots,|G|\}$ such that, for every subset $S \subseteq G$ with $|S| \ge r_{\mathrm{sc}}$, the averaged objective $F_S$ is $\mu_S$-strongly convex. Define the subset-curvature profile

Then $\mu(h)$ is nondecreasing in $h$ and Assumption 3.III holds with

Proof. The monotonicity of $\mu(h)$ is immediate from the definition as minimizing over the smaller family of sets can only increase the value of the minimum. Fix $x\in\mathbb{R}$. Conditional on $x_t=x$, on the realized sample $S_t$, and on the event $i_t\in G_t$, the algorithm selects $i_t$ uniformly from the good accepted set $G_t$. Therefore

and similarly, since $\nabla f_i(x^*)=0$ for all $i\in G$,

Hence

If $|G_t|\ge r_{\mathrm{sc}}$, then the subset strong-convexity assumption gives

If $|G_t|<r_{\mathrm{sc}}$, then $F_{G_t}$ is convex, since it is an average of convex good components. Hence

Taking conditional expectation over $S_t$ and the infimum over $x\in\mathbb{R}$ gives the claim. $\square$

Remark 2. The subset-curvature profile $\mu(h)$ provides a monotone lower bound on the curvature associated with a realized accepted good set. Thus, Assumption 3.III holds with

*In the deterministic large-sample regime, when $|G_t|\ge\tau\ge r_{\mathrm{sc}}$, and hence $\mu(|G_t|)\ge\mu(\tau)=\mu^*$. As a result, $\mu_{q,k}\ge\mu^*$, so we recover the large-sample curvature lower bound from the section above. In the general small-sample regime, $|G_t|$ may be smaller than $\tau$, and even smaller than $r_{\mathrm{sc}}$. On these iterations, Theorem 2 guarantees no contraction even for small $\mu_{q,k}$.人體藝術

Interpretation under large separation regime

We now specialize the small-sample analysis to a simplified “warm start and large outliers” regime, in which every good loss lies strictly below every corrupted loss.

Assumption 4 (Idealized Model). For every $\mathbf{x} \in\mathbb{R}$,

The remainder of this section discusses the implications of Assumption 4 with respect to the small-sample regime. Proposition 2 provides an upper bound on the probability of selecting an outlier, $\pi_{q,k}$. Corollary 1 relates the good-step curvature parameter to subset strong convexity. Lastly, we end this section with a discussion on the consequences of this idealized corruption setting.

Proposition 2 (Hard-separation upper bound on the outlier-selection probability). Suppose Assumption 4 holds. Let $S_t = \{J_{t,1}, \ldots, J_{t,k}\}$ denote the sampled indices in iteration $t$ and define

Then, for every $\mathbf{x} \in\mathbb{R}$ and every $q < p_G$,

In particular, Assumption 3.II holds with $\pi_{q,k} = \exp\left(-2k(p_G-q)^2\right)$.

Proof. Under Assumption 4, if at least $qk$ good indices are sampled, then the $qk$ smallest sampled losses all correspond to good components. In that case, the empirical quantile threshold is the loss of a good component. Therefore, the algorithm can select an outlier only if $H < qk$, and hence

Define the outlier indicators

The variables $Y_1,\ldots,Y_k$ form a sample without replacement from a finite set consisting of $s$ ones and $m-s$ zeros, with the mean $\frac{s}{m} = 1-p_G$, also observe that

Hoeffding’s inequality for sampling without replacement (e.g., [4], based on the classical techniques from [21]) yields, for $q < p_G$,

We next show how the subset strong-convexity profile of the good components provides an admissible choice of the good-step curvature constant $\mu_{q,k}$ in Assumption 3.III.

Corollary 1 (Hard-separation verification of good-step curvature). Suppose Assumption 4 and the hypotheses of Proposition 1 hold, and let $H$ be as defined in Proposition 2. Then, Assumption 3.III holds with

if $qk \ge r_{\mathrm{sc}}$ and $q < p_G$.

Proof. Let

Under Assumption 4, on the event $\mathcal{A}$ all accepted indices are good and $|G_t|\ge qk$. Therefore,

Moreover, $\mathcal{A}\subseteq\{i_t\in G_t\}$. Hence, for every $\mathbf{x}\in\mathbb{R}$,

Here the final inequality uses $\mathbb{P}(i_t\in G_t\mid x_t=\mathbf{x})\le1$, and the fresh sample $S_t$ is independent of $x_t$. Taking the infimum over $\mathbf{x}\in\mathbb{R}$ gives

The claim follows from Proposition 2.

Proposition 2 and Corollary 1 immediately imply

Corollary 2 (Explicit rate and error floor under hard separation). Suppose Assumption 4 and the hypotheses of Proposition 1 hold. Assume

and define

Then Theorem 2 applies with

Therefore,

where

and

If $\bar{\kappa}_{q,k}<1$, then

Choosing $q = 1/k$ recovers min-$k$-loss SGD [34]. This prior work derives a state-dependent one-step recursion for this rule, in which the rank-dependent sampling probabilities control both the good-step contraction and the outlier contribution. That analysis observes that minimum-loss selection may reduce the outlier term while also slowing contraction. Corollary 2 gives a different type of guarantee: under hard separation, it replaces these state-dependent quantities by explicit, uniform bounds in terms of $\varepsilon_{q,k}$ and $\mu(qk)$. This yields a multi-iteration convergence bound and an explicit limiting-error bound for any choice of quantile, while making the tradeoff between outlier avoidance and good-step progress directly interpretable.

Corollary 2 illustrates the dependence of the convergence of Algorithm 1 on the basic sample size $k$ and quantile $q$ parameters:

Effect of increasing $k$ at fixed $q < p_G$. As $k$ increases, $\varepsilon_{q,k}$ decreases exponentially, while $\mu(qk)$ is nondecreasing. Hence $\overline{\kappa}_{q,k}$ and $\overline{b}_{q,k}$ are nonincreasing in $k$. Whenever $\overline{\kappa}_{q,k} < 1$, the corresponding limiting-error bound is also nonincreasing. This illustrates that larger samples improve the guaranteed reliability and convergence behavior, at the expense of more loss evaluations per iteration.

Effect of varying $q$ at fixed $k$. Decreasing $q$ lowers the outlier-selection and additive-error bounds, but may also lower the curvature factor $\mu(qk)$. Therefore, its effect on the multiplicative rate and limiting-error bound is governed by the balance between robustness and good-step progress. This illustrates that Smaller quantiles produce more robust loss selection, but may also result in slower progress on selected good steps.

Experiments

In this section, we present numerical experiments across several objective classes to demonstrate how quantile-based robust SGD remains effective across increasingly general finite-sum optimization problems. The most basic instance of such problem classes is the corrupted linear system setting, which was studied in earlier work on quantile-based Kaczmarz methods, including [18, 19]. Here we focus on finite-sum objectives that move beyond the linear setting. Code for all numerical experiments are publicly available at https://github.com/jamiehadd/QuantileSGD.

Table 1: The table records model properties, as per Assumption 2: I = good-component regularity, II = outlier nonnegativity, III = component smoothness, and IV = subset strong convexity on good accepted sets. A checkmark in column IV indicates the existence of positive subset curvature. For the nonsmooth hinge loss, strong convexity is understood in the subgradient sense.

Algorithm 1 Quantile-$k$-loss SGD (QkL-SGD)

1: Input: sample size $k$, quantile $q$, step size $\eta$, number of iterations $T$

2: Initialize $\mathbf{x}_0$

3: for $t = 0,\ldots,T-1$ do

4: Uniformly select a subset $S_t \subset[m]$ with $|S_t| = k$

5: Set

$B_t := \{j \in S_t : f_j(\mathbf{x}_t) \le Q_q(\{f_\ell(\mathbf{x}_t)\}_{\ell\in S_t})\}$

6: Uniformly select $i_t \in B_t$

7: Update

$\mathbf{x}_{t+1} = \mathbf{x}_t - \eta\nabla f_{i_t}(\mathbf{x}_t)$

8: end for

9: return $\mathbf{x}_T$

Section	Model	I	II	III	IV
Subsection 3.1	Noiseless polynomial regression	✓	✓	✓	✓
Subsection 3.2	Noisy polynomial regression	✗	✓	✓	✓
Subsection 3.3	Regularized logistic regression	✗	✓	✓	✓
Subsection 3.4	Regularized hinge loss	✗	✓	✗	✓

We begin with polynomial regression, first in a noiseless interpolating regime that is closest to the assumptions of Theorem 1, and then consider noisy observations. We next consider regularized logistic regression, which has a smooth nonlinear loss, and regularized hinge loss, which provides a nonsmooth stress test.

Table 1 reports model-level properties relevant to our analyses. Note that a checkmark for subset strong convexity means that sufficiently large good subsets admit a positive strong-convexity; it does not verify that it is large enough to satisfy the quantitative contraction conditions of Theorem 1 (and in most experimental settings it is not). Indeed, except for the noiseless polynomial-regression model, the experiments intentionally consider settings in which one or more assumptions of the deterministic theory fail, to stress-test $Q_k$L-SGD on increasingly challenging problems. The probabilistic assumptions in Assumption 3 are not included in the table, because they depend on $q$, $k$, the corruption model, and the resulting algorithmic trajectory rather than on the component-loss model alone.

For each objective class, we compare $Q_k$L-SGD with standard SGD and min-$k$-loss SGD ($M_k$L-SGD), where $M_k$L-SGD denotes the rule that selects the sampled component with the smallest loss (see, e.g., [34]). We present first the large-sample experiments in Sections 3.1–3.4, where we take $k = m$ for both $Q_k$L-SGD and $M_k$L-SGD. These comparisons isolate the effect of the loss-based selection rule, and they are plotted per iteration.

Then, in Section 3.5, we study the effect of the sample size and compare the methods as functions of the total number of component-loss evaluations across all iterations. In the fixed-quantile experiments, we use the oracle choice $q = 1 - \beta$ to isolate the behavior of the loss-filtering rule. The varying-$q$ experiments then assess sensitivity to misspecification of this choice.

Noiseless Polynomial Regression

We begin by considering a noiseless polynomial regression task, a least-squares problem with zero optimal loss. We aim to illustrate the robustness of $Q_k$L-SGD to a small fraction $\beta$ of corrupted regression response values. In each experiment, we generate ideal noiseless polynomial regression sample data and introduce significant corruption into a small number of outlier response values. We note that the typical polynomial regression task is not noiseless and thus does not have zero optimal uncorrupted loss; we consider such a task in the next subsection, Subsection 3.2. However, we begin with the noiseless case since this task satisfies all model-level assumptions in Table 1 and Assumption 2.

We consider the problem of fitting a polynomial of degree 3 to data $\{(x_i,y_i)\}_{i=1}^{m}$, where the data is generated according to

the $x_i$ are uniformly distributed over the interval $[-3,3]$, and $m = 200$. We will call $p(x)$ the ‘clean polynomial’ and note that $p(x) = \mathbf{d}_{\mathrm{clean}}^{\mathsf{T}}\mathbf{x}_{\mathrm{clean}}$ where $\mathbf{x}_{\mathrm{clean}} = [1, 0.5, -0.2, 0.05]^{\mathsf{T}}$ and $\mathbf{d} = [1,x,x^2,x^3]^{\mathsf{T}}$. In the plots below, we visualize $p(x)$ and label this “Clean”. To introduce outliers, we randomly select a fraction $\beta$ of the response variables $y_i$ and add large corruptions sampled from $\mathcal{N}(0,100)$; this set is the outlier set $O$ and the remaining uncorrupted set is $G$.

The optimal regression coefficients $\mathbf{x}_{\mathrm{clean}}^* \in\mathbb{R}^4$ corresponding to clean polynomial $p(x)$ are estimated by minimizing the empirical least-squares objective

with respect to the parameter vector $\mathbf{x}$, where $\mathbf{d}_i = [1,x_i,x_i^2,x_i^3]^{\mathsf{T}}$ denotes the feature vector corresponding to sample $x_i$. Any coefficient parameter vector $\mathbf{x} \in\mathbb{R}^4$ defines a polynomial as $\mathbf{x}^{\mathsf{T}}\mathbf{d】【。 where $\mathbf{d} = [1, x, x^2, x^3]^\top$. We may visualize any such univariate polynomial by plotting it alongside the clean polynomial $p(x)$ and the samples; we do so in the right plot of the experiments below.

The objective in each experiment is to learn a parameter vector $\mathbf{x} \in\mathbb{R}^4$ that defines a polynomial near to clean polynomial $p(x)$, and thus fitting the samples whose response values have not been corrupted. In all experiments, SGD, QkL-SGD, and MkL-SGD are applied to objective $F(\mathbf{x})$ using step size $\eta= 0.001$.

Assumptions for noiseless polynomial regression loss The polynomial regression components (14) are nonnegative, convex, and smooth with

Here, for $\tau_{\mathrm{sc}} = 4$ and every subset $S \subseteq G$ with $\lvert S \rvert\ge\tau_{\mathrm{sc}} = 4$, we have that the least-squares objective $F_S(\mathbf{x})$ is strongly convex, since in our case where each $x_i$ is distinct, the design matrix $D_S$ of subset $S$ has full column rank. Because the uncorrupted data is assumed to be noiseless, we have $f_i(\mathbf{x}^{\star}_{\mathrm{clean}}) = 0$ and $\nabla f_i(\mathbf{x}^{\star}_{\mathrm{clean}}) = 0$ for $i \in G$. Thus, Assumptions 2.I, 2.II, 2.III, and 2.IV all hold for this model.

Various outlier settings

In this section, we illustrate the behavior of QkL-SGD on noiseless polynomial regression models under a small to moderate fraction of outliers $\beta$. Here we apply QkL-SGD with $q = 1 - \beta$.

Few outliers ($\beta= 0.05$, $q = 0.95$, $k = m$) In our first experiment, whose results are presented in fig:1a, 5% of the sample response values $y_i$ are corrupted by large additive corruption sampled from $\mathcal{N}(0, 100)$. We compare QkL-SGD with $q = 0.95$ and $k = m$ to SGD and MkL-SGD with $k = m$. We see QkL-SGD converges towards the zero optimal relative loss and parameter vector faster and to a lower final relative error than SGD. MkL-SGD stalls nearly immediately with respect to both loss and error, as the algorithmic selection of the component with minimum loss begins near zero and thus the update is nearly negligible. We plot the polynomials learned by SGD, QkL-SGD, and MkL-SGD; see the right plot. The learned polynomial from QkL-SGD closely matches the true function even in regions influenced by outliers, while the SGD fit is visibly distorted by the corrupted points.

Moderate outliers ($\beta= 0.1$, $q = 0.9$, $k = m$) In our next experiment, presented in fig:1b, 10% of the sample response values $y_i$ are corrupted by large additive corruption sampled from $\mathcal{N}(0, 100)$. We see that QkL-SGD with $q = 0.9$ and $k = m$ again outperforms SGD with respect to both relative loss and relative error, and MkL-SGD again stagnates early. We visualize the learned polynomials in the right plot; the polynomial learned by QkL-SGD is nearly identical to the true polynomial $p(x)$, while the SGD-learned polynomial suffers due to the corrupted samples.

Varying $q$ with fixed corruption fraction

In our final experiment with the noiseless polynomial regression model, we explore how QkL-SGD behaves with different choices of quantile $q$ under a fixed corruption fraction $\beta$. In Figure 2, we plot the final relative loss (left plot) and final relative error (right plot) after 10000 iterations of QkL-SGD with $q \in\{0.05, 0.1, \cdots, 1.0\}$ and $k = m$. We apply QkL-SGD to the noiseless polynomial regression loss (14) applied to the data model described above where $\beta\in\{0.1, 0.2, 0.3, 0.4\}$ fraction of data is corrupted. Relative loss and relative errors are averaged over 100 independent trials. of 10000 iterations of QkL-SGD. Here, we see that the quantile value $q$ that achieves the lowest relative loss and relative error is near $1-\beta$. For larger corruption fractions $\beta$, quantiles $q$ very slightly larger than $1-\beta$ can be optimal. Lowest values of relative error and loss are similar for each fraction $\beta$, illustrating that QkL-SGD provides robustness to even significant amounts of data corruption.

Polynomial Regression

We next turn to the typical polynomial regression task, where the data samples are all assumed to be affected by a small amount of noise in the response values. This change causes Assumption 2.I to fail. As in the experiments in the previous section, Subsection 3.1, our goal is to assess the robustness of QkL-SGD to a small fraction of samples with response values affected by significant corruption.

The data setting is identical to Subsection 3.1, with the exception that the data $\{(x_i,y_i)\}_{i=1}^{m}$ is generated according to

where noise values $\epsilon_i$ are sampled from $\mathcal{N}(0,0.3^2)$, and as before, the $x_i$ are uniformly distributed over the interval $[-3,3)$ and $m=200$. The outlier set and corruptions are generated as before in Subsection 3.1.

The model (14) and the experimental setup is the same as in Subsection 3.1.

Assumptions for polynomial regression loss As before for the noiseless polynomial regression model, Assumptions 2.II, 2.III, and 2.IV all hold for the noisy polynomial regression model with the same parameters. However, due to the noise in the uncorrupted response variables, we no longer have $f_i(\mathbf{x}^{\star}_{\mathrm{clean}})=0$ and $\nabla f_i(\mathbf{x}^{\star}_{\mathrm{clean}})=0$ for $i \in[G]$, and thus Assumption 2.I fails.

Various outlier settings

We now turn to QkL-SGD for the noisy polynomial regression model under a variety of small to moderate corruption fractions $\beta$. We take the ideal quantile value $q=1-\beta$.

Few outliers ($\beta=0.05$, $q=0.95$, $k=m$) In the noisy polynomial regression experiments shown in fig:3a, we again corrupt 5% of the sample response values $y_i$ with large additive corruptions drawn from $\mathcal{N}(0,100)$. We compare QkL-SGD with $q=0.95$ and $k=m$ against SGD and MkL-SGD with $k=m$. Consistent with the noiseless setting, QkL-SGD achieves faster convergence and lower final relative loss and relative squared error than SGD. In contrast, MkL-SGD exhibits little progress, as selecting the minimum-loss component yields updates of negligible magnitude early in training. The learned polynomials (right plot) further illustrate the robustness of QkL-SGD: its fit remains close to the underlying target function despite the presence of corrupted observations, whereas the polynomial obtained with SGD is noticeably skewed by the outliers.

Moderate outliers ($\beta=0.1$, $q=0.9$, $k=m$) fig:3b reports results for a more heavily corrupted setting in which 10% of the response values $y_i$ are perturbed by additive corruption drawn from $\mathcal{N}(0,100)$. In this regime, QkL-SGD with $q=0.9$ and $k=m$ continues to substantially outperform SGD in both relative loss and relative error, while MkL-SGD once again stagnates after only limited progress. The polynomial visualization (right plot) highlights the robustness of QkL-SGD under corruption: the recovered polynomial remains closely aligned with the clean polynomial $p(x)$, whereas the polynomial obtained by SGD deviates significantly due to sensitivity to the corrupted observations.

Varying q with fixed corruption fraction $\beta$

Figure 4 illustrates the effect of varying the quantile parameter $q \in\{0.05,0.1,\ldots,1.0\}$ on the final relative loss (left) and relative error (right) after 10,000 iterations of QkL-SGD with $k=m$.

The method is applied to the noisy polynomial regression problem (14) using the data model described above with corruption fractions $\beta\in\{0.1,0.2,0.3,0.4\}$. Relative loss and relative errors are averaged over 100 independent trials of 10000 iterations of QkL-SGD. Like in the noiseless polynomial regression case, we see that the quantile $q$ producing lowest relative error and loss is approximately $1-\beta$. However, in this case, the relative loss values are very similar for quantiles nearby to the optimal, but the relative error illustrates the sensitivity of QkL-SGD to the quantile if an accurate solution is desired.

Regularized Logistic Regression

We next consider $\ell_2$-regularized logistic regression as a smooth nonlinear classification problem with corrupted labels. This experiment keeps the smoothness present in the polynomial-regression examples, but moves from quadratic least squares to a nonquadratic classification loss. As in noisy polynomial regression, the interpolation part of Assumption 2 fails: the individual good losses and gradients need not vanish at the clean-data reference solution. In this section, we generate synthetic, linearly separable two-dimensional data and examine the impact of introducing label corruption on optimization performance. The experiments are designed to assess robustness to outliers, which are introduced by randomly flipping (corrupting) a fraction $\beta$ of the labels.

For a parameter vector $\mathbf{x}$, the logistic model predicts the probability of the positive class for data point $\mathbf{d}_i$ via the sigmoid function as

Given binary labels $l_i \in\{0,1\}$, we use the regularized component losses

and the finite-sum objective

In all experiments, we generate $m=200$ augmented data points $\mathbf{d}_i=(1,u_i,v_i)^\top\in\mathbb{R}^3$. The first component of each data point is fixed to be $(\mathbf{d}_i)_1=1$ to allow for an affine bias term in the logistic regression model.

Half of the points belong to the positive class, with $(u_i,v_i)$ sampled i.i.d. from a Gaussian distribution centered at $(2,2)$ with identity covariance and clean label $l_i^{\mathrm{clean}}=1$. The remaining half belong to the negative class, with $(u_i,v_i)$ sampled i.i.d. from a Gaussian distribution centered at $(-2,-2)$ with identity covariance and clean label $l_i^{\mathrm{clean}}=0$. Note that before corruption, the data are linearly separable with high probability. To create outliers, we select a fraction $\beta$ of the data points and flip their labels. Thus, for $i \in G$ the observed label agrees with the clean label, while for $i \in O$ the observed label is $l_i=1-l_i^{\mathrm{clean}}$. The algorithms use only the observed labels. In the visualizations below, we plot the last two coordinates $(u_i,v_i)$ together with the learned decision boundary

The objective is to learn a parameter vector $\mathbf{x}\in\mathbb{R}^3$ that correctly classifies the data points whose labels have not been corrupted, and ideally generalizes to correctly classify even data points whose labels have been corrupted and no longer represents to which class the data truly belongs. Aligned with that, we run SGD on the clean dataset before any labels are flipped. We denote the resulting parameter after 10000 iterations by $\mathbf{x}^{\star}_{\mathrm{clean}}$ and plot the corresponding clean-data reference boundary

This boundary is used only as a visual reference and is labeled “Clean” in the plots.

In all logistic-regression experiments, SGD, QkL-SGD, and min-$k$-loss SGD (MkL-SGD) are run with stepsize $\eta=0.01$ and regularization parameter $\lambda=1$. The reported objective values are evaluated on the good set $G$, and the reported parameter errors are measured relative to $\mathbf{x}^{\star}_{\mathrm{clean}}$.

Assumptions for regularized logistic regression The regularized logistic regression components in (15) are nonnegative, convex, and smooth, with

Moreover, because of the quadratic regularizer, $F_S$ is $\lambda/m$-strongly convex for every nonempty subset $S \subseteq G$. Thus Assumptions 2.II, 2.III, and 2.IV hold at the model level. However, Assumption 2.I fails: although the good component losses are convex, they do not satisfy $f_i(\mathbf{x}_{\mathrm{clean}}^\star) = 0$ and $\nabla f_i(\mathbf{x}_{\mathrm{clean}}^\star) = 0$ individually.

Various outlier settings

In this section, we explore the convergence of QkL-SGD in a variety of outlier settings. Here we let quantile $q = 1 - \beta$.

Few outliers from a single class ($\beta= 0.01$, $q = 0.99$, $k = m$) In the first logistic-regression experiment, shown in fig:5a, we corrupt 1% of the data points, all chosen from the positive class, by flipping their labels. We compare standard SGD, QkL-SGD with $(k, q) = (m, 0.99)$, and MkL-SGD with $k = m$. In this full-sample setting, QkL-SGD and MkL-SGD both screen all component losses at each iteration, so the comparison isolates the effect of selecting from the lower empirical quantile rather than selecting the minimum-loss component. QkL-SGD decreases the good-set objective $F_G(x_t)$ faster than SGD and tracks the clean-data reference parameter more closely. By contrast, MkL-SGD stalls early: selecting the minimum-loss component can repeatedly choose nearly solved components and produce updates of negligible size. The decision-boundary plot shows the same qualitative behavior: QkL-SGD remains close to the clean-data reference boundary, while the SGD boundary is more visibly affected by the flipped labels.

Moderate outliers from both classes ($\beta= 0.1$, $q = 0.9$, $k = m$) In the experiment shown in fig:5b, 10% of the data points are selected uniformly from both classes and their labels are flipped. We compare standard SGD, QkL-SGD with screening size $k = m$ and quantile parameter $q = 0.9$, and MkL-SGD with $k = m$. Thus, both QkL-SGD and MkL-SGD evaluate all component losses before selecting an update; the comparison between them isolates the effect of selecting from the lower empirical $q$-quantile rather than selecting the minimum-loss component.

QkL-SGD achieves smaller good-set loss $F_G(x_t)$ and smaller parameter error relative to the clean-data reference than standard SGD, while full-sample MkL-SGD stalls early. The decision-boundary visualization shows the same qualitative behavior: the QkL-SGD boundary remains closer to the clean-data reference boundary, whereas the SGD boundary is influenced by the flipped labels: a single data point with a non-corrupted label in the positive class is misclassified.

Moderate outliers from a single class ($\beta= 0.1$, $q = 0.9$, $k = m$) We next consider a more structured corruption pattern, where 10% of the labels are flipped but all corrupted points are chosen from the positive class. This asymmetric corruption concentrates the outlier effect in one region of the data. We again compare standard SGD, QkL-SGD with screening size $k = m$ and quantile parameter $q = 0.9$, and MkL-SGD with $k = m$.

As shown in fig:5c, QkL-SGD remains more robust to the corrupted labels than standard SGD, achieving lower good-set loss and smaller parameter error relative to the clean-data reference. We see that QkL-SGD learns a decision boundary that correctly classifies all correctly labeled data points. Additionally, the extreme imbalance of the mislabeled data causes the decision boundary learned by SGD to misclassify additional correctly labeled data in the positive class. Finally, full-sample MkL-SGD again makes little progress, consistent with the conservative behavior of minimum-loss selection.

Varying $q$ with fixed corruption fraction $\beta$

Our final experiment in this section examines the sensitivity of QkL-SGD to the choice of quantile parameter $q$ for the regularized logistic regression problem. For each corruption level $\beta\in\{0.1, 0.2, 0.3, 0.4\}$, we run QkL-SGD for 10,000 iterations with $q \in\{0.05, 0.1, \ldots, 1.0\}$ and record the resulting final relative loss and relative error. The underlying optimization problem is the regularized logistic regression objective (16) using the data model described above, where a fraction $\beta$ of the samples, selected uniformly across the two classes, are corrupted. The results are presented in Figure 6, with the left panel showing the final relative loss and the right panel showing the final relative error. Relative loss and relative errors are averaged over 100 independent trials of 10000 iterations of QkL-SGD. As in polynomial regression applications, we see that the quantile $q$ that minimizes relative error and loss is approximately $1-\beta$. In this case, we see that using a quantile $q$ less than this optimal choice produces better results than even slight overestimates of the optimal quantile.

Regularized Hinge Loss

Next, we turn to the $\ell_2$-regularized hinge loss objective, which is the standard loss used in support vector machines. This loss is nonsmooth so Assumption 2.III fails, unlike the other models considered. Here, like with the noisy polynomial regression and logistic regression models, Assumption 2.I fails. Like in Subsection 3.3, the experiments are designed to assess robustness to outliers, which are introduced by randomly flipping (corrupting) a fraction $\beta$ of the labels.

The $\ell_2$-regularized hinge loss model is typically employed as a supervised binary classification model where data points $\mathbf{d}_i \in\mathbb{R}^n$ with labels $l_i \in\{-1,+1\}$ are available. The regularized hinge loss component objective for parameter vector $\mathbf{x} \in\mathbb{R}^n$ associated to a single data point and corresponding label $(\mathbf{d}_i,l_i)$ is

and the regularized hinge loss over all data points is

Here, the data generation is the same as in Subsection 3.3, with the exception that the labels $\mathbf{l}\in\{-1,+1\}^{m}$. The positive class data points have corresponding binary label $l_i^{\mathrm{clean}}=+1$ and the negative class data points have corresponding binary label $l_i^{\mathrm{clean}}=-1$. This generation of data and labels again ensures that the data is linearly separable before label corruption, which follows the same process as in Subsection 3.3 with the exception that for $i\in O$, the observed label is $l_i=-l_i^{\mathrm{clean}}$.

In the bottom plots below, we again visualize this data in two dimensions, taking the last two components of the data $(\mathbf{d}_i)_{2:}$. We additionally plot the decision boundary of the learned classification models with parameter vector $\mathbf{x}\in\mathbb{R}^3$, $\{\mathbf{y}\in\mathbb{R}^2:x_1+\mathbf{y}^{\mathsf{T}}\mathbf{x}_{2:}=0\}$.

As in Subsection 3.3, the aim in each experiment is to learn a parameter vector $\mathbf{x} \in\mathbb{R}^{3}$ that correctly classifies the data points with uncorrupted labels. In all experiments, SGD, QkL-SGD, and MkL-SGD were run with step size parameter $\eta= 0.01$ and regularization parameter $\lambda= 1$. We again let $\mathbf{x}^{\star}_{\mathrm{clean}}$ represent the iterate $\mathbf{x}_{10000}$ learned by 10000 iterations of SGD on the linearly separable dataset before any labels are flipped. We plot the boundary corresponding to this parameter vector,

This boundary is labeled “Clean” in the following plots.

Assumptions for regularized hinge loss The components of the regularized hinge loss (17) are convex and nonnegative. However, unlike the other model settings, they are not smooth. Due to the regularization, by the definition of strongly convex functions in terms of subgradients, for every nonempty subset $S \subseteq G$, we have that $F_{S}$ is $\lambda/m$-strongly convex. Thus, Assumptions 2.II and 2.IV hold for this model, but Assumptions 2.I and 2.III fail.

Various outlier settings

We now explore the behavior of QkL-SGD on the hinge loss (18) with $q = 1 - \beta$ in a variety of outlier settings.

Few outliers from a single class ($\beta= 0.01$, $q = 0.99$, $k = m$) Our first experiment, with results presented in fig:7a, explores the setting where 1% of the labels, all from the same class, are corrupted (flipped). We compare QkL-SGD with $q = 0.99$ and $k = m$ to SGD and MkL-SGD with $k = m$. We note that although QkL-SGD only slightly outperforms SGD in terms of relative loss $F_{G}(\mathbf{x}_{t})/F_{G}(\mathbf{x}_{0})$ (left plot), it yields a more significantly lower relative error $\lVert\mathbf{x}_{t} - \mathbf{x}^{\star}_{\mathrm{clean}} \rVert_{2}^{2}/\lVert\mathbf{x}_{0} - \mathbf{x}^{\star}_{\mathrm{clean}} \rVert_{2}^{2}$ (center plot) and a cleaner decision boundary (right plot). MkL-SGD has increasing relative loss and stagnating relative error due to difficulties in separating the effects of the good and outlier sets.

Moderate outliers from both classes, ($\beta= 0.05$, $q = 0.95$, $k = m$) In our next experiment, presented in fig:7b, 5% of the labels are flipped, selected uniformly from both classes. We see that QkL-SGD with $q = 0.95$ and $k = m$ substantially outperforms SGD and MkL-SGD with $k = m$ in terms of both relative loss (left plot) and relative error (center plot) convergence. In this case, the decision boundaries learned by SGD and QkL-SGD (right plot) are not significantly visually different, due to possible larger deviations between the bias terms in the learned parameter vectors which are more difficult to differentiate in this visualization. Again, MkL-SGD has increasing relative loss and stagnating relative error.

Moderate outliers from a single class ($\beta= 0.05$, $q = 0.95$, $k = m$) We now consider a more structured form of label corruption where corruptions occur in only the positive class. In the experiment presented in fig:7c, we corrupt 5% of the labels, but only from the positive class. QkL-SGD with $q = 0.95$ and $k = m$ again demonstrates robustness, yielding lower relative loss (left plot) and smaller relative error (center plot) than SGD and MkL-SGD. In the right plot, the QkL-SGD decision boundary is not visibly significantly better than that of SGD, again likely due to differences in the bias term. Again, MkL-SGD has increasing relative loss and stagnating relative error.

Varying $q$ with fixed corruption fraction $\beta$

Figure 8 explores how different quantile values $q$ affect QkL-SGD under a fixed corruption fraction $\beta$. We apply QkL-SGD with $k=m$ to the regularized hinge loss (18) applied to the data model described above where $\beta\in\{0.1,0.2,0.3,0.4\}$ fraction of data sampled uniformly across both classes are corrupted, and plot the final relative loss (left plot) and final relative error (right plot) after 10000 iterations of QkL-SGD with $q \in\{0.05,0.1,\cdots,1.0\}$. Relative loss and relative errors are averaged over 100 independent trials of 10000 iterations of QkL-SGD. Again, in this case, we see that the quantile $q$ producing the lowest relative error and loss values is approximately $1-\beta$. However, in this case, we see that QkL-SGD produces lower final relative loss and error when the corruption fraction $\beta$ is smaller.

Varying Sample Size $k$

We now explore the effect of the sample size $k$ on the behavior of QkL-SGD and MkL-SGD. We first consider the case where $k$ is a fraction of $m$, denoted $\alpha$ in Subsection 3.5.1. We then compare the convergence of QkL-SGD where $k=m$ and MkL-SGD where $k$ is a small constant value as a function of the total number of loss evaluations in Subsection 3.5.2.

Sample Fraction $\alpha$

In this section, we explore how the sample size parameter $\alpha$ affects the convergence of QkL-SGD and MkL-SGD. Figure 9a compares the relative loss and relative error of QkL-SGD and MkL-SGD with sampling rates $\alpha\in\{0.1,0.5,0.9\}$ on the noiseless polynomial regression problem (14). We generate data as described in Subsection 3.1; starting from the uncorrupted dataset, we corrupt 5% of the target values $y_i$ using additive noise drawn from $\mathcal{N}(0,100)$. For this simple problem, we see very little difference in the behavior of MkL-SGD under different sampling rates. QkL-SGD, on the other hand, suffers from increased variance in both loss and error as the sampling rate decreases; the method is likely occasionally sampling a small corrupted component. Regardless, the relative error and relative loss of all QkL-SGD decrease significantly over all iterations.

In Figure 9b, we plot the loss and error over iterations of QkL-SGD and MkL-SGD applied to the polynomial regression loss (14) with sampling rate $\alpha\in\{0.1,0.5,0.9\}$. We generate the ideal (uncorrupted) data as described in Section 3.2 and then sample 5% of the data and corrupt the corresponding targets $y_i$ by large additive noise sampled from $\mathcal{N}(0, 100)$. In this experiment, we again note that MkL-SGD performs better with smaller sampling rate, while QkL-SGD again achieves smaller variance with larger sampling rate.

In the experiment presented in Figure 9c, we generate the uncorrupted data as in Section 3.3. We then sample 5% of the data points for corruption and their labels are flipped. We implement QkL-SGD and MkL-SGD on the regularized logistic regression loss (16) with sampling rate $\alpha\in\{0.1, 0.5, 0.9\}$ and compare the relative loss and relative error across iterations. We note that MkL-SGD suffers when the sample size is large, as selecting the minimum loss components can actually cause the loss and error to increase. On the other hand, QkL-SGD can suffer when the sample size is too small, although the improvement in both loss and error is much better than that of MkL-SGD.

In the experiment given in Figure 9d, we generate the data as in Section 3.4 and then sample 5% of the data and flip the labels associated to these data points. We compare the relative loss and relative error of QkL-SGD and MkL-SGD applied to the regularized hinge loss objective (18) with sample rates $\alpha\in\{0.1, 0.5, 0.9\}$. Again, MkL-SGD suffers when the sampling rate is too large, while QkL-SGD suffers when the sampling rate is too small, although QkL-SGD achieves significantly lower values of loss and error.

In our final experiment presented in Figure 10, we plot the final relative loss or error (after 10000 iterations) for $\alpha\in(0, 1]$ for QkL-SGD and MkL-SGD applied to the polynomial regression, logistic regression, and hinge loss problems described above. We use the same problem set-up described previously in this section for noiseless polynomial regression (top row), noisy polynomial regression (row two), regularized logistic regression (row three), and regularized hinge loss (bottom row). The lines represent the average over 100 independent trials of 10000 iterations, and the shaded ribbon presents the spread of the maximum and minimum final relative losses and errors across the 100 trials. We note that generally MkL-SGD performs best with smaller values of $\alpha$ in terms of both relative error and loss, while QkL-SGD performs best with a larger value of $\alpha$, although the best behavior is for $\alpha< 1$.

Small Sample Size

Noting that MkL-SGD was intended to be used with a very small sample size $k$, we now explore how the loss and error of MkL-SGD and QkL-SGD decrease with respect to cumulative evaluations of loss components. Figure 11a shows the relative loss and relative error measured against the number of loss component evaluations for QkL-SGD with sampling rate $\alpha= 1.0$ and $q = 0.95$ and for MkL-SGD with $k \in\{2, 5, 10\}$ on the polynomial regression problem (14) on the noiseless uncorrupted data. Starting from the baseline dataset described in Section 3.1, we corrupt 5% of the target values $y_i$ using additive noise drawn from $\mathcal{N}(0, 100)$. The results indicate that QkL-SGD attains performance comparable to MkL-SGD with $k = 2$ and $k = 10$ in terms of both relative loss and relative error, while MkL-SGD with $k = 5$ achieves the lowest relative loss and error on this very simple problem.

In Figure 11b, we plot the relative loss and relative error over loss component evaluations of QkL-SGD with sample rate $\alpha= 1.0$ and $q = 0.95$ and MkL-SGD with $k \in\{2, 5, 10\}$ applied to the polynomial regression loss (14). We generate the ideal (uncorrupted) data as described in Section 3.2 and then sample 5% of the data and corrupt the corresponding targets $y_i$ by large additive noise sampled from $\mathcal{N}(0, 100)$. In this case, QkL-SGD and MkL-SGD with $k = 5$ and $k = 10$ achieve similar relative loss. However, QkL-SGD achieves the lowest final relative error.

In the experiment presented in Figure 11c, we generate the uncorrupt data as in Section 3.3. We then sample 5% of the data points for corruption and their labels are flipped. We implement

QkL-SGD with sampling rate $\alpha= 1.0$ and $q = 0.95$, and MkL-SGD with $k \in\{2,5,10\}$ on the regularized logistic regression loss (16) and compare the relative loss and relative error across loss component evaluations. We note that while the MkL-SGD loss and error decrease quickly with respect to loss component evaluations, QkL-SGD eventually achieves lower values.

Next, in the experiment given in Figure 11d, we generate the data as in Section 3.4 and then sample 5% of the data and flip the labels associated to these data points. We compare the loss and error of QkL-SGD with sampling rate $\alpha= 1.0$ and $q = 0.95$, and MkL-SGD with $k \in\{2,5,10\}$ applied to the regularized hinge loss objective (18). In this case, the relative loss and relative error of QkL-SGD decrease at roughly the same rate as MkL-SGD and again eventually achieve lower values for each.

Conclusions and Future Work

We propose a broad framework for optimization on corrupted data through quantile-based loss filtering. Our work shows that the QkL-SGD admits both deterministic guarantees, when the sample size scales with the corruption size, and probabilistic guarantees, in the small sample size regime. Empirically, we show that our framework is effective across several machine learning and optimization problems under a variety of models of corruption.

Many natural extensions remain open. First, QkL-SGD uses a potentially large set of sampled losses only to select a single update index. Since the method has already paid the cost of evaluating $k$ component losses, it is natural to ask whether one can use the accepted lower-tail set more fully, for example by averaging gradients over accepted components or by designing large-batch variants with robust loss filtering. Second, momentum and variance-reduced versions of QkL-SGD may improve practical performance, especially in regimes where the quantile rule successfully filters out large corruptions but the selected good updates remain noisy. Developing convergence theory for such batch, momentum, and adaptive variants are interesting directions for future work.

Acknowledgments

J.H. was partially supported by NSF CAREER #2440040 A.M. was partially supported by the Rose Hills Foundation and Simons Grant MPS-TSM-00014026. E.R. was partially supported by NSF DMS #2309685.

Generative AI tools were used to assist with drafting and refining portions of the manuscript. The authors developed all ideas, numerical results, and conclusions and made all final editorial decisions. The authors reviewed, revised, and take full responsibility for the manuscript’s content.