Fundamental Limits of Learning Single-Index Models under Structured Data

Recent works have developed a comprehensive picture of gradient-based learning of isotropicGaussian single-index models by developing computational lower bounds along with optimalalgorithms. In this work, we demonstrate that the picture can change significantly when the datacovariance is structured and contains some degree of information about the target. Through studying aspiked 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. Weprove similar lower bounds in the Statistical Query (SQ) class, where we demonstrate a gap betweenthe SQ lower bound and the performance of the algorithms that are known to be optimal in theisotropic setting. Finally, we show a stark contrast in the information-theoretic limit, where the tightlower 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 ofwhen and how the spike simplifies learning by improving over isotropic covariance.