Robust stochastic optimization: RGD vs. SEVER

Course research · Yale CPSC 561 · Spring 2025

Ordinary least squares has no defense against a saboteur. Let an adversary move even 1% of your training points and the fitted parameters can be dragged arbitrarily far from the truth. Robust statistics has algorithms that buy that accuracy back. I implemented two of them, Robust Gradient Descent and SEVER, added a hybrid of the pair, and ran them head-to-head while corrupting anywhere from 0 to 50% of the data. There is no single winner: which defense holds up depends on what the bad points look like, and the two winners trade places when the corruption changes shape.

The setting: an adversary owns an ε-fraction of your data

Classical estimation minimizes a population risk: pick the θ that minimizes the expected loss E[ℓ(θ, z)] over samples z drawn from a distribution. In practice you never see the population, so you minimize the loss on your sample instead. That substitution, empirical risk minimization, is fine when the sample looks like the population. Its guarantees lean on light tails: if the data is roughly sub-Gaussian, the empirical gradient concentrates around the true one and the fit lands where it should.

The robust question is what happens when that assumption is a lie. The model here is ε-contamination: your data is drawn from (1−ε)·P + ε·Q, where P is the clean distribution and Q is arbitrary. An adversary who knows your estimator gets to pick an ε-fraction of the points and place them wherever hurts most. The corruption is of data points, but it does its damage through the gradients those points produce: to bend the fit, a bad point has to pull on it, and that pull is a gradient contribution. So the whole fight happens in gradient space.

The test bed is kept plain on purpose. Ridge regression (least squares with a penalty that keeps the coefficients from blowing up) to recover a true parameter vector θ* in 500 dimensions, from 5,000 Gaussian samples with a little label noise (standard deviation 0.1, so the best achievable test MSE is 0.01). On uncorrupted data the fit is nearly perfect: parameter error about 0.03. Then the adversary replaces a slice of the points, and naive ridge collapses. At just ε = 1% its parameter error jumps to about 1.0, no better than returning zeros. Everything below is about getting the fit back.

Both defenses reduce to the same problem

Here is the observation both papers are built on. Estimating the population-risk gradient from your sample is a mean-estimation problem: the true descent direction is the average gradient over the clean distribution, and all you have is a contaminated sample of gradients to average. So a robust optimizer is really a robust mean estimator in disguise. If you can estimate the mean of a set of vectors when an ε-fraction of them are adversarial, you can optimize robustly by feeding that estimate to gradient descent.

RGD and SEVER are two ways to spend that idea, and they differ in where they put the robustness. RGD hardens the optimizer and keeps every point; SEVER hardens the data and throws points away. The way I put it in my writeup: SEVER is a version of RGD where many steps of gradient descent are applied between rounds of robust mean estimation. RGD re-hardens every single step; SEVER hardens rarely and lets a plain solver run in between.

How RGD works

RGD, from Prasad et al. (2018), is ordinary gradient descent with one substitution: at each step, replace the sample mean of the gradients with a robust mean, then take the step as usual. The corrupted points still contribute their gradients, but the robust mean refuses to be dragged by a small fraction of extreme ones, so the descent direction stays honest.

The robust mean estimator, for the ε-contamination case, is the Huber Gradient Estimator built on an idea from Lai, Rao & Vempala (2016): robust mean estimation is easy in one dimension. In 1-D you can just trim the tails, or take a median, and a small fraction of outliers cannot move the answer much. The problem is only hard in high dimensions, because an adversary can hide the shift across many coordinates. The fix is to find the few directions where the corruption actually pushes the mean, handle those directions robustly, and use the plain mean everywhere else:

• Keep the points inside the smallest ball that contains about a (1−ε) fraction of them, discarding the gross outliers in norm.
• If the data is one-dimensional, return its mean. This is the base case where robust estimation is trivially safe.
• Otherwise split the space. Project onto the top half of the principal-component directions, the subspace V where the variance (and any adversarial shift) concentrates, and recurse there. In the orthogonal complement W, where the adversary has no room to hide, just take the plain mean. Return μ̂_V + μ̂_W.

Recursively hunting for the subspace where corruption lives is what makes RGD good at dispersed, isotropic outliers: extreme points scattered in many directions raise the variance conspicuously, and the recursion follows that variance to them. (The heavy-tailed variant of RGD swaps this estimator for a geometric median-of-means, from Minsker (2015), but the experiments here are all in the ε-contamination setting.) I used a pared-down version of the estimator, dropping the confidence-parameter machinery: enough to capture the mechanism, not a line-for-line reproduction of the paper.

How SEVER works

