Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2411.00775 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916464823369728 |
|---|---|
| author | Dagan, Yuval Jordan, Michael I. Yang, Xuelin Zakynthinou, Lydia Zhivotovskiy, Nikita |
| author_facet | Dagan, Yuval Jordan, Michael I. Yang, Xuelin Zakynthinou, Lydia Zhivotovskiy, Nikita |
| contents | We present differentially private algorithms for high-dimensional mean estimation. Previous private estimators on distributions over $\mathbb{R}^d$ suffer from a curse of dimensionality, as they require $Ω(d^{1/2})$ samples to achieve non-trivial error, even in cases where $O(1)$ samples suffice without privacy. This rate is unavoidable when the distribution is isotropic, namely, when the covariance is a multiple of the identity matrix, or when accuracy is measured with respect to the affine-invariant Mahalanobis distance. Yet, real-world data is often highly anisotropic, with signals concentrated on a small number of principal components. We develop estimators that are appropriate for such signals$\unicode{x2013}$our estimators are $(\varepsilon,δ)$-differentially private and have sample complexity that is dimension-independent for anisotropic subgaussian distributions. Given $n$ samples from a distribution with known covariance-proxy $Σ$ and unknown mean $μ$, we present an estimator $\hatμ$ that achieves error $\|\hatμ-μ\|_2\leq α$, as long as $n\gtrsim\mathrm{tr}(Σ)/α^2+ \mathrm{tr}(Σ^{1/2})/(α\varepsilon)$. In particular, when $\pmbσ^2=(σ_1^2, \ldots, σ_d^2)$ are the singular values of $Σ$, we have $\mathrm{tr}(Σ)=\|\pmbσ\|_2^2$ and $\mathrm{tr}(Σ^{1/2})=\|\pmbσ\|_1$, and hence our bound avoids dimension-dependence when the signal is concentrated in a few principal components. We show that this is the optimal sample complexity for this task up to logarithmic factors. Moreover, for the case of unknown covariance, we present an algorithm whose sample complexity has improved dependence on the dimension, from $d^{1/2}$ to $d^{1/4}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_00775 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Dimension-free Private Mean Estimation for Anisotropic Distributions Dagan, Yuval Jordan, Michael I. Yang, Xuelin Zakynthinou, Lydia Zhivotovskiy, Nikita Machine Learning We present differentially private algorithms for high-dimensional mean estimation. Previous private estimators on distributions over $\mathbb{R}^d$ suffer from a curse of dimensionality, as they require $Ω(d^{1/2})$ samples to achieve non-trivial error, even in cases where $O(1)$ samples suffice without privacy. This rate is unavoidable when the distribution is isotropic, namely, when the covariance is a multiple of the identity matrix, or when accuracy is measured with respect to the affine-invariant Mahalanobis distance. Yet, real-world data is often highly anisotropic, with signals concentrated on a small number of principal components. We develop estimators that are appropriate for such signals$\unicode{x2013}$our estimators are $(\varepsilon,δ)$-differentially private and have sample complexity that is dimension-independent for anisotropic subgaussian distributions. Given $n$ samples from a distribution with known covariance-proxy $Σ$ and unknown mean $μ$, we present an estimator $\hatμ$ that achieves error $\|\hatμ-μ\|_2\leq α$, as long as $n\gtrsim\mathrm{tr}(Σ)/α^2+ \mathrm{tr}(Σ^{1/2})/(α\varepsilon)$. In particular, when $\pmbσ^2=(σ_1^2, \ldots, σ_d^2)$ are the singular values of $Σ$, we have $\mathrm{tr}(Σ)=\|\pmbσ\|_2^2$ and $\mathrm{tr}(Σ^{1/2})=\|\pmbσ\|_1$, and hence our bound avoids dimension-dependence when the signal is concentrated in a few principal components. We show that this is the optimal sample complexity for this task up to logarithmic factors. Moreover, for the case of unknown covariance, we present an algorithm whose sample complexity has improved dependence on the dimension, from $d^{1/2}$ to $d^{1/4}$. |
| title | Dimension-free Private Mean Estimation for Anisotropic Distributions |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2411.00775 |