Learning from Untrusted Data

Introduction

What can be learned from data that is only partially trusted? In this paper, we study this question by considering the following setting: we observe $n$ data points, of which $\alpha n$ are drawn independently from a distribution of interest, $p^{*}$, and we make no assumptions about the remaining $(1-\alpha)n$ points—they could be very biased, arbitrary, or chosen by an adversary who is trying to obscure $p^{*}$. Our goal is to accurately recover a parameter of interest of $p^{*}$ (such as the mean), despite the presence of significant amounts of untrusted data. Perhaps surprisingly, we will show that in high dimensions, accurate estimation and learning is often possible, even when the fraction of real data is small (i.e., $\alpha\ll 1$). To do this, we consider two notions of successful learning–the list decodable model and the semi-verified model–and provide strong positive results for both notions. Our results have implications in a variety of domains, including building secure machine learning systems, performing robust statistics in the presence of outliers, and agnostically learning mixture models.

The goal of accurate robust estimation appears at first glance to be impossible if the fraction $\alpha$ of real data is less than one half. Indeed, in the $\alpha=\frac{1}{2}$ case, it is possible that the real and fake data are distributed identically, except that the mean of the fake data is shifted by some large amount; in such a case, it is clearly impossible to differentiate which of these two distributions is “right”. Perhaps, however, such symmetries are the only real problem that can occur. It might then be possible to output a short list of possible parameter sets–if $\alpha=\frac{1}{2}$, perhaps a list of two parameter sets–such that at least one is accurate. To this end, we consider a notion of successful learning called list decodable learning, first introduced by Balcan et al. (2008). In analogy with list decodable coding theory, the goal is for the learning algorithm to output a short list of possible hypotheses.

We say that a learning, estimation, or optimization problem is $(m,\epsilon)$ list decodably solvable if an efficient algorithm can output a set of at most $m$ hypotheses/estimates/answers, with the guarantee that at least one is accurate to within error $\epsilon$.

A central question in this paper concerns which learning problems can be robustly solved in the above sense:

To what extent are learning problems robustly solvable in the list decodable sense? If the dataset consists of only an $\alpha$-fraction of real data, in what settings is it possible to efficiently output a list of at most $\frac{1}{\alpha}$ or $\operatorname{poly}(\frac{1}{\alpha})$ parameter sets or estimates with the guarantee that at least one closely approximates the solution that could be obtained if one were given only honest data?

The intuition for why strong positive results are obtainable in the list decodable setting is the following. Given a dataset with an $\alpha$ fraction of trusted data, the remaining data might do one of two things: either it can be fairly similar to the good data, in which case it can bias the overall answers by only a small amount, or the adversarial data may be very different from the trusted data. The key is that if a portion of the untrusted data tries too hard to bias the final result, then it will end up looking quite different, and can be clustered out. Given this viewpoint, the question of robust learning in the list decodable model becomes a question of the extent to which an adversary can completely obscure the inherent structure possessed by a dataset drawn from a well-behaved distribution.

Our investigation of robust learning has three motivations. First, from a theoretical perspective, it is natural to ask what guarantees are possible in the setting in which a majority of data is untrusted ($\alpha<\frac{1}{2}$). Is it the case that learning really becomes impossible (as is often stated), or can one at least narrow down the possible answers to a small set? Second, in many practical settings, there is a trade-off between the amount of data one can collect, and the quality of the data. For a fixed price, one might be able to collect either a small and accurate/trusted dataset, or a large but less trusted dataset. It is worth understanding how the quality of models derived from such datasets varies, across this entire range of dataset quality/quantity. Finally, robust learning with $\alpha\ll 1$ provides a new perspective on learning mixtures of distributions—by treating a single mixture component as the real data, and the remaining components as fake data, we can ask to what extent a mixture component can be learned, independently of the structure of the other components. While this perspective may seem to give up too much, we will show, somewhat surprisingly, that it is possible to learn mixtures almost as well under these adversarial assumptions as under stochastic assumptions.

When $\alpha\leq\frac{1}{2}$, the list decodable model handles symmetries by allowing the learner to output multiple possible answers; an alternative is to break these symmetries with a small amount of side information. In particular, in many practical settings it is possible to obtain a (sometimes extremely small) verified set of data that has been carefully checked, which could be used to determine which of multiple alternative answers is correct. This motivates us to introduce the following new notion of learnability:

In the semi-verified model, we observe $n$ data points, of which an unknown $\alpha n$ are “real” data reflecting an underlying distribution $p^{*}$, and the remaining $(1-\alpha)n$ points are arbitrary. Furthermore, we observe $k$ “verified” data points that are guaranteed to be drawn from $p^{*}$.

The definition of the semi-verified model is inspired by the semi-supervised model of learning (see e.g. Chapelle et al. (2006)). In semi-supervised learning, one is concerned with a prediction/labeling task, and has access to a large amount of unlabeled data together with a small amount of labeled data; the central question is whether the presence of the unlabeled data can reduce the amount of labeled data required to learn. Analogously, in our robust learning setting, we are asking whether the presence of a large amount of untrusted data can reduce the amount of trusted data required for learning. Clearly the answer is “no” if we make no assumptions on the untrusted data. Nevertheless, the assumption that a significant fraction of that data is drawn from $p^{*}$ seems plausible, and may be sufficient to achieve strong positive results. We therefore ask:

To what extent can the availability of a modest amount of “verified” data facilitate (either computationally or information theoretically) the extraction of the information contained in the larger but untrusted dataset? What learning tasks can be performed in the above semi-verified setting given $k\ll n$ verified data points? How does the amount $k$ of verified data that is needed vary with the setting, the fraction $\alpha$ of honest data, etc.?

The above definition and associated questions reflect challenges faced in a number of practical settings, particularly those involving large crowdsourced datasets, or datasets obtained from unreliable sensors or devices. In such settings, despite the unreliability of the data, it is often possible to obtain a small verified dataset that has been carefully checked. Given its pervasiveness, it is somewhat surprising that neither the theory nor the machine learning communities have formalized this model; we think it is important to develop an understanding of the algorithmic possibilities in this domain. Obtaining theoretical guarantees seems especially important for designing provably secure learning systems that are guaranteed to perform well even if an adversary obtains control over some of the training data used by the algorithm.

The semi-verified and list decodable models can be reduced to each other. Informally, given $m$ candidate outputs from a list decodable algorithm, we expect to be able to distinguish between them with $\mathcal{O}\left(\log(m)\right)$ verified data points. Conversely, if a model is learnable with $k$ verified points then we can output $\mathcal{O}\left(({\frac{1}{\alpha}})^{k}\right)$ candidate parameters in the list decodable setting (since if we sample that many $k$-tuples from the untrusted data, at least one is likely to contain only honest data). For simplicity we state most results in the list decodable model.

From our general results (discussed in detail in the next section), we immediately obtain corollaries in specific settings, starting with mean estimation:

Since our results hold for any stochastic optimization problem, we can also study density estimation, by taking $f_{i}$ to be the negative log-likelihood:

Robust density estimation: Given an exponential family model $p_{\theta}(x)\propto\exp\left(\theta^{\top}\phi(x)\right)$, we can find a distribution $p_{{\theta}}$ with $\operatorname{KL}\left(p_{\theta^{*}}\ \|\ p_{{\theta}}\right)\leq\mathcal{O}({\frac{\sigma r}{\sqrt{\alpha}}})$, where $\operatorname{Cov}_{p_{\theta^{*}}}[\phi(x)]\preceq\sigma^{2}I$ and $r=\|\theta^{*}\|_{2}$.

While density estimation could be reduced to mean estimation (via estimating the sufficient statistics), our analysis applies directly, to an algorithm that can be interpreted as approximately maximizing the log likelihood while removing outliers.

