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_*: Rᵈ with additive structure, that is, f_* (x) = 1M₌=₁M fₘ (x, vₘ), where f₁, f₂,. . . , fM: R are nonlinear link functions of single-index models (ridge functions) with diverse and near-orthogonal index features \vₘ\₌=₁M, and the number of additive tasks M grows with the dimensionality M 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 fₘ, 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.