論文の概要: Shallower ReLU Network Representations via Exact Linear Algebra
- arxiv url: http://arxiv.org/abs/2607.21651v1
- Date: Wed, 22 Jul 2026 16:58:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-27 20:58:56.942257
- Title: Shallower ReLU Network Representations via Exact Linear Algebra
- Title（参考訳）: Exact Linear AlgebraによるShallower ReLUネットワーク表現
- Abstract要約: 実数$n$の最大値は、$nle 10$ごとに2つの隠された層を持つReLUネットワークによって正確に表現可能であることを証明している。
特に$mathbbRd$ for $dle 9$ 上のすべての連続ピースワイズ線型関数は、2層ReLU表現を許容する。
- 参考スコア（独自算出の注目度）: 6.437241429006478
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove that the maximum of $n$ real numbers is exactly representable by a ReLU network with two hidden layers for every $n\le 10$. The constructions are obtained by reducing the problem to exact rational linear algebra: after a symmetry reduction, the necessary cancellations are encoded in finite linear systems over $\mathbb{Q}$, which we solve and verify computationally. The representation of $\max_{10}$ has a structured first hidden layer consisting only of pairwise maxima, a feature that allows it to be recursively substituted into larger networks. We use this to show that for every $n>10$, the maximum $\max_{n}$ can be exactly represented with $\lceil{\log_5 (n / 2)\rceil}+1 < \log_5(n) +1.5694$ hidden layers. Via the generalized hinging-hyperplane representation [Wang, Sun, IEEE Trans. Inf. Theory 2005], the same depth bound holds for all continuous piecewise-linear functions on $\mathbb{R}^d$, with $d+1$ in place of $n$. In particular, every continuous piecewise-linear function on $\mathbb{R}^d$ for $d\le 9$ admits a two-hidden-layer ReLU representation. Our results improve on [Bakaev, Brunck, Hertrich, Stade, Yehudayoff, STOC'26]. In that work, the authors established a two-hidden-layer representation for $\max_{5}$ and an upper bound of $\lceil{\log_3 (n-2)\rceil}+1$ hidden layers for $\max_{n}$.
- Abstract（参考訳）: 実数$n$の最大値は、$n\le 10$の2つの隠蔽層を持つReLUネットワークによって正確に表現可能であることを証明している。
これらの構成は、問題を正確な有理線型代数に還元することで得られる:対称性の減少の後、必要なキャンセルは$\mathbb{Q}$を超える有限線型系に符号化され、計算によって解かれ検証される。
$\max_{10}$ の表現は、ペアの最大値のみからなる構造化された第1の隠れ層を持ち、これはより大きなネットワークに再帰的に置換できる特徴である。
これは、すべての$n>10$に対して、最大$\max_{n}$が$\lceil{\log_5 (n / 2)\rceil}+1 < \log_5(n) +1.5694$隠された層で正確に表現できることを示すために使われる。
一般化されたヒンキング超平面表現 (Wang, Sun, IEEE Trans. Inf. Theory 2005) により、同じ深さ境界は$\mathbb{R}^d$ 上のすべての連続なピースワイド線型函数に対して、$n$ の代わりに$d+1$ を持つ。
特に、$\mathbb{R}^d$ for $d\le 9$ 上のすべての連続ピースワイズ線型函数は、2層ReLU表現を許容する。
我々の結果は[Bakaev, Brunck, Hertrich, Stade, Yehudayoff, STOC'26]で改善されました。
この研究において、著者らは$\max_{5}$と$\lceil{\log_3 (n-2)\rceil}+1$の上限を$\max_{n}$に隠蔽する2つの層表現を確立した。
関連論文リスト
- Representing MAX functions using two-hidden-layer ReLU networks [4.726777092009554]
2層ReLUニューラルネットワークを用いて,$mathrmMAX_N(x)=maxx-1,ldots,x_N$の正確な表現について検討した。
論文 参考訳（メタデータ） (2026-08-25T23:22:33Z) - Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
マルチベクタ埋め込みは、ポイントクラウドごとにアイテムを表現し、クエリとドキュメントポイントクラウドを、Chamferの類似性を使って比較する。
シングルトンクエリでは、Chamferは最大内部積類似度(MAX-IP)になる。
我々の設定では、MUVERA は次元 $mO (1/varepsilon2)$citedhulipala2024muvera を与える。
論文 参考訳（メタデータ） (2026-07-22T17:27:20Z) - 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) - Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文 参考訳（メタデータ） (2025-10-12T15:42:44Z) - Better Neural Network Expressivity: Subdividing the Simplex [6.311952568615851]
我々は、$lceillog_3(n-1)rceil+1$ hidden layerは、$mathbbRn$上の全てのCPWL関数を計算するのに十分であることを示す。
この証明の重要なステップは、2つの隠れた層を持つReLUニューラルネットワークが5つの入力の最大関数を正確に表現できることである。
論文 参考訳（メタデータ） (2025-05-20T13:23:57Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。
我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
論文 参考訳（メタデータ） (2024-10-07T19:47:13Z) - Learning Hierarchical Polynomials with Three-Layer Neural Networks [56.71223169861528]
3層ニューラルネットワークを用いた標準ガウス分布における階層関数の学習問題について検討する。
次数$k$s$p$の大規模なサブクラスの場合、正方形損失における階層的勾配によるトレーニングを受けた3層ニューラルネットワークは、テストエラーを消すためにターゲット$h$を学習する。
この研究は、3層ニューラルネットワークが複雑な特徴を学習し、その結果、幅広い階層関数のクラスを学ぶ能力を示す。
論文 参考訳（メタデータ） (2023-11-23T02:19:32Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳（メタデータ） (2023-07-11T08:51:53Z) - Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor
Decompositions [51.19236668224547]
テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。
テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。
さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
論文 参考訳（メタデータ） (2022-07-15T11:55:09Z) - 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) - On minimal representations of shallow ReLU networks [0.0]
f$の最小表現は$n$、$n+1$または$n+2$のどちらかを使用する。
特に入力層が一次元の場合、最小表現は常に少なくとも$n+1$のニューロンで使用されるが、高次元設定では$n+2$のニューロンを必要とする関数が存在する。
論文 参考訳（メタデータ） (2021-08-12T10:22:24Z) - Deep Neural Networks with ReLU-Sine-Exponential Activations Break Curse
of Dimensionality on H\"older Class [6.476766717110237]
活性化関数としてReLU,sine,2x$のニューラルネットワークを構築した。
スーパー表現力に加えて、ReLU-sine-$2x$ネットワークで実装された関数は(一般化)微分可能である。
論文 参考訳（メタデータ） (2021-02-28T15:57:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。