PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning from Untrusted Data

Moses Charikar, Jacob Steinhardt, Gregory Valiant

arXiv:1611.02315v2cs.LGcs.AIcs.CCcs.CRmath.ST

TL;DR

The paper asks what can be learned when substantial portions of the data are arbitrary or adversarial. It studies list-decodable and semi-verified learning through a general robust stochastic-optimization framework. The resulting guarantees apply to robust mean estimation, mixture clustering, and planted-partition recovery, with sharper concentration obtained by handling bad samples.

  • Problem

    The paper asks whether learning remains possible when only an α-fraction of data is trusted and the remaining data are arbitrary or adversarial.

  • Method

    The paper develops robust stochastic-optimization methods based on convex optimization, spectral control, novel matrix concentration, minimum-trace-ellipsoid regularization, and clustering techniques.

  • Results

    The framework yields robust mean estimation, mixture clustering, and planted-partition recovery, including mean error O(σ) under bounded second moments and sharper concentration after removing bad samples.

  • Takeaways & Limitations

    Robust learning can be effective with significant untrusted data across estimation, mixture-learning, and planted-structure settings.

  • Takeaways & Limitations

    A concrete bound in one stochastic-optimization result relies on the specified functional form for the observed functions.

Abstract

from arXiv · show

The vast majority of theoretical results in machine learning and statistics assume that the available training data is a reasonably reliable reflection of the phenomena to be learned or estimated. Similarly, the majority of machine learning and statistical techniques used in practice are brittle to the presence of large amounts of biased or malicious data. In this work we consider two frameworks in which to study estimation, learning, and optimization in the presence of significant fractions of arbitrary data. The first framework, list-decodable learning, asks whether it is possible to return a list of answers, with the guarantee that at least one of them is accurate. For example, given a dataset of $n$ points for which an unknown subset of $αn$ points are drawn from a distribution of interest, and no assumptions are made about the remaining $(1-α)n$ points, is it possible to return a list of $\operatorname{poly}(1/α)$ answers, one of which is correct? The second framework, which we term the semi-verified learning model, considers the extent to which a small dataset of trusted data (drawn from the distribution in question) can be leveraged to enable the accurate extraction of information from a much larger but untrusted dataset (of which only an $α$-fraction is drawn from the distribution). We show strong positive results in both settings, and provide an algorithm for robust learning in a very general stochastic optimization setting. This general result has immediate implications for robust estimation in a number of settings, including for robustly estimating the mean of distributions with bounded second moments, robustly learning mixtures of such distributions, and robustly finding planted partitions in random graphs in which significant portions of the graph have been perturbed by an adversary.

1 Introduction

The paper studies learning when only an α-fraction of data is trusted, introducing list-decodable and semi-verified perspectives and obtaining strong robust-learning results. Its general stochastic-optimization framework yields applications to mean estimation, mixture learning, and planted-partition recovery.

  • Problem and frameworks: With only αn trusted samples and arbitrary remaining data, accurate recovery can remain possible in high dimensions even when α is much smaller than one.The list-decodable framework returns multiple possible answers, while the semi-verified framework uses a small trusted set to interpret a larger untrusted dataset.
  • General framework: The general framework minimizes the population mean of convex functions when αn observed functions are sampled from p∗, using spectral norm bounds on gradients.The guarantees apply whenever the good data satisfy suitable matrix concentration, including some bounded-second-moment settings.
  • Applications: For bounded-covariance distributions, the method robustly estimates the mean to ℓ2 error O(σ), improving prior guarantees under weaker assumptions for α bounded away from one.Earlier comparable rates either incurred a log(d) factor under a fourth-moment bound or required sub-Gaussian data.
  • Applications: When α ≤ 1/2, the paper studies mean estimation in a previously unexplored regime and obtains error ˜O(σ/√α).
  • Applications: For mixtures with minimum component weight α, accurate clustering is possible with mean separation ˜Ω(σ/√α), despite additional adversarial data.This nearly matches the best efficient clustering rates that exploit full mixture structure when α is sufficiently large.
  • Applications and techniques: The framework also recovers planted partitions at average degree ˜Ω(1/α^3), while introducing matrix concentration, minimum-trace-ellipsoid regularization, and padded decompositions.The authors suggest a possible connection between robustness thresholds and computational thresholds for recovering planted structure.

2 Main Results and Implications

