A Subquadratic Time Algorithm for Robust Sparse Mean Estimation
Authors: Ankit Pensia
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main contribution is an algorithm for robust sparse mean estimation which runs in subquadratic time using poly(k, log d, 1/ϵ) samples, with similar 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 (Valiant, 2015). |
| Researcher Affiliation | Industry | 1IBM Research. Correspondence to: Ankit Pensia <ankitp@ibm.com>. |
| Pseudocode | Yes | Algorithm 1 Algorithmic Blueprint [...] Algorithm 2 RANDOMLYCHECKCOORDINATES [...] Algorithm 3 Subroutine to Identify Corrupted Coordinates [...] Algorithm 4 Quadratic Scores [...] Algorithm 5 Randomized Filtering [...] Algorithm 6 Main Subroutine (Expanded version of Algorithm 3) [...] Algorithm 7 Main Algorithm [...] Algorithm 8 PCA Filter [...] Algorithm 9 Robust Sparse PCA Algorithm |
| Open Source Code | No | The paper does not provide any statements about releasing code or links to a code repository. |
| Open Datasets | No | The paper is theoretical, focusing on algorithm design and analysis. It does not use or refer to any publicly available datasets for training or experimentation. |
| Dataset Splits | No | The paper is theoretical and does not discuss dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and analyzes algorithm complexity. It does not mention any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and describes algorithms; it does not provide implementation details or software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any empirical experiments or their setup, thus no hyperparameters or training settings are mentioned. |