In the list decodable setting, our results also yield bounds for learning mixtures:

It is fairly surprising that, despite making no assumptions on the structure of the data outside of a mixture component, we nearly match the best computationally efficient results that fully leverage this structure. This suggests that there may be a connection between robustness and computation: perhaps the computational threshold for recovering a planted structure in random data (such as a geometric cluster or a high-density subgraph) matches the robustness threshold for recovering that structure in the presence of an adversary.

Beyond our main results, we develop certain technical machinery that may be of broader interest. Perhaps the most relevant is a novel matrix concentration inequality, based on ideas from spectral graph sparsification (Batson et al., 2012), which holds assuming only bounded second moments:Since the writing of this paper, we were able to prove a stronger version of Proposition 1.1 that requires only bounded first moments.

This result is strong in the following sense: if one instead uses all $n$ samples $x_{i}$, the classical result of Rudelson (1999) only bounds the maximum eigenvalue by roughly ${\sigma^{2}\log(n)}$, and even then only in expectation. Even under stronger assumptions, one often needs either at least $d\log(d)$ samples, or incurs a $\log(d)$ factor in the bound on $\lambda_{\max}$. In the planted partition model, this log factor causes natural spectral approaches to fail on sparse graphs, and avoiding the log factor has been a topic of recent interest (Guédon and Vershynin, 2014; Le et al., 2015; Rebrova and Tikhomirov, 2015; Rebrova and Vershynin, 2016).

Proposition 1.1 says that the undesirable log factor only arises due to a manageable fraction of bad samples, which when removed give us sharper concentration. Our framework allows us to exploit this by defining the good data to be the (unknown) set $I$ for which the conclusion of Proposition 1.1 holds. One consequence is that we are able to recover planted partitions in sparse graphs essentially “for free”.

Separately, we introduce a novel regularizer based on minimum trace ellipsoids. This regularizer allows us to control the spectral properties of the model parameters at multiple scales simultaneously, and yields tighter bounds than standard trace norm regularization. We define the regularizer in Section 3, and prove a local Hölder’s inequality (Lemma 5.1), which exploits this regularization to achieve concentration bounds solely from deterministic spectral information.

We also employ padded decompositions, a space partitioning technique from the metric embedding literature (Fakcharoenphol et al., 2003). Their use is the following: when the loss functions are strongly convex, we can improve our bounds by identifying clusters in the data, and re-running our main algorithm on each cluster. Padded decompositions help us because they can identify clusters even if the remaining data has arbitrary structure. Our clustering scheme is described in Section 6.

The work closest to ours is Lai et al. (2016) and Diakonikolas et al. (2016), who study high-dimensional estimation in the presence of adversarial corruptions. They focus on the regime $\alpha\approx 1$, while our work focuses on $\alpha\ll 1$. In the overlap of these regimes (e.g. for $\alpha=\frac{3}{4}$) our results improve upon these existing results. (The existing bounds are better as $\alpha\to 1$, but do not hold at all if $\alpha\leq\frac{1}{2}$.) The popular robust PCA algorithm (Candès et al., 2011; Chandrasekaran et al., 2011) allows for a constant fraction of the entries to be arbitrarily corrupted, but assumes the locations of these entries are sufficiently evenly distributed. However, Xu et al. (2010) give a version of PCA that is robust to arbitrary adversaries if $\alpha>\frac{1}{2}$. Bhatia et al. (2015) study linear regression in the presence of adversaries, and obtain bounds for sufficiently large $\alpha$ (say $\alpha\geq\frac{64}{65}$) when the design matrix is subset strong convex. Klivans et al. (2009) and Awasthi et al. (2014) provide strong bounds for robust classification in high dimensions for isotropic log-concave distributions.

The only works we are aware of that achieve general adversarial guarantees when $\alpha\leq\frac{1}{2}$ are Hardt and Moitra (2013), who study robust subspace recovery in the presence of a large fraction of outliers, and Steinhardt et al. (2016), which is an early version of this work that focuses on community detection.

Balcan et al. (2008) introduce the list-decodable learning model, which was later studied by others, e.g. Balcan et al. (2009) and Kushagra et al. (2016). That work provides bounds for clustering in the presence of some adversarial data, but has two limitations relative to our results (apart from being in a somewhat different setting): the fraction of adversaries tolerated is small ($\mathcal{O}(\frac{1}{k})$), and the bounds are not meaningful in high dimensions (e.g. Balcan et al. (2008) output a list of $k^{\mathcal{O}(k/\gamma^{2})}$ hypotheses, where $\gamma$ typically scales as $1/\sqrt{d}$).

Kumar and Kannan (2010) and the follow-up work of Awasthi and Sheffet (2012) find deterministic conditions under which efficient $k$-means clustering is possible, even in high dimensions. While the goal is different from ours, their condition is similar to the quantities appearing in our error bounds, and there is some overlap in techniques. They also obtain bounds in the presence of adversaries, but only if the fraction of adversaries is smaller than $\frac{1}{k}$ as in Balcan et al. (2008). Our corollaries for learning mixtures can be thought of as extending this line of work, by providing deterministic conditions under which clustering is possible even in the presence of a large fraction of adversarial data.

Separately, there has been considerable interest in semi-random graph models (Blum and Spencer, 1995; Feige and Krauthgamer, 2000; Feige and Kilian, 2001; Coja-Oghlan, 2004; Krivelevich and Vilenchik, 2006; Coja-Oghlan, 2007; Makarychev et al., 2012; Chen et al., 2014b; Guédon and Vershynin, 2014; Moitra et al., 2015; Agarwal et al., 2015) and robust community detection (Kumar and Kannan, 2010; Moitra et al., 2015; Makarychev et al., 2015; Cai and Li, 2015). In these models, a random graph is generated with a planted structure (such as a planted clique or partition) and adversaries are then allowed to modify some parts of this structure. Typically, the adversary is constrained to only modify $o(n)$ nodes or to only modify the graph in restricted ways, though some of the above work considers substantially stronger adversaries as well.

Finally, there is a large literature on learning in the presence of errors, spanning multiple communities including learning theory (Kearns and Li, 1993) and statistics (Tukey, 1960). We refer the reader to Huber and Ronchetti (2009) and Hampel et al. (2011) for some recent surveys.

We pause to explain how our techniques relate to those of other recent robust learning papers by Diakonikolas et al. (2016) and Lai et al. (2016). At a high level, our algorithm works by solving a convex optimization problem whose objective value will be low if all of the data come from $p^{*}$; then, if the objective is high, by looking at the dual we can identify which points are responsible for the high objective value and remove them as outliers.

In contrast, Diakonikolas et al. (2016) solve a convex feasibility problem, where the feasible set depends on the true distribution $p^{*}$ and hence is not observable. Nevertheless, they show that given a point that is far from feasible, it is possible to provide a separating hyperplane demonstrating infeasibility. Roughly speaking, then, we solve a “tainted” optimization problem and clean up errors after the fact, while they solve a “clean” (but unobserved) optimization problem and show that it is possible to make progress if one is far from the optimum. The construction of the separation oracle in Diakonikolas et al. (2016) is similar to the outlier removal step we present here, and it would be interesting to further understand the relationship between these approaches.

Diakonikolas et al. (2016) also propose another algorithm based on filtering. In the case of mean estimation, the basic idea is to compute the maximum eigenvector of the empirical covariance of the data — if this eigenvector is too large, then we can find a collection of points that are responsible for it being large, and remove them as outliers. Though it is not phrased this way, it can be thought of–similarly to our approach–as solving a tainted optimization problem (top eigenvalue on the noisy data) and then cleaning up outliers afterwards. Their outlier removal step seems tighter than ours, and it would be interesting to find an approach that obtains such tight bounds for a general class of optimization problems.

