Computationally tractable robust differentially private mean estimation

Technical Summary: Computationally Tractable Robust Differentially Private Mean Estimation

Problem Statement
The paper addresses the challenge of estimating the mean of a high-dimensional distribution under two simultaneous constraints: differential privacy (DP) and robustness to outliers. The setting involves a sample of $n$ vectors in $\mathbb{R}^d$ drawn from an unknown elliptical distribution $\nu = EC(\mu, \Sigma, F)$, which is subject to $\eta$-contamination. In this model, an adversary replaces up to $\lfloor \eta n \rfloor$ observations with arbitrary values that may depend on the original sample. The goal is to estimate the population mean $\mu$ while satisfying zero-concentrated differential privacy (zCDP) and maintaining statistical accuracy despite heavy-tailed distributions and adversarial contamination.

Existing methods in this domain face significant trade-offs. Many robust private estimators rely on computationally intensive techniques such as Markov Chain Monte Carlo (MCMC), sum-of-squares relaxations, or gradient-based optimization, rendering them impractical for high-dimensional data. Others, while efficient, often rely on approximate differential privacy or lack robustness guarantees under strong privacy notions like pure or zero-concentrated DP. Furthermore, many existing approaches require tuning parameters that are difficult to interpret or scale poorly with dimension.

Methodology: The Balloon Mean
The authors propose a new estimator, the balloon mean, which avoids complex optimization subroutines in favor of simple linear-algebraic operations. The algorithm operates iteratively, alternating between two steps:

1. Mean Update (Projection and Noisy Averaging): Given a current center estimate $\tilde{\mu}_{m-1}$ and a radius $\tilde{R}_{m-1}$, the algorithm projects all data points onto the Mahalanobis ball $B_{\tilde{R}_{m-1}, \Sigma}(\tilde{\mu}_{m-1})$. It then computes the sample mean of these projections and adds Gaussian noise calibrated to the sensitivity of the projection (which depends on the radius). This yields a new private mean estimate $\tilde{\mu}_m$.
2. Balloon Update (Private Radius Expansion): The algorithm "blows up" the ball centered at the new estimate $\tilde{\mu}_m$ until it contains a target fraction $\tau_m$ of the data. This is achieved using a private version of the AboveThreshold algorithm. The algorithm queries a sequence of radii defined by a geometric grid ($R_{min} + \beta^i - 1$) and privately counts how many points fall within each radius. It stops at the first radius where the noisy count exceeds a noisy threshold corresponding to the target fraction $\tau_m$.

The process repeats for $M$ iterations. The final estimate is the mean of the projections onto the final balloon. The method relies on a few interpretable tuning parameters: the initial radius, the grid expansion factor $\beta$, the number of iterations $M$, and the target fraction $\tau$.

Key Contributions

1. Algorithmic Innovation: The introduction of the balloon mean, a computationally efficient estimator that iteratively localizes the mean by privately identifying Mahalanobis balls containing the bulk of the data. It avoids MCMC, sum-of-squares, and gradient descent.
2. Theoretical Guarantees: The paper provides finite-sample error bounds for the balloon mean under both heavy-tailed models (where only the second moment exists) and adversarially contaminated elliptical models. The analysis assumes a known covariance matrix $\Sigma$ (though the authors note a robust private estimate of $\Sigma$ can be substituted).
3. Privacy and Complexity: The estimator satisfies $\rho$-zero-concentrated differential privacy (zCDP) with a natural extension to pure DP. The computational complexity is $O(d^3 + nd^2 + Mnd + Mn \log n)$, which reduces to $O(nd^2)$ under standard assumptions ($n > d$ and $M < \log n$).

Theoretical Results
The main theoretical result (Theorem 4.4) establishes an upper bound on the Mahalanobis error $|\tilde{\mu}_M - \mu|_\Sigma$. With high probability, the error scales as:
$$\sqrt{\frac{d}{n(\rho_- \wedge 1)}} + \sqrt{d\eta} + \sqrt{\frac{\log(\dots)}{n}}$$
where $\rho_-$ is the minimum privacy budget allocated per iteration.

• Heavy-Tailed Setting ($\eta=0$): The estimator achieves the minimax-optimal rate of convergence up to logarithmic factors.
• Adversarial Contamination ($\eta > 0$): The error includes a term scaling as $\sqrt{d\eta}$. The authors note that while existing lower bounds suggest a dependence of $\sqrt{\eta}$ (independent of $d$) might be achievable, the current dependence on $\sqrt{d}$ is likely structural due to the algorithm's inability to explicitly handle contaminants placed along a single direction in high-dimensional shells. They acknowledge this gap but emphasize that no existing algorithm simultaneously achieves optimal contamination dependence, strong privacy, and computational efficiency.

Empirical Evaluation
Extensive simulations across dimensions ($d \in \{2, \dots, 128\}$), sample sizes, and privacy budgets ($\rho \in \{0.01, 1\}$) demonstrate the method's performance:

• Robustness: The balloon mean significantly outperforms existing computationally tractable private estimators (such as COINPRESS, private Huber M-estimators, and instance-optimal means) in contaminated and heavy-tailed settings.
• Parameter Sensitivity: The method exhibits low sensitivity to the initial mean guess, initial radius, and grid size $\beta$. The parameter $\tau$ acts as a robustness control; smaller values of $\tau$ (excluding more data) improve performance in contaminated settings but may slightly increase error in clean settings.
• Iteration Count: The error stabilizes after 3–4 iterations, suggesting $M=4$ is sufficient for most practical applications.

Significance and Claims
The paper positions the balloon mean as a practical solution to the "trilemma" of robustness, privacy, and computational tractability. The authors claim that while the method may not achieve the theoretically optimal dependence on contamination for adversarial settings (due to structural limitations), it offers a unique combination of:

1. Computational Simplicity: It is implementable in high dimensions without complex optimization.
2. Strong Privacy: It satisfies zCDP, a stronger privacy notion than the approximate DP often used in robust settings.
3. Statistical Optimality: It achieves minimax rates in the heavy-tailed setting and provides robust performance in contaminated settings where other efficient methods fail.

The authors conclude that the balloon mean is a viable tool for private mean estimation in real-world scenarios involving high-dimensional, potentially heavy-tailed, and contaminated data, offering a balance between theoretical guarantees and practical feasibility.