Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations

We study the computational and sample complexity of learning a target function f_*:ℝd→ℝ with additive structure, that is, f_*(x) = frac1√Msumm=1M fm(langle x, vmrangle), where f1,f2,...,fM:ℝ→ℝ are nonlinear link functions of single-index models (ridge functions) with diverse and near-orthogonal index features vmm=1M, and the number of additive tasks M grows with the dimensionality Masymp dγ for γ≥ 0. This problem setting is motivated by the classical additive model literature, the recent representation learning theory of two-layer neural network, and large-scale pretraining where the model simultaneously acquires a large number of "skills" that are often localized in distinct parts of the trained network. We prove that a large subset of polynomial f_* can be efficiently learned by gradient descent training of a two-layer neural network, with a polynomial statistical and computational complexity that depends on the number of tasks M and the information exponent of fm, despite the unknown link function and M growing with the dimensionality. We complement this learnability guarantee with computational hardness result by establishing statistical query (SQ) lower bounds for both the correlational SQ and full SQ algorithms.