High-Dimensional Robust Mean Estimation in Nearly-Linear Time

Yu Cheng; Ilias Diakonikolas; Rong Ge

Source-linked AI summary

High-Dimensional Robust Mean Estimation in Nearly-Linear Time

Yu Cheng, Ilias Diakonikolas, Rong Ge

arXiv:1811.09380v1Nov 23, 2018cs.LGcs.DSmath.STstat.MLstat.TH

TL;DR

Robust high-dimensional mean estimation must handle adversarially corrupted samples while seeking dimension-independent accuracy. This paper uses mean-guess-parameterized SDPs and reports nearly-linear-time algorithms for sub-Gaussian data and unknown bounded covariance.

Problem
The problem is to estimate a high-dimensional mean despite a constant fraction of adversarially corrupted samples, while seeking robust algorithms with dimension-independent error and nearly-linear runtime.
Source: §1.1 · pp. 2–3
Method
The algorithms reweight samples and use second-moment SDPs parameterized by a current mean guess, with a primal solution estimating the mean when the guess is close.
Source: §1.4 · p. 5, §3.3 · p. 11
Results
O(δ)=O(ε log(1/ε)) error is achieved for sub-Gaussian identity-covariance data, while unknown covariance bounded by σ^2I yields O(σ√ε) error, with nearly-linear-time algorithms.
Source: §1.2 · pp. 3–4
Takeaways & Limitations
The authors identify robust covariance estimation as a possible extension, but state that they have not explored it in this work.
Source: §6 · p. 23
The runtime retains an extraneous poly(1/ε) factor, which the authors leave as an open direction to remove.
Source: §6 · p. 23

Abstract

from arXiv · show

We study the fundamental problem of high-dimensional mean estimation in a robust model where a constant fraction of the samples are adversarially corrupted. Recent work gave the first polynomial time algorithms for this problem with dimension-independent error guarantees for several families of structured distributions. In this work, we give the first nearly-linear time algorithms for high-dimensional robust mean estimation. Specifically, we focus on distributions with (i) known covariance and sub-gaussian tails, and (ii) unknown bounded covariance. Given $N$ samples on $\mathbb{R}^d$, an $\epsilon$-fraction of which may be arbitrarily corrupted, our algorithms run in time $\tilde{O}(Nd) / \mathrm{poly}(\epsilon)$ and approximate the true mean within the information-theoretically optimal error, up to constant factors. Previous robust algorithms with comparable error guarantees have running times $\tilde{\Omega}(N d^2)$, for $\epsilon = \Omega(1)$. Our algorithms rely on a natural family of SDPs parameterized by our current guess $\nu$ for the unknown mean $\mu^\star$. We give a win-win analysis establishing the following: either a near-optimal solution to the primal SDP yields a good candidate for $\mu^\star$ -- independent of our current guess $\nu$ -- or the dual SDP yields a new guess $\nu'$ whose distance from $\mu^\star$ is smaller by a constant factor. We exploit the special structure of the corresponding SDPs to show that they are approximately solvable in nearly-linear time. Our approach is quite general, and we believe it can also be applied to obtain nearly-linear time algorithms for other high-dimensional robust learning problems.

1 Introduction

The introduction frames robust high-dimensional mean estimation as finding dimension-independent accuracy despite adversarial corruption, without the computational cost of earlier methods. It presents guess-parameterized SDPs as the basis for nearly-linear-time algorithms under two distributional assumptions.

1.1 Background

The robust setting allows an adversary to replace a constant fraction of samples, making the empirical mean vulnerable while earlier efficient approaches could have dimension-dependent error or high runtime.The introduction motivates algorithms with near-optimal sample complexity and dimension-independent error that run in nearly-linear time.Source: §1.1 · pp. 2–3

1.2 Our Results

For sub-Gaussian data with identity covariance, the algorithm uses N = Ω(d/δ^2) samples and runs in eO(Nd)/poly(ε) time for error O(δ)=O(ε log(1/ε)), matching optimal error and sample complexity up to constants.The lower bounds apply even without corruptions for sample complexity and even in the infinite-sample regime for error.Source: §1.2 · p. 3
For unknown covariance Σ ⪯ σ^2I, N = Ω((d log d)/ε) samples yield error O(σ√ε) in eO(Nd)/poly(ε) time with probability at least 9/10.The error guarantee is information-theoretically optimal up to constants; the sample complexity is optimal within a logarithmic factor.Source: §1.2 · p. 4

1.3 Related and Prior Work

Prior approaches include the convex-programming and filtering methods of, the dimension-halving method of, and the bounded-second-moment method of, with high-dimensional runtimes.The convex program relies on the ellipsoid algorithm; filtering can require Ω(d) power iterations, while the cited SVD-based methods incur Ω(d^3) runtime.Source: §1.3 · pp. 4–5

1.4 Our Approach and Techniques

