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
| CREATOR | Abhigyan Dutta, Itay Safran, Paul Valiant |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 176 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-07219