The Median is Easier than it Looks: Approximation with a Constant-Depth, Linear-Width ReLU Network
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908818407948288 |
|---|---|
| author | Dutta, Abhigyan Safran, Itay Valiant, Paul |
| author_facet | Dutta, Abhigyan Safran, Itay Valiant, Paul |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_07219 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Median is Easier than it Looks: Approximation with a Constant-Depth, Linear-Width ReLU Network Dutta, Abhigyan Safran, Itay Valiant, Paul Machine Learning Artificial Intelligence 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. |
| title | The Median is Easier than it Looks: Approximation with a Constant-Depth, Linear-Width ReLU Network |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2602.07219 |