The Computational Complexity of Learning Gaussian Single-Index Models
The Computational Complexity of Learning Gaussian Single-Index Models
Single-Index Models are high-dimensional regression problems with planted structure, whereby labels depend on an unknown one-dimensional projection of the input via a generic, non-linear, and potentially non-deterministic transformation. As such, they encompass a broad class of statistical inference tasks, and provide a rich template to study statistical and computational trade-offs …