論文の概要: Representing MAX functions using two-hidden-layer ReLU networks

• arxiv url: http://arxiv.org/abs/2608.25221v1
• Date: Tue, 25 Aug 2026 23:22:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-27 14:15:15.49205
• Title: Representing MAX functions using two-hidden-layer ReLU networks
• Title（参考訳）: 2層ReLUネットワークを用いたMAX関数の表現
• Abstract要約: 2層ReLUニューラルネットワークを用いて,$mathrmMAX_N(x)=maxx-1,ldots,x_N$の正確な表現について検討した。
• 参考スコア（独自算出の注目度）: 4.726777092009554
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study exact representations of $\mathrm{MAX}_N(x)=\max{x_1,\ldots,x_N}$ using two-hidden-layer ReLU neural networks. This problem has been studied in recent years in an attempt to characterize the exact number of hidden layers required to represent continuous piecewise linear functions. The best lower bound is 2, while the current upper bound is logarithmic in $N$. It remains completely open if the right answer is a constant number of hidden layers (possibly even 2!) or not. In fact, a recent breakthrough was the representation of $\mathrm{MAX}_5$ as a two-hidden-layer ReLU function obtained in [Bakaev et al., 2026], and the case of $\mathrm{MAX}_N$ was stated as open for $N\geq 6$ in that paper. Using a careful computer assisted search, we obtain two-hidden-layer ReLU representations of $\mathrm{MAX}_5, \mathrm{MAX}_6, \mathrm{MAX}_7$, and $\mathrm{MAX}_8$. We obtain these by considering rational linear combinations of terms of the form $\max\{\sum_{r=1}^{s}\max(x_{a_r},x_{b_r}),\sum_{r=1}^{s}\max(x_{c_r},x_{d_r})\}$, where $a_r,b_r,c_r,d_r\in\{1,\ldots,N\}$. Each inner maximum of two coordinates can be computed in a first hidden layer, and the outer maximum of the two side-sums can be computed in a second hidden layer. Consequently, every finite linear combination of these terms has a two-hidden-layer ReLU realization. An identity for $\mathrm{MAX}_N$ in this form therefore gives an exact two-hidden-layer ReLU representation of $\mathrm{MAX}_N$. Very recently, two-hidden-layer representations of $\mathrm{MAX}_N$ of the above form were obtained for all $N\leq 10$ in [Ruess et al., 2026]. Our representations are different and were developed independently. While our techniques share most of the high-level ideas presented in [Ruess et al., 2026], there are also some minor differences which may be of interest for future research on this problem.
• Abstract（参考訳）: 2層ReLUニューラルネットワークを用いて,$\mathrm{MAX}_N(x)=\max{x_1,\ldots,x_N}$の正確な表現について検討した。 この問題は近年、連続な断片線型関数を表現するのに必要な隠蔽層の正確な数を特徴付けるために研究されている。 最大の下限は 2 であり、現在の上限は$N$の対数である。 正しい答えが一定の数の隠れたレイヤ(おそらく2! 実際、最近のブレークスルーは、[Bakaev et al , 2026] で得られる2層 ReLU 関数として $\mathrm{MAX}_5$ の表現であり、$\mathrm{MAX}_N$ の場合、この論文では$N\geq 6$ のオープンとして記述されている。 注意深いコンピュータ支援探索を用いて、$\mathrm{MAX}_5, \mathrm{MAX}_6, \mathrm{MAX}_7$, $\mathrm{MAX}_8$の2層ReLU表現を得る。 これらは、$\max\{\sum_{r=1}^{s}\max(x_{a_r},x_{b_r}),\sum_{r=1}^{s}\max(x_{c_r},x_{d_r})\}$,}$a_r,b_r,c_r,d_r\in\{1,\ldots,N\}$という形の項の有理線型結合を考えることによって得られる。 2つの座標の内極大を第1の隠蔽層で計算し、2つのサイドサムの外極大を第2の隠蔽層で計算することができる。 したがって、これらの項のすべての有限線型結合は、2つの隠れた層ReLU実現を持つ。 したがって、この形式の$\mathrm{MAX}_N$の恒等式は、$\mathrm{MAX}_N$の正確な2層ReLU表現を与える。 つい最近、上記の形式の$\mathrm{MAX}_N$の2つの隠れた層表現が、すべての$N\leq 10$ in [Ruess et al , 2026] に対して得られた。 私たちの表現は異なり、独立して開発されました。 我々の技術は[Ruess et al , 2026]で提示された高レベルなアイデアのほとんどを共有していますが、この問題に関する今後の研究にはいくつかの小さな違いがあります。

