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

Abhigyan Dutta, Itay Safran, Paul Valiant
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2145-2199, 2026.

Abstract

We study the approximation of the median of $d$ inputs using ReLU neural networks. We present depth-width tradeoffs under several settings, culminating in a constant-depth, linear-width construction that achieves exponentially small approximation error with respect to the uniform distribution over the unit hypercube. By further establishing a general reduction from the maximum to the median, our results break a barrier suggested by prior work on the maximum function, which indicated that linear width should require depth growing at least as $\log \log d$ to achieve comparable accuracy. Our construction relies on a multi-stage procedure that iteratively eliminates non-central elements while preserving a candidate set around the median. We overcome obstacles that do not arise for the maximum to yield approximation results that are strictly stronger than those previously known for the maximum itself.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-dutta26a, title = {The Median is Easier than it Looks: Approximation with a Constant-Depth, Linear-Width ReLU Network}, author = {Dutta, Abhigyan and Safran, Itay and Valiant, Paul}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {2145--2199}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/dutta26a/dutta26a.pdf}, url = {https://proceedings.mlr.press/v336/dutta26a.html}, abstract = {We study the approximation of the median of $d$ inputs using ReLU neural networks. We present depth-width tradeoffs under several settings, culminating in a constant-depth, linear-width construction that achieves exponentially small approximation error with respect to the uniform distribution over the unit hypercube. By further establishing a general reduction from the maximum to the median, our results break a barrier suggested by prior work on the maximum function, which indicated that linear width should require depth growing at least as $\log \log d$ to achieve comparable accuracy. Our construction relies on a multi-stage procedure that iteratively eliminates non-central elements while preserving a candidate set around the median. We overcome obstacles that do not arise for the maximum to yield approximation results that are strictly stronger than those previously known for the maximum itself.} }
Endnote
%0 Conference Paper %T The Median is Easier than it Looks: Approximation with a Constant-Depth, Linear-Width ReLU Network %A Abhigyan Dutta %A Itay Safran %A Paul Valiant %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-dutta26a %I PMLR %P 2145--2199 %U https://proceedings.mlr.press/v336/dutta26a.html %V 336 %X We study the approximation of the median of $d$ inputs using ReLU neural networks. We present depth-width tradeoffs under several settings, culminating in a constant-depth, linear-width construction that achieves exponentially small approximation error with respect to the uniform distribution over the unit hypercube. By further establishing a general reduction from the maximum to the median, our results break a barrier suggested by prior work on the maximum function, which indicated that linear width should require depth growing at least as $\log \log d$ to achieve comparable accuracy. Our construction relies on a multi-stage procedure that iteratively eliminates non-central elements while preserving a candidate set around the median. We overcome obstacles that do not arise for the maximum to yield approximation results that are strictly stronger than those previously known for the maximum itself.
APA
Dutta, A., Safran, I. & Valiant, P.. (2026). The Median is Easier than it Looks: Approximation with a Constant-Depth, Linear-Width ReLU Network. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:2145-2199 Available from https://proceedings.mlr.press/v336/dutta26a.html.

Related Material