論文の概要: Bayes meets Bernstein at the Meta Level: an Analysis of Fast Rates in
Meta-Learning with PAC-Bayes
- arxiv url: http://arxiv.org/abs/2302.11709v1
- Date: Thu, 23 Feb 2023 00:07:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-24 16:49:21.125037
- Title: Bayes meets Bernstein at the Meta Level: an Analysis of Fast Rates in
Meta-Learning with PAC-Bayes
- Title（参考訳）: ベイズはメタレベルでバーンスタインと出会う:PAC-Bayesを用いたメタラーニングの高速化分析
- Authors: Charles Riou, Pierre Alquier and Badr-Eddine Ch\'erief-Abdellatif
- Abstract要約: バーンスタインの条件は、機械学習における高速な速度を保証する重要な仮定である。
従来の$O(sqrtd_pi/n)$とは対照的に、$O(d_pi/n)$に余剰リスクがあることを示す。
- 参考スコア（独自算出の注目度）: 6.961253535504979
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bernstein's condition is a key assumption that guarantees fast rates in
machine learning. For example, the Gibbs algorithm with prior $\pi$ has an
excess risk in $O(d_{\pi}/n)$, as opposed to the standard
$O(\sqrt{d_{\pi}/n})$, where $n$ denotes the number of observations and
$d_{\pi}$ is a complexity parameter which depends on the prior $\pi$. In this
paper, we examine the Gibbs algorithm in the context of meta-learning, i.e.,
when learning the prior $\pi$ from $T$ tasks (with $n$ observations each)
generated by a meta distribution. Our main result is that Bernstein's condition
always holds at the meta level, regardless of its validity at the observation
level. This implies that the additional cost to learn the Gibbs prior $\pi$,
which will reduce the term $d_\pi$ across tasks, is in $O(1/T)$, instead of the
expected $O(1/\sqrt{T})$. We further illustrate how this result improves on
standard rates in three different settings: discrete priors, Gaussian priors
and mixture of Gaussians priors.
- Abstract（参考訳）: Bernsteinの条件は、機械学習における高速な速度を保証する重要な仮定である。
例えば、$\pi$のGibbsアルゴリズムは、標準的な$O(\sqrt{d_{\pi}/n})$とは対照的に、$O(d_{\pi}/n)$の余剰リスクを持ち、$n$は観測数を表し、$d_{\pi}$は以前の$\pi$に依存する複雑性パラメータである。
本稿では,メタ分布によって生成される$t$タスク(それぞれ$n$観察)から以前の$\pi$を学習する際に,メタ学習の文脈でgibbsアルゴリズムを調べる。
我々の主な結果は、ベルンシュタインの状態が観測レベルでの妥当性に関わらず常にメタレベルに留まっていることである。
これは、タスク間で$d_\pi$という用語を減少させる$\pi$以前のgibbsを学ぶ追加コストが、期待される$o(1/\sqrt{t})$ではなく$o(1/t)$となることを意味する。
さらに、この結果は、離散事前、ガウス先行、ガウス先行の混合の3つの異なる設定における標準レートをどのように改善するかを示す。
関連論文リスト
- Mini-Batch Kernel $k$-means [4.604003661048267]
私たちのアルゴリズムの1つのイテレーションは$widetildeO(kb2)$時間であり、フルバッチカーネルの$k$-meansに必要な$O(n2)$時間よりもはるかに高速です。
実験により,本アルゴリズムは品質の低下を最小限に抑えた10-100倍の高速化を実現していることがわかった。
論文 参考訳（メタデータ） (2024-10-08T10:59:14Z) - Data Structures for Density Estimation [66.36971978162461]
p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。
また、Acharyaなどのアルゴリズムの改良版も提供します。
論文 参考訳（メタデータ） (2023-06-20T06:13:56Z) - Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。
我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。
平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文 参考訳（メタデータ） (2023-04-17T10:38:08Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - A spectral least-squares-type method for heavy-tailed corrupted
regression with unknown covariance \& heterogeneous noise [2.019622939313173]
重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。
本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
論文 参考訳（メタデータ） (2022-09-06T23:37:31Z) - Faster Sampling from Log-Concave Distributions over Polytopes via a
Soft-Threshold Dikin Walk [28.431572772564518]
我々は、$d$-dimensional log-concave distribution $pi(theta) propto e-f(theta)$からポリトープ$K$に制約された$m$不等式をサンプリングする問題を考える。
我々の主な成果は、少なくとも$O((md + d L2 R2) times MDomega-1) log(fracwdelta)$ arithmetic operation to sample from $pi$ の "soft-warm' variant of the Dikin walk Markov chain" である。
論文 参考訳（メタデータ） (2022-06-19T11:33:07Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Mediated Uncoupled Learning: Learning Functions without Direct
Input-output Correspondences [80.95776331769899]
ペア化されたデータがない場合、$X$から$Y$を予測するタスクを考えます。
単純なアプローチは、$S_X$で$U$から$U$を予測し、$S_Y$で$U$から$Y$を予測することである。
我々は$U$を予測しない新しい方法を提案するが、$f(X)$と$S_X$をトレーニングすることで$Y = f(X)$を直接学習し、$h(U)$を予測する。
論文 参考訳（メタデータ） (2021-07-16T22:13:29Z) - The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。
加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
論文 参考訳（メタデータ） (2020-07-16T04:23:57Z) - Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。
我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
論文 参考訳（メタデータ） (2020-06-11T00:55:35Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。