論文の概要: Reality Only Happens Once: Single-Path Generalization Bounds for Transformers
- arxiv url: http://arxiv.org/abs/2405.16563v1
- Date: Sun, 26 May 2024 13:19:32 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-28 20:29:27.972016
- Title: Reality Only Happens Once: Single-Path Generalization Bounds for Transformers
- Title(参考訳): 現実は一度だけ起こる:変圧器の単一パス一般化境界
- Authors: Yannick Limmer, Anastasis Kratsios, Xuwei Yang, Raeid Saqur, Blanka Horvath,
- Abstract要約: 我々は、この設定における非漸近的な統計的保証を、将来的な$t$における変圧器ネットワークのテキスト一般化のバウンダリによって導き出す。
私たちの境界は3つの要素から構成される: (I) 第一に、データ生成マルコフ過程の定常分布と、その時間で$t$の分布とのギャップを定量化する。
次の項は変換器モデルの複雑さを符号化し、十分な時間があれば、最終的には$O(log(N)r/sqrtN)$で$0$に収束する。
- 参考スコア(独自算出の注目度): 9.305677878388664
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: One of the inherent challenges in deploying transformers on time series is that \emph{reality only happens once}; namely, one typically only has access to a single trajectory of the data-generating process comprised of non-i.i.d. observations. We derive non-asymptotic statistical guarantees in this setting through bounds on the \textit{generalization} of a transformer network at a future-time $t$, given that it has been trained using $N\le t$ observations from a single perturbed trajectory of a Markov process. Under the assumption that the Markov process satisfies a log-Sobolev inequality, we obtain a generalization bound which effectively converges at the rate of ${O}(1/\sqrt{N})$. Our bound depends explicitly on the activation function ($\operatorname{Swish}$, $\operatorname{GeLU}$, or $\tanh$ are considered), the number of self-attention heads, depth, width, and norm-bounds defining the transformer architecture. Our bound consists of three components: (I) The first quantifies the gap between the stationary distribution of the data-generating Markov process and its distribution at time $t$, this term converges exponentially to $0$. (II) The next term encodes the complexity of the transformer model and, given enough time, eventually converges to $0$ at the rate ${O}(\log(N)^r/\sqrt{N})$ for any $r>0$. (III) The third term guarantees that the bound holds with probability at least $1$-$\delta$, and converges at a rate of ${O}(\sqrt{\log(1/\delta)}/\sqrt{N})$.
- Abstract(参考訳): 時系列上でトランスフォーマーをデプロイする際の固有の課題の1つは、 \emph{reality only occur once} である。
マルコフ過程の1つの摂動軌跡から$N\le t$ の観測を用いて訓練されたことを考慮し、この設定における非漸近的統計的保証を、将来的な$t$における変圧器ネットワークの \textit{ Generalization} のバウンダリによって導き出す。
マルコフ過程が対数ソボレフの不等式を満たすという仮定の下で、${O}(1/\sqrt{N})$の速度で効果的に収束する一般化境界を得る。
私たちのバウンダリは、アクティベーション関数($\operatorname{Swish}$, $\operatorname{GeLU}$, $\tanh$)、自己アテンションヘッドの数、深さ、幅、およびトランスフォーマーアーキテクチャを定義するノルムバウンドに依存する。
第一に、データ生成マルコフ過程の定常分布と時間$t$での分布とのギャップを定量化し、この項は指数関数的に$0$に収束する。
(II)
次の項は変換モデルの複雑さをエンコードし、十分な時間を与えると、任意の$r>0$に対して${O}(\log(N)^r/\sqrt{N})$で$0$に収束する。
(III)
第3項は、有界が少なくとも1$-$\delta$の確率を持ち、${O}(\sqrt{\log(1/\delta)}/\sqrt{N})$の速度で収束することを保証している。
関連論文リスト
- Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers [29.212403229351253]
我々は、このマルコフ連鎖のほぼ最適な実装を示し、ステップごとの複雑さは、約$A$のゼロでないエントリの数であるのに対して、マルコフ連鎖のステップの数は同じである。
1) このダイキンウォークで生じる行列はゆっくりと変化すること,2) この遅い変化を利用した効率的な線形解法を展開し, 以前のステップで計算した情報を用いて行列の逆転を高速化すること,3) ランダム化されたテイラー級数に基づく推定器を用いてメトロポリスフィルタステップにおける行列項の計算を高速化すること,である。
論文 参考訳(メタデータ) (2024-09-06T14:49:43Z) - Accelerated Variance-Reduced Forward-Reflected Methods for Root-Finding Problems [8.0153031008486]
そこで本研究では,Nesterovの高速前方反射法と分散還元法を新たに提案し,根絶問題の解法を提案する。
我々のアルゴリズムは単ループであり、ルートフィリング問題に特化して設計された非バイアス分散還元推定器の新たなファミリーを利用する。
論文 参考訳(メタデータ) (2024-06-04T15:23:29Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳(メタデータ) (2024-02-06T15:39:09Z) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳(メタデータ) (2024-02-01T07:21:32Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳(メタデータ) (2023-09-25T17:54:19Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳(メタデータ) (2022-06-16T17:10:57Z) - An iterative quantum-phase-estimation protocol for near-term quantum
hardware [0.0]
エンタングルメントフリーなプロトコルが開発され、$mathcalO left[ sqrtlog (log N_textrmtot) / N_textrmtot right]$ mean-absolute-error scaling.
そこで本研究では,誤差スケーリングを改良した2段階間位相推定プロトコルを提案する。
論文 参考訳(メタデータ) (2022-06-13T18:00:09Z) - The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning [3.8098187557917464]
この論文は$d$-dimensional recursion approximation, $$theta_n+1=theta_n + alpha_n + 1 f(theta_n, Phi_n+1)に関するものである。
主な結果は、ドスカー・バラダン・リャプノフドリフト条件(DV3)の平均流とバージョンに関する追加条件の下で確立される。
a example is given where $f$ and $barf$ are linear in $theta$, and $Phi$ is a geometryal.
論文 参考訳(メタデータ) (2021-10-27T13:38:25Z) - A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning [3.655021726150368]
マルチエージェント強化学習(MARL: Multi-Agent Reinforcement Learning)では、複数のエージェントが共通の環境と相互作用し、シーケンシャルな意思決定において共有問題を解く。
我々は、MARLで有用な分散非線形近似スキームの族を反復する新しい法則を導出する。
論文 参考訳(メタデータ) (2021-10-27T08:01:17Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳(メタデータ) (2020-06-04T17:51:00Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳(メタデータ) (2020-03-05T01:56:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。