The paper develops robust learning for convex stochastic optimization with an α-fraction of good data and arbitrary remaining data, using spectral gradient concentration. This framework yields an ellipse of plausible parameters, supports list-decoding and semi-verified learning, and gives implications for robust estimation, mixtures, and planted partitions.

  • General stochastic optimization: The framework observes convex functions with an α-fraction sampled independently from p∗ while allowing the remaining functions to be chosen adversarially.The goal is to find a parameter with small population excess loss under the mean function.
  • General stochastic optimization: The spectral norm S measures uniform gradient deviation on the good data and is independent of the adversary.S serves as an analogue of uniform convergence for the adversarial setting.
  • General stochastic optimization: Under sub-Gaussian, Lipschitz gradient deviations and sufficient αn, S=O(σ) with probability 1−δ.The sample-size condition depends on dimension, radius, smoothness, noise scale, and confidence.
  • Main results: Theorem 2.2 obtains a small ellipse E_Y containing a parameter with small population error using only the untrusted data.The ellipse narrows the possible parameter space from H to a much smaller set.
  • Main results: For strongly convex losses, the method produces at most m candidate parameters, one of which has small error, enabling list-decodable learning.Padded decompositions provide the clustering tool used in this adversarial setting.
  • Main results: With verified data, reducing H to E_Y can enable accurate recovery even when only a single verified point is available.A concrete lemma treats Lipschitz generalized linear losses under bounded qth moments.
  • Implications: For bounded-covariance mean estimation, the paper gives O(σ) error with n=O(d) under weaker assumptions than earlier results.The summary also reports O(σ) robust mean error, a mixture bound of ˜O(σ√(log(2/α))) when α=Ω(1/k), and planted-partition requirements of k^3 log(k).
  • Implications: The framework applies to robust mean estimation, mixture learning, and planted-partition recovery despite arbitrary corruptions.The paper reports matching or near-matching rates in several settings, while planted-partition recovery requires average degree k^3 log(k) versus a best known k^2 bound.

3 Algorithm

The algorithm jointly optimizes per-function parameters inside a shared small-trace ellipse, then repeatedly downweights functions whose individually improved losses indicate outlier behavior. A minimum-trace ellipsoid regularizer controls local spectral structure while soft outlier removal limits adversarial influence.

  • Core optimization: The algorithm assigns each function its own parameter wi and minimizes weighted losses while constraining all wi inside an ellipse defined by Y.This separates per-function fitting from adversarial coupling, which occurs through the shared regularizer.
  • Core optimization: The minimum-trace ellipsoid regularizer encourages parameters to remain close and simultaneously controls trace norms on every subset of points.This yields stronger local control than penalizing only the overall trace norm.
  • Computational form: The optimization problem can be solved in polynomial time in n and d with oracle access to the functions.The semidefinite constraint wiwi^T ⪯ Y is convex and equivalent to requiring each wi to lie inside the ellipse.
  • Outlier removal: Outlier influence is reduced softly by multiplying ci by a factor based on fi(˜wi) − fi(ˆwi), rather than deleting functions outright.The procedure aims to downweight adversarial functions substantially while only slightly reducing weights of good points.
  • Outlier removal: The method compares each fitted parameter ˆwi with a parameter ˜wi optimized as an average of many other candidate parameters, using their loss gap to detect outliers.The comparison is designed to identify functions lacking sufficient agreement with the other data points.

4 Approach and Proof Outline

The proof separates optimization error from statistical error, then controls the shared ellipse and removes outliers to obtain a parameter with small population error. The central result is an ellipse containing an explicitly good parameter, while adversarial contributions are controlled through adaptive reweighting.

  • Proof structure: The proof follows the uniform-convergence template by separately bounding optimization error and statistical error, but must additionally remove outliers.Standard concentration cannot directly apply because each function is evaluated at a different fitted parameter.
  • Main guarantee: Theorem 2.2 produces an ellipse EY containing a parameter with small error under the population objective ¯f.The theorem’s geometric output narrows the possible parameter space from H to a small ellipse.
  • Error decomposition: The statistical analysis bounds deviations using the trace of the fitted ellipse and the spectral norm bound S on the good data.The two error components compare fi(ˆwi) with fi(ˆwavg) and fi(ˆwavg) with ¯f(ˆwavg).
  • Outlier removal: The outlier-removal step distinguishes whether loss gaps are comparable on all points and good points or substantially larger on all points.When the latter occurs, adversarial weights decrease faster than good-point weights.
  • Combined guarantee: The resulting bounds combine statistical error O(√(αnS/r)) with optimization error O(√(αnrS)).These terms arise after controlling the ellipse trace and the adaptive weights.

5 Concentration of Errors: A Local H¨older’s Inequality