Finally, Lai et al. (2016) pursue an approach based on iteratively finding the top $n/2$ eigenvectors (rather than just the top) and projecting out the remaining directions of variation, as well as removing outliers if the eigenvalues are too large. This seems similar in spirit to the filtering approach described above.

Our paper is organized as follows. In Section 2 we present our main results and some of their implications in specific settings. In Section 3 we explain our algorithm and provide some intuition for why it should work. In Section 4 we provide a proof outline for our main results. In Sections 5 and 6, we sharpen our results, first showing how to obtain concentration inequalities on the errors, and then showing how to obtain tighter bounds and stronger guarantees for strongly convex losses. In Section 7 we present lower bounds showing that our results are optimal in some settings. In Section 8 we present some intuition for our bounds, and in Section 9 we prove our main corollaries. The remaining sections are dedicated to deferred proofs.

We thank the anonymous reviewers who made many helpful comments that improved this paper. MC was supported by NSF grants CCF-1565581, CCF-1617577, CCF-1302518 and a Simons Investigator Award. JS was supported by a Fannie & John Hertz Foundation Fellowship, a NSF Graduate Research Fellowship, and a Future of Life Institute grant. GV was supported by NSF CAREER award CCF-1351108, a Sloan Foundation Research Fellowship, and a research grant from the Okawa Foundation.

Main Results and Implications

This stochastic optimization setting captures most concrete settings of interest — for instance, mean estimation corresponds to $f_{i}(w)=\|w-x_{i}\|_{2}^{2}$, linear regression to $f_{i}(w)=(y_{i}-\langle w,x_{i}\rangle)^{2}$, and logistic regression to $f_{i}(w)=\log(1+\exp(-y_{i}\langle w,x_{i}\rangle))$.

The fact that $f_{i}\sim p^{*}$ is irrelevant to our results—all that matters is the quantity $S$, which exists even for a deterministic set of functions $f_{1},\ldots,f_{n}$. Furthermore, $S$ only depends on the good data and is independent of the adversary.

The definition (1) is a bit complex, so we go over some examples for intuition. We will see later that for the first two examples below (estimating means and product distributions), our implied error bounds are “good”, while for the final example (linear classification), our bounds are “bad”.

Product distributions: Suppose that $x_{i}$ is drawn from a product distribution on $\{0,1\}^{d}$, where the $j$th coordinate is $1$ with probability $p_{j}$. Let $f_{i}(w)=\sum_{j=1}^{d}x_{ij}\log(w_{j})+(1-x_{ij})\log(1-w_{j})$. In this case $\bar{f}(w)=\sum_{j=1}^{d}p_{j}\log(w_{j})+(1-p_{j})\log(1-w_{j})$, and $w_{j}^{*}=p_{j}$, so that $\bar{f}(w)-\bar{f}(w^{*})$ is the KL divergence between $p$ and $w$.

Linear classification: Suppose that $x_{i}\sim\mathcal{N}(0,I)$ and that $y_{i}=\operatorname{sign}(u^{\top}x_{i})$ for some unknown vector $u$. Our loss function is the logistic loss $f_{i}(w)=\log(1+\exp(-y_{i}\langle w,x_{i}\rangle))$. In this case $\nabla f_{i}(w)=-\frac{y_{i}}{1+\exp(y_{i}\langle w,x_{i}\rangle)}x_{i}$. It is less obvious how to compute $S$, but Lemma 2.1 below implies that it is $\mathcal{O}(1)$.

If $\nabla f_{i}(w)-\nabla\bar{f}(w)$ is $\sigma$-sub-Gaussian and $L$-Lipschitz for $f_{i}\sim p^{*}$, and $\alpha n$ is at least $d\max(1,\log(\tfrac{rL}{\sigma}))+\log(1/\delta)$, then $S=\mathcal{O}\left(\sigma\right)$ with probability $1-\delta$.

1 Main Results

We can now state our main results. Our first result is that, just using the untrusted data, we can output a small ellipse which contains a parameter attaining small error under $\bar{f}$. This meta-result leads directly to our more specific results in the list decoding and semi-verified settings.

By applying our algorithm multiple times we can improve the bound $\|w-\mu\|_{2}^{2}=\mathcal{O}\left(\sigma\|\mu\|_{2}/\sqrt{\alpha}\right)$ to $\|w-\mu\|_{2}^{2}=\mathcal{O}\left(\sigma^{2}/\alpha\right)$, so that our bounds are meaningful for large $d$ independent of $\|\mu\|_{2}$. We discuss this in more detail in Section 6.

For an example where Theorem 2.2 is less meaningful, consider the linear classification example from above. In that case $S=\mathcal{O}(1)$, and $r$ is likely also $\mathcal{O}(1)$, so we obtain the bound $\bar{f}(w)-\bar{f}(w^{*})=\mathcal{O}(1/\sqrt{\alpha})$. However, $\bar{f}(0)=\log(2)$ while $\bar{f}(w^{*})\geq 0$, so this bound is essentially vacuous.

Using Theorem 2.2 as a starting point we can derive bounds for both models defined in Section 1, starting with the list decodable model. Here, we must make the further assumption that the $f_{i}$ are $\kappa$-strongly convex, meaning that $f_{i}(w^{\prime})-f_{i}(w)\geq(w^{\prime}-w)^{\top}\nabla f_{i}(w)+\frac{\kappa}{2}\|w^{\prime}-w\|_{2}^{2}$. The strong convexity allows us to show that for the good $f_{i}$, the parameters $\hat{w}_{i}=\operatornamewithlimits{arg\,min}_{w\in\mathcal{E}_{Y}}f_{i}(w)$ concentrate around $w^{*}$, with radius $r^{\prime}\ll r$. By clustering the $\hat{w}_{i}$ and iteratively re-running our algorithm on each cluster, we can obtain bounds that do not depend on $r$, and output a single candidate parameter $\hat{w}_{j}$ for each cluster. We can thereby show:

In Section 6 we state and prove a stronger version of this result. A key tool in establishing Theorem 2.3 is padded decompositions (Fakcharoenphol et al., 2003), which identify clusters in data while making minimal assumptions on the geometry of points outside of a cluster, and are thus useful in our adversarial setting.

If the $f_{i}$ are not strongly convex then we cannot employ the clustering ideas above. However, because we have reduced $\mathcal{H}$ to the much smaller set $\mathcal{E}_{Y}$, we can nevertheless often approximate $w^{*}$ with only a small amount of verified data. In fact, in some settings we only need a single verified data point:

The particular functional form for $f_{i}$ was needed to obtain a concrete bound, but analogs of Lemma 2.4 should be possible in any setting where we can leverage the low complexity of $\mathcal{E}_{Y}$ into a bound on $f-\bar{f}$. Note that if we replace $\mathcal{E}_{Y}$ with $\mathcal{H}$ in Lemma 2.4, then the $\frac{r}{\sqrt{\alpha}}$ dependence becomes $r\sqrt{d}$, which is usually vacuous.

The dependence on $S$, $r$ and $\kappa$ in the results above seems essentially necessary, though the optimal dependence on $\alpha$ is less clear. In Section 7 we show lower bounds for robust mean estimation even if $p^{*}$ is known to be Gaussian. These bounds roughly translate to a lower bound of \Omega\big{(}{\frac{S}{\kappa}{\sqrt{\log{({1}/{\alpha})}}}}\big{)} for strongly convex $f_{i}$, and \Omega\big{(}{Sr\sqrt{\log(\smash{{1}/{\alpha}})}}\big{)} for linear $f_{i}$, and hold in both the list decodable and semi-verified settings. It is unclear whether the optimal dependence on $\alpha$ is $\sqrt{{1}/{\alpha}}$ or $\sqrt{\log({1}/{\alpha})}$ or somewhere between. We do note that any dependence better than $\sqrt{{1}/{\alpha}}$ would improve the best known results for efficiently solving $k$-means for well-separated clusters, which may suggest at least a computational barrier to achieving $\sqrt{\log({1}/{\alpha})}$.

