Processing math: 100%

kuditipudi23a@v195@PMLR

Total: 1

#1 A Pretty Fast Algorithm for Adaptive Private Mean Estimation [PDF1] [Copy] [Kimi6] [REL]

Authors: Rohith Kuditipudi, John Duchi, Saminul Haque

We design an (ε,δ)-differentially private algorithm to estimate the mean of a d-variate distribution, with unknown covariance Σ, that is adaptive to Σ. To within polylogarithmic factors, the estimator achieves optimal rates of convergence with respect to the induced Mahalanobis norm ||||Σ, takes time ˜O(nd2) to compute, has near linear sample complexity for sub-Gaussian distributions, allows Σ to be degenerate or low rank, and adaptively extends beyond sub-Gaussianity. Prior to this work, other methods required exponential computation time or the superlinear scaling n=Ω(d3/2) to achieve non-trivial error with respect to the norm ||||Σ.

Subject: COLT.2023 - Award