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

arXiv: https://arxiv.org/abs/2406.11828 · HTML: https://mlsanity.com/paper/2406.11828/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 82 references that are in the map.
- First posted on arXiv 17 Jun 2024.

## Builds on (most cited first, 28 of 28)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [Prefix-Tuning: Optimizing Continuous Prompts for Generation](https://mlsanity.com/paper/2101.00190/) (2021)
- [Toy Models of Superposition](https://mlsanity.com/paper/2209.10652/) (2022)
- [Knowledge Neurons in Pretrained Transformers](https://mlsanity.com/paper/2104.08696/) (2021)
- [Function Vectors in Large Language Models](https://mlsanity.com/paper/2310.15213/) (2023)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Few-Shot Learning via Learning the Representation, Provably](https://mlsanity.com/paper/2002.09434/) (2020)
- [Feature Learning in Infinite-Width Neural Networks](https://mlsanity.com/paper/2011.14522/) (2020)
- [Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality](https://mlsanity.com/paper/1810.08033/) (2018)
- [A Theory for Emergence of Complex Skills in Language Models](https://mlsanity.com/paper/2307.15936/) (2023)
- [Task-Specific Skill Localization in Fine-tuned Language Models](https://mlsanity.com/paper/2302.06600/) (2023)
- [Training Dynamics of Multi-Head Softmax Attention for In-Context Learning: Emergence, Convergence, and Optimality](https://mlsanity.com/paper/2402.19442/) (2024)
- [Finding Skill Neurons in Pre-trained Transformer-based Language Models](https://mlsanity.com/paper/2211.07349/) (2022)
- [Learning time-scales in two-layers neural networks](https://mlsanity.com/paper/2303.00055/) (2023)
- [On Learning Gaussian Multi-index Models with Gradient Flow](https://mlsanity.com/paper/2310.19793/) (2023)
- [The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents](https://mlsanity.com/paper/2402.03220/) (2024)
- [Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit](https://mlsanity.com/paper/2406.01581/) (2024)
- [Computational-Statistical Gaps in Gaussian Single-Index Models](https://mlsanity.com/paper/2403.05529/) (2024)
- [Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functions](https://mlsanity.com/paper/2405.15459/) (2024)
- [Risk Bounds for High-dimensional Ridge Function Combinations Including Neural Networks](https://mlsanity.com/paper/1607.01434/) (2016)
- [Statistical Queries and Statistical Algorithms: Foundations and Applications](https://mlsanity.com/paper/2004.00557/) (2020)
- [On the Impact of Overparameterization on the Training of a Shallow Neural Network in High Dimensions](https://mlsanity.com/paper/2311.03794/) (2023)
- [Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networks](https://mlsanity.com/paper/2307.06887/) (2023)
- [Stationary Points of Shallow Neural Networks with Quadratic Activation Function](https://mlsanity.com/paper/1912.01599/) (2019)
- [Statistical-Computational Trade-offs in Tensor PCA and Related Problems via Communication Complexity](https://mlsanity.com/paper/2204.07526/) (2022)
- [Learning Hierarchical Polynomials with Three-Layer Neural Networks](https://mlsanity.com/paper/2311.13774/) (2023)
- [Agnostically Learning Multi-index Models with Queries](https://mlsanity.com/paper/2312.16616/) (2023)

## Built on by (most cited first, 13 of 13)

- [Pretrained transformer efficiently learns low-dimensional target functions in-context](https://mlsanity.com/paper/2411.02544/) (2024)
- [Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamics](https://mlsanity.com/paper/2408.07254/) (2024)
- [Learning Gaussian Multi-Index Models with Gradient Flow: Time Complexity and Directional Convergence](https://mlsanity.com/paper/2411.08798/) (2024)
- [Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recovery](https://mlsanity.com/paper/2502.01583/) (2025)
- [Robust Feature Learning for Multi-Index Models in High Dimensions](https://mlsanity.com/paper/2410.16449/) (2024)
- [Learning a Single Index Model from Anisotropic Data with vanilla Stochastic Gradient Descent](https://mlsanity.com/paper/2503.23642/) (2025)
- [From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD](https://mlsanity.com/paper/2510.21020/) (2025)
- [Provably Extracting the Features from a General Superposition](https://mlsanity.com/paper/2512.15987/) (2025)
- [The Mechanism of Weak-to-Strong Generalization: Feature Elicitation from Latent Knowledge](https://mlsanity.com/paper/2605.12908/) (2026)
- [Robust Fourier Neural Networks](https://mlsanity.com/paper/2409.02052/) (2024)
- [A Derandomization Framework for Structure Discovery: Applications in Neural Networks and Beyond](https://mlsanity.com/paper/2510.19382/) (2025)
- [Neuron Block Dynamics for XOR Classification with Zero-Margin](https://mlsanity.com/paper/2602.00172/) (2026)
- [Feature Learning in Linear-Width Two-Layer Networks: Two vs. One Step of Gradient Descent](https://mlsanity.com/paper/2605.17767/) (2026)

## Abstract (arXiv)

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.