Shallower ReLU Network Representations via Exact Linear Algebra

• URL: http://arxiv.org/abs/2607.21651v1
• Date: Wed, 22 Jul 2026 16:58:02 GMT
• Title: Shallower ReLU Network Representations via Exact Linear Algebra
• Abstract summary: We prove that the maximum of $n$ real numbers is exactly representable by a ReLU network with two hidden layers for every $nle 10$.<n>In particular, every continuous piecewise-linear function on $mathbbRd$ for $dle 9$ admits a two-hidden-layer ReLU representation.
• Score: 6.437241429006478
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove that the maximum of $n$ real numbers is exactly representable by a ReLU network with two hidden layers for every $n\le 10$. The constructions are obtained by reducing the problem to exact rational linear algebra: after a symmetry reduction, the necessary cancellations are encoded in finite linear systems over $\mathbb{Q}$, which we solve and verify computationally. The representation of $\max_{10}$ has a structured first hidden layer consisting only of pairwise maxima, a feature that allows it to be recursively substituted into larger networks. We use this to show that for every $n>10$, the maximum $\max_{n}$ can be exactly represented with $\lceil{\log_5 (n / 2)\rceil}+1 < \log_5(n) +1.5694$ hidden layers. Via the generalized hinging-hyperplane representation [Wang, Sun, IEEE Trans. Inf. Theory 2005], the same depth bound holds for all continuous piecewise-linear functions on $\mathbb{R}^d$, with $d+1$ in place of $n$. In particular, every continuous piecewise-linear function on $\mathbb{R}^d$ for $d\le 9$ admits a two-hidden-layer ReLU representation. Our results improve on [Bakaev, Brunck, Hertrich, Stade, Yehudayoff, STOC'26]. In that work, the authors established a two-hidden-layer representation for $\max_{5}$ and an upper bound of $\lceil{\log_3 (n-2)\rceil}+1$ hidden layers for $\max_{n}$.

Related papers

• Representing MAX functions using two-hidden-layer ReLU networks [4.726777092009554]
  We study exact representations of $mathrmMAX_N(x)=maxx-1,ldots,x_N$ using two-hidden-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2026-08-25T23:22:33Z)
• Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
  Multi-vector embeddings represent items by point clouds and compare query and document point clouds using Chamfer similarity.<n>For singleton queries, Chamfer becomes maximum inner product similarity (MAX-IP)<n>In our setting, MUVERA gives dimension $mO (1/varepsilon2)$citedhulipala2024muvera.
  arXiv  Detail & Related papers  (2026-07-22T17:27:20Z)
• Is Dimensionality a Barrier for Retrieval Models? [21.1705493494434]
  We show that the best possible margin without a restriction on the dimension, $mathsfmmathsfrd(+infty, A)-2log n)$ can be nearly achieved in dimension $d = O(mathsfmmathsfrd(+infty, A)-2log n)$.<n>Our main theorem establishes that the best possible margin without a restriction on the dimension, $mathsfmmathsfrd(+infty, A)-2log n)$ can be
  arXiv  Detail & Related papers  (2026-05-22T12:22:20Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  We show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $tildeOmega(d1/2/alpha2)$.
  arXiv  Detail & Related papers  (2025-10-12T15:42:44Z)
• Better Neural Network Expressivity: Subdividing the Simplex [6.311952568615851]
  We show that $lceillog_3(n-1)rceil+1$ hidden layers are sufficient to compute all CPWL functions on $mathbbRn$.<n>A key step in the proof is that ReLU neural networks with two hidden layers can exactly represent the maximum function of five inputs.
  arXiv  Detail & Related papers  (2025-05-20T13:23:57Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  We show that for any $K$, there is a universal set" $U subset [n]$ of size independent of $n$, such that for any $Q$ and any row $i$, the large attention scores $A_i,j$ in row $i$ of $A$ all have $jin U$. We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well.
  arXiv  Detail & Related papers  (2024-10-07T19:47:13Z)
• Learning Hierarchical Polynomials with Three-Layer Neural Networks [56.71223169861528]
  We study the problem of learning hierarchical functions over the standard Gaussian distribution with three-layer neural networks. For a large subclass of degree $k$s $p$, a three-layer neural network trained via layerwise gradientp descent on the square loss learns the target $h$ up to vanishing test error. This work demonstrates the ability of three-layer neural networks to learn complex features and as a result, learn a broad class of hierarchical functions.
  arXiv  Detail & Related papers  (2023-11-23T02:19:32Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  We consider the randomized communication complexity of the distributed $ell_p$-regression problem in the coordinator model. For $p = 2$, i.e., least squares regression, we give the first optimal bound of $tildeTheta(sd2 + sd/epsilon)$ bits. For $p in (1,2)$,we obtain an $tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound.
  arXiv  Detail & Related papers  (2023-07-11T08:51:53Z)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  We study low rank approximation of tensors, focusing on the tensor train and Tucker decompositions. For tensor train decomposition, we give a bicriteria $(1 + eps)$-approximation algorithm with a small bicriteria rank and $O(q cdot nnz(A))$ running time. In addition, we extend our algorithm to tensor networks with arbitrary graphs.
  arXiv  Detail & Related papers  (2022-07-15T11:55:09Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• On minimal representations of shallow ReLU networks [0.0]
  We show that the minimal representation for $f$ uses either $n$, $n+1$ or $n+2$ neurons. In particular, where the input layer is one-dimensional, minimal representations always use at most $n+1$ neurons but in all higher dimensional settings there are functions for which $n+2$ neurons are needed.
  arXiv  Detail & Related papers  (2021-08-12T10:22:24Z)
• Deep Neural Networks with ReLU-Sine-Exponential Activations Break Curse of Dimensionality on H\"older Class [6.476766717110237]
  We construct neural networks with ReLU, sine and $2x$ as activation functions. In addition to its supper expressive power, functions implemented by ReLU-sine-$2x$ networks are (generalized) differentiable.
  arXiv  Detail & Related papers  (2021-02-28T15:57:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.