mlsanityData to 14 Oct 2026

How Many Neurons Does it Take to Approximate the Maximum?

arXiv 2307.09212 ↗First posted 18 Jul 2023cs.LGcited by 12

Not on the map. Why?

Abstract (arXiv)

We study the size of a neural network needed to approximate the maximum function over d inputs, in the most basic setting of approximating with respect to the L2 norm, for continuous distributions, for a network that uses ReLU activations. We provide new lower and upper bounds on the width required for approximation across various depths. Our results establish new depth separations between depth 2 and 3, and depth 3 and 5 networks, as well as providing a depth O(log(log(d))) and width O(d) construction which approximates the maximum function. Our depth separation results are facilitated by a new lower bound for depth 2 networks approximating the maximum function over the uniform distribution, assuming an exponential upper bound on the size of the weights. Furthermore, we are able to use this depth 2 lower bound to provide tight bounds on the number of neurons needed to approximate the maximum by a depth 3 network. Our lower bounds are of potentially broad interest as they apply to the widely studied and used max function, in contrast to many previous results that base their bounds on specially constructed or pathological functions and distributions.

Key facts. Cited by 12 papers in the map (data through 14 Oct 2026). Builds on 20 of its 26 references that are in the map. First posted on arXiv 18 Jul 2023.

Builds on

20 of 26 references.

References · 20

  1. 2014Very Deep Convolutional Networks for Large-Scale Image Recognitioncited by 15,364
  2. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 7,005
  3. 2016Error bounds for approximations with deep ReLU networkscited by 574
  4. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 257
  5. 2016Benefits of depth in neural networkscited by 250
  6. 2015The Power of Depth for Feedforward Neural Networkscited by 183
  7. 2019Complexity of Linear Regions in Deep Networkscited by 167
  8. 2016Why Deep Neural Networks for Function Approximation?cited by 82
  9. 2016Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networkscited by 59
  10. 2021Towards Lower Bounds on the Depth of ReLU Neural Networkscited by 56
  11. 2017Depth Separation for Neural Networkscited by 46
  12. 2023Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopescited by 36
8 more
  1. 2021On the Approximation Power of Two-Layer Networks of Random ReLUscited by 29
  2. 2019Depth Separations in Neural Networks: What is Actually Being Separated?cited by 27
  3. 2017Lower bounds over Boolean inputs for deep neural networks with ReLU gatescited by 21
  4. 2021The Connection Between Approximation, Depth Separation and Learnability in Neural Networkscited by 19
  5. 2021Depth separation beyond radial functionscited by 18
  6. 2021Optimization-Based Separations for Neural Networkscited by 17
  7. 2015Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuitscited by 6
  8. 2022The Theoretical Expressiveness of Maxpoolingcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 4; 2025: 5; 2026: 3.

12 papers.

  1. 2024When Can Transformers Count to n?cited by 24
  2. 2025On the Expressiveness of Rational ReLU Neural Networks With Bounded Depthcited by 18
  3. 2025Better Neural Network Expressivity: Subdividing the Simplexcited by 12
  4. 2025Depth-Bounds for Neural Networks via the Braid Arrangementcited by 11
  5. 2025On the Depth of Monotone ReLU Neural Networks and ICNNscited by 11
  6. 2024Decomposition Polyhedra of Piecewise Linear Functionscited by 9
  7. 2024Stable Learning Using Spiking Neural Networks Equipped With Affine Encoders and Decoderscited by 5
  8. 2024Depth Separations in Neural Networks: Separating the Dimension from the Accuracycited by 4
  9. 2026A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theorycited by 3
  10. 2026Shallower ReLU Network Representations via Exact Linear Algebracited by 3
  11. 2025Optimization over Trained (and Sparse) Neural Networks: A Surrogate within a Surrogatecited by 0
  12. 2026Every Layer Counts: An Exponential L2 Depth Hierarchy for ReLU Networkscited by 0