PaperlayerView exact revision on arXiv

Source-linked AI summary

Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers

Jacob Steinhardt, Moses Charikar, Gregory Valiant

arXiv:1703.04940v3cs.LGcs.AIcs.CCcs.CRstat.ML

TL;DR

Robust learning asks which dataset properties permit reliable estimation despite a large fraction of arbitrary, potentially adversarial additions. This paper introduces resilience and develops information-theoretic and algorithmic results, including a bounded-moment guarantee for samples.

  • Problem

    The central question is which properties let a dataset be robustly learned from when a large fraction of arbitrary, potentially adversarial data is added.

    Source: §1 · p. 1

  • Method

    The paper introduces resilience as a condition for robust estimation and relates it, in strongly convex norms, to large subsets with bounded variance.

    Source: §1 · pp. 2–3

  • Results

    Bounded-kth-moment samples are (O(σϵ^(1−1/k)), ϵ)-resilient in ℓ2 with high probability; the paper also gives robust-learning bounds for discrete distributions and stochastic block models.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    In strongly convex norms, the connection between resilience and bounded-variance cores provides a route to efficient algorithms.

    Source: §1 · p. 3

    The d^1.5/ϵ sample-complexity term is likely loose; the authors believe the true dimension dependence is at most d log(d).

    Source: §1.2 · p. 5

Abstract

from arXiv · show

We introduce a criterion, resilience, which allows properties of a dataset (such as its mean or best low rank approximation) to be robustly computed, even in the presence of a large fraction of arbitrary additional data. Resilience is a weaker condition than most other properties considered so far in the literature, and yet enables robust estimation in a broader variety of settings. We provide new information-theoretic results on robust distribution learning, robust estimation of stochastic block models, and robust mean estimation under bounded $k$th moments. We also provide new algorithmic results on robust distribution learning, as well as robust mean estimation in $\ell_p$-norms. Among our proof techniques is a method for pruning a high-dimensional distribution with bounded $1$st moments to a stable "core" with bounded $2$nd moments, which may be of independent interest.

1. Introduction

The section presents resilience as a condition for robust mean estimation despite arbitrary outliers, supporting information-theoretic recovery results and, under further assumptions, efficient algorithms. It also covers robust low-rank recovery, estimation in general and ℓp norms, and finite-sample variance bounds.

1. Introduction

  • Resilience requires every sufficiently large subset’s mean to remain close to the dataset mean, reducing robust estimation to finding a large resilient subset in the corrupted data.The paper also gives an efficient subset-finding algorithm under strong convexity and an approximate generalized eigenvalue solver.Source: §1 · pp. 2–3

1.1. Information-Theoretic Sufficiency

  • For ϵ<1/2, resilience permits mean recovery with error controlled by resilience at deletion fraction ϵ/(1−ϵ); even when the good set is a minority, randomized recovery succeeds with probability at least α/2.When the good set has size α times the corrupted set’s size, the proposition also bounds the recovery error in terms of resilience at α/4.Source: §1.1 · p. 3

1.2. Finite-Sample Concentration

  • Thin tails in every direction characterize distributional resilience, which transfers with high probability to a resilient (1−ϵ)n-sample subset sufficient for robust recovery.The excluded samples can be treated as additional outliers in the recovery guarantee.Source: §1.2 · p. 4
  • For distributions with bounded kth moments, the paper obtains ℓ2 mean error O(σϵ^(1−1/k)); if only an α-fraction of points are good, recovery has error O(σα^(−1/k)) with probability Ω(α).The stated sample requirement is n ≥ d^1.5/ϵ^2.Source: §1.2 · p. 5
  • For discrete distribution learning from k-tuples, the method estimates the underlying distribution in total variation and achieves k-times smaller error when each tuple is either entirely good or entirely corrupted.The result relies on resilience in the ℓ1 norm.Source: §1.2 · p. 5
  • In the semi-random stochastic block model, resilient good-vertex adjacency rows yield recovery with probability α and an information-theoretic threshold matching Kesten–Stigum up to a log(2/α) factor.The resilience argument uses a truncated ℓ1 norm.Source: §1.2 · p. 5

