論文の概要: Bridging the Gap Between Approximation and Learning via Optimal Approximation by ReLU MLPs of Maximal Regularity
- arxiv url: http://arxiv.org/abs/2409.12335v1
- Date: Wed, 18 Sep 2024 22:05:07 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-07 15:14:47.201000
- Title: Bridging the Gap Between Approximation and Learning via Optimal Approximation by ReLU MLPs of Maximal Regularity
- Title（参考訳）: 最大正規性のReLU MLPによる最適近似による近似と学習のギャップを埋める
- Authors: Ruiyang Hong, Anastasis Kratsios,
- Abstract要約: 最適関数近似器であり,統計的に良好であるReLU多層認識(MLP)のクラスを同定する。
我々は、小さなスパイクに頼って犠牲になる最適なReLU近似器を構築するための標準的なアプローチを避けることで、これを実現する。
- 参考スコア（独自算出の注目度）: 8.28720658988688
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The foundations of deep learning are supported by the seemingly opposing perspectives of approximation or learning theory. The former advocates for large/expressive models that need not generalize, while the latter considers classes that generalize but may be too small/constrained to be universal approximators. Motivated by real-world deep learning implementations that are both expressive and statistically reliable, we ask: "Is there a class of neural networks that is both large enough to be universal but structured enough to generalize?" This paper constructively provides a positive answer to this question by identifying a highly structured class of ReLU multilayer perceptions (MLPs), which are optimal function approximators and are statistically well-behaved. We show that any $L$-Lipschitz function from $[0,1]^d$ to $[-n,n]$ can be approximated to a uniform $Ld/(2n)$ error on $[0,1]^d$ with a sparsely connected $L$-Lipschitz ReLU MLP of width $\mathcal{O}(dn^d)$, depth $\mathcal{O}(\log(d))$, with $\mathcal{O}(dn^d)$ nonzero parameters, and whose weights and biases take values in $\{0,\pm 1/2\}$ except in the first and last layers which instead have magnitude at-most $n$. Unlike previously known "large" classes of universal ReLU MLPs, the empirical Rademacher complexity of our class remains bounded even when its depth and width become arbitrarily large. Further, our class of MLPs achieves a near-optimal sample complexity of $\mathcal{O}(\log(N)/\sqrt{N})$ when given $N$ i.i.d. normalized sub-Gaussian training samples. We achieve this by avoiding the standard approach to constructing optimal ReLU approximators, which sacrifices regularity by relying on small spikes. Instead, we introduce a new construction that perfectly fits together linear pieces using Kuhn triangulations and avoids these small spikes.
- Abstract（参考訳）: 深層学習の基礎は、近似や学習理論の反対の視点によって支えられている。
前者は一般化する必要のない大/表象モデルの提唱者であり、後者は一般化するクラスを考えるが、普遍近似子になるには小・制約すぎるかもしれない。
本稿では,表現的かつ統計的に信頼性の高い実世界のディープラーニングの実装を動機として,「普遍的かつ一般化に十分な大きさのニューラルネットワークのクラスがあるのか?」と問う。本稿は,最適な関数近似器であり,統計的に良好なReLU多層認識(MLP)の高度に構造化されたクラスを特定することによって,この問題に対する肯定的な回答を提供する。
L$-Lipschitz関数が$[0,1]^d$から$[-n,n]$までの任意の$L$-Lipschitz関数は、均一な$Ld/(2n)$エラーが$[0,1]^d$とスパース的に連結された$L$-Lipschitz ReLU MLP of width $\mathcal{O}(dn^d)$, depth $\mathcal{O}(\log(d))$, with $\mathcal{O}(dn^d)$ nonzeroパラメータを持つ。
普遍ReLU MLPの「大きな」クラスとは異なり、我々のクラスの経験的ラデマッハ複雑性は、その深さと幅が任意に大きくなるときでも有界である。
さらに、我々のMLPのクラスは、正規化されたガウス級訓練サンプルが与えられたときに、$\mathcal{O}(\log(N)/\sqrt{N})$のほぼ最適サンプル複雑性を達成する。
我々は、小さなスパイクに頼って正規性を犠牲にする最適なReLU近似器を構築するための標準的なアプローチを避けることで、これを実現する。
代わりに、クーン三角法を用いて線形部分を完全に整合させる新しい構成を導入し、これらの小さなスパイクを避ける。
関連論文リスト
- A Theory of Interpretable Approximations [61.90216959710842]
我々は、ある基底クラス $mathcalH$ の概念の小さな集合によってターゲット概念 $c$ を近似するという考え方を研究する。
任意の$mathcalH$と$c$のペアに対して、これらのケースのちょうど1つが成り立つ: (i) $c$を任意の精度で$mathcalH$で近似することはできない。
解釈可能な近似の場合、近似の複雑さに関するわずかに非自明なa-priori保証でさえ、定数(分布自由かつ精度)の近似を意味することを示す。
論文 参考訳（メタデータ） (2024-06-15T06:43:45Z) - Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes [29.466981306355066]
固定学習率$eta$の勾配降下はスムーズな関数を表す局所最小値しか見つからないことを示す。
また、$n$のデータポイントのサポートの厳密な内部で、$widetildeO(n-4/5)$のほぼ最適MSE境界を証明します。
論文 参考訳（メタデータ） (2024-06-10T22:57:27Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Approximation Rates and VC-Dimension Bounds for (P)ReLU MLP Mixture of Experts [17.022107735675046]
Mixture-of-Experts(MoEs)は、従来のディープラーニングモデルを越えてスケールアップすることができる。
MoMLPモデル全体のVC次元が$tildeO(LmaxnL,JW)$であるので、MoMLPが一般化可能であることを示す。
論文 参考訳（メタデータ） (2024-02-05T19:11:57Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Bottleneck Structure in Learned Features: Low-Dimension vs Regularity Tradeoff [12.351756386062291]
低次元表現の学習と特徴写像の複雑性/不規則性の最小化のバランスを定式化する。
大深度の場合、ほとんどすべての隠れ表現はおよそ$R(0)(f)$次元であり、ほとんど全ての重み行列は$W_ell$が$R(0)(f)$特異値である。
興味深いことに、大きな学習率の使用は、ほぼすべての層の表現の無限深度収束を保証する注文$O(L)$ NTKを保証するために要求される。
論文 参考訳（メタデータ） (2023-05-30T13:06:26Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs
with a Generative Model [3.749193647980305]
本稿では,一連の状態対応機能を有するマルコフ決定プロセス(MDP)について考察する。
モデルに基づくアプローチ(resp.$Q-learning)が、高い確率で$varepsilon$-Optimalポリシーを確実に学習することを示す。
論文 参考訳（メタデータ） (2021-05-28T17:49:39Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。