The paper refines average error bounds using a local spectral quantity Sε and a local Hölder inequality. When good-data gradients are sub-Gaussian, the resulting function errors concentrate sub-Gaussianly despite arbitrary adversarial data, and the algorithm can preserve nearly all inliers.

  • Error concentration: The refined analysis shows that fi(ˆwavg) − fi(ˆwi) is close to a nominal value for almost all good points.This strengthens bounds that control only average differences.
  • Local spectral control: The local Hölder inequality uses Sε, a spectral bound over every sufficiently large subset of good points, to sharpen average error control.Sε captures worst-case operator norms beyond the full good set, with S1 = S.
  • Preserving inliers: A buffered outlier-removal rule can ensure that the mass removed from good points is at most ε times the total mass removed.The threshold τ delays downweighting until a function’s error is sufficiently large.
  • Sub-Gaussian case: For sub-Gaussian good-data gradients, the fraction of errors exceeding tσ/√α is at most exp(−Ω(t^2)) for sufficiently large t.Thus adversarial points cannot prevent sub-Gaussian concentration of the function errors.
  • General moment case: With only a general bound on S, the errors satisfy a Chebyshev-like concentration guarantee rather than requiring sub-Gaussian data.The refined result improves on the corresponding naïve Markov bound.

6 Bounds for Strongly Convex Losses

For strongly convex losses, the paper iteratively clusters candidate solutions and reruns its robust optimization algorithm to shrink the search radius around the true optimum. The resulting procedure concentrates most good-point estimates near the optimum and strengthens semi-verified guarantees.

  • Consequences: The strong-convexity result also yields strengthened guarantees in the semi-verified model because list decoding reduces to semi-verified learning.The paper omits the resulting strengthened statements for brevity.
  • Algorithm and proof overview: Algorithm 4 repeatedly clusters candidate estimates with padded decompositions and reruns Algorithm 1 on each cluster.The radius bound r(t) halves across iterations, while repeated randomized decompositions preserve the good points together with high probability.
  • Concentration of individual estimates: Proposition 6.2 establishes that most good-point outputs of Algorithm 1 lie close to w∗ under strong convexity.This converts the average-error guarantee into concentration of individual estimates for almost all good points.
  • Concentration of individual estimates: Corollary 6.4 shows that all but an ε fraction of good estimates concentrate around their average estimate.At most εαn good points fall outside the stated concentration region.
  • Analyzing Algorithm 4: Each outer iteration contracts the good-point radius from r(t) to 1/2r(t), provided the current radius is sufficiently large.Lemma 6.5 supplies the contraction property used to prove correctness of the iterative algorithm.

7 Lower Bounds

The lower bounds show that the dependence of robust-learning guarantees on covariance structure and the trusted fraction cannot generally be removed. In particular, exponentially large lists may be necessary for fine-grained covariance dependence.

  • Covariance dependence: The dependence of the bounds on S is necessary even in the strongly convex setting.The lower-bound section explicitly establishes this necessity.
  • Dependence on α: The true worst-case dependence on α remains open, although the paper establishes a necessary dependence involving 1/α in the Gaussian case.The authors identify determining the exact dependence on α as an open problem.
  • Covariance dependence: 2^k−1 candidate means can be insufficient when the target mean varies in directions associated with the kth singular value.The construction applies even when the target distribution is a multivariate Gaussian with bounded covariance.
  • Scope of lower bounds: The same lower-bound arguments extend to non-strongly-convex losses and imply corresponding requirements in the semi-verified model.The semi-verified lower bound follows by reduction from the semi-verified model to list decoding.
  • Covariance dependence: At least 2^Ω(k) candidates are necessary to achieve error tied to the kth singular value of the covariance bound.This rules out replacing the dependence on the maximum singular value with the kth singular value using only a small list.

8 Intuition: Stability Under Subsets

The paper develops a stability-based intuition for robust recovery: if a statistic remains nearly unchanged on every sufficiently large subset, it can be recovered despite arbitrary additional data. An exponential-time procedure realizes this idea, while semidefinite relaxations address computational efficiency.

  • Robustness duality: If a statistic is approximately preserved across every large subset, it can be robustly recovered despite additional arbitrary or adversarial data.This is the paper’s stated duality between stability under subsets and robustness to contamination.
  • Stability condition: The motivating stability condition requires every sufficiently large subset of a good set to have a mean close to the good set’s mean.The paper asks whether this mean can be approximated when the good set is unknown and the remaining points are arbitrary.
  • Exponential-time recovery: An exponential-time algorithm searches for large α-stable sets and outputs representatives whose means approximate the unknown good-set mean.The algorithm greedily collects stable sets with limited overlap.
  • Computational relaxation: The computational test for α-stability is relaxed through semidefinite constraints on a matrix representing subset membership.The resulting sufficient condition remains non-convex until an additional relaxation is applied.
  • Distributional implications: For sub-Gaussian samples, large subsets are α-stable with high probability, while bounded-second-moment distributions require selecting a suitable subset.This connects the stability framework to the paper’s robust mean-estimation results.

9 Applications

