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

Abhigyan Dutta, Itay Safran, Paul Valiant

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-…