2 Implications

We now go over some implications of our general results in some more specific settings. All of the results below follow as corollaries of our main theorems, and are proved in Section 9.

Suppose that $p^{*}$ has bounded covariance: $\operatorname{Cov}_{p^{*}}[x]\preceq\sigma^{2}I$. Then, for $n\geq\frac{d}{\alpha}$, with probability $1-\exp\left(-\Omega(\alpha n)\right)$ it is possible to output $m\leq\mathcal{O}\left(\frac{1}{\alpha}\right)$ candidate means $\hat{\mu}_{1},\ldots,\hat{\mu}_{m}$ such that \min_{j=1}^{m}\|\mu-\hat{\mu}_{j}\|_{2}\leq\mathcal{O}\Big{(}{\sigma\sqrt{\frac{\log(2/\alpha)}{\alpha}}}\Big{)}. Moreover, if $\alpha\geq 0.51$ then we can take $m=1$.

We can compare to the results of Lai et al. (2016) and Diakonikolas et al. (2016), who study mean estimation when $\alpha>\frac{1}{2}$ and one is required to output a single parameter (i.e., $m=1$). For simplicity take $\alpha=\frac{3}{4}$. Roughly, Lai et al. (2016) obtain error $\mathcal{O}({\sigma\sqrt{\log(d)}})$ with sample complexity $n=\mathcal{O}\left(d\right)$, while requiring a bound on the fourth moments of $p^{*}$; Diakonikolas et al. (2016) obtain error $\mathcal{O}\left(\sigma\right)$ with sample complexity $n=\mathcal{O}\left(d^{3}\right)$, and require $p^{*}$ to be Gaussian. Corollary 2.5 improves both of these by yielding error $\mathcal{O}\left(\sigma\right)$ with sample complexity $n=\mathcal{O}\left(d\right)$, and only requires $p^{*}$ to have bounded second moments. Some fine print: Diakonikolas et al. also estimate the covariance matrix, and their recovery results are stronger if $\Sigma=\operatorname{Cov}[x]$ is highly skewed; they roughly show $\|\hat{\mu}-\mu\|_{\Sigma^{-1}}=\mathcal{O}(1)$. The adversary model considered in both of these other papers is also slightly more general than ours: first $n$ points are drawn from $p^{*}$ and then an adversary is allowed to corrupt $(1-\alpha)n$ of the points. However, it is straightforward to show (by monotonicity of the operator norm) that our bounds will be worse by at most a $1/\sqrt{\alpha}$ factor in this stricter setting, which is a constant if $\alpha=\frac{3}{4}$. We note that in contrast to our results, these other results obtain error that vanishes as $\alpha\to 1$ (at a rate of $(1-\alpha)^{1/2}$ in the first case and $\widetilde{\mathcal{O}}(1-\alpha)$ in the second case). We thus appear to incur some looseness when $\alpha\approx 1$, in exchange for obtaining results in the previously unexplored setting $\alpha\leq\frac{1}{2}$. It would be interesting to obtain a single algorithm that both applies when $\alpha\ll 1$ and achieves vanishing error as $\alpha\to 1$.

Suppose we are given $n$ samples, where each sample either comes from one of $k$ distributions $p_{1}^{*},\ldots,p_{k}^{*}$ (with $\operatorname{Cov}_{p_{i}^{*}}[x]\preceq\sigma^{2}I$ for all $i$), or is arbitrary. Let $\mu_{i}$ be the mean of $p_{i}^{*}$, let $\alpha_{i}$ be the fraction of points from $p_{i}^{*}$, and let $\alpha=\min_{i=1}^{k}\alpha_{i}$. Then if $n\geq\frac{d}{\alpha}$, with probability $1-k\exp(-\Omega(\alpha\varepsilon^{2}n))$ we can obtain a partition $T_{1},\ldots,T_{m}$ of $[n]$ and corresponding candidate means $\hat{\mu}_{1},\ldots,\hat{\mu}_{m}$ such that: for all but $\varepsilon\alpha_{i}n$ of the points drawn from $p_{i}^{*}$, the point is assigned a set $T_{j}$ and candidate mean $\hat{\mu}_{j}$ with $\|\mu_{i}-\hat{\mu}_{j}\|_{2}\leq\mathcal{O}\left(\frac{\sigma}{\varepsilon}\sqrt{\frac{\log(\frac{2}{\alpha})}{\alpha}}\right)$. Moreover, $m\leq\mathcal{O}\left(\frac{1}{\alpha}\right)$.

The $\frac{1}{\varepsilon}$ dependence can be replaced with $\sqrt{\log(n)/\varepsilon}$, or with $\sqrt{\log(2/\varepsilon)}$ if the $x_{i}$ are sub-Gaussian. The only difference is in which matrix concentration bound we apply to the $x_{i}$. Corollary 2.6 says that we can partition the points into $\mathcal{O}\left(\frac{1}{\alpha}\right)$ sets, such that two points from well-separated clusters are unlikely to end up in the same set. Note however that one cluster might be partitioned into multiple sets. In the adversarial setting, this seems unavoidable, since an adversary could create a fake cluster very close to a real cluster, and one would be forced to either combine the clusters or risk splitting the real cluster in two.

We next consider implications of our results in a version of the planted partition model (McSherry, 2001). In this model we observe a random directed graph, represented as a matrix $A\in\{0,1\}^{n\times n}$. For disjoint subsets $I_{1},\ldots,I_{k}$ of $[n]$, we generate edges as follows: (i) If $u,v\in I_{i}$, then $p(A_{uv}=1)=\frac{a}{n}$. (ii) If $u\in I_{i},v\not\in I_{i}$, then $p(A_{uv}=1)=\frac{b}{n}$. (iii) If $u\not\in\cup_{i=1}^{k}I_{i}$, the edges emanating from $u$ can be arbitrary. In contrast to the typical planted partition model, we allow some number of corrupted vertices not belonging to any of the $I_{i}$. In general $a$ and $b$ could depend on the partition indices $i$, $j$, but we omit this for simplicity.

Note that the distribution over the row $A_{u}$ is the same for all $u\in I_{i}$. By taking this distribution to be the distribution $p^{*}$, Theorem 2.3 yields the following result:

For the planted partition model above, let $\alpha=\min_{i=1}^{k}\frac{|I_{i}|}{n}$. Then, with probability $1-\exp(-\Omega(\alpha n))$, we can obtain sets $T_{1},\ldots,T_{m}\subseteq[n]$, with $m\leq\mathcal{O}\left(\frac{1}{\alpha}\right)$, such that for all $i\in[k]$, there is a $j\in[m]$ with $|I_{i}\triangle T_{j}|\leq\mathcal{O}\left(\frac{a\log(\frac{2}{\alpha})}{\alpha^{2}(a-b)^{2}}\right)n$, where $\triangle$ denotes symmetric difference.

This shows that we can approximately recover the planted partition, even in the presence of arbitrary corruptions, provided $\frac{(a-b)^{2}}{a}\gg\frac{\log(2/\alpha)}{\alpha^{3}}$ (since the bound on $|I_{i}\triangle T_{j}|$ needs to be less than $\alpha n$ to be meaningful). In contrast, the best efficient methods (assuming no corruptions) roughly require $\frac{(a-b)^{2}}{a+(k-1)b}\gg k$ in the case of $k$ equal-sized communities (Abbe and Sandon, 2015a; b). In the simplifying setting where $b=\frac{1}{2}a$, our bounds require $a\gg k^{3}\log(k)$ while existing bounds require $a\gg k^{2}$. The case of unequal size communities is more complex, but roughly, our bounds require $a\gg\frac{\log(2/\alpha)}{\alpha^{3}}$ in contrast to $a\gg\frac{1}{\alpha^{2}}$.

