A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910357460615168 |
|---|---|
| author | Pensia, Ankit |
| author_facet | Pensia, Ankit |
| contents | We study the algorithmic problem of sparse mean estimation in the presence of adversarial outliers. Specifically, the algorithm observes a \emph{corrupted} set of samples from $\mathcal{N}(μ,\mathbf{I}_d)$, where the unknown mean $μ\in \mathbb{R}^d$ is constrained to be $k$-sparse. A series of prior works has developed efficient algorithms for robust sparse mean estimation with sample complexity $\mathrm{poly}(k,\log d, 1/ε)$ and runtime $d^2 \mathrm{poly}(k,\log d,1/ε)$, where $ε$ is the fraction of contamination. In particular, the fastest runtime of existing algorithms is quadratic ($Ω(d^2)$), which can be prohibitive in high dimensions. This quadratic barrier in the runtime stems from the reliance of these algorithms on the sample covariance matrix, which is of size $d^2$. Our main contribution is an algorithm for robust sparse mean estimation which runs in \emph{subquadratic} time using $\mathrm{poly}(k,\log d,1/ε)$ samples. We also provide analogous results for robust sparse PCA. Our results build on algorithmic advances in detecting weak correlations, a generalized version of the light-bulb problem by Valiant. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_04726 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation Pensia, Ankit Data Structures and Algorithms Machine Learning Statistics Theory We study the algorithmic problem of sparse mean estimation in the presence of adversarial outliers. Specifically, the algorithm observes a \emph{corrupted} set of samples from $\mathcal{N}(μ,\mathbf{I}_d)$, where the unknown mean $μ\in \mathbb{R}^d$ is constrained to be $k$-sparse. A series of prior works has developed efficient algorithms for robust sparse mean estimation with sample complexity $\mathrm{poly}(k,\log d, 1/ε)$ and runtime $d^2 \mathrm{poly}(k,\log d,1/ε)$, where $ε$ is the fraction of contamination. In particular, the fastest runtime of existing algorithms is quadratic ($Ω(d^2)$), which can be prohibitive in high dimensions. This quadratic barrier in the runtime stems from the reliance of these algorithms on the sample covariance matrix, which is of size $d^2$. Our main contribution is an algorithm for robust sparse mean estimation which runs in \emph{subquadratic} time using $\mathrm{poly}(k,\log d,1/ε)$ samples. We also provide analogous results for robust sparse PCA. Our results build on algorithmic advances in detecting weak correlations, a generalized version of the light-bulb problem by Valiant. |
| title | A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation |
| topic | Data Structures and Algorithms Machine Learning Statistics Theory |
| url | https://arxiv.org/abs/2403.04726 |