The Broader Landscape of Robustness in Algorithmic Statistics

Gautam Kamath · 2024

Read The Broader Landscape of Robustness in Algorithmic Statistics by Gautam Kamath (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-02670.txt.

Introduction

Gautam Kamath surveys robust statistics algorithms in a 2024 paper. Estimators can be robust in several distinct senses. Data may be contaminated, heavy-tailed, or privacy-sensitive. The past decade brought efficient algorithms for all three settings.

Kamath centers the survey on mean estimation as a test problem. Results from each robustness flavor are reviewed in turn. Technical and conceptual links among the flavors are drawn out. The same core algorithmic ideas recur across settings. That unity yields efficient estimators in each case. The survey assumes comfort with modern algorithms and probability. Specialists in data science theory are the main audience. The author frames robustness as one landscape, not three silos. Future work can exploit the shared machinery further. Privacy, in particular, benefits from the transfer of tricks.

Catalog record

CREATORGautam Kamath
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE80 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-02670

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Broader Landscape of Robustness in Algorithmic Statistics Gautam Kamath Abstract The last decade has seen a number of advances in computationally efficient algorithms for statistical methods subject to robustness constraints. An estimator may be robust in a number of different ways: to contamination of the dataset, to heavy-tailed data, or in the sense that it preserves privacy of the dataset. We survey recent results in these areas with a focus on the problem of mean estimation, drawing technical and conceptual connections between the various forms of robustness, showing that the same underlying algorithmic ideas lead to computationally efficient estimators in all these settings. 1 Introduction Mean estimation is one of the most fundamental statistical tasks: given samples from a probability distribution, output an estimate of that distribution’s mean. It is the prototypical question in statistical inference, and an important primitive that underlies a variety of more complex procedures (e.g., gradient descent, linear regression, etc.). In other words, understanding mean estimation is a prerequisite for understanding essentially any other inference task. As we will see, even in this basic setting, introducing new constraints or desiderata significantly affects the algorithmic ideas needed to solve the problem, particularly with a focus on computational efficiency. More precisely, mean estimation refers to the following statistical problem. Given a dataset X_{1},\dots,X_{n} sampled i.i.d. from a distribution \mathcal{D} supported on \mathbb{R}^{d} , output an estimate \hat{\mu} of its mean \mu\triangleq\mbox{\bf E}_{X\sim\mathcal{D}}[X] . The quality of the estimate is usually measured in terms of the \ell_{2} -distance between the true mean \mu and the estimate \hat{\mu} . We will focus on the following two cases for the distribution \mathcal{D} : 1. When it is a Gaussian distribution with identity covariance, i.e., \mathcal{D}=\mathcal{N}(\mu,I) ; and 2. When it has bounded covariance, i.e., \Sigma(\mathcal{D})\preceq I . In either of these two cases, a textbook calculation demonstrates the efficacy of the empirical mean \frac{1}{n}\sum_{i=1}^{n}X_{i} . Specifically, we have that, with probability \geq 95\% , \left\|\frac{1}{n}\sum_{i=1}^{n}X_{i}-\mu\right\|_{2}\leq O\left(\sqrt{\frac{d}{n}}\right). Furthermore, standard minimax lower bounds establish that no estimator can achieve a rate better than \Omega\left(\sqrt{\frac{d}{n}}\right) , demonstrating that this result is optimal up to constant factors. To summarize, under fairly mild assumptions (i.e., only a bound on the variance of the distribution \mathcal{D} ), the most basic statistic possible (the empirical mean) achieves the optimal error rate for mean estimation. However, the picture changes dramatically when we want our estimator to satisfy some flavor of robustness . Robustness can mean many different things. We may want our estimator to be robust to contamination of the distribution \mathcal{D} . We may desire that our estimator is robust in the case when the distribution \mathcal{D} has heavy tails . And we may require the estimator to preserve privacy of the given dataset, particularly when the data represents sensitive information pertaining to individuals – this too can be viewed as a form of robustness, as the estimator is not allowed to depend too much on individual data points. As we will see, under any of these forms of robustness, the empirical mean is no longer the ideal solution, and the problem becomes substantially more complex. Table 1: Summary of different types of robustness considered in this article. Type of Robustness Input data Estimator’s Goal Section Contamination Stochastic, a fraction is modified arbitrarily Bounded error, depending on corruption rate Section 2 Heavy-Tailed Data Stochastic, from a distribution with heavy tails Mild dependence of error on (inverse) failure probability Section 3 Privacy Arbitrary, a single point is modified arbitrarily Approximately preserve estimator’s output distribution Section 4 Over the last decade, there have been significant algorithmic advances on statistical estimation in these settings. While previous estimators ran into computational barriers, making them intractable for settings of even moderate dimensionality, these new results have produced the first computationally efficient algorithms for robust estimation. We will survey these results with a focus on mean estimation. Perhaps surprisingly, we will see that many of the same technical ideas and solution concepts underpin all of these (seemingly different) types of robustness, hinting at a broader theory for multivariate algorithmic statistics. 2 Contamination We will first explore the most common notion of robustness for estimation tasks, robustness to contamination . 2 2 2 In the literature, this setting is most commonly referred to as robust estimation . However, to avoid confusion with the other forms of robustness, we will instead use the term contamination-robust estimation . Our discussion so far relies heavily upon the assumption that samples are drawn i.i.d. from a well-behaved distribution \mathcal{D} . However, there are many reasons why this may not be the case for real-world data, and we can view our data as contaminated . By this, we mean that a fraction of our data comes from some other source, potentially adversarial in nature. Reasons for this contamination can range from innocuous (e.g., errors by the data curator, model misspecification) to malicious (e.g., data poisoning attacks [ SKL17 , DKK+19 , CGD+23 ] ). There are a variety of ways this type of contamination could cause the data to diverge from our assumptions, and we would like our algorithms to be robust to such deviations. A classic and well-studied way to capture this style of robustness is Huber’s contamination model [ Hub64 ] from Statistics. In this model, (1-\eta)n samples are drawn i.i.d. from a distribution \mathcal{D} , and \eta n samples are drawn i.i.d. from some other (adversarially chosen) distribution. The resulting dataset is thus drawn from a mixture of the original distribution and another distribution with \eta -mixing weight, and can be viewed as simulating an adversary who can add a small fraction of data to the dataset. We will focus on an even stronger adversary, known as the \eta -strong contamination model . In this model, n samples are first drawn i.i.d. from a distribution \mathcal{D} . An adversary is allowed to inspect these samples, and replace any \eta n of them with arbitrary other datapoints. 3 3 3 A common question is whether the algorithm has knowledge of the corruption fraction \eta . In most cases, this turns out to not matter much [ JOR22 ] (though there are exceptions, e.g., for identifiability reasons when both \eta and the covariance matrix are unknown, see Exercise 1.7 (b) of [ DK22 ] ). For simplicity, we will assume \eta is known. The resulting (modified) dataset is provided to the algorithm. This setting is more challenging than Huber’s contamination model, in that strong contamination allows the adversary to a) see the realization of the samples before choosing their contamination strategy (sometimes called an adaptive adversary); and b) modify points (or, equivalently, add and remove points), whereas a Huber adversary can only add points. 4 4 4 Though it is beyond the scope of this piece, understanding how these differences in capability affect the power of an adversary remain at the frontier of research [ BLMT22 , BBKL23 , BV25 , LBK25 ] . In particular, this captures the setting where samples are drawn from a distribution which is \eta -close to \mathcal{D} in total variation distance , thus expressing situations such as model misspecification. Despite the power of the adversary in the strong contamination model, we will

Read the complete text