Algorithm

In this section we present our algorithm, which consists of an SDP coupled with an outlier removal step. At a high level, our algorithm works as follows: first, we give each function $f_{i}$ its own parameter vector $w_{i}$, and minimize $\sum_{i=1}^{n}f_{i}(w_{i})$ subject to regularization which ensures the $w_{i}$ remain close to each other; formally, we bound the $w_{i}$ to lie within a small ellipse. The reason for doing this is that the different $w_{i}$ are now only coupled via this regularization, and so the influence of adversarial data on the good parameters can only come from its effect on the shape of the ellipse. We will show that whenever the adversaries affect the shape of the ellipse more than a small amount, they are necessarily outliers that can be identified and removed. In the remainder of this section, we elaborate on these two steps of regularization and outlier removal, and provide pseudocode.

If the functions $f_{1},\ldots,f_{n}$ were all drawn from $p^{*}$ (i.e., there are no adversaries), then a natural approach would be to let $\hat{w}$ be the minimizer of $\sum_{i=1}^{n}f_{i}(w)$, which will approximately minimize $\bar{f}(w)$ by standard concentration results.

The problem with using this approach in the adversarial setting is that even a single adversarially chosen function $f_{i}$ could substantially affect the value of $\hat{w}$. To minimize this influence, we give each $f_{i}$ its own parameter $w_{i}$, and minimize $\sum_{i=1}^{n}f_{i}(w_{i})$, subject to a regularizer which encourages the $w_{i}$ to be close together. The adversary now has no influence on the good $w_{i}$ except via the regularizer, so the key challenge is to find a regularizer which sufficiently controls statistical error while also bounding the influence of the adversary.

It turns out that the right choice of regularizer in this case is to constrain the $w_{i}$ to lie within an ellipse with small trace. Formally, the centerpiece of our algorithm is the following convex optimization problem:

Here the coefficients $c_{i}$ are non-negative weights which will eventually be used to downweight outliers (for now it is fine to imagine that $c_{i}=1$). Note that $w_{i}w_{i}^{\top}\preceq Y$ is equivalent to the semidefinite constraint \left[\begin{array}[]{cc}Y&w_{i}\\ w_{i}^{\top}&1\end{array}\right]\succeq 0. The problem (4) can be solved in polynomial time in $n$ and $d$ assuming oracle access to the gradients $\nabla f_{i}$.

Note that the semidefinite constraint $w_{i}w_{i}^{\top}\preceq Y$ is equivalent to $w_{i}^{\top}Y^{-1}w_{i}\leq 1$, which says that $w_{i}$ lies within the ellipse centered at defined by $Y$. The regularizer is thus the trace of the minimum ellipse containing the $w_{i}$; penalizing this trace will tend to push the $w_{i}$ closer together, but is there any intuition behind its geometry? The following lemma shows that $\operatorname{tr}(Y)$ is related to the trace norm of $\left[w_{1}\ \cdots\ w_{n}\right]$:

The appearance of the trace norm makes sense in light of the intuition that we should be clustering the functions $f_{i}$; indeed, trace norm regularization is a key ingredient in spectral algorithms for clustering (see e.g. Zha et al. (2001); Chen et al. (2014a; b)). Lemma 3.1 says that $\operatorname{tr}(Y)$ simultaneously bounds the trace norm on every subset $T$ of $[n]$, which ends up yielding better results than are obtained by simply penalizing the overall trace norm; we believe that this local trace norm regularization likely leads to better results even in non-adversarial spectral learning settings. The most important property of $\operatorname{tr}(Y)$ is that it admits a certain type of local Hölder’s inequality which we will explain in Section 5.

Pseudocode for our algorithm is given in Algorithms 1 and 2.

Approach and Proof Outline

We now provide an outline of the proof of Theorem 2.2, by analyzing the output of Algorithm 1. The structure of our proof has analogies to classical uniform convergence arguments, so we will start by reviewing that case.

In uniform convergence arguments, we assume that all of $f_{1},\ldots,f_{n}$ are drawn from $p^{*}$, which brings us into the realm of classical learning theory. The analogue to the optimization (3) in Algorithm 1 is regularized empirical risk minimization:

where $h(w)$ is a non-negative regularizer. Uniform convergence arguments involve two parts:

Bound the optimization error: Use the definition of $\hat{w}$ to conclude that $\sum_{i=1}^{n}f_{i}(\hat{w})\leq\sum_{i=1}^{n}f_{i}(w^{*})+\lambda h(w^{*})$ (since $\hat{w}$ minimizes (7)). This step shows that $\hat{w}$ does almost as well as $w^{*}$ at minimizing the empirical risk $\sum_{i=1}^{n}f_{i}(w)$.

Bound the statistical error: Show, via an appropriate concentration inequality, that $\frac{1}{n}\sum_{i=1}^{n}f_{i}(w)$ is close to $\bar{f}(w)$ for all $w\in\mathcal{H}$. Therefore, $\hat{w}$ is nearly as good as $w^{*}$ in terms of the true risk $\bar{f}$.

We will see next that the proof of Theorem 2.2 contains steps similar to these, though bounding the statistical error in the presence of adversaries requires an additional step of removing outliers.

Proof Overview

We will establish a stronger version of Theorem 2.2, which exhibits an explicit $w\in\mathcal{E}_{\hat{Y}}$ with small error:

To prove Theorem 4.1, recall that Algorithm 1 has at its core the following optimization problem:

Throughout the argument, we will make use of the optimality of $(\hat{w}_{1:n},\hat{Y})$ for (8), which implies that

The solution $\hat{w}_{1:n}$ to (8) satisfies

We next consider the statistical error. We cannot bound this error via standard uniform convergence techniques, because each $f_{i}$ has a different argument $\hat{w}_{i}$. However, it turns out that the operator norm bound $S$, together with a bound on $\operatorname{tr}(\hat{Y})$, yield concentration of the $f_{i}$ to $\bar{f}$. In particular, we have:

Moreover, the above supposition holds if $\lambda=\frac{\sqrt{8\alpha}nS}{r}$ and $\operatorname{tr}(\hat{Y})>\frac{6r^{2}}{\alpha}$.

Lemma 4.5 ensures that eventually we have $\operatorname{tr}(\hat{Y})\leq\mathcal{O}\left(\frac{r^{2}}{\alpha}\right)$, which allows us to bound the overall statistical error (using Lemma 4.3) by $\mathcal{O}\left(\sqrt{\alpha}nrS\right)$. In addition, since $\lambda=\mathcal{O}\left(\sqrt{\alpha}nS/r\right)$, the optimization error is bounded (via Lemma 4.2) by $\mathcal{O}\left(\sqrt{\alpha}nrS\right)$, as well. Combining the various bounds, we end up obtaining

In the remainder of this section, we will prove Lemmas 4.2 through 4.5, then show more formally how Theorem 4.1 follows from these lemmas.

Proof of Lemma 4.2

Proof of Lemma 4.3

For any $w_{0}$ and any $w_{1:n}$ satisfying $w_{i}w_{i}^{\top}\preceq Y$ for all $i$, we have

To establish (11) from Lemma 4.6, note that

where (i) is by convexity of $f_{i}$, (ii) is because

Proof of Lemma 4.4

Proof of Lemma 4.5

Now, remember that $c_{i}^{\prime}=c_{i}\cdot\frac{z_{\max}-z_{i}}{z_{\max}}$. Then for any $S\subseteq[n]$, we have

Proof of Theorem 4.1

Concentration of Errors: A Local Hölder’s Inequality

If the good data is sub-Gaussian, then can we obtain sub-Gaussian concentration of the errors, or can the adversaries force the error to only be small in expectation? What properties of the good data affect concentration of errors in the presence of an adversary?

