Sever: A Robust Meta-Algorithm for Stochastic Optimization

Ilias Diakonikolas; Gautam Kamath; Daniel M. Kane; Jerry Li; Jacob Steinhardt; Alistair Stewart

Source-linked AI summary

Sever: A Robust Meta-Algorithm for Stochastic Optimization

Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Jacob Steinhardt, Alistair Stewart

arXiv:1803.02815v2Mar 7, 2018cs.LGcs.AIcs.DSstat.ML

TL;DR

High-dimensional learning is vulnerable to structured and potentially adversarial outliers, while existing robust methods can be difficult to scale or narrowly specialized. Sever hardens a base learner through gradient-based singular-vector outlier detection and removal. On spam and drug-design tasks, Sever showed greater robustness than several baselines under corruption while retaining strong performance on uncorrupted data.

Problem
High-dimensional machine learning methods are sensitive to structured outliers, creating a need for training algorithms robust to an ε-fraction of arbitrary or adversarial outliers.
Method
Sever is a meta-algorithm that fits a base learner, analyzes per-example gradients with a top singular vector, removes high-scoring points, and retrains if needed.
Results
Sever achieved greater robustness than several baselines on spam and drug-design tasks, including 7.3% spam error with 1% outliers and 1.42 mean-squared error with 10% corruptions.
Takeaways & Limitations
Sever combines theoretical robustness with practical use as a scalable plugin for common learning procedures and real datasets.
Takeaways & Limitations
Sever’s theoretical error dependence is O(√ε), while improving it toward O(ε) would require stronger realistic assumptions or more expensive robust-mean-estimation methods.

Abstract

from arXiv · show

In high dimensions, most machine learning methods are brittle to even a small fraction of structured outliers. To address this, we introduce a new meta-algorithm that can take in a base learner such as least squares or stochastic gradient descent, and harden the learner to be resistant to outliers. Our method, Sever, possesses strong theoretical guarantees yet is also highly scalable -- beyond running the base learner itself, it only requires computing the top singular vector of a certain $n \times d$ matrix. We apply Sever on a drug design dataset and a spam classification dataset, and find that in both cases it has substantially greater robustness than several baselines. On the spam dataset, with $1\%$ corruptions, we achieved $7.4\%$ test error, compared to $13.4\%-20.5\%$ for the baselines, and $3\%$ error on the uncorrupted dataset. Similarly, on the drug design dataset, with $10\%$ corruptions, we achieved $1.42$ mean-squared error test error, compared to $1.51$-$2.33$ for the baselines, and $1.23$ error on the uncorrupted dataset.

1 Introduction

Sever addresses the challenge of robust, scalable learning with arbitrary high-dimensional outliers by wrapping standard learning procedures with gradient-based outlier detection. The paper presents Sever as robust, general, and practical, with theoretical guarantees and stronger empirical performance than baseline detectors on biological and security tasks.

High-dimensional machine learning methods are sensitive to structured outliers, motivating algorithms that preserve robustness, accuracy, and running time.
Classical and recent robust-estimation methods often fail to scale, depend on restrictive assumptions, or perform poorly on real high-dimensional data.
Sever is a robust, general, and practical meta-algorithm that handles arbitrary outliers, applies to regression, classification, and non-convex models, and uses standard machine learning libraries.
Sever fits a base learner, computes per-example gradients and their top singular vector, removes points with large projections, and retrains when necessary.
7.3% error was achieved on Enron spam with 1% outliers, versus 13.4%-20.5% for baselines; drug-design error was 1.42 mean-squared error with 10% corruptions, versus 1.51-2.33.

2 Framework and Algorithm

The paper formulates stochastic optimization under ε-contamination and presents Sever, a black-box learner hardened by gradient filtering. Its guarantees are dimension-independent under regularity assumptions and extend to concrete classification and regression applications.

Framework: The framework models training data as functions sampled from a true distribution, with an adversary replacing up to an ε-fraction by arbitrary samples.The theoretical model allows both adding and removing points, whereas experiments use additive corruptions.
Algorithm: Sever runs a black-box learner, computes the per-point gradients at its output, identifies systematic large-gradient directions using singular-value decomposition, removes extreme points, and retrains.The procedure can be iterated until no points are removed.
Theoretical Guarantees: With probability at least 9/10, Sever returns a (γ + O(σ√ε))-approximate critical point of the true objective, with no dependence on dimension d in the error guarantee.For convex objectives, the result further guarantees an approximate global minimum.
Applications: For generalized linear models, the paper gives an additive ˜O(ε1/4) excess-loss guarantee for hinge or logistic classification and an O(√ε) parameter error guarantee for linear regression.The classification result uses n = ˜O(d/ε) corrupted samples; the regression result uses O(d5/ε2) corrupted samples.
Algorithm: Robust gradient estimation can also be viewed as robust mean estimation, motivating a polynomial-time robust stochastic optimization method under fairly general assumptions.This alternative perspective treats gradient descent as being simulated with robustly estimated gradients.