1.3. Strong Convexity, Second Moments, and Efficient Algorithms

  • In strongly convex norms, every resilient set contains a bounded-variance core of at least half its points, with no dimension-dependent factor; this prunes bounded first moments to bounded second moments.The analogous guarantee fails for third moments or non-strongly-convex norms without polynomial dimension factors.Source: §1.3 · p. 6
  • Efficient robust mean estimation is possible for bounded-variance data when the generalized eigenvalue problem is approximately solvable; in ℓ1, this gives an efficient algorithm for robust discrete distribution learning.The algorithmic result assumes polynomial-time optimization over a convex set of positive semidefinite matrices.Source: §1 · p. 3, §1.3 · p. 6
  • Theorem 7 gives polynomial-time robust mean estimation under bounded variance and Assumption 6, with a strongly convex-norm extension for smaller good subsets.The theorem’s displayed error bounds are truncated in the supplied passages; its conditions and polynomial-time guarantee are stated there.Source: §1.3 · pp. 6–7
  • The algorithm applies to ℓp norms for p ∈ [1, 2], and its ℓ1 use yields a stronger discrete-distribution metric than the stated ℓ2 bound when πmax is large.For k-tuples from a discrete distribution, the ℓ1 approach recovers a distribution in total variation distance; the supplied bound expressions are truncated.Source: §1.3 · p. 7
  • A finite-sample result finds, with high probability, a bounded-variance subset from d samples in R^d with bounded population variance, using pruning informed by graph sparsification.The result is presented as a generalization of Proposition B.1 of Charikar et al. (2017).Source: §1.3 · p. 7

1.4. Low-Rank Recovery

  • Under rank-resilience, the paper gives efficient recovery of a rank-at-most-15k matrix whose residual operator norm is O(σk+1(XS)), when the resilient subset has size (1 − δ)n.The authors emphasize dependence on σk+1 rather than σ2; the stated guarantee requires the good subset to be relatively large.Source: §1.4 · p. 8

1.5. Summary, Technical Highlights, and Roadmap

  • The technical highlights include a pigeonhole proof that resilience suffices for robust estimation and a pruning argument combining strong convexity with minimax duality to obtain bounded-variance subsets.The latter argument is described as revealing geometric structure in resilient sets.Source: §1.5 · p. 8

1.6. Related Work

  • Earlier work included special cases of resilience, but the general sufficiency of resilience for information-theoretic recovery had gone unappreciated.The passage notes that those earlier conditions appeared alongside stronger conditions, and that Li (2017) used a reduction to a tournament lemma for its information-theoretic results.Source: §1.6 · p. 9

2. Resilience and Robustness: Information-Theoretic Sufficiency

Resilience makes robust mean recovery information-theoretically possible: a large resilient subset of the corrupted data has a mean close to the true mean. The section also constructs a family of candidate resilient subsets when only an α-fraction of points are good, with at least one candidate mean close to the true mean.

2. Resilience and Robustness: Information-Theoretic Sufficiency

  • An exponential-time strategy estimates the mean by finding a large resilient subset of the corrupted data and outputting its mean.The true and candidate subsets overlap substantially, so resilience bounds the distance between their means by 2σ.Source: §2 · p. 9
  • When only an α-fraction of points are good, a maximal family of resilient subsets contains at least one candidate mean close to the true mean.The argument uses maximality and overlap with the good set to establish a close candidate.Source: §2 · pp. 9–10

3. Powering up Resilience: Finding a Core with Bounded Variance

In strongly convex norms, resilience yields large subsets with bounded variance, supporting algorithmic applications that require this condition. A sharper result uses finer-grained resilience to obtain a core of size (1 − ϵ)|S| whose variance is controlled by eσ∗.