We call this a local Hölder’s inequality because it is a sharpening of Lemma 4.6, which established via Hölder’s inequality that

Moreover, for any $w,w^{\prime}\in\mathcal{H}$, we have

Our outlier removal step can be modified based on $S_{\varepsilon}$ so that almost none of the good points are removed. This is not strictly necessary for any of our later results, but is an intuitively appealing property for our algorithm to have. That we can preserve the good points is unsurprising in light of Corollary 5.3, which says that the good points concentrate, and hence should be cleanly separable from any outliers. The modified outlier removal step is given as Algorithm 3.

Suppose that $\lambda=\frac{\sqrt{8\alpha}nS}{r}$ and $\operatorname{tr}(\hat{Y})>\frac{35r^{2}}{\alpha}$. Then, the update step in Algorithm 3 satisfies

We end this section by giving some intuition for the typical scale of $S_{\varepsilon}$. Recall that Lemma 2.1 shows that, when the gradients of $f_{i}$ are sub-Gaussian with parameter $\sigma$, then $S\leq\mathcal{O}({\sigma})$ assuming $n\gg d/\alpha$. A similar bound holds for $S_{\varepsilon}$, with an additional factor of $\sqrt{\log(2/\varepsilon)}$:

If $\nabla f_{i}(w)-\nabla\bar{f}(w)$ is $\sigma$-sub-Gaussian and $L$-Lipschitz, then with probability $1-\delta$ we have

In particular, if $n\geq\frac{1}{\varepsilon\alpha}\left(d\max\left(1,\log(\tfrac{rL}{\sigma})\right)+\log(1/\delta)\right)$, then $S_{\varepsilon}=\mathcal{O}\left(\sigma\sqrt{\log(2/\varepsilon)}\right)$ with probability $1-\delta$, where $\mathcal{O}(\cdot)$ masks only absolute constants.

What happens if the function errors are not sub-Gaussian, but we still have a bound on $S=S_{1}$? We can then bound $S_{\varepsilon}$ in terms of $S$ by exploiting the monotonicity of the operator norm.

For any $\varepsilon_{1}\leq\varepsilon_{2}$, $S_{\varepsilon_{1}}\leq\sqrt{\frac{\lfloor\varepsilon_{2}\alpha n\rfloor}{\lfloor\varepsilon_{1}\alpha n\rfloor}}S_{\varepsilon_{2}}\leq 2\sqrt{\frac{\varepsilon_{2}}{\varepsilon_{1}}}S_{\varepsilon_{2}}$.

Proof of Lemma 5.1

Throughout this section we will for convenience use $\Delta_{i}$ to denote $\nabla f_{i}(w_{0})-\nabla\bar{f}(w_{0})$. We start with a helper lemma that translates information about $S_{\varepsilon}$ into a more useful form:

Letting $D_{T}=[\Delta_{i}]_{i\in T}$, we show this as follows:

as was to be shown. Here (i) is Cauchy-Schwarz and (ii) uses the condition $w_{i}w_{i}^{\top}\preceq Y$. ∎

Proof of Lemma 5.2

In the final step we invoke (46) twice, identically to Lemma 4.3.

For (50), we follow an identical argument to (12) from Lemma 4.3. Defining $w(t)=tw+(1-t)w^{\prime}$, we have

This yields (50) and completes the lemma.

Proof of Corollary 5.3

On the other hand, by Lemmas 4.3 and 4.2, we also have

Proof of Lemma 5.4

Proof of Lemma 5.6

Bounds for Strongly Convex Losses

We now turn our attention to the special case that the functions $f_{i}$ are strongly convex in $w$, in the sense that for all $w,w^{\prime}\in\mathcal{H}$,

In this case, we will obtain stronger bounds by iteratively clustering the output $\hat{w}_{1:n}$ of Algorithm 1 and re-running the algorithm on each cluster. The main theorem in this section is a recovery result in the list decoding model, for an algorithm (Algorithm 4) that formalizes this clustering intuition:

Note, interestingly, that the bound does not depend on the radius $r$. Since the list decoding model can be reduced to the semi-verified model, Theorem 6.1 also yields strengthened results in the semi-verified model when the functions are strongly convex (we omit these for brevity).

By strong convexity of $f_{i}$, we then have

Let $x_{1},\ldots,x_{n}$ be points in a metric space. A ($\rho,\tau,\delta$)-padded decomposition is a (random) partition $\mathcal{P}$ of $\{x_{1},\ldots,x_{n}\}$ such that: (i) each element of $\mathcal{P}$ has diameter at most $\rho$, and (ii) for each $x_{i}$, with probability $1-\delta$ all points within distance $\tau$ of $x_{i}$ lie in a single element of $\mathcal{P}$.

Fakcharoenphol et al. (2003) show that for any $\tau$ and $\delta$, a $(\rho,\tau,\delta)$-padded decomposition exists with $\rho=\mathcal{O}\left(\frac{\tau\log(n)}{\delta}\right)$. Moreover, the same proof shows that, if every $x_{i}$ is within distance $\tau$ of at least $\Omega(\alpha n)$ other $x_{i}$, then we can actually take $\rho=\mathcal{O}\left(\frac{\tau\log(2/\alpha)}{\delta}\right)$. In particular, in our case we can obtain a $(\mathcal{O}\left(s\log(2/\alpha)\right),2s,7/8)$-padded decomposition of the $\hat{w}_{i}$ output by Algorithm 1; we show this formally in Lemma A.1. This probabilistic notion of clustering turns out to be sufficient for our purposes.

We are now prepared to analyze Algorithm 4. In each iteration, Algorithm 4 independently samples $l=112\log\left(\frac{t(t+1)}{\delta}\right)$ padded decompositions of the $\hat{w}_{i}$. For each decomposition $\mathcal{P}_{h}$, it then runs Algorithm 1 on each component of the resulting partition, and thereby obtains candidate values $\bar{w}_{1}(h),\ldots,\bar{w}_{n}(h)$. Finally, it updates $\hat{w}_{i}$ by finding a point close to at least $\frac{1}{2}$ of the candidate values $\bar{w}_{i}(h)$, across $h=1,\ldots,l$.

If we formalize this argument, then we obtain Lemma 6.5, which controls the behavior of the update $\hat{w}_{1:n}^{(t)}\to\hat{w}_{1:n}^{(t+1)}$ on each iteration of the loop:

Essentially, Lemma 6.5 shows that if almost all of the good points are within $r^{(t)}$ of $w^{*}$ at the beginning of a loop iteration, then almost all of the good points are within $\frac{1}{2}r^{(t)}$ of $w^{*}$ at the end of that loop iteration, provided $r^{(t)}$ is large enough. Using Lemma 6.5, we can establish Theorem 6.1.

Proof of Theorem 6.1

Proof of Proposition 6.2

Proof of Corollary 6.4

where the first inequality is convexity of $\|\cdot\|_{2}^{2}$, and the second is because we only added positive terms to the sum.

Now, we will apply Lemma 6.3 at the value $b_{i}^{\prime}=\frac{1}{2}\left(b_{i}+\frac{B}{C}c_{i}\right)$. This satisfies $b_{i}^{\prime}\in$ (since $\sum_{j}c_{j}\geq\sum_{j}b_{j}$), and also $\sum_{i}b_{i}^{\prime}=\sum_{i}b_{i}\geq\varepsilon\alpha n$. We can therefore invoke Lemma 6.3 to obtain

Proof of Lemma 6.5

