Median の近似は見た目よりも簡単：定数深さ、線形幅の ReLU ネットワークを用いた近似

arXiv:2602.07219v1 Announce Type: new 抽象: 我々は ReLU ニューラルネットワークを用いて d 個の入力の位分散の近似を研究します。我々は複数の設定における深さ幅のトレードオフを提示し、単位超立方体上における一様分布に対して、指数関数的に小さい近似誤差を持つ定数深さ、線形幅の構成を導き出します。最大値関数に関する先行的な研究が示唆していた、同様の精度を達成するには線形幅を得るためには少なくとも loglog d となるような深さが必要であるという壁を、最大値からの一般化の減少関係確立を通じて突破します。我々の構成は、介在要素を逐次排除し、位分散の候補集合を保存するマルチステージの手続きに依存しています。これは、最大値に対しては生じない困難を克服し、最大値それ自体に対して知られている結果よりもより強力な近似結果をもたらします。

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