Robust learning methods that run at scale, such as SEVER, defend against poisoned training data by examining the second moments of per-example gradients. A second moment here means the covariance, which measures how much the gradients spread out in each direction. The defense finds the direction of largest spread and removes the examples that stick out along it. This leaves a known blind spot. An attacker who keeps the gradient covariance within its normal range can still shift the learned model by up to roughly $\sqrt{\epsilon}$, where $\epsilon$ is the fraction of corrupted data. Theory for "certifiable hypercontractivity" narrows that blind spot. Hypercontractivity is the property that clean data's fourth moments are controlled by its second moments. "Certifiable" means this control can be proven with simple polynomial algebra, specifically a low-degree Sum-of-Squares (SoS) proof. With such a certificate, attacks whose damage is larger than about $\epsilon^{3/4}$ can be detected. The catch is that the algorithms achieving this are large semidefinite programs, which do not run on real datasets.
This note proposes to take the simplest SoS certificate of fourth-moment control and use it directly as a filter. The certificate reduces to one number: the top eigenvalue of the covariance of the whitened outer products $gg^\top - I$, where $g$ is an example's gradient. We apply it to per-example gradients inside a SEVER-style loop. The filter removes examples that load heavily on the violating direction. It stops only when the degree-4 certificate holds on the examples that remain. The central empirical claim is falsifiable. For attacks that match the gradient covariance, there is a window of attack strength, with model damage between about $\epsilon^{3/4}$ and $\epsilon^{1/2}$. Inside that window, SEVER is blind by construction and the degree-4 filter is not. Outside the window, the two should be indistinguishable. The note also states plainly where the added cost, especially the need for many more samples, can make the method not worth using.
Core Claim
Whiten the gradients $g_i$ using a robust covariance estimate, and let $V$ range over symmetric $d\times d$ matrices with $\|V\|_F=1$. The degree-4 statistic is
$$\lambda_4 \;=\; \max_{V}\; \frac{1}{|S|}\sum_{i\in S}\big(g_i^\top V g_i - \mathrm{tr}\,V\big)^2 ,$$
where $S$ is the current set of retained examples. For Gaussian data this quantity equals 2. For certifiably 4-hypercontractive data it is bounded by a constant $C$, and the fact that it can be computed as an eigenvalue is exactly what makes it a degree-4 SoS certificate.
The attack model is as follows. The adversary shifts the gradient mean by $\delta$ along a unit direction $u$ using an $\epsilon$-fraction of points. Those points must sit at distance about $\delta/\epsilon$ along $u$. They therefore add about $\delta^2/\epsilon$ to the variance along $u$ and about $\delta^4/\epsilon^3$ to $\lambda_4$ at $V=uu^\top$.
- The variance increase is invisible to a covariance filter whenever $\delta\lesssim\sqrt{\epsilon}$.
- The $\lambda_4$ increase breaks the certificate once $\delta\gtrsim\epsilon^{3/4}$.
The window between these two scales is where a degree-4 filter should win. The prediction is sharp enough to fail. If SEVER already resists covariance-matching attacks in this window on real data, the proposal's rationale collapses.
Relation to Prior Work
The certifiability results supply the mathematical justification. SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications proves that every subgaussian distribution has low-degree SoS certificates and derives $\epsilon^{1-1/m}$ robust mean estimation. Robust Linear Regression: Optimal Rates in Polynomial Time reaches optimal regression rates under $k$-hypercontractivity with an $n^{O(k)}$-time SoS program. Efficient Algorithms for Outlier-Robust Regression introduced the degree-4 certifiable-hypercontractivity approach for regression under corruption of both inputs and labels, with a $\sqrt{\eta}$-type bound. All three solve full SoS relaxations over pseudo-distributions. We use only the single spectral inequality at the bottom of that hierarchy, and we apply it to gradients rather than raw covariates. That is how the idea transfers from linear regression to general models trained by gradient descent.
The scalable-filtering results supply the algorithmic template and the main competitor. Sever: A Robust Meta-Algorithm for Stochastic Optimization filters on the top singular vector of centered gradients and carries an $O(\sqrt{\epsilon})$ guarantee. Robust Regression Revisited: Acceleration and Improved Estimation Rates moves SoS identifiability arguments into SEVER and gets $O(\sigma\sqrt{\kappa\epsilon})$ regression error. That paper also constrains this proposal. Its improvement costs $n\approx d^2$ samples, and our flattened fourth-moment statistic concentrates only at the same scale. We treat this as a limit on our method, not something to work around. Our contribution relative to Jambulapati et al. is not a better sample complexity. It is a certificate-based stopping rule, an extension beyond linear regression, and an empirical test of whether the degree-4 window exists on real data.
Tester-Learners for Halfspaces: Universal Algorithms motivates a secondary use of the statistic. That paper tests certifiable hypercontractivity before trusting a learner. Borrowing the idea, $\lambda_4$ measured on held-out data we trust tells us whether the degree-4 filter is valid at all. Heavy-tailed gradient distributions would fail this test, and there the filter should not be used. Learning large-margin halfspaces with more malicious noise shows that convex losses alone cannot tolerate malicious noise. This is why the filter wraps a standard training procedure rather than replacing the loss.
Research Program
The algorithm alternates two steps: fit the model on the retained set $S$, then compute per-example gradients. At each round it first runs SEVER's degree-2 check. It then computes $\lambda_4$ by power iteration on the operator $V\mapsto \frac{1}{|S|}\sum_i (g_i^\top V g_i-\mathrm{tr}V)(g_ig_i^\top - I)$.
- Cost. Each power-iteration step costs $O(|S|d^2)$ and never forms the $d^2\times d^2$ matrix. For ChEMBL at $d=410$ this is routine on a GPU.
- Filtering. If $\lambda_4$ exceeds a threshold $C$ calibrated on trusted data, each example is scored by $(g_i^\top V^\star g_i-\mathrm{tr}V^\star)^2$. Examples are removed at random with probability proportional to this score, as SEVER does.
- High dimensions. For Enron ($d>5{,}000$) we first project gradients onto a random subspace of dimension $r$ ($r$ from 200 to 800). This keeps $r^2$ comparable to $n$. It is a deliberate approximation, and we measure its cost.
The theory is kept narrow on purpose. For mean estimation and for linear regression with certifiably 4-hypercontractive covariates, we aim to prove that the filtered estimator reaches error of order $\epsilon^{3/4}$ with $n=\tilde O(d^2)$ samples. The argument should follow the stability approach of Optimal Robust Estimation under Local and Global Corruptions, which shows that stability arguments survive stronger adversaries. We do not claim to match the SoS rates of Bakshi and Prasad, nor to break the $d^2$ sample barrier. For nonconvex models we make only the empirical claim.
The attack construction matters as much as the defense. We build a covariance-matching poisoner, a nasty-noise adversary that sees the clean data. It adds points that shift the gradient mean by $\delta$ along a chosen direction. It deletes clean points with large $u$-projections so that the retained gradient covariance stays within SEVER's threshold. Sweeping $\delta$ traces out the predicted window.
Baselines
No defense. The naive reference is ordinary training on the poisoned data. SEVER reports a 3% error rate on clean Enron, which serves as the floor for all methods.
SEVER. The strongest existing scalable method is Sever. It is the closest competitor because our method is SEVER plus one additional check, so any gain must come from the degree-4 statistic. Reported results give the reference points:
- Enron, 1% outliers: SEVER 7.3% error, other defenses 13.4% to 20.5%.
- ChEMBL, 10% corruption: SEVER MSE 1.42, baselines 1.51 to 2.33.
- Synthetic Gaussian ($d=500$): no reported numerical result found on Lacuna; the paper reports only a flat error curve.
We will rerun SEVER ourselves on identical splits, attacks, models, and filtering budgets. Its threshold and number of rounds will be tuned on the same trusted validation set used to calibrate our $C$. Wall-clock time for both methods will be reported.
What counts as beating SEVER. Three conditions must all hold:
- Under the covariance-matching attack in the predicted $\delta$ window, our method achieves clearly lower test error or MSE than rerun SEVER across seeds.
- On SEVER's original attacks, our method is no worse than rerun SEVER.
- Our method removes no more clean points than SEVER does.
Acceleration-based estimator. The robust regression method of Robust Regression Revisited is included on the regression tasks. It is the strongest first-order method that already uses SoS-style arguments. No reported empirical result was found on Lacuna for it.
Diagonal kurtosis filter (ablation). This scores each example by $\|g_i\|^4$ after whitening. It uses fourth moments but not the eigenvector structure of the certificate. If it matches our method, the SoS certificate is not the ingredient doing the work.
Exact degree-4 SoS (ablation at small $d$). For $d\le 12$, we solve the full degree-4 SoS program to measure how much the spectral shortcut gives up.
Why not just…?
Why not just use SEVER with a tighter threshold? Lowering SEVER's threshold does not help against an attack that holds the covariance at its clean value. There is nothing extra in the second moment to detect, so tightening only removes more clean data. The experiment tests this directly: SEVER is swept across thresholds on the covariance-matching attack, and we report its best error against clean points removed. If some threshold setting closes the gap, the proposal fails, and we will report that.
Why not just run the real SoS estimator? The estimator of Robust Linear Regression: Optimal Rates in Polynomial Time runs in $n^{O(k)}$ time, and the authors of SoS Certifiability of Subgaussian Distributions leave practical realizations of these methods open. We run it only where it fits, at $d\le12$. This settles whether the higher SoS levels buy measurable accuracy beyond the single spectral certificate.
Why not just use classical robust methods like Huber loss, RANSAC, or coordinate clipping? SEVER's own experiments already show these methods at 13.4% to 20.5% error on Enron and MSE of 1.51 to 2.33 on ChEMBL. Coordinate clipping cannot see perturbations spread thinly across many coordinates. These methods are included only as reference rows.
Why not just score points by their squared gradient norm? This is the most serious simple competitor for data resembling what we will test. A shift concentrated on a few examples inflates their norms, and a norm score needs no power iteration. It fails when the adversary spreads the shift across directions that are individually normal. The diagonal-kurtosis ablation measures whether real attacks do that. If it ties with our method on every attack, we will conclude that the eigenvector structure is not needed.
Proposed Experiments
Data. We use three settings:
- Synthetic Gaussian and Student-t covariates at $d\in\{50,200,500\}$, following SEVER's synthetic setup. The Student-t cases have degrees of freedom chosen just above and just below 4, so fourth moments are barely finite or infinite.
- ChEMBL regression at $d=410$ (Mayr et al.).
- Enron spam classification (Klimt and Yang) with random projection.
Each setting is tested against SEVER's original attacks and our covariance-matching attack at $\epsilon\in\{0.01,0.05,0.1\}$.
Metrics. We report test error or MSE, parameter error against the clean-data fit, fraction of clean points removed, and runtime.
Decisive check: the predicted window. Plot error against attack strength $\delta$ on a log scale. The prediction is that SEVER's error rises from around $\delta\approx\epsilon^{3/4}$ onward while ours stays flat, and that the two curves merge above about $\sqrt{\epsilon}$. The boundaries should move with $\epsilon$ at the predicted slopes.
Decisive check: the certificate as a validity test. On clean Student-t data with fewer than four degrees of freedom, $\lambda_4$ on trusted data should fail calibration. If our filter is run anyway, it should remove too many clean points. That result would confirm the test is needed rather than decorative.
Decisive check: sample size. Sweep $n/d^2$ on the synthetic data and measure where the clean-data $\lambda_4$ stabilizes. On Enron, measure how much of the gain survives as the projection dimension $r$ shrinks. If the gain disappears whenever $n\ll d^2$, the method is limited to moderate dimensions, and the note will say so.
References
- SoS Certifiability of Subgaussian Distributions and Its Algorithmic Applications
- Robust linear regression: optimal rates in polynomial time
- Efficient Algorithms for Outlier-Robust Regression
- Sever: A Robust Meta-Algorithm for Stochastic Optimization
- Robust Regression Revisited: Acceleration and Improved Estimation Rates
- Tester-Learners for Halfspaces: Universal Algorithms
- Learning large-margin halfspaces with more malicious noise
- Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Error
- Large-scale comparison of machine learning methods for drug target prediction on ChEMBL
- Introducing the Enron Corpus