Now if $i$ is not bad, then $\|\bar{w}_{i}(h)-w^{*}\|_{2}\leq\frac{1}{6}r^{(t)}$ for at least $\frac{5l}{8}$ values of $h$ (because it is small for all but $\frac{l}{8}$ of the at least $\frac{3l}{4}$ good $h$). Now, consider any $\bar{w}_{i}(h_{0})$ that is within distance $\frac{1}{3}r^{(t)}$ of at least $\frac{l}{2}$ of the $\bar{w}_{i}(h)$. By the pigeonhole principle, $\bar{w}_{i}(h_{0})$ is therefore close to at least one of these good $\bar{w}_{i}(h)$, and so satisfies $\|\bar{w}_{i}(h_{0})-w^{*}\|_{2}\leq\|\bar{w}_{i}(h_{0})-\bar{w}_{i}(h)\|_{2}+\|\bar{w}_{i}(h)-w^{*}\|_{2}\leq\frac{1}{2}r^{(t)}$. Moreover, such a $h_{0}$ exists since any of the good $\bar{w}_{i}(h)$ be within distance $\frac{1}{3}r^{(t)}$ of the other good $\bar{w}_{i}(h^{\prime})$.

Lower Bounds

In this section we prove lower bounds showing that the dependence of our bounds on $S$ is necessary even if $p^{*}$ is a multivariate Gaussian. For $\alpha$, we are only able to show a necessary dependence of $\sqrt{\log(\frac{1}{\alpha})}$, rather than the $\sqrt{{1}/{\alpha}}$ appearing in our bounds. Determining the true worst-case dependence on $\alpha$ is an interesting open problem.

One natural question is whether $S$, which typically depends on the maximum singular value of the covariance matrix, is really the right dependence, or whether we could achieve bounds based on e.g. the average singular value instead. Lemma 7.1 rules this out, showing that it would require $\Omega(2^{k})$ candidates in the list-decodable setting to achieve dependence on even the $k$th singular value of the covariance matrix.

Suppose that $p^{*}$ is known to be a multivariate Gaussian $\mathcal{N}(\mu,\Sigma)$ with covariance $\Sigma\preceq\Sigma_{0}$, where $\mu$ and $\Sigma$ are otherwise unknown. Also let $\sigma_{k}^{2}$ denote the $k$th largest singular value of $\Sigma_{0}$. Then, given any amount of data, an $\alpha$-fraction of which is drawn from $p^{*}$, any procedure for outputting at most $m=2^{k-1}$ candidate means $\hat{\mu}_{1},\ldots,\hat{\mu}_{m}$ must have, with probability at least $\frac{1}{2}$, $\min_{j=1}^{m}\|\hat{\mu}_{j}-\mu\|_{2}\geq\frac{\sigma_{k}}{4}\cdot\frac{\log(\frac{1}{\alpha})}{\sqrt{1+\log(\frac{1}{\alpha})}}$.

By the reduction from the semi-verified to the list-decodable model, we obtain a lower bound in the semi-verified setting as well:

Any algorithm that has $\|\hat{\mu}-\mu\|_{2}<\frac{\sigma_{k}}{4}\cdot\frac{\log(\frac{1}{\alpha})}{\sqrt{1+\log(\frac{1}{\alpha})}}$ with probability at least $\frac{1}{2}$ in the semi-verified model requires at least $\frac{k-2}{\log_{2}(\frac{1}{\alpha})}$ verified samples.

Let us suppose that the unverified data has distribution $\hat{p}=\mathcal{N}(0,\Sigma_{0})$, which is possible iff $\hat{p}\geq\alpha p^{*}$. We start with a lemma characterizing when it is possible that the true distribution $p^{*}$ has mean $\mu$:

Let $\hat{p}=\mathcal{N}(0,\Sigma_{0})$ and $p^{*}=\mathcal{N}(\mu,\Sigma_{0}-\lambda\mu\mu^{\top})$. Then $\hat{p}\geq\alpha p^{*}$ provided that $\mu^{\top}\Sigma_{0}^{-1}\mu\leq\frac{\log^{2}(\frac{1}{\alpha})}{1+\log(\frac{1}{\alpha})}$ and $\lambda=\frac{1}{\log(\frac{1}{\alpha})}$.

As a consequence, if $\mu^{\top}\Sigma_{0}^{-1}\mu\leq t^{2}$ for $t=\frac{\log(\frac{1}{\alpha})}{\sqrt{1+\log(\frac{1}{\alpha})}}$, then $p^{*}$ could have mean $\mu$. Now, consider the space spanned by the $k$ largest eigenvectors of $\Sigma_{0}$, and let $B_{k}$ be the ball of radius $t\sigma_{k}$ in this space. Also let $\mathcal{P}$ be a maximal packing of $B_{k}$ of radius $\frac{t}{4}\sigma_{k}$. A simple volume argument shows that $|B_{k}|\geq 2^{k}$. On the other hand, every element $\mu$ of $B_{k}$ is a potential mean because it satisfies $\mu^{\top}\Sigma_{0}^{-1}\mu\leq\frac{\|\mu\|_{2}^{2}}{\sigma_{k}^{2}}\leq t^{2}$. Therefore, if the true mean $\mu$ is drawn uniformly from $B_{k}$, any $2^{k-1}$ candidate means $\hat{\mu}_{j}$ must miss at least half of the elements of $B_{k}$ (in the sense of being distance at least $\frac{t}{4}\sigma_{k}$ away) and so with probability at least $\frac{1}{2}$, $\|\hat{\mu}_{j}-\mu\|_{2}$ is at least $\frac{t}{4}\sigma_{k}$ for all $j$, as was to be shown.

Proof of Corollary 7.2

Suppose that we can obtain $\hat{\mu}$ satisfying $\|\hat{\mu}-\mu\|_{2}<\frac{\sigma_{k}}{4}\cdot\frac{\log(\frac{1}{\alpha})}{\sqrt{1+\log(\frac{1}{\alpha})}}$ with $m\leq\frac{k-2}{\log_{2}(\frac{1}{\alpha})}$ samples, with probability at least $\frac{1}{2}$. If we sample $m$ elements uniformly from the unverified samples, with probability $\alpha^{m}$ we will obtain only samples from $p^{*}$, and therefore with probability $\frac{1}{2}\alpha^{m}$ we can obtain (by assumption) a candidate mean $\hat{\mu}$ with $\|\hat{\mu}-\mu\|_{2}<\frac{\sigma_{k}}{4}\cdot\frac{\log(\frac{1}{\alpha})}{\sqrt{1+\log(\frac{1}{\alpha})}}$. If we repeat this $\frac{2}{\alpha^{m}}$ times, then with probability $1-\left(1-\frac{1}{2}\alpha^{m}\right)^{\frac{2}{\alpha^{m}}}\geq 1-\frac{1}{e}>\frac{1}{2}$, at least one of the candidate means will be close to $\mu$. But by Lemma 7.1, this implies that $\frac{2}{\alpha^{m}}\geq 2^{k-1}$, and so $m\geq\frac{k-2}{\log_{2}(\frac{1}{\alpha})}$, as claimed.

Intuition: Stability Under Subsets

In this section, we establish a sort of “duality for robustness” that provides intuition underlying our results. Essentially, we will show the following:

If a statistic of a dataset is approximately preserved across every large subset of the data, then it can be robustly recovered even in the presence of a large amount of additional arbitrary/adversarial data.

In such a case, can we approximate the mean of $I$, even if $I$ is not known and the points in $[n]\backslash I$ are arbitrary?

If we do not care about computation, the answer is yes, via a simple exponential-time algorithm. Call a set of points $J$ $\alpha$-stable if it satisfies the following properties: $|J|\geq\alpha n$, and (102) holds with $I$ replaced by $J$ (i.e., the mean moves by at most $\varepsilon$ when taking subsets of $J$ of size at least $\frac{1}{2}\alpha^{2}n$). Then, we can run the following (exponential-time) algorithm:

