Sever Spectral Gradient Filtering Meta-Algorithm for Robust Stochastic Optimization
Algorithms AIMech:SeverSpectralGradientFilteringMetaAlgorithmForRobustStochasticOptimization DRAFT
Aliases: Sever Robust Meta-Algorithm for Stochastic Optimization, Sever Spectral Outlier Gradient Filtering, Sever SVD Gradient Filtering Meta-Algorithm
An outlier-robust stochastic optimization meta-algorithm that iteratively invokes a black-box gamma-approximate learner L on the current active sample subset S subseteq {1, ..., n} to obtain parameters w = L({f_i}_{i in S}), forms the |S| x d matrix of centered sample gradients G = [nabla f_i(w) - nabla_hat]_{i in S} where nabla_hat = (1/|S|) sum_{i in S} nabla f_i(w), computes the top right singular vector v of G, scores each sample by its squared spectral projection tau_i = ((nabla f_i(w) - nabla_hat) . v)^2, and filters out high-scoring outliers whenever the total spectral variance exceeds a threshold before re-running the base learner until convergence.
Identity Notes & Concept Scope
Introduced by Diakonikolas, Kamath, Kane, Li, Steinhardt, and Stewart (ICML 2019, PMLR 97:1596-1606, arXiv:1803.02815). Distinct from every-iteration robust-mean-estimation projected gradient descent (Appendix D; Prasad et al. 2018), which calls a robust mean estimator at every gradient step rather than only at approximate critical points of a black-box learner. Also distinct from client-update Byzantine federated aggregation rules such as DnC (AIMech:DncDivideAndConquerSpectralByzantineRobustAggregation), Multi-Krum (AIMech:KrumAndMultiKrumByzantineResilientGradientAggregation), and Bulyan (AIMech:BulyanByzantineResilientGradientAggregation), which aggregate distributed worker updates in a single communication round rather than iteratively filtering training examples around a black-box empirical risk minimizer.
Claims & Grounded Evidence
4 Claims
Mechanism
#c1-mechanism-svd-centered-gradient-outlier-filtering
At each outer iteration on active index set S subseteq {1, ..., n}, Sever runs the gamma-approximate learner w <- L({f_i}_{i in S}), computes the empirical mean gradient nabla_hat = (1/|S|) sum_{i in S} nabla f_i(w) and centered gradient matrix G = [nabla f_i(w) - nabla_hat]_{i in S} in R^{|S| x d}, extracts the top right singular vector v of G, computes outlier scores tau_i = ((nabla f_i(w) - nabla_hat) . v)^2, and if sum_{i in S} tau_i > c * sigma, draws T ~ Unif[0, max_i tau_i] (or removes the top p fraction of scores) to update S <- {i in S : tau_i < T} until no points are removed.
Scope
#c2-scope-dimension-independent-approximate-critical-point
Under the epsilon-contamination model (Definition 2.1), if the uncorrupted sample set I_good subseteq [n] (|I_good| >= (1 - epsilon)n) satisfies bounded gradient covariance Cov_{I_good}[nabla f_i(w)] <= sigma^2 I and bounded empirical mean gradient deviation ||nabla f_hat(w) - nabla f_bar(w)||_2 <= sigma * sqrt(epsilon), Sever terminates in at most n iterations and returns with probability at least 9/10 a (gamma + O(sigma * sqrt(epsilon)))-approximate critical point of the true population objective f_bar(w), achieving an error guarantee independent of the ambient dimension d.
Application
#c3-application-poisoning-resilient-regression-and-svm
Sever hardens ridge regression on high-dimensional ChEMBL drug-discovery data (410 dimensions) and hinge-loss support vector machines on Enron spam classification (5116 dimensions) against correlated data poisoning attacks that fool loss-based, l2-distance, centered-gradient l2-norm, and RANSAC outlier detectors.
Limitation
#c4-limitation-multiple-large-singular-values-and-sqrt-epsilon-rate
Sever's theoretical guarantee incurs an O(sigma * sqrt(epsilon)) error dependence on the corruption fraction epsilon without stronger distributional assumptions, and its single-top-singular-vector filter assumes the clean gradient covariance has small spectral norm in all directions, requiring multiple filtering rounds when subsets of outliers are initially hidden with zero hinge-loss gradient.
⚠️ Curated Limitations & Negative Results
- Without stronger distributional assumptions on inliers, the theoretical optimization error scales as O(sigma * sqrt(epsilon)) in the outlier fraction epsilon rather than O(epsilon).
- Filtering along a single top singular vector per outer iteration requires multiple outer re-training rounds when subsets of poisoning points initially have zero gradient (e.g., correctly classified hinge-loss points).
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:RegressionAnalysis
Regression Analysis
|
related_match | Sever is an outlier-robust stochastic optimization meta-algorithm evaluated on ridge regression, generalized linear models, and support vector classification under epsilon-corruption. |
Evidence Sources & Primary Literature
3 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
r527-primary-pdf
|
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Jacob Steinhardt, Alistair Stewart
|
primary paper
full_text
|
ID: https://dblp.org/rec/conf/icml/DiakonikolasKK019
sha256:7679bd56f381…
|
r527-arxiv-abs
|
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Jacob Steinhardt, Alistair Stewart
|
primary paper
abstract_only
|
ID: https://arxiv.org/abs/1803.02815
sha256:8496c250bca8…
|
r527-metadata-cr
|
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Jacob Steinhardt, Alistair Stewart
|
primary paper
abstract_only
|
ID: https://dblp.org/rec/conf/icml/DiakonikolasKK019
sha256:cc991a9a2c20…
|
Ontology & Grounding Topology
Open in interactive network graph →Curation Provenance
Curator: Antigravity
Method: ai_assisted
Model: Gemini
Created: 2026-10-19T10:10:00Z
Updated: 2026-10-19T10:10:00Z
Explore across X-Mech
Related computational & biological Mechs:
Embedding Map
Network Graph
ProteinTraitsMech (ESM-2 pLM)
DUFMech (Domain pLM)
TraitMech
CultureMech
All 14 X-Mech Repositories