Pith. sign in

REVIEW 3 cited by

Robust Sparse Estimation Tasks in High Dimensions

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1702.05860 v2 pith:I2FNE4FT submitted 2017-02-20 cs.LG cs.DS

Jerry Li This is my paper · ORCID
classification cs.LGcs.DS
keywords sparseestimationnoiseproblemsrobustdimensionshighnumber
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
abstract

In this paper we initiate the study of whether or not sparse estimation tasks can be performed efficiently in high dimensions, in the robust setting where an $\eps$-fraction of samples are corrupted adversarially. We study the natural robust version of two classical sparse estimation problems, namely, sparse mean estimation and sparse PCA in the spiked covariance model. For both of these problems, we provide the first efficient algorithms that provide non-trivial error guarantees in the presence of noise, using only a number of samples which is similar to the number required for these problems without noise. In particular, our sample complexities are sublinear in the ambient dimension $d$. Our work also suggests evidence for new computational-vs-statistical gaps for these problems (similar to those for sparse PCA without noise) which only arise in the presence of noise.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries

    cs.CC 2019-08 accept novelty 8.0 of 10

    Assuming a k-partite planted clique conjecture, the authors prove tight k-to-k^2 sample-complexity lower bounds for robust sparse mean estimation, semirandom community recovery, and a universal class of sparse mixture...

  2. Fundamental Limits of Query-Based Subgraph Detection

    math.ST 2026-07 conditional novelty 7.0 of 10

    For non-adaptive edge-query detection of arbitrary planted subgraphs, the minimum query count is governed by whether the planted graph has dense local witnesses, high-degree hubs, or just many edges.

  3. Recovery of Planted Subgraphs

    cs.IT 2026-07 unverdicted novelty 6.0 of 10

    Sharp conditions for exact recovery of general planted subgraphs in ER graphs are given by the minimal maximum subgraph density, with matching bounds, a spectral algorithm, and computational hardness results via low-d...

Pith tools