3 Experiments

Sever post-processes a base learner by detecting outliers through gradient projections and iteratively removing high-scoring points. Across synthetic, drug discovery, and spam experiments, it generally outperformed baseline defenses, including under attacks designed to defeat those baselines.

Method: Sever runs a base learner, computes per-point gradients, removes points with large projections onto the gradients’ top singular vector, and retrains as needed.In experiments, filtering used centered gradients, the top singular vector, squared projection scores, and repeated removal.
Experimental setup: The experiments compare Sever with no defense, distance-, loss-, gradient-, centered-gradient-, and RANSAC-based baselines.The ridge-regression experiments used synthetic Gaussian and drug discovery data, while SVM experiments used synthetic Gaussian and Enron spam data.
Ridge Regression: At ε ≈1.5% for synthetic data and ε ≈5.5% for drug discovery data, Sever substantially outperformed baselines under attacks tuned to defeat them.Even when attack parameters were tuned against Sever, its resulting error remained small.
Ridge Regression: 10% outliers were difficult for baseline score rules because outlier scores remained within the uncorrupted distribution, whereas Sever assigned outliers tail scores.This separation made the outliers easier for Sever to detect without removing a large fraction of uncorrupted points.
Support Vector Machines: On synthetic classification attacks targeting loss, Sever nearly matched 5.8% uncorrupted test accuracy while loss exceeded 30% error at 1.5% injected outliers.Against attacks targeting Sever, Sever still achieved at most 9.05% test error.
Support Vector Machines: At ε = 0.01 on Enron, Sever’s worst error was 7.34% versus 13.43%–20.48% for baselines; at ε = 0.03, its error was 13.53%.Across 48 attacks, three filtering iterations reduced the six higher-error cases to at most 7.4%.

4 Discussion

The discussion presents Sever as a robust, practical meta-algorithm while identifying assumptions and directions for improving its data scope, outlier dependence, and representations.

Discussion: Sever combines strong theoretical robustness with good performance on real datasets by recasting learning as robust mean estimation.The paper frames approximate stationarity as a robust mean estimation problem and leverages efficient robust mean estimation techniques.
More general assumptions: The authors propose extending Sever to more general data assumptions and improving its empirical characterization across diverse datasets.They suggest resilience as a possible template for identifying properties that enable robust estimation.
More general assumptions: Sever assumes the top singular value of the data gradients is small, although the evaluated datasets appeared to satisfy this condition.The authors note that practical data may instead contain a few large singular values alongside many small ones.
Stronger robustness to outliers: Sever’s theoretical error depends on the outlier fraction as O(√ε), while practice would ideally support a dependence closer to O(ε).Improving this dependence requires advances in the robust mean estimation primitive used by Sever.
Learning a favorable representation: Sever performs best when features have small covariance and strong predictive power, motivating future work on learning favorable representations robustly.The paper identifies approximately independent predictive features as one setting where this condition holds.

B General Analysis of Sever

The general analysis shows that Sever converts an approximate learner into an outlier-robust optimizer, with guarantees for nonconvex critical points and convex optima under regularity assumptions.

General analysis: Sever finds an approximate critical point of the target function even when the underlying functions are non-convex.The guarantee holds with probability at least 9/10 under Assumption B.1.
General analysis: The analysis begins with deterministic regularity conditions on the uncorrupted data and then establishes that these conditions hold with high probability under mild distributional assumptions.The probabilistic argument uses polynomially many samples.
Definitions: A γ-approximate learner returns a point whose empirical objective is a γ-approximate critical point.Common methods such as stochastic gradient descent satisfy this property according to the paper.
Convex objectives: For convex objectives, Sever’s critical-point guarantee yields approximate global minimization guarantees, including objective and parameter bounds under strong convexity.These results are stated in Corollary B.3 and extended in Corollary B.4.
Strong convexity: In the strongly convex setting, repeatedly applying Sever with decreasing search radii removes dependence on σ1 and r from the resulting guarantee.The iterative procedure shrinks the search region around the estimated optimum.

B.1 Proof of Theorem B.2

The proof establishes Sever’s guarantee by showing its filter removes corrupted points preferentially and that termination implies the empirical gradient is close to the true gradient.

