論文の概要: Evaluated CMI Bounds for Meta Learning: Tightness and Expressiveness
- arxiv url: http://arxiv.org/abs/2210.06511v1
- Date: Wed, 12 Oct 2022 18:10:59 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-14 15:16:53.529137
- Title: Evaluated CMI Bounds for Meta Learning: Tightness and Expressiveness
- Title(参考訳): メタ学習におけるcmi境界の評価 : タイトネスと表現力
- Authors: Fredrik Hellstr\"om and Giuseppe Durisi
- Abstract要約: 評価CMI(e-CMI)を用いたメタ学習のための新しい一般化境界を提案する。
e-CMI フレームワークは、$sqrt の数学カル C(mathcal H)/(nhat n) + 数学カル C(mathcal F)/n $, ここで $mathcal C(cdot)$ は仮説クラスの複雑性測度を表す。
- 参考スコア(独自算出の注目度): 14.147617330278662
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent work has established that the conditional mutual information (CMI)
framework of Steinke and Zakynthinou (2020) is expressive enough to capture
generalization guarantees in terms of algorithmic stability, VC dimension, and
related complexity measures for conventional learning (Harutyunyan et al.,
2021, Haghifam et al., 2021). Hence, it provides a unified method for
establishing generalization bounds. In meta learning, there has so far been a
divide between information-theoretic results and results from classical
learning theory. In this work, we take a first step toward bridging this
divide. Specifically, we present novel generalization bounds for meta learning
in terms of the evaluated CMI (e-CMI). To demonstrate the expressiveness of the
e-CMI framework, we apply our bounds to a representation learning setting, with
$n$ samples from $\hat n$ tasks parameterized by functions of the form $f_i
\circ h$. Here, each $f_i \in \mathcal F$ is a task-specific function, and $h
\in \mathcal H$ is the shared representation. For this setup, we show that the
e-CMI framework yields a bound that scales as $\sqrt{ \mathcal C(\mathcal
H)/(n\hat n) + \mathcal C(\mathcal F)/n} $, where $\mathcal C(\cdot)$ denotes a
complexity measure of the hypothesis class. This scaling behavior coincides
with the one reported in Tripuraneni et al. (2020) using Gaussian complexity.
- Abstract(参考訳): 最近の研究では、steinke and zakynthinou (2020) の条件付き相互情報(cmi)フレームワークは、アルゴリズムの安定性、vc次元、および従来の学習のための関連する複雑性尺度の観点から、一般化の保証を捉えるのに十分な表現力を持っている(haltyunyan et al., 2021, haghifam et al., 2021)。
したがって、一般化境界を確立する統一的な方法を提供する。
メタラーニングでは、情報理論の結果と古典的な学習理論の成果との間には、これまでのところ分割があった。
この作業では、この分割をブリッジする第一歩を踏み出します。
具体的には、評価されたCMI(e-CMI)の観点からメタ学習のための新しい一般化境界を提案する。
e-CMIフレームワークの表現性を示すために、f_i \circ h$という形式の関数によってパラメータ化された$\hat n$タスクの$n$サンプルを表現学習設定に適用する。
ここで、各$f_i \in \mathcal f$ はタスク固有関数であり、$h \in \mathcal h$ は共有表現である。
この設定のために、e-CMIフレームワークは、$\sqrt{ \mathcal C(\mathcal H)/(n\hat n) + \mathcal C(\mathcal F)/n} $ とスケールする有界性を持ち、$\mathcal C(\cdot)$ は仮説クラスの複雑性測度を表す。
このスケーリング挙動は、Gaussian complexityを用いてTripuraneni et al. (2020)で報告されたものと一致する。
関連論文リスト
- A Theory of Interpretable Approximations [61.90216959710842]
我々は、ある基底クラス $mathcalH$ の概念の小さな集合によってターゲット概念 $c$ を近似するという考え方を研究する。
任意の$mathcalH$と$c$のペアに対して、これらのケースのちょうど1つが成り立つ: (i) $c$を任意の精度で$mathcalH$で近似することはできない。
解釈可能な近似の場合、近似の複雑さに関するわずかに非自明なa-priori保証でさえ、定数(分布自由かつ精度)の近似を意味することを示す。
論文 参考訳(メタデータ) (2024-06-15T06:43:45Z) - Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。
SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
論文 参考訳(メタデータ) (2024-06-03T17:56:58Z) - Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization [36.28082578445787]
我々は,円錐曲線最適化(SCO)の文脈における記憶と学習の相互作用について検討する。
我々は,Steinke と Zakynthinou が提唱した条件付き相互情報(CMI)の枠組みを用いた記憶の定量化(2020年)
L2$ Lipschitz-bounded set and under strong convexity, every learner with a excess error have CMI bounded by $Omega (1/varepsilon2)$ and $Omega (1/varepsilon)$。
論文 参考訳(メタデータ) (2024-02-14T17:17:30Z) - Convergence of a Normal Map-based Prox-SGD Method under the KL
Inequality [0.0]
我々は、$symbol$k$収束問題に対して、新しいマップベースのアルゴリズム(mathsfnorMtext-mathsfSGD$)を提案する。
論文 参考訳(メタデータ) (2023-05-10T01:12:11Z) - HappyMap: A Generalized Multi-calibration Method [23.086009024383024]
マルチキャリブレーション(英: Multi-calibration)はアルゴリズムフェアネスの分野を起源とする、強力で進化した概念である。
この研究では、$(f(x)-y)$ という用語を1つの特定の写像とみなし、豊かなクラスの写像のパワーを探求する。
マルチキャリブレーションを一般化したtextitHappyMap を提案する。
論文 参考訳(メタデータ) (2023-03-08T05:05:01Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳(メタデータ) (2023-02-13T22:51:07Z) - Multi-Task Imitation Learning for Linear Dynamical Systems [50.124394757116605]
線形システム上での効率的な模倣学習のための表現学習について検討する。
学習対象ポリシーによって生成された軌道上の模倣ギャップは、$tildeOleft(frack n_xHN_mathrmshared + frack n_uN_mathrmtargetright)$で制限されている。
論文 参考訳(メタデータ) (2022-12-01T00:14:35Z) - Towards a Unified Information-Theoretic Framework for Generalization [43.23033319683591]
まず、このフレームワークを用いて、任意の学習アルゴリズムに対して非自明な(しかし、準最適)境界を表現できることを実証する。
我々は、CMIフレームワークが、ハーフスペースを学習するためのSVM(Support Vector Machines)の予測されるリスクに最適な境界をもたらすことを証明した。
論文 参考訳(メタデータ) (2021-11-09T17:09:40Z) - On the Power of Multitask Representation Learning in Linear MDP [61.58929164172968]
本稿では,線形マルコフ決定過程(MDP)におけるマルチタスク表現学習の統計的メリットについて分析する。
簡単な最小二乗アルゴリズムが $tildeO(H2sqrtfrackappa MathcalC(Phi)2 kappa dNT+frackappa dn) というポリシーを学ぶことを証明した。
論文 参考訳(メタデータ) (2021-06-15T11:21:06Z) - On the Theory of Transfer Learning: The Importance of Task Diversity [114.656572506859]
一般的な関数クラス$mathcalF circ MathcalH$において、$f_j circ h$という形の関数によってパラメータ化される$t+1$タスクを考える。
多様なトレーニングタスクに対して、最初の$t$のトレーニングタスク間で共有表現を学ぶのに必要なサンプルの複雑さが、$C(mathcalH) + t C(mathcalF)$であることを示す。
論文 参考訳(メタデータ) (2020-06-20T20:33:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。