Find an $\alpha$-stable set $J$ which has overlap at most $\frac{1}{2}\alpha^{2}n$ with all elements of $\mathcal{U}$.

Append $J$ to $\mathcal{U}$ and continue until no more such sets exist.

A simple inclusion-exclusion argument Specifically, $k$ sets of size $\alpha n$ with pairwise overlap $\frac{1}{2}\alpha^{2}n$ must have a union of size at least $k\alpha n-\frac{1}{2}\binom{k}{2}\alpha^{2}n$, which implies $k\leq\frac{2}{\alpha}$. shows that $k\leq\frac{2}{\alpha}$. Therefore, the above algorithm terminates with $|\mathcal{U}|\leq\frac{2}{\alpha}$. On the other hand, by construction, $I$ must have overlap at least $\frac{1}{2}\alpha^{2}n$ with at least one element of $\mathcal{U}$ (as otherwise we could have also added $I$ to $\mathcal{U}$). Therefore, for some $J\in\mathcal{U}$, $|I\cap J|\geq\frac{1}{2}\alpha^{2}n$. But then, letting $T=I\cap J$, we have $\|\mu_{I}-\mu_{J}\|_{2}\leq\|\mu_{I}-\mu_{T}\|_{2}+\|\mu_{T}-\mu_{J}\|_{2}\leq 2\varepsilon$. Therefore, the mean over $I$ is within distance $2\varepsilon$ of at least one of the $\mu_{J}$, for $J\in\mathcal{U}$.

We have therefore established our stated duality property for robustness: if a statistic is stable under taking subsets of data, then it can also be recovered if the data is itself a subset of some larger set of data.

Can we make the above algorithm computationally efficient? First, can we even check if a set $J$ is $\alpha$-stable? This involves checking the following constraint:

It is already unclear how to check this constraint efficiently. However, defining the matrix $C_{ij}=c_{i}c_{j}\in^{J\times J}$, we can take a semi-definite relaxation of $C$, resulting in the constraints $C_{ij}\in$ and $\operatorname{tr}(C)\geq\frac{1}{2}\alpha^{2}n$. Letting $A_{ij}=(x_{i}-\mu_{J})^{\top}(x_{j}-\mu_{J})$, this results in the following sufficient condition for $\alpha$-stability:

As an aside, we note that the above discussion, together with the bound (Lemma B.3) on the operator norm of samples from a sub-Gaussian distribution, implies that a set of samples from a sub-Gaussian distribution is $\alpha$-stable with high probability, and in particular the mean of any large subset of samples is close to the mean of the overall set. Moreover, even if a distribution has only bounded second moments, Proposition B.1 shows that a suitable subset of samples from the distribution will be $\alpha$-stable.

Applications

In this section we present several applications of our main results.

For robustly learning the mean of a distribution with bounded variance, we have the following result:

Define $f_{i}(w)=\|w-x_{i}\|_{2}^{2}$, which is $1$-strongly convex and has $w^{*}=\mu$. In this case, $\nabla f_{i}(w)-\nabla\bar{f}(w)=x_{i}-\mu$, and so Proposition B.1 implies that with probability $1-\exp(-\Omega(\varepsilon^{2}\alpha n))$ there is a subset of $(1-\varepsilon/2)\alpha n$ of the good points satisfying $S=\mathcal{O}\left(\sigma/\sqrt{\varepsilon}\right)$, and hence (by Lemma 5.6) $S_{\varepsilon/2}=\mathcal{O}\left(\sigma/\varepsilon\right)$. Theorem 6.1 then says that we can output parameters $\hat{w}_{1},\ldots,\hat{w}_{m}$, where $m\leq\lfloor\frac{1}{(1-\varepsilon/2)^{2}\alpha}\rfloor\leq\lfloor\frac{1}{(1-\varepsilon)\alpha}\rfloor$, such that $\min_{j=1}^{m}\|\hat{w}_{j}-\mu\|_{2}\leq\mathcal{O}\left(\frac{\sigma}{\varepsilon}\sqrt{\frac{\log(2/\alpha)}{\alpha}}\right)$, as was to be shown. ∎

For robustly learning a mixture of distributions, we have the following result:

Suppose we are given $n$ samples, where each sample either comes from one of $k$ sub-Gaussian distributions $p_{1}^{*},\ldots,p_{k}^{*}$ (with $\operatorname{Cov}_{p_{i}^{*}}[x]\preceq\sigma^{2}I$), or is arbitrary. Let $I_{i}$, $\alpha_{i}$, and $\mu_{i}$ denote respectively the set of points drawn from $p_{i}^{*}$, the fraction of points drawn from $p_{i}^{*}$, and the mean of $p_{i}^{*}$, and let $\alpha=\min_{i=1}^{k}\alpha_{i}$. Suppose that $n\geq\frac{d}{\alpha}$. Then for any $\varepsilon\leq\frac{1}{2}$, with probability $1-k\exp(-\Omega(\varepsilon^{2}\alpha n))$, we can output a partition $T_{1},\ldots,T_{m}$ of $[n]$ and candidate means $\hat{\mu}_{1},\ldots,\hat{\mu}_{m}$ such that:

$m\leq\lfloor\frac{1}{(1-\varepsilon)\alpha}\rfloor$.

For all but $\varepsilon\alpha_{i}n$ of the elements of $h$ of $I_{i}$, $h$ is assigned a partition $T_{j}$ such that \|\mu_{i}-\hat{\mu}_{j}\|_{2}\leq\mathcal{O}\Big{(}{\frac{\sigma}{\varepsilon}\sqrt{\frac{\log(2/\alpha)}{\alpha}}}\Big{)}, where $\mathcal{O}(\cdot)$ masks only absolute constants.

For the planted partition model, we have the following result:

Let $I_{1},\ldots,I_{k}$ be disjoint subsets of $[n]$, and consider the following random directed graph with vertex set $[n]$:

If $u,v\in I_{i}$, the probability of an edge from $u$ to $v$ is $\frac{a}{n}$.

If $u\in I_{i},v\not\in I_{i}$, the probability of an edge from $u$ to $v$ is $\frac{b}{n}$.

If $u\not\in\cup_{i=1}^{k}I_{i}$, the edges emanating from $u$ can be arbitrary.

Let $\alpha=\min_{i=1}^{k}\frac{|I_{i}|}{n}$. Then with probability $1-k\exp(-\Omega(\alpha n))$, we can output sets $T_{1},\ldots,T_{m}\subseteq[n]$, with $m\leq\frac{4}{\alpha}$, such that for all $i\in[k]$, there is a $j\in[m]$ with $|I_{i}\triangle T_{j}|\leq\mathcal{O}\left(\frac{a\log(2/\alpha)}{\alpha^{2}(a-b)^{2}}n\right)$, where $\triangle$ denotes the symmetric difference of two sets.

It turns out that this problem reduces to mean estimation as well, though we will need to be more careful in how we apply our matrix concentration bound.

In this case we have $d=n$, so Proposition B.1 implies that we can find a subset of $I_{i}$ of size at least $|I_{i}|/2\geq\frac{\alpha}{2}n$ such that $S=\mathcal{O}\left(\sigma\sqrt{1+\frac{d}{\alpha n}}\right)=\mathcal{O}\left(\sqrt{\frac{a}{\alpha n}}\right)$. Invoking Theorem 6.1 with $\varepsilon=\frac{1}{2}$, we obtain candidate means $\hat{\mu}_{1},\ldots,\hat{\mu}_{m}$, with $m\leq\frac{4}{\alpha}$, such that $\|\mu_{i}-\hat{\mu}_{j}\|_{2}^{2}\leq\mathcal{O}\left(\frac{S^{2}\log(2/\alpha)}{\alpha}\right)=\mathcal{O}\left(\frac{a\log(2/\alpha)}{\alpha^{2}n}\right)$.