論文の概要: On the Sample Complexity of Two-Layer Networks: Lipschitz vs.
Element-Wise Lipschitz Activation
- arxiv url: http://arxiv.org/abs/2211.09634v4
- Date: Sat, 20 Jan 2024 22:04:21 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-23 22:27:23.971475
- Title: On the Sample Complexity of Two-Layer Networks: Lipschitz vs.
Element-Wise Lipschitz Activation
- Title(参考訳): 2層ネットワークのサンプル複雑性について:Lipschitz vs. Element-Wise Lipschitz Activation
- Authors: Amit Daniely and Elad Granot
- Abstract要約: 本研究では,異なるアクティベーション関数を用いた有界二層ニューラルネットワークのサンプル複雑性について検討する。
我々は、$sigma$ が要素ワイドであれば、$mathcalH$ のサンプルの複雑さは、幅の対数依存しか持たないことを証明する。
- 参考スコア(独自算出の注目度): 20.70453775428433
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We investigate the sample complexity of bounded two-layer neural networks
using different activation functions.
In particular, we consider the class
$$ \mathcal{H} = \left\{\textbf{x}\mapsto \langle \textbf{v}, \sigma \circ
W\textbf{b} + \textbf{b} \rangle : \textbf{b}\in\mathbb{R}^d, W \in
\mathbb{R}^{\mathcal{T}\times d}, \textbf{v} \in
\mathbb{R}^{\mathcal{T}}\right\} $$
where the spectral norm of $W$ and $\textbf{v}$ is bounded by $O(1)$, the
Frobenius norm of $W$ is bounded from its initialization by $R > 0$, and
$\sigma$ is a Lipschitz activation function.
We prove that if $\sigma$ is element-wise, then the sample complexity of
$\mathcal{H}$ has only logarithmic dependency in width and that this complexity
is tight, up to logarithmic factors.
We further show that the element-wise property of $\sigma$ is essential for a
logarithmic dependency bound in width, in the sense that there exist
non-element-wise activation functions whose sample complexity is linear in
width, for widths that can be up to exponential in the input dimension.
For the upper bound, we use the recent approach for norm-based bounds named
Approximate Description Length (ADL) by arXiv:1910.05697.
We further develop new techniques and tools for this approach that will
hopefully inspire future works.
- Abstract(参考訳): 異なる活性化関数を用いた有界二層ニューラルネットワークのサンプル複雑性について検討する。
特に、クラス $$$ \mathcal{H} = \left\{\textbf{x}\mapsto \langle \textbf{v}, \sigma \circ W\textbf{b} + \textbf{b} \rangle : \textbf{b}\in\mathbb{R}^d, W \in \mathbb{R}^{\mathcal{T}\times d}, \textbf{v} \in \mathbb{R}^{\mathcal{T}}\right\} $$$$$W$と$\textbf{v}$のノルムが$O(1)$で束縛され、$W$W$のフロベニウスノルムはその初期化から$R>$0で束縛される。
すると、$\sigma$ が要素単位であるなら、$\mathcal{h}$ のサンプル複雑性は対数依存性のみを持ち、この複雑性は対数因子まで密接であることが証明される。
さらに、入力次元において指数的となる幅に対して、サンプルの複雑さが線形な非要素的活性化関数が存在するという意味で、$\sigma$の要素ワイド性は、幅に有界な対数依存に必須であることを示す。
上界に対しては、arXiv:1910.05697 により Approximate Description Length (ADL) と呼ばれるノルムベース境界に対する最近のアプローチを用いる。
このアプローチのための新しい技術やツールがさらに開発され、将来的な成果が期待できる。
関連論文リスト
- Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳(メタデータ) (2024-02-06T15:39:09Z) - Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
本稿では,シャッフルラベルを用いた線形回帰の課題について考察する。
mathbb Rntimes m の $mathbf Y、mathbb Rntimes p の mathbf Pi、mathbb Rptimes m$ の mathbf B、mathbb Rntimes m$ の $mathbf Win mathbb Rntimes m$ である。
論文 参考訳(メタデータ) (2023-10-02T16:44:47Z) - An Over-parameterized Exponential Regression [18.57735939471469]
LLM(Large Language Models)の分野での最近の発展は、指数的アクティベーション関数の使用への関心を喚起している。
ニューラル関数 $F: mathbbRd times m times mathbbRd times mathbbRd times mathbbRd times mathbbRd times mathbbRd times mathbbRd times mathbbRd times mathbbRdd
論文 参考訳(メタデータ) (2023-03-29T07:29:07Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳(メタデータ) (2022-06-17T17:55:43Z) - Low-degree learning and the metric entropy of polynomials [49.1574468325115]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳(メタデータ) (2022-03-17T23:52:08Z) - Infinite-Horizon Offline Reinforcement Learning with Linear Function
Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
本稿では,オフライン強化学習におけるポリシー評価のサンプル複雑さについて検討する。
低分布シフトの仮定の下では、最大$oleft(maxleft fracleftvert thetapirightvert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$サンプルを必要とするアルゴリズムがあることを示す。
論文 参考訳(メタデータ) (2021-03-17T18:18:57Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳(メタデータ) (2020-05-29T07:20:35Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳(メタデータ) (2020-02-12T03:40:52Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳(メタデータ) (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。