Filtering: The filter removes, in expectation, at least as many corrupted points as uncorrupted points.This comparison is the central property used to control the number of removed good samples.
Termination: When filtering terminates without excessive removal, the empirical gradient is close to the true gradient, completing the approximate critical-point guarantee.The proof combines Lemmas B.6 and B.7 with the base learner’s γ-approximate critical-point property.
Proof strategy: Sever terminates after at most n iterations because every nonfinal main-loop iteration removes at least one point.This bounds the number of filtering rounds independently of the proof’s probabilistic correctness argument.
Filtering: The number of removed samples is controlled by a supermartingale, yielding n − |S| ≤ 11εn with probability at least 9/10.The argument starts from at most εn corrupted points and bounds the accumulated removal of good points.
Convex consequences: For convex functions, approximate criticality translates into objective and distance guarantees through a one-dimensional convexity argument.Strong convexity gives |f(x) − f(y)| ≤ 2δ^2/ξ and ||x − y||2 ≤ 2δ/ξ.

B.3 Proof of Corollary B.4

The proof of Corollary B.4 repeatedly applies Sever on shrinking domains, using strong convexity to reduce the search radius until a final accuracy bound is reached.

Iterative refinement: The iterative method starts with the full domain and applies Sever at a sequence of decreasing radii.Each iteration produces an estimate used to define the next restricted domain.
Iterative refinement: Strong convexity converts each approximate critical-point guarantee into a distance bound from the true optimum.The next radius is chosen around the current estimate using this distance guarantee.
Contraction: The radius recursion contracts when ξ is sufficiently large relative to σ1√ε.The proof assumes ξ ≥ Cσ1√ε for an absolute constant C.
Termination: The procedure stops after at most O(log(r) − log(8γ/ξ + 2Cσ0√ε/ξ)) iterations.At termination, the final iterate satisfies the stated distance guarantee from the optimum.
Scope: The broader analysis notes that explicit bounds on calls to the approximate learner require additional assumptions on the individual functions.For linear regression, a closed-form least-squares minimum can instead be exploited even when a Lipschitz constant is not small.

C Analysis of Sever for GLMs

This section extends Sever’s robust stochastic optimization analysis to generalized linear models, including applications such as SVMs and logistic regression. Under stated regularity and link-function conditions, the analysis establishes high-probability guarantees for Sever.

GLMs are highlighted as an important case covering applications including SVMs and logistic regression.
The GLM is defined through convex link functions and an expected loss over samples drawn from Dxy.
The analysis seeks to approximately minimize the population objective using ε-corrupted samples, with H contained in a radius-r ball.
Assumption C.1 requires an unknown set containing at least (1 − ε)n good functions satisfying specified regularity conditions.
The section proves both that Assumption C.1 implies Sever succeeds and that the assumption holds after polynomially many GLM samples.
Under Assumption C.1, Theorem C.2 gives a probability-at-least-9/10 guarantee for finding a point w ∈ H with the stated objective bound; strong convexity yields a corresponding guarantee.
For GLM samples satisfying the listed conditions, Proposition C.3 shows that, with probability at least 9/10, a (1 − ε)n subset satisfies Assumption C.1 with σ0 = 2, σ1 = 0, and σ2 = 1 + r.

C.1 Proof of Theorem C.2

The proof of Theorem C.2 first establishes that Assumption C.1 induces the regularity conditions needed by Sever, then transfers Sever’s approximate critical-point guarantee to the population objective.

Sever either terminates or discards at least one sample per iteration, so it cannot run for more than n iterations.
Lemma C.4 shows that, under Assumption C.1, Sever returns a (γ + O(σ0√ε))-approximate critical point with probability at least 9/10.
The lemma proves that the empirical function satisfies Assumption B.1 with the same good set and σ1 = 0, enabling application of Theorem B.2.
Conditioning on Lemma C.4, the proof uses Assumption C.1 to relate the empirical objective at Sever’s output and at the population minimizer.
Convexity converts the approximate critical-point guarantee into the stated population objective bound, while the strongly convex case follows by using the corresponding strongly convex lemma.

C.2 Proof of Proposition C.3

The proof of Proposition C.3 verifies the GLM regularity conditions through spectral control, truncation, concentration, and a covering argument over the parameter domain.

