# Optimization-Based Separations for Neural Networks

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 41 references that are in the map.
- First posted on arXiv 4 Dec 2021.

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

- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Exponential expressivity in deep neural networks through transient chaos](https://mlsanity.com/paper/1606.05340/) (2016)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Review](https://mlsanity.com/paper/1611.00740/) (2016)
- [Linearized two-layers neural networks in high dimension](https://mlsanity.com/paper/1904.12191/) (2019)
- [On the Power and Limitations of Random Features for Understanding Neural Networks](https://mlsanity.com/paper/1904.00687/) (2019)
- [Why Deep Neural Networks for Function Approximation?](https://mlsanity.com/paper/1610.04161/) (2016)
- [Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks](https://mlsanity.com/paper/1910.01619/) (2019)
- [Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks](https://mlsanity.com/paper/1610.09887/) (2016)
- [Learning a Single Neuron with Gradient Methods](https://mlsanity.com/paper/2001.05205/) (2020)
- [Depth Separation for Neural Networks](https://mlsanity.com/paper/1702.08489/) (2017)
- [Agnostic Learning of a Single Neuron with Gradient Descent](https://mlsanity.com/paper/2005.14426/) (2020)
- [Towards Understanding Hierarchical Learning: Benefits of Neural Representations](https://mlsanity.com/paper/2006.13436/) (2020)
- [Neural tangent kernels, transportation mappings, and universal approximation](https://mlsanity.com/paper/1910.06956/) (2019)
- [On the Approximation Power of Two-Layer Networks of Random ReLUs](https://mlsanity.com/paper/2102.02336/) (2021)
- [Depth Separations in Neural Networks: What is Actually Being Separated?](https://mlsanity.com/paper/1904.06984/) (2019)
- [Is Deeper Better only when Shallow is Good?](https://mlsanity.com/paper/1903.03488/) (2019)
- [On the Quality of the Initial Basin in Overspecified Neural Networks](https://mlsanity.com/paper/1511.04210/) (2015)
- [The Connection Between Approximation, Depth Separation and Learnability in Neural Networks](https://mlsanity.com/paper/2102.00434/) (2021)
- [Depth separation beyond radial functions](https://mlsanity.com/paper/2102.01621/) (2021)
- [Neural Networks with Small Weights and Depth-Separation Barriers](https://mlsanity.com/paper/2006.00625/) (2020)
- [Learning a Single Neuron with Bias Using Gradient Descent](https://mlsanity.com/paper/2106.01101/) (2021)

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

- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [Random Feature Amplification: Feature Learning and Generalization in Neural Networks](https://mlsanity.com/paper/2202.07626/) (2022)
- [Provable Guarantees for Nonlinear Feature Learning in Three-Layer Neural Networks](https://mlsanity.com/paper/2305.06986/) (2023)
- [How Many Neurons Does it Take to Approximate the Maximum?](https://mlsanity.com/paper/2307.09212/) (2023)
- [Depth Separation with Multilayer Mean-Field Networks](https://mlsanity.com/paper/2304.01063/) (2023)
- [Learning Hierarchical Polynomials with Three-Layer Neural Networks](https://mlsanity.com/paper/2311.13774/) (2023)
- [How Transformers Get Rich: Approximation and Dynamics Analysis](https://mlsanity.com/paper/2410.11474/) (2024)
- [Understanding the Mechanisms of Fast Hyperparameter Transfer](https://mlsanity.com/paper/2512.22768/) (2025)
- [Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining](https://mlsanity.com/paper/2601.19756/) (2026)
- [Depth Separations in Neural Networks: Separating the Dimension from the Accuracy](https://mlsanity.com/paper/2402.07248/) (2024)
- [Blessing of Nonconvexity in Deep Linear Models: Depth Flattens the Optimization Landscape Around the True Solution](https://mlsanity.com/paper/2207.07612/) (2022)
- [A Functional-Space Mean-Field Theory of Partially-Trained Three-Layer Neural Networks](https://mlsanity.com/paper/2210.16286/) (2022)
- [A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theory](https://mlsanity.com/paper/2601.01417/) (2026)
- [Towards Antisymmetric Neural Ansatz Separation](https://mlsanity.com/paper/2208.03264/) (2022)
- [Algorithmic Separation between Constant-Depth and Logarithmic-Depth Neural Networks](https://mlsanity.com/paper/2607.25200/) (2026)
- [Every Layer Counts: An Exponential L2 Depth Hierarchy for ReLU Networks](https://mlsanity.com/paper/2608.23877/) (2026)

## Abstract (arXiv)

Depth separation results propose a possible theoretical explanation for the benefits of deep neural networks over shallower architectures, establishing that the former possess superior approximation capabilities. However, there are no known results in which the deeper architecture leverages this advantage into a provable optimization guarantee. We prove that when the data are generated by a distribution with radial symmetry which satisfies some mild assumptions, gradient descent can efficiently learn ball indicator functions using a depth 2 neural network with two layers of sigmoidal activations, and where the hidden layer is held fixed throughout training. By building on and refining existing techniques for approximation lower bounds of neural networks with a single layer of non-linearities, we show that there are d-dimensional radial distributions on the data such that ball indicators cannot be learned efficiently by any algorithm to accuracy better than Omega(d-4), nor by a standard gradient descent implementation to accuracy better than a constant. These results establish what is to the best of our knowledge, the first optimization-based separations where the approximation benefits of the stronger architecture provably manifest in practice. Our proof technique introduces new tools and ideas that may be of independent interest in the theoretical study of both the approximation and optimization of neural networks.