3. Powering up Resilience: Finding a Core with Bounded Variance

  • Resilience in a norm corresponds to bounded first moments in the dual norm, linking the criterion to the condition used to find a bounded-variance core.A resilient set has first moments bounded by 3σ; conversely, bounded first moments by σ imply (2σ, 1/2)-resilience.Source: §3 · p. 10
  • A resilient set in a γ-strongly-convex norm contains a core of at least half its points with variance bounded by 32σ^2/γ.The paper identifies this bounded-variance core as useful for algorithmic applications that depend on bounded variance.Source: §3 · p. 10
  • The core-existence assumptions are restrictive: such a core need not exist in ℓp for p > 2 or with bounded third moments when p = 2.The proof of the bounded-variance core result uses minimax duality and Khintchine’s inequality.Source: §3 · p. 10

3.1. Finding Resilient Cores when α ≈1

  • For ϵ ≤ 1/2, a resilient set in a γ-strongly-convex norm has a core of size (1 − ϵ)|S| with variance controlled by eσ∗.This sharper result aims to retain a larger core by using finer-grained resilience information; the supplied proposition passage does not give the bound’s full expression.Source: §3.1 · p. 11

4. Efficient Recovery Algorithms

The section develops efficient mean recovery by soft-pruning points with large reconstruction error, first in the ℓ2 norm and then under assumptions on general norms. Its general result connects resilience to bounded variance and uses strong convexity and an approximate norm-optimization procedure.

4.1. Warm-Up: Recovery in ℓ2-norm

  • In the ℓ2 warm-up, an efficient randomized algorithm recovers the mean from a bounded-variance subset, with success probability proportional to that subset’s size.When the subset has size αn with α=1−ϵ, the mean of the retained set is within O(σ√(1−α)) of the original mean.Source: §4.1 · pp. 12, 15
  • The warm-up repeatedly solves a reconstruction optimization and downweights points with high reconstruction error, retaining an active set for the final estimate.Points in the good subset can be reconstructed using its mean with small error, motivating the soft-removal rule.Source: §4.1 · p. 12
  • The ℓ2 analysis relies on operator-norm control: the low-rank projection keeps the data matrix close to its original form while supporting a mean estimate.The passage contrasts this with Frobenius-norm control, which would scale as σ.Source: §4.1 · pp. 12, 14

4.2. General Case

  • For general norms, the algorithm assumes bounded variance on the good subset and κ-approximability of the dual norm; strong convexity supports recovery even when the good subset is smaller.The algorithm uses a κ-approximation to the 2→ψ norm; computing that norm is NP-hard for general norms.Source: §4.2 · p. 15
  • For general norms, the algorithm replaces the maximum-eigenvalue step with a κ-approximation over a feasible set and uses polynomial-time optimization under the stated oracle assumption.The theorem’s analysis uses strong convexity to relate the resulting low-rank structure to bounded variance.Source: §4.2 · pp. 15–16

5. Robust Low-Rank Recovery

The section treats rank-resilience as sufficient for information-theoretic recovery of a near-best rank-k approximation, then gives an efficient recovery algorithm. The efficient output has rank at most 15k and controls the residual on the good points.

5.1. Information-Theoretic Sufficiency

  • The section’s recovery guarantee is motivated by rank-resilience, which requires large subsets to span the same column space and bounds how much the full good data can expand relative to such subsets.These conditions are the stated form of δ-rank-resilience.Source: §5.1 · p. 17
  • Rank-resilience permits an information-theoretic rank-k projection whose residual on the good points is at most twice their best rank-k approximation residual.The bound is expressed as ∥(I−P)XS∥2 ≤ 2σk+1(XS).Source: §5.1 · p. 17

5.2. Efficient Recovery

  • An efficient algorithm recovers a projection of rank at most 15k with a controlled residual on the good subset, assuming that subset is rank-resilient.The supplied theorem statement gives the residual as O(σ…), but its expression is incomplete in the passage.Source: §5.2 · p. 17
  • The efficient recovery procedure resembles the earlier mean-recovery algorithm, but the authors provide its own algorithm and proof because the rank-recovery analysis has important differences.The procedure is presented as Algorithm 2.Source: §5.2 · p. 17

6. Finite-Sample Concentration

The section gives two finite-sample results for finding resilient subsets with high probability. One applies broadly to resilient distributions but has suboptimal sample complexity; the other is more restrictive, assumes bounded variance, and has near-optimal sample complexity.

