The Median is Easier than it Looks: Approximation with a Constant-Depth, Linear-Width ReLU Network

Abhigyan Dutta, Itay Safran, Paul Valiant · 2026

Read The Median is Easier than it Looks: Approximation with a Constant-Depth, Linear-Width ReLU Network by Abhigyan Dutta, Itay Safran, Paul Valiant (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-07219.txt.

Description

Finding the middle value of many numbers sounds easy, but neural networks struggle to do it accurately without growing very deep. Abhigyan Dutta and two co-authors study how ReLU networks approximate the median of many inputs, and their construction beats expectations.

They build a constant-depth, linear-width network whose error shrinks exponentially over the unit hypercube, using stages that discard non-central values while guarding a candidate set around the median. A reduction from the maximum to the median breaks a barrier suggested by earlier work on the maximum, which implied depth must grow. Approximation theorists get a stronger result for the median than was known even for the maximum.

Catalog record

CREATORAbhigyan Dutta, Itay Safran, Paul Valiant
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE176 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-07219

Browse the full library · About the Tower of Babel