The general robust stochastic-optimization results yield applications to robust mean estimation, mixtures, planted partitions, and density modeling. These applications recover candidate parameters or structures despite arbitrary data outside the trusted fractions.

  • Robust mean estimation: Robust mean estimation applies to distributions with bounded covariance and returns candidate means covering nearly all good samples.The guarantee is obtained by applying the strongly convex optimization theorem to the squared-loss mean-estimation problem.
  • Mixture learning: For mixtures of k sub-Gaussian distributions, the method outputs candidate means so that each component is represented despite other components acting as untrusted data.The formulation treats each mixture component as the real distribution of interest in turn.
  • Planted partitions: In planted partition graphs, the method outputs candidate vertex sets close in symmetric difference to each planted subset.Vertices outside the planted subsets may have arbitrary outgoing edges.
  • Planted partitions: The planted-partition problem reduces to robust mean estimation using rows of the adjacency matrix as data vectors.The reduction defines a squared-loss objective for each vertex and thresholds candidate mean coordinates to form sets.
  • Density modeling: Density modeling is handled by applying the framework to exponential-family negative log-likelihoods, linking optimization error to KL divergence.The method also considers using a single verified sample to select a parameter from the candidate region.

C Deferred Proofs

The deferred proof establishes z ≤ 2a + b + c by converting the bound into a quadratic inequality and ruling out larger z by contradiction.

  • For nonnegative a, b, and c, the claimed bound is z ≤ 2a + b + c.
  • Removing the square root yields z^2 − (2a + b)z + (a^2 − c^2) ≤ 0.
  • Assuming z > 2a + b + c makes the quadratic strictly positive, contradicting the preceding inequality.

C.2 Proof of Lemma 2.1

The proof is omitted because it is a special case of Lemma 5.5, which is proved later.

  • The proof is omitted as a special case of Lemma 5.5.
  • Lemma 5.5 provides the deferred proof for this case.
  • The relevant argument appears below rather than in this subsection.

C.3 Proof of Lemma 2.4

The proof bounds a statistic using moment inequalities, Lipschitzness, matrix ordering, eigendecomposition, and Markov’s inequality before invoking uniform convergence.

  • The argument starts from μ = E[x] and Σ = Cov[x].
  • Power mean inequalities, the 1-Lipschitz property of φ, and ww⊤ ⪯ Y justify intermediate bounds.
  • The qth moment condition and q > 2 yield a trace bound involving tr(Y)^(q/2)σ^q.
  • An eigendecomposition of Y and further power-mean and qth-moment arguments produce the required statistic bound.
  • Markov’s inequality gives a tail bound on sup_w∈E_Y |f(w) − f̄(w)|, followed by a standard uniform-convergence argument.

C.4 Proof of Lemma 3.1

The proof uses operator–trace norm duality and matrix-ordering inequalities to establish the desired bound.

  • Operator and trace norm duality reduces the argument to a sum involving the rows z_i of matrix Z.
  • The first intermediate inequality follows from Cauchy–Schwarz.
  • The second intermediate inequality uses wiwi⊤ ⪯ Y.

C.5 Proof of Lemma 4.6

The proof restricts gradient-deviation and parameter matrices to the αn good rows, then bounds their operator-norm expression using norm inequalities and Lemma 3.1.

  • Matrix setup: F and W are formed from the αn rows indexed by I_good, giving matrices with αn rows and d columns.F contains centered gradients ∇f_i(w_0) − ∇̄f(w_0), while W contains the corresponding w_i rows.
  • Norm bounds: The operator norm of diag(c)F is bounded by the product of the operator norms of diag(c) and F, and hence by ∥F∥op.The argument uses ∥diag(c)∥op ≤ 1.
  • Conclusion: Combining the norm bounds with Lemma 3.1 bounds the target expression by αnS tr(Y).The displayed fragments identify this as the final bound established in the proof.

C.6 Proof of Lemma 5.5

The section proves Lipschitz and probabilistic properties through operator-norm arguments, covering and union bounds, Gaussian-density comparison, and a sub-Gaussian moment bound.

  • Uniform control: A covering argument for H combined with a union bound yields a statement holding simultaneously for all w ∈ H with probability 1 − δ.The intermediate argument uses the Lipschitz property of S_ε(w) around fixed points.
  • Lipschitz property: Lemma C.2 establishes that S_ε(w) is L-Lipschitz when each gradient deviation ∇f_i(w) − ∇̄f(w) is L-Lipschitz.The proof reduces this to showing the relevant operator-norm term is L-Lipschitz for each T.
  • Gaussian comparison: The Gaussian comparison proof seeks αp* ≤ p̂ by expanding the density inequality and minimizing the resulting quadratic over x.The proof invokes the Woodbury matrix inversion lemma and identifies the minimizing value of s as 1/λ.
  • Sub-Gaussian bound: Lemma C.3 begins by deriving moment bounds from an exponential-moment assumption valid for |λ| ≤ 1/(4σ^2).The proof applies concavity of log, converts |Z| to Z, and invokes the sub-Gaussian assumption at a selected λ.
Loading 1611.02315v2…