6.2. Concentration Under Bounded Covariance

  • The bounded-variance result gives a more restrictive finite-sample condition with near-optimal sample complexity, while the general resilient-distribution result has suboptimal sample complexity.The bounded-variance proposition states that for n≥d samples, a subset of (1−ϵ)n points has bounded variance with probability 1−exp(−ϵ²n/16).Source: §6 · p. 18, §6.2 · p. 20

6.1. Concentration for Resilient Distributions

  • For any (σ,ϵ)-resilient distribution, the first result establishes that a large subset of sampled points is itself resilient with high probability.The guarantee is stated for a subset of (1−ϵ)n samples, with probability 1−δ−exp(−ϵn/6); its resilience parameter depends on the distributional and covering-number bounds.Source: §6.1 · p. 18
  • The general bound controls deviations across directions by covering the dual unit ball and splitting projected samples into small- and large-magnitude components.The proof applies Hoeffding’s inequality to the bounded component and Bernstein’s inequality after using resilience to bound the other component’s second moment.Source: §6.1 · pp. 18–19

7. Information-Theoretic Applications

The section applies resilience-based recovery to distribution learning, bounded-moment mean estimation, and a semi-random stochastic block model. Across these settings, finite-sample resilience results yield information-theoretic recovery guarantees under corruption.

7. Information-Theoretic Applications

  • The applications use finite-sample concentration together with the information-theoretic recovery result for resilient sets to establish robust recovery guarantees.The section explicitly identifies this combination as the basis for its applications.Source: §7 · p. 20

7.1. Distribution Learning

  • For distribution learning, the paper derives information-theoretic recovery of π from corrupted samples drawn as k-tuples from π, with total-variation error depending on the corruption fraction.The setup maps each tuple to its empirical distribution in the simplex before applying the resilience results.Source: §7.1 · pp. 20–21

7.2. Bounded kth Moments

  • For distributions with bounded kth moments, the paper obtains ℓ2 mean recovery error O(ϵ^(1−1/k)σk) from samples with an ϵ fraction of corruptions.The stated sample regime is n=Ω(d^1.5/ϵ²), with success probability 1−exp(−Ω(d)).Source: §7.2 · p. 22

7.3. Stochastic Block Model

  • In the semi-random stochastic block model, good-vertex rows are shown to be resilient under a norm that takes the largest ℓ1 norm over αn coordinates, supporting information-theoretic recovery of the good-vertex set.The resilience statement holds with probability 1−exp(−Ω(αn)).Source: §7.3 · pp. 22–23

8. Algorithmic Applications

The section applies the paper’s algorithmic result to robust mean recovery in ℓ_p norms and robust discrete-distribution learning. It gives recovery guarantees for resilient sets and finite-sample guarantees when some samples are arbitrary.

Robust mean recovery

  • For ℓ_p-resilient sets with p ∈ (1, 2], an efficient algorithm recovers the mean, with probability 1 in the specified near-clean regime.The result also applies when the set has bounded variance.Source: §8 · p. 24
  • A resilient set contains a bounded-variance core, allowing the algorithmic result to be applied for robust mean recovery.The proof uses strong convexity of ℓ_p for p ∈ (1, 2].Source: §8 · p. 24

Robust distribution learning

  • For discrete-distribution learning, the guarantees assume αn clean independent k-tuples from π and allow the remaining samples to be arbitrary.The section states randomized and deterministic finite-sample regimes, each with success probability 1 − exp(−Ω(m)).Source: §8 · p. 24
  • When αn ≥ m, the section gives a randomized distribution-learning guarantee; for α = 1 − ϵ with ϵ sufficiently small, it also gives a deterministic guarantee.Both bounds are stated in total variation distance, with polylogarithmic factors in ϵ and m hidden by the ˜O notation.Source: §8 · p. 24

Appendix A. Counterexample to Analogues of Proposition 12

The appendices give a counterexample delimiting when a resilience-to-bounded-variance result can hold, then review basic properties of resilience. In particular, the counterexample imposes a necessary relation between the moment order and the norm parameter for large n.

