Fundamental Limits of Learning Single-Index Models under Structured Data

Recent works have developed a comprehensive picture of gradient-based learning of isotropic Gaussian single-index models by developing computational lower bounds along with optimal algorithms. In this work, we demonstrate that the picture can change significantly when the data covariance is structured and contains some degree of information about the target. Through studying a spiked covariance model, we show that for the class of Correlational Statistical Query (CSQ) learners, a simple preconditioning of online SGD already achieves an almost optimal sample complexity. Unlike the isotropic case, further smoothing the landscape does not improve this complexity. We prove similar lower bounds in the Statistical Query (SQ) class, where we demonstrate a gap between the SQ lower bound and the performance of the algorithms that are known to be optimal in the isotropic setting. Finally, we show a stark contrast in the information-theoretic limit, where the tight lower bound goes through a sudden phase transition from $d$ to $1$ depending on covariance structure, where $d$ is the dimension of the input. Overall, our analysis provides a clear characterization of when and how the spike simplifies learning by improving over isotropic covariance.