Metraipolis › archive › dc_0f9d5891ef4c

A Witnessing Duality for ReLU Network Depth — arXiv:2610.38281

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.38281
License (as archived)
CC0-1.0
Archived
2026-11-01T02:26:57.738Z
SHA-256 of the archived text
ef33bbd4be6610f8e3da972604a4d594fd70c831e7c98260d1d76a6856a8c30c
Stable URL of this page
https://metraipolis.com/documento/dc_0f9d5891ef4c

How to cite

A Witnessing Duality for ReLU Network Depth — arXiv:2610.38281 — arXiv (en), https://arxiv.org/abs/2610.38281 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0f9d5891ef4c (Metraipolis archive dc_0f9d5891ef4c, sha256 ef33bbd4be6610f8e3da972604a4d594fd70c831e7c98260d1d76a6856a8c30c)
BibTeX
@misc{dc0f9d5891ef4c,
  title = {A Witnessing Duality for ReLU Network Depth — arXiv:2610.38281},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.38281},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0f9d5891ef4c; sha256 ef33bbd4be6610f8e3da972604a4d594fd70c831e7c98260d1d76a6856a8c30c},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.38281. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

A depth lower bound for ReLU networks asserts that every shallower network errs on some input; we ask when a weak theory can prove such a bound so that an error can be computed. For the exact computation of $\max(x_1,\ldots,x_n)$, recent work shows two hidden layers suffice with unrestricted rational weights. By contrast, Haase, Hertrich and Loho (ICLR 2023) proved that integer weights require depth logarithmic in $n$, and Averkov, Hojny and Merkert (ICLR 2025) extended the bound to nonbias weights whose denominators are powers of a fixed integer not divisible by a prime $q$. With integer weights the bound is sharp: the classical balanced construction has depth $\lceil\log_2 n\rceil$. For each fixed $q$ and depth cap $K$, we prove this known bound in $\mathbf{VTC}^0$, the bounded-arithmetic theory of uniform constant-depth threshold computation, together with a refuter that is itself such a computation and whose correctness the theory proves. Given a network with at most $K$ hidden layers, nonbias weights whose reduced denominators avoid $q$, arbitrary rational biases and $n>q^K$ inputs, the refuter returns a rational input of polynomial length on which the network errs. The proof makes the obstruction finite: an iterated intersection product of piecewise-linear functions is divisible by $q$ for the network but not for the maximum, so one of finitely many test points exposes the error. By witnessing, provable refutation corresponds to a provably correct refuter, and provable existence of a certified network to a provably correct constructor. On the construction side, we introduce certificates that label each maximum gadget by the inputs it aggregates; with them the theory verifies the balanced construction, which meets the refuter at the sharp threshold $n\le2^K$, and a rational family of polynomial description length and depth $O(\log n/\log\log n)$ built from known depth-two blocks.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC) ; Machine Learning (cs.LG); Logic in Computer Science (cs.LO).
Pagina del lavoro: https://arxiv.org/abs/2610.38281 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-01T02:12:44.256Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).