The algorithm reweights samples and minimizes second moments around a guess ν: a good primal solution estimates μ⋆, while the dual moves a distant guess closer; covering/packing SDP solvers enable nearly-linear time.The solvers’ approximate solutions may mildly violate original constraints, but the paper’s arguments are designed to tolerate those violations.Source: §1.4 · pp. 5–6

1.5 Structure of This Paper

The paper develops the sub-Gaussian algorithm in Section 3, SDP solvers in Section 4, and the bounded-covariance algorithm in Section 5.Source: §1.5 · p. 6

2 Preliminaries

The preliminaries establish notation for samples, the unknown mean, and corruption, alongside the vector and matrix operations used in the paper. They also define the admissible reweighting set used to handle corrupted samples.

The notation section defines vector ℓ1 and ℓ2 norms and inner products, plus matrix spectral norm, maximum eigenvalue, trace, entry-wise inner product, and positive semidefiniteness.Source: §2 · p. 6
The input is partitioned into remaining good samples and adversarially added bad samples, with at least (1 − ε)N good samples and at most εN bad samples.Source: §2 · p. 7
The paper denotes the unknown true mean by μ⋆, the current estimate by ν, and the i-th sample by X_i; a weight vector defines a weighted empirical mean.Source: §2 · p. 7
Δ_N,ε is the convex hull of uniform distributions over sample subsets of size (1 − ε)N.Source: §2 · p. 7

3 Robust Mean Estimation for Known Covariance Sub-Gaussian Distributions

For known-covariance sub-Gaussian distributions, the section analyzes an iterative SDP method that either returns an accurate weighted empirical mean or contracts its current guess toward the true mean using a dual solution. It also bounds the algorithm’s failure probability and establishes nearly-linear runtime in the sample and dimension sizes, up to factors depending on ε and logarithms.

3 Robust Mean Estimation for Known Covariance Sub-Gaussian Distributions

The method uses a primal-dual win-win: a good primal solution yields an accurate weighted mean, while a good dual solution moves the guess closer to the true mean.The dual-based improvement is repeated only logarithmically many times before the primal case yields termination.Source: §3 · p. 7, §3.3 · p. 12, §3.4 · p. 12

3.1 SDP Formulation and Algorithm Description

The primal SDP reweights samples to minimize their second moment around ν, while the algorithm iteratively updates ν from primal or dual solutions and outputs the weighted empirical mean when the primal objective is small.The intended primal weights are uniform on the good samples when ν is close to µ⋆.Source: §3.1 · pp. 7–9

3.2 Optimal Value of the SDPs

(1 −δ2) + r2 −2δr ≤ OPTν,2ǫ ≤ OPTν,ǫ ≤ (1 + δ2) + r2 + 2δr, where r = ∥ν −µ⋆∥2.Under the lemma’s assumptions, these bounds relate both SDP optimal values to the distance between the current guess and true mean.Source: §3.2 · p. 9

3.3 When Primal SDP Has Good Solutions

If a feasible weight vector’s weighted mean is at least c3δ from µ⋆, its primal objective is at least 1 + Ω(δ2/ǫ), so a good primal solution gives an accurate estimate.The section further states that when the guess is O(β) from µ⋆, an optimal primal solution gives a weighted mean O(δ) from µ⋆.Source: §3.3 · pp. 11–12

3.4 When Primal SDP Has No Good Solutions

When the primal SDP has no good solution, a good dual solution’s top eigenvector provides a direction for updating ν and reducing its distance to µ⋆ by a constant factor.The eigenvector approximately aligns with ν −µ⋆; the update estimates the distance from the SDP value and uses candidate SDP values to choose between opposite directions.Source: §3.4 · pp. 12, 14

3.5 Proof of Theorem 1.2

The algorithm applies the primal and dual lemmas in their respective cases, using the geometric improvement to require at most a logarithmic number of dual updates before termination via the primal case.The primal case is Lemma 3.2; the dual-based guess improvement is Lemma 3.3.Source: §3.5 · p. 14
For N = Ω(d/δ^2), the good samples satisfy Condition (4) with probability at least 1−1/30.The overall failure probability is at most 1/10 by a union bound over three bad events.Source: §3.5 · p. 14
Each iteration either returns a primal solution whose weighted empirical mean is close to the true mean or uses a dual solution’s top eigenvector to bring the current guess closer by a constant factor.The correctness proof bounds the total failure probability by 1/10.Source: §3.5 · p. 14
The overall running time is O~(Nd/ε^6), with at most O(log d) guess updates and O~(Nd/ε^6) time per loop.Each loop repeats Proposition 4.1 O(log log d) times to control its failure probability.Source: §3.5 · pp. 14–15

4 Solving Primal/Dual SDPs in Nearly-Linear Time

The section reduces the original primal and dual SDPs to a parameterized packing/covering pair, then solves that pair approximately in nearly-linear time. A binary search selects the parameter needed to translate the solutions back to the original SDPs.