The proof bounds gradient fluctuations through a matrix inequality whose final expression is independent of w.
The good set consists of uncorrupted samples satisfying a norm bound, and covariance control over this set supplies the required spectral bound.
Removing an additional ε-fraction changes the relevant gradient variance by at most 3ε/2.
Because the sample losses are 1-Lipschitz, uniform control over H is reduced to control on an ε/2-cover.
The covariance bound limits the contribution of samples with large |Xi · w|, after which concentration controls the remaining truncated sample average.
For n at least a sufficiently large multiple of d log(dr/ε)/ε, the concentration bound holds across the cover with high probability.

D An Alternative Algorithm: Robust Filtering in Each Iteration

This alternative algorithm repeatedly estimates gradients robustly and feeds them into projected gradient descent. It supports weaker conditions than Sever but is slower in practice because filtering is repeated over the dataset.

Alternative algorithm: The alternative method computes approximate gradients with robust mean estimation and uses them in projected gradient descent.
Alternative algorithm: Unlike Sever’s single shared good set, this method allows a potentially different good set Igood(w) for each parameter w.
Robust mean estimation: Theorem D.2 supplies an efficient robust mean estimator with estimation error O(σ√ε).
Algorithmic interface: The general algorithm treats robust mean estimation and projection onto H as black-box operations, measuring cost by their total number of calls.
Comparison with Sever: The method is conceptually simpler and works under somewhat more general assumptions, but Sever is preferred practically because it often needs only a constant number of base-learner runs.
Comparison with Sever: Sever’s black-box non-robust learner interface enables problem-specific optimization, including optimized libraries for linear regression and SVM.
Comparison with Sever: The alternative requires at least linear time per stochastic-gradient iteration because it robustly processes the entire dataset each time.
Applications: The framework is instantiated for robust linear regression, support vector machines, and logistic regression.

E.1 Linear Regression

This section applies Sever to linear regression, formalizes the squared-loss setting and assumptions, and derives robustness guarantees through gradient-covariance bounds.

Linear regression uses squared loss f_i(w) = (Y_i − ⟨w, X_i⟩)^2, with samples generated by Y_i = ⟨w∗, X_i⟩ + e_i.
The analysis assumes conditions on the feature and noise distributions, including bounded covariance and moment properties.
The main theorem gives an algorithm that, with probability at least 9/10, produces an approximate minimizer under the stated assumptions.
If ∥w∗∥2 ≤ r, the resulting objective value is bounded by the optimum plus an error term depending on ξ, ε, and r.
The proof bounds the covariance of per-example gradients by decomposing signal, noise, and covariance terms.
For linear regression, the gradient covariance equals 4 E_x[⟨w∗−w,x⟩^2(xx^T)] + 4 Var[e]Σ − 4Σ(w∗−w)(w∗−w)^TΣ.
These bounds supply the parameters required by the meta-theorem, completing the linear-regression guarantee.

E.1.2 Proof of Lemma E.4

This proof establishes the sample conditions needed for the robust framework and then applies the framework to support vector machines and logistic regression under distributional assumptions.

Proof of Lemma E.4: The proof removes high-norm samples and defines an uncorrupted subset to control empirical moments.
Proof of Lemma E.4: With high probability, the retained uncorrupted samples satisfy the covariance and moment conditions required by Lemma E.3.
Proof of Lemma E.4: Expectation differences caused by removing samples are bounded using a mixture-distribution inequality and variance control.
Proof of Lemma E.4: The proof bounds both feature-covariance deviation and the noise-feature term, obtaining parameters σ0 = 30√ξ + √ε and σ1 = 18√C.
E.2 Support Vector Machines: For SVMs, the method uses hinge loss, sub-gradients, a bounded parameter ball, and ε1/4-anticoncentration of the feature distribution.
E.2 Support Vector Machines: Given O(d log(d/ε)/ε) ε-noisy samples, the SVM guarantee holds with probability 9/10 and excess expected hinge loss O(ε1/4).
Logistic Regression: The same framework is extended to logistic regression under its corresponding assumptions.

F Additional Experimental Results

The additional experiments compare Sever with baselines across synthetic, drug-discovery, and Enron spam settings under attacks varying the corruption fraction ε.

Figure 7 plots ε against test error for baselines and Sever on synthetic data and the drug discovery dataset.
On synthetic and drug-discovery attacks that defeat previous baselines, Sever maintains statistical accuracy.
Even under an attack optimized to increase Sever’s drug-discovery test error, Sever retains relatively small test error.
Figure 8 shows that Sever remains accurate on synthetic data when outliers defeat previous baselines and performs much better under attacks targeting Sever.
Figure 9 compares ε with test error on Enron using attacks optimized against two baselines and against Sever.
Sever is consistently accurate on Enron, except for certain ε = 0.03 attacks where the defenses use two rather than the three required removal rounds.