用浅层窄网络高精度逼近中位数，突破了此前对深度的理论限制。
The Median is Easier than it Looks: Approximation with a Constant-Depth, Linear-Width ReLU Network
- 分阶段迭代剔除非中心元素，保留接近中位数的候选集。
- 常数深度、线性宽度下，对单位超立方体均匀分布误差指数级小。
- 首次实现比最大值函数更优的逼近效果，适合关注高效神经近似者。
我们研究使用ReLU神经网络近似d个输入的中位数。在多种设置下分析深度与宽度的权衡，最终提出一种常数深度、线性宽度的构造，在单位超立方体上的均匀分布下实现指数级小的近似误差。通过建立最大值到中位数的一般化归约，我们的结果打破了先前关于最大值函数的理论瓶颈——此前认为线性宽度需至少log log d的深度才能达到可比精度。该构造依赖多阶段过程，逐步消除非中心元素，同时保持一个围绕中位数的候选集。克服了最大值情形中不存在的障碍，得到了比以往已知最大值近似更优的结果。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。