On the Geometry of Stable Mean Estimation

Driven by an increasing need for data privacy and the crisis of replicability in science, recent years have seen the intense study of algorithmic stability in statistics and learning. In this talk, we study a fundamental variant of stable mean estimation introduced in [ILPS21,GKM21]: given an unknown distribution D over \mathbb{R}^n, how many samples are needed to produce an estimator satisfying

Correctness: The estimator is \varepsilon-accurate w.h.p
Stability: Run over two i.i.d samples and shared randomness, the estimator produces the same result w.h.p

While several ad hoc algorithms for stable mean estimation exist in the literature [ILPS21,BGH+23,KVYZ23,DPVV23], the lack of a principled approach to stability has left its true computational and statistical cost a mystery.

In this talk, we give a partial resolution to this problem by viewing stability as a geometric property. In particular, we show stable mean estimation is computationally and statistically equivalent to the famous problem of constructing low surface area tilings of \mathbb{R}^n. In combination with classical geometriy, our equivalence resolves the statistical complexity of stable mean estimation and raises new geometric questions on the computational cost of surface-efficient tilings.

Based on joint work with Daniel Kane, Russell Impagliazzo, Sihan Liu, and Chris Ye.

===============================

For more info, see https://math.mit.edu/combin/