Appendix A. Counterexample to Analogues of Proposition 12

  • The standard-basis set is (2n^(1/p−1), 1/2)-resilient around 0 in ℓ_p for every p ∈ [1, ∞].Source: Appendix A · p. 25
  • For large n, an analogue of Proposition 12 requires k ≤ p/(p−1); the case k = 3, p = 1.5 remains unresolved.For k = 2, this condition implies p ≤ 2; for p = 2, it implies k ≤ 2.Source: Appendix A · p. 25

Appendix B. Basic Properties of Resilience

  • Appendix B relates resilience around the mean to bounded tails and gives a relation between ϵ-resilience and (1 − ϵ)-resilience.The appendix also treats resilience around a point that is not the mean.Source: Appendix B · pp. 25–26

Appendix C. Proof of Lemma 11

The proof splits directional deviations by sign and uses the larger sign class to establish the claimed bound. It also considers the reverse direction for an arbitrary subset.

Appendix C. Proof of Lemma 11

  • For a fixed direction, the proof uses whichever of the positive- or negative-deviation sets contains at least half the points, then completes the bound and treats the converse for any subset.Source: Appendix C · pp. 26–27

Appendix D. Proof of Lemma 13

The proof relaxes a discrete selection problem to continuous weights, then uses minimax to bound its value through a distribution over vectors. The relaxation costs at most a factor of two before the resulting bound is transferred back.

Appendix D. Proof of Lemma 13

  • Relaxing the discrete weights to continuous weights yields an objective whose value is at most twice that of the relaxed problem.Source: Appendix D · p. 27
  • A minimax swap replaces a single vector with a distribution over vectors; bounding the resulting expression by 4B(v1:m)^2 gives an upper bound of 8B(v1:m)^2 for the original objective.Source: Appendix D · p. 27

Appendix E. Proof of Proposition 15

Appendix E proves Proposition 15 using a more careful version of Proposition 12’s bookkeeping, then presents an efficient SVD-based approach for the ℓ2 mean-estimation optimization. The proof bounds the relevant terms using ordered sums and Lemma 31; the algorithm reduces the optimization to a form solvable with an SVD and linear-time post-processing.

Appendix E. Proof of Proposition 15

  • The proof of Proposition 15 follows Proposition 12 with more careful bookkeeping, including a revised constraint on ∥c∥1.The constraint uses (1 − ϵ/2)n in place of 3n/4.Source: Appendix E · pp. 27–28
  • Ordering the inner sums lets the proof bound the smallest terms using averages of larger terms, Khinchine’s inequality, and Lemma 31.The proof selects the (1 − ϵ/2)n smallest inner-sum values, corresponding to the optimal choice of c.Source: Appendix E · p. 28

Appendix F. Fast Algorithm for ℓ2 Mean Estimation

  • The ℓ2 mean-estimation optimization can be solved efficiently by reducing it to a unitarily invariant problem handled with an SVD and linear-time post-processing.The proof replaces an entrywise constraint with a Frobenius-norm constraint; the resulting vector minimization can be done in linear time.Source: Appendix F · p. 29

Appendix G. Proof of Lemma 17

Appendix G verifies that two conditions remain true through the algorithm’s line 5, using bounds on the removal rate and the number of removed elements. Appendix H proves Proposition 20 by transforming the distribution to identity covariance before applying a result of Charikar et al. (2017).

Appendix G. Proof of Lemma 17

  • The proof of Lemma 17 preserves both conditions by bounding the removal rate and the number of elements removed from A.The removal-rate comparison preserves (i), while the bound on removed elements establishes |S ∩ A| ≥ α(2 + α)/(4 − α)n and preserves (ii).Source: Appendix G · p. 30

Appendix H. Proof of Proposition 20

  • To prove Proposition 20, the argument whitens samples using Σ^−1/2(x_i − µ), yielding transformed data with identity covariance and mean zero.It then applies Proposition B.1 of Charikar et al. (2017) to find a subset of (1 − ϵ)n transformed samples.Source: Appendix H · p. 30
  • The proof applies Proposition B.1 of Charikar et al. (2017) to the transformed distribution rather than directly to p.The transformed subset is then expressed in terms of the original samples.Source: Appendix H · p. 30
Loading 1703.04940v3…