The Median is Easier than it Looks: Approximation with a Constant-Depth, Linear-Width ReLU Network
arXiv:2602.07219v1 Announce Type: new 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 […]