関連論文リスト

• Shallower ReLU Network Representations via Exact Linear Algebra [6.437241429006478]
  実数$n$の最大値は、$nle 10$ごとに2つの隠された層を持つReLUネットワークによって正確に表現可能であることを証明している。 特に$mathbbRd$ for $dle 9$ 上のすべての連続ピースワイズ線型関数は、2層ReLU表現を許容する。
  論文  参考訳（メタデータ） (2026-07-22T16:58:02Z)
• Is Dimensionality a Barrier for Retrieval Models? [21.1705493494434]
  次元の制限のない最良のマージンである$mathsfmmathsfrd(+infty, A)-2log n)$は次元$d = O(mathsfmmathsfrd(+infty, A)-2log n)$でほぼ達成可能であることを示す。 我々の主定理は、次元の制限なしに可能な最良のマージンである$mathsfmmathsfrd(+infty, A)-2log n)$が成り立つことを証明している。
  論文  参考訳（メタデータ） (2026-05-22T12:22:20Z)
• Minimax optimal submatrix detection: Sharp non-asymptotic rates [1.7188280334580195]
  平均行列 $mathbf X$ における植木部分行列を検出する問題を考える。 2つの仮説が高い確率で識別可能であることを保証するために、$がどれほど大きいかを示すミニマックス最適化を確立する。 我々の漸近的でない上境界と下限は、これらのパラメータの任意の構成に一致する。
  論文  参考訳（メタデータ） (2026-05-10T14:30:16Z)
• On the Capacity Region of Individual Key Rates in Vector Linear Secure Aggregation [55.126702858312456]
  すべてのユーザがキーを保持する必要はないことを示し、それによって文学における最もよく知られた到達可能な領域を厳密に拡大する。 以上の結果から,各ユーザがキーを保持する必要はないという新たな事実が明らかになった。
  論文  参考訳（メタデータ） (2026-01-06T18:34:07Z)
• Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs [54.28273395444243]
  我々は,モノトニック値 Omega (MVP) アルゴリズムが,差分を考慮した差分依存残差境界を$tildeOleft(left(sum_Delta_h(s,a)>0 fracH2 log K land MathttVar_maxtextc$。
  論文  参考訳（メタデータ） (2025-06-06T20:33:57Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Minimum width for universal approximation using ReLU networks on compact domain [8.839687029212673]
  活性化関数が ReLU-like (ReLU, GELU, Softplus) であれば、$Lp$関数の近似の最小幅は正確に$maxd_x,d_y,2$であることを示す。 ReLUネットワークの既知の結果と比較すると、$w_min=maxd_x+1,d_y$ ドメインが $smashmathbb Rd_x$ の場合、まず、コンパクトなドメインでの近似はそれよりも小さい幅を必要とすることを示す。
  論文  参考訳（メタデータ） (2023-09-19T08:04:48Z)
• Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension [18.57735939471469]
  我々は注意問題のスパシフィケーションを考慮する。 超大規模特徴量の場合、文の長さをほぼ線形に縮めることができる。
  論文  参考訳（メタデータ） (2023-04-10T05:52:38Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
  非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
  論文  参考訳（メタデータ） (2019-06-02T03:03:45Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。