Robust Statistical Estimators with Bounded Empirical Sensitivity

Valentio Iverson, Gautam Kamath, Argyris Mouzakis, Adam Smith · 2026

Read Robust Statistical Estimators with Bounded Empirical Sensitivity by Valentio Iverson, Gautam Kamath, Argyris Mouzakis, Adam Smith (2026) 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-2605-21860.txt.

Introduction

Valentio Iverson and coauthors present empirical sensitivity, a robustness measure. An estimator has bounded sensitivity if changing at most eta of its points usually moves the estimate slightly. For Gaussian mean estimation they prove lower bounds. Any estimator with optimal square-root-of-dimension-over-n error has sensitivity of order eta plus square root of eta times dimension over n. The two terms come from mean and variance obstructions via Efron-Stein. The bound is tight up to log factors, using recent robust mean estimation results.

Catalog record

CREATORValentio Iverson, Gautam Kamath, Argyris Mouzakis, Adam Smith
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE99346
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.21860

Browse the full library · About the Tower of Babel

Full text

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

Robust Statistical Estimators with Bounded Empirical Sensitivity Thanks: Authors are listed in alphabetical order. Valentio Iverson, Gautam Kamath, Argyris Mouzakis, Adam Smith Abstract We introduce a new measure of robustness for statistical estimators, which we call empirical sensitivity . An estimator θ ^ \hat{\theta} has bounded empirical sensitivity if, with high probability over a dataset X = ( X 1 , … , X n ) ∼ 𝒟 ⊗ n X=(X_{1},\dots,X_{n})\sim\mathcal{D}^{\otimes n} , for any dataset Y Y obtained by modifying at most η ​ n \eta n points in X X , we have that θ ^ ​ ( Y ) \hat{\theta}(Y) is close to θ ^ ​ ( X ) \hat{\theta}(X) . We study bounds on this quantity for the prototypical problem of Gaussian mean estimation. We prove new lower bounds, showing that for any estimator μ ^ \hat{\mu} which achieves an optimal ℓ 2 \ell_{2} -error bound of O ⁡ ( d / n ) O(\sqrt{d/n}) , the empirical sensitivity is at least Ω ⁡ ( η + η ​ d / n ) \Omega(\eta+\sqrt{\eta d/n}) . The two terms arise due to obstructions on the mean and variance (via an Efron-Stein argument) of such an estimator. We show that this bound is tight up to logarithmic factors, by employing recent results for robust empirical mean estimation. 1 Introduction Robustness is a classic topic of study within Statistics [ 17 ] . It tries to understand and bound how much an estimator can fluctuate when data diverges from our assumptions. Such divergences could arise for innocuous reasons such as model misspecification, or more malicious reasons like an adversary manipulating or poisoning the dataset. A popular style of robustness ensures that an estimator maintains accuracy after an adversary modifies a portion of the input dataset. In more detail, suppose we have an estimator \hat{\theta} for a parameter \theta^{*} of some family of distributions \mathcal{D}_{\theta} . Let X=(X_{1},\dots,X_{n})\sim\mathcal{D}_{\theta^{*}} , and let Y be any dataset obtained by modifying \eta n points in X . Robustness of the estimator \hat{\theta} is then measured in terms of \|\hat{\theta}(Y)-\theta^{*}\| , the distance between the estimator on the contaminated dataset and the true parameter of interest. While algorithms satisfying this definition are quite powerful, the notion does not capture some natural properties we might hope for an estimator to possess. We illustrate by considering the estimator \hat{\mu} to be the median, and the dataset X to be sampled from a univariate Gaussian distribution \mathcal{N}(\mu,1)^{\otimes n} . For an uncontaminated dataset X , with high probability, the median is well known to achieve the near optimal statistical rate: |\hat{\mu}(X)-\mu|\leq O(1/\sqrt{n}) . Furthermore, the median is the canonical example of a robust statistic. For any dataset Y , formed by changing \eta n entries of X , we have that |\hat{\mu}(Y)-\mu|\leq O(\eta+1/\sqrt{n}) —a mild (but inherent) degradation of the rate from the uncontaminated case. However, we consider how much the estimator can shift due to contamination. For simplicity, focus on the case when \eta=1/n , i.e., a single point is contaminated. The aforementioned robustness guarantee allows us only to say that |\hat{\mu}(Y)-\hat{\mu}(X)|\leq O(1/n+1/\sqrt{n}) . This is a rather large radius for only a single contamination, with the dominant term being the parametric rate of 1/\sqrt{n} . In fact, as we show in Section B , the median enjoys a quadratically stronger guarantee on this quantity: |\hat{\mu}(Y)-\hat{\mu}(X)|\leq O(1/n) . To summarize, the conventional measures of robustness may not give insight into how sensitive the estimator may be. Motivated by this deficiency, we introduce a new measure of robustness for statistical estimators, which we call the empirical sensitivity . Informally, we would like for an estimator \hat{\theta} to simultaneously have the following two properties. • Accuracy: Given a dataset X\sim\mathcal{D}_{\theta^{*}} , we have that \|\hat{\theta}(X)-\theta^{*}\| is small. • Bounded empirical sensitivity: For X\sim\mathcal{D}_{\theta} , and for any dataset Y obtained by modifying \eta n entries of X , we have that \|\hat{\theta}(Y)-\hat{\theta}(X)\| is small—either in expectation over X or with high probability. Similar to traditional robustness, we focus on the case where the dataset X is drawn stochastically, but Y is an arbitrary or worst-case contamination of X . As usual, obtainable guarantees will depend on properties of the class of distributions \mathcal{D}_{\theta} . On the other hand, this can be seen as a stronger type of robustness: by triangle inequality, an accurate estimator with bounded empirical sensitivity will also enjoy a bound on \|\hat{\theta}(Y)-\theta^{*}\| , the traditional object of study in robust estimation. The robustness of the estimated value to corruption has been considered before as a worst-case constraint on a function, notably in the design of differentially private algorithms. To our knowledge, ours is the first work that studies the interaction of empirical sensitivity with statistical efficiency, and also the first to explicitly study the average-case notion. See Related Work ( Section 1.2 ) for more detail. 1.1 Results and Techniques We initiate study of empirical sensitivity focusing on one of the most fundamental statistical tasks: Gaussian mean estimation . Our main result is the following lower bound on the empirical sensitivity of optimal estimators. Theorem 1.1 . Consider any estimator \hat{\mu} such that \sup_{\mu\in\mathbb{R}^{d}}\mathbb{E}_{X\sim\mathcal{N}(\mu,\mathbb{I}_{d})^{\otimes n}}\|\hat{\mu}(X)-\mu\|_{2}^{2}\lesssim\frac{d}{n}. (1) For every \eta\in(0,1) , 1 1 1 Throughout, it is implicit that \eta\geq 1/n , i.e., there is at least one contaminated point. we have that \sup_{\mu\in\mathbb{R}^{d}}\left(\mathbb{E}_{X\sim\mathcal{N}(\mu,\mathbb{I}_{d})^{\otimes n}}\left[\sup_{Y\colon d_{H}(X,Y)\leq\lfloor\eta n\rfloor}\|\hat{\mu}(Y)-\hat{\mu}(X)\|_{2}^{2}\right]\right)^{1/2}\geq\Omega\left(\eta+\sqrt{\frac{\eta d}{n}}\right). This lower bound is tight up to logarithmic factors. Very recent work by Chen, Ding, Majid, and McKelvie [ 11 ] studies robust empirical mean estimation. An easy argument shows that their estimator satisfies near-optimal accuracy and also average-case empirical sensitivity (Theorem 3.2 ) essentially matching Theorem 1.1 above. We recall that, for robust Gaussian mean estimation, the optimal rate for \|\hat{\mu}(X)-\mu\|_{2} is \tilde{\Theta}\left(\eta+\sqrt{\frac{d}{n}}\right) . By triangle inequality, this implies that one may have hoped for an empirical stability bound as small as \tilde{\Theta}(\eta) . 2 2 2 Note that triangle inequality only implies a lower bound of \Omega(\eta) in the regime where \eta=\Omega\left(\sqrt{d/n}\right) . Indeed, proving the lower bound of \eta in all regimes appears to require significant technical work, and is quite different from how this term arises for conventional robust statistics, see Section 3 for more details. Instead, the larger bound of \tilde{\Theta}\left(\eta+\sqrt{\frac{\eta d}{n}}\right) arises. Technically, the two terms in the lower bound are proven by showing obstructions on the mean and variance of the estimator. The mean obstruction. We first reduce a d -dimensional uniformly accurate estimator to a scalar estimator along a direction and an orthogonal subspace. Then we prove scalar sensitivity lower bounds in two overlapping regimes. In the low corruption regime \eta\lesssim\frac{1}{\sqrt{n}} , we compare a valid local corruption, which shifts k random samples, to a statistically indistinguishable global dataset corruption that the estimator is forced to track due to its accuracy guarantees. For \eta\gtrsim\frac{\log n}{n} , a coupling argument compares two samples from two nearby Gaussian means whose total variance distance is of order \eta , so that the coupled samples differ in at most \lfloor\eta n\rfloor coordinates with high probability. The two regimes overlap for large n , covering the full range of values for \eta . 3 3 3 In Section 4 , we also show this

Read the complete text