SEVER, from Diakonikolas et al. (2019), is a meta-algorithm that wraps any base learner and filters the data between rounds. It needs almost nothing from the learner: just that it returns a γ-approximate critical point, a w where the average gradient is nearly zero. No convexity required, which is why SEVER composes with things RGD cannot. Each round goes:

• Run the learner to convergence at some w. Stack the centered gradients into a matrix G, where row i is ∇f_i(w) minus the mean gradient.
• Take the top right singular vector v of G, the single direction along which the gradients vary most.
• Score each point by how far its gradient sticks out along that direction: τ_i = ((∇f_i(w) − mean)·v)². Remove the highest scorers, and repeat until a round removes nothing.

The reason this works is a constraint on the adversary. For a set of outliers to actually bias the fit, their gradients have to be both large and aligned: pulling in a common direction is the only way to move the mean gradient, and a bias in the mean gradient is the only way to move the solution. But a common direction of large gradients is exactly a dominant singular vector. The corruption that does damage is the corruption that lights up v, so scoring against v catches precisely the points that matter. That makes SEVER strong against coherent, directional attacks, the kind engineered to look ordinary point-by-point.

Following the paper’s own experiments, my implementation uses the empirical variant of the filter: a fixed number of rounds (4), removing the top p-fraction of scorers each round, rather than the randomized-threshold filter from the theory. Its only knobs are an estimate of ε and the round count.

A hybrid: SEVER around RGD

The obvious next move is to stack them. My hybrid, SEVER+RGD, runs SEVER’s filtering loop but swaps the inner solver from plain ridge to RGD, so every round already descends with a robust gradient and the filter peels off whatever slips through. If robustness composes, the hybrid should dominate both parents. I built it and ran it, and the result is one of the more interesting findings below.

Two kinds of outlier, chosen to break different filters

Everything downstream hinges on what the adversary is allowed to do. RGD catches outliers that give themselves away by their size; SEVER catches the ones that give themselves away by pulling in a common direction. To make that contrast bite, I tested the two standard threat models that target those two blind spots:

• Isotropic, high-leverage junk (following Prasad et al.): with θ* all ones, corrupt covariates are drawn from a hugely inflated Gaussian, N(0, d²). Each bad point is individually extreme, flung far out into feature space, but they share no common direction. This is the case a distance filter and RGD’s variance-hunting recursion should love: the points are conspicuous by their norm.
• Adversarial, directionally-coherent (following Diakonikolas et al. 2017): with a random θ*, the bad points are constructed as X_bad = (1/(α·ε·n))·yᵀX + noise with labels y_bad = −β, tuned so the corruption drives the ridge fit toward θ̂ = 0. The trick is that these outliers are low-leverage: their norms are even smaller than clean data, so an ℓ₂-distance filter is blind to them. They do their damage by being coherently aligned, not by being big. This is the attack SEVER was designed to catch.

That is the whole point of running both. The ℓ₂ filter is a one-liner that catches the first model instantly and cannot see the second at all, because “far from the mean in distance” and “coherent in gradient” are different signals. Here are the actual results, median parameter-recovery error and test MSE across the sweep, from my runs. Toggle the outlier model and the metric, and click the legend to isolate a method:

Reading it

On aligned outliers, SEVER holds the clean floor best: about 0.04 parameter error and about 0.012 MSE all the way out to ε = 25%, with plain RGD a close second. Naive ridge and RANSAC (the classic robust-regression trick of fitting on random subsets and keeping the best consensus) are gone by ε = 1%. The simple ℓ₂-distance filter tracks SEVER until about ε = 9% and then falls off a cliff, exactly where the adversary tuned the outliers to overlap the clean data in ℓ₂ distance. The filter’s blindness is by construction, and you can watch it hit.

On high-variance junk, the ranking inverts. The trivial ℓ₂ filter is suddenly the best of the bunch (MSE 0.011–0.016 across almost the whole sweep, 0.067 even at ε = 50%): the outliers are so far out in feature space that distance-to-the-mean catches them instantly. Plain RGD is the most consistent of the gradient-based methods, holding near the floor through ε = 25% (0.029 MSE). SEVER degrades earlier here (1.09 MSE at ε = 25%), because incoherent junk gives it a weaker singular-vector signal to lock onto. And the hybrid I hoped would combine both strengths is meaningfully worse than plain RGD at high contamination: 12.98 vs. 0.029 MSE at ε = 25%. It inherited the weaker parent.

At ε = 50% everything collapses, but not in the same way on both datasets, so it is worth being precise. On high-variance junk the RGD-based methods diverge numerically, RGD to about 19.3 MSE and the hybrid to about 426, while SEVER blows up to about 435. On aligned outliers the RGD-based methods run off to roughly 10³⁷, while SEVER only fails up to its natural ceiling of about 1.3 (the point where the attack has driven the fit to zero). These blow-ups are an artifact of pushing a simplified implementation past where the theory guarantees anything, and I’ve kept them in the plot rather than trimming them away.

What the theory says, at a readable level

The experiments and the guarantees agree, and the guarantees explain both why the two methods land so close and why they are not interchangeable. Both hit the same leading dependence on the contamination level, O(√ε), which is the information-theoretic floor for ε-contamination: below some error you simply cannot go, because the adversary can make a corrupted problem look identical to a clean one shifted by that much. RGD carries an extra log d factor on top. The catch is that the two guarantees are stated in different currencies (different sample counts, dimension dependence, and probability), so they are not directly comparable, and the paper concludes the choice “depends on sample availability and empirical success.”

SEVER is a little easier on its assumptions. Its ε-contamination guarantee needs only bounded 4th moments on the covariates and 2nd on the noise, where RGD’s Huber-estimator route asks for 8th and 4th, and the same SEVER analysis covers the heavy-tailed setting too. RGD’s τ_l and τ_u are the strong-convexity and smoothness constants of the loss, which is also why RGD needs the loss to be strongly convex at all: it is doing gradient descent on the objective, so the objective has to be well-behaved. SEVER only asks its base learner to reach a near-critical point, which is a much weaker demand and is what lets it wrap non-convex learners.

Runtime: SEVER filters rarely, RGD hardens constantly

The same frame predicts the running times. Robust mean estimation is the expensive part, and RGD pays for it at every gradient step, while SEVER pays only once per filtering round and lets a cheap solver run in between. At ε = 10% on the high-variance data (median seconds): naive ridge 0.03, the simple filters 0.17–0.21, SEVER 1.31, RANSAC 2.32, RGD 46.24, and the SEVER+RGD hybrid a distant last at 212.51. SEVER comes in about 35× faster than RGD. The hybrid pays both costs at once, running RGD’s per-step estimator inside every one of SEVER’s rounds, so it is not only the least accurate but also the slowest thing in the study.

The exact setup

The whole study is one self-contained script; the source is on GitHub. Synthetic Gaussian design, n = 5000, d = 500, ridge penalty λ = 5.0 (≈ d·σ²), the two outlier generators behind a config flag, and every cell reported as the median of 3 seeds. Eight estimators are compared: uncorrupted ridge, the three simple filters (by covariate norm, by loss, by centered-gradient norm), RANSAC, RGD, SEVER, and the hybrid.

eps_grid = [0, .01, .02, .03, .04, .05, .06, .07, .08, .09, .10, .25, .50]
methods  = [naive_ridge, l2_filter, loss_filter, gradcov_filter,
            RANSAC, SEVER, RGD, SEVER_RGD]   # 8 estimators, 2 metrics

for eps in eps_grid:                 # median over 3 seeds
    X, y, w_star = make_data(n=5000, d=500, eps=eps, outliers=OUTLIER_MODEL)
    for m in methods:
        w_hat = m.fit(X, y, eps)
        record(test_mse(w_hat), param_error(w_hat, w_star))
# OUTLIER_MODEL: "aligned" (DKK) or "high_variance" (N(0, p^2))

A few honest limits. The SEVER I ran is the simplified version, fixed rounds and top-p removal rather than the randomized-threshold filter, and I simplified RGD’s estimator too. The experiments cover the ε-contamination setting only; the heavy-tailed case is discussed but not tested. It is linear regression on all-synthetic data, three seeds per point.

What the comparison shows

“Robust” on its own does not say much. It always means robust against some specific kind of corruption, and the best defense flips depending on which kind you expect. The one line I would keep is that RGD hardens the optimizer while SEVER removes the corrupted data, and that framing predicts the rest: SEVER is cheaper and cleaner against coherent attacks, RGD holds up better against dispersed junk, and the hybrid is the part I got wrong. I expected two robust methods to stack; instead the SEVER filter kept discarding data that RGD would have used, so the composition mostly tracked its weaker half and cost more than either parent. The more promising direction is not stacking them but improving the shared ingredient: a better robust mean estimator lifts both, and SEVER could be taught to filter on vulnerable subspaces the way RGD’s estimator already does.

References: Prasad, Suggala, Balakrishnan & Ravikumar, Robust estimation via robust gradient estimation (2018); Diakonikolas, Kamath, Kane, Li, Steinhardt & Stewart, SEVER: A robust meta-algorithm for stochastic optimization (ICML 2019); Diakonikolas et al., Being robust (in high dimensions) can be practical (2017); Lai, Rao & Vempala, Agnostic estimation of mean and covariance (2016); Minsker, Geometric median and robust estimation in Banach spaces (2015).