4 Solving Primal/Dual SDPs in Nearly-Linear Time

The packing/covering SDPs can be solved in eO(Nd/ε^6) time, enabling the section’s nearly-linear-time primal/dual procedure.The solver succeeds with probability at least 9/10.Source: §4 · p. 15
The original SDPs are related to packing and covering SDPs whose objectives are close to 1, allowing solutions to translate back with objective value roughly 1/ρ.The method switches an objective with a constraint and introduces ρ > 0.Source: §4 · pp. 15–16
Binary search finds a suitable ρ because the packing/covering optimum varies continuously and monotonically with ρ.The search uses the packing and covering solution values to decide whether to decrease or increase ρ.Source: §4 · pp. 16, 18

4.1 Positive SDP Solvers

The positive SDP solver applies because the reduced SDPs are packing/covering programs, and their matrix input has O(Nd) nonzeros.The dual solution is maintained implicitly to avoid writing an (N + d) × (N + d) matrix.Source: §4.1 · pp. 18–19

5 Robust Mean Estimation under Second Moment Assumptions

For bounded-covariance distributions, the algorithm retains the guess-and-SDP strategy but changes the analysis and preprocessing to handle second-moment assumptions. It alternates between a useful primal solution and a dual solution that improves the current guess.

5 Robust Mean Estimation under Second Moment Assumptions

Preprocessing uses a coordinate-wise median to identify distant samples, replaces those samples, and supplies the bounded-covariance algorithm with data whose samples are not too far from the mean.The section notes that bounded covariance alone does not prevent a few good samples from distorting empirical covariance, motivating removal of such samples.Source: §5 · pp. 19–20

5.1 Optimal Values of the SDPs

When the guess is at least c2β from the true mean, the bounded-covariance SDP optimum is approximately proportional to the squared distance.The section contrasts this with the known-identity-covariance setting, where the optimum is roughly 1 plus squared distance.Source: §5.1 · p. 20

5.2 When Primal SDP Has Good Solutions

A primal solution with objective O(β^2) gives a weighted empirical mean close to the true mean, regardless of the current guess.This is the section’s stated consequence of Lemma 5.3.Source: §5.2 · p. 22

5.3 When Primal SDP Has No Good Solutions

When the primal SDP has no good solution, an approximately optimal dual solution yields a new guess closer to the true mean by a constant factor.The section says the geometric argument is the same as in Lemma 3.3.Source: §5.3 · p. 22

5.4 Proof of Theorem 1.3

Proposition 5.5 computes either a low-objective primal solution or a sufficiently high-objective dual solution in eO(Nd/ε^6) time with probability at least 9/10.Combining the two alternatives lets the algorithm make progress at each guess.Source: §5.4 · p. 22
Theorem 1.3’s algorithm runs in eO(Nd log(1/τ)/ε^6) time, invoking the primal-or-dual procedure at most O(log(d/ε)) times.The proof combines the primal and dual guarantees with Proposition 5.5.Source: §5.4 · p. 23

6 Conclusions and Future Directions

The paper’s main contribution is a first nearly-linear-time approach to robust high-dimensional mean estimation with dimension-independent error guarantees. It also identifies extensions and runtime improvements that remain open.

6 Conclusions and Future Directions

The paper gives the first nearly-linear-time algorithms with dimension-independent error guarantees for robust high-dimensional mean estimation on structured distribution families with a constant fraction of corruptions.The authors describe this as their main technical contribution.Source: §6 · p. 23
Whether the techniques extend to robust covariance estimation remains unexplored, while the authors believe such a generalization may be possible.They also pose robust sparse mean estimation, robust sparse PCA, and faster SoS convex programs as directions for future work.Source: §6 · p. 23
The runtime retains a poly(1/ε) dependence, and removing it is an open question.The authors note that solving a covering SDP to multiplicative accuracy 1 + ε incurs a poly(1/ε) slowdown.Source: §6 · p. 23

A Setting Constants in Section 3

This appendix specifies an order for choosing the universal constants used in Section 3. The choices are made sequentially so each constant depends only on those set earlier.

A Setting Constants in Section 3

The constants are chosen in the order c1, c2, c4, c5, c7, c6, then c3, with each depending only on earlier choices.Each constant has only lower-bound requirements, so it can be chosen sufficiently large.Source: A Setting Constants in Section 3 · p. 26
The threshold c2 separates guesses at distance at least c2β, where the SDP optimum is roughly 1 + r^2.Here r is the distance between the current guess and the true mean.Source: A Setting Constants in Section 3 · p. 26
The constant c4 sets the primal-versus-dual branch threshold: use the primal when OPT ≤ 1 + c4β^2, otherwise use the dual.The later choices of c5, c6, and c7 support the corresponding mean-error and second-moment bounds.Source: A Setting Constants in Section 3 · p. 26