論文の概要: A Characterization of Semi-Supervised Adversarially-Robust PAC
Learnability
- arxiv url: http://arxiv.org/abs/2202.05420v1
- Date: Fri, 11 Feb 2022 03:01:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-14 14:20:27.816003
- Title: A Characterization of Semi-Supervised Adversarially-Robust PAC
Learnability
- Title(参考訳): 半教師付き逆回転PAC学習性の評価
- Authors: Idan Attias and Steve Hanneke and Yishay Mansour
- Abstract要約: 本研究では,PACモデルにおける逆回転予測器の半教師付き学習の問題について検討する。
半教師付き学習におけるサンプルの複雑さには、ラベル付きサンプルの数とラベルなしサンプルの数という2つのパラメータがある。
- 参考スコア(独自算出の注目度): 50.570683146531564
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of semi-supervised learning of an adversarially-robust
predictor in the PAC model, where the learner has access to both labeled and
unlabeled examples. The sample complexity in semi-supervised learning has two
parameters, the number of labeled examples and the number of unlabeled
examples. We consider the complexity measures, $VC_U \leq dim_U \leq VC$ and
$VC^*$, where $VC$ is the standard $VC$-dimension, $VC^*$ is its dual, and the
other two measures appeared in Montasser et al. (2019). The best sample bound
known for robust supervised PAC learning is $O(VC \cdot VC^*)$, and we will
compare our sample bounds to $\Lambda$ which is the minimal number of labeled
examples required by any robust supervised PAC learning algorithm. Our main
results are the following: (1) in the realizable setting it is sufficient to
have $O(VC_U)$ labeled examples and $O(\Lambda)$ unlabeled examples. (2) In the
agnostic setting, let $\eta$ be the minimal agnostic error. The sample
complexity depends on the resulting error rate. If we allow an error of
$2\eta+\epsilon$, it is still sufficient to have $O(VC_U)$ labeled examples and
$O(\Lambda)$ unlabeled examples. If we insist on having an error
$\eta+\epsilon$ then $\Omega(dim_U)$ labeled examples are necessary, as in the
supervised case. The above results show that there is a significant benefit in
semi-supervised robust learning, as there are hypothesis classes with $VC_U=0$
and $dim_U$ arbitrary large. In supervised learning, having access only to
labeled examples requires at least $\Lambda \geq dim_U$ labeled examples.
Semi-supervised require only $O(1)$ labeled examples and $O(\Lambda)$ unlabeled
examples. A byproduct of our result is that if we assume that the distribution
is robustly realizable by a hypothesis class, then with respect to the 0-1 loss
we can learn with only $O(VC_U)$ labeled examples, even if the $VC$ is
infinite.
- Abstract(参考訳): 学習者がラベル付きとラベル付きの両方の例にアクセスできるpacモデルにおける,逆ロバスト予測器の半教師付き学習の問題点について検討する。
半教師付き学習におけるサンプル複雑性は、ラベル付きサンプル数とラベルなしサンプル数という2つのパラメータを持つ。
例えば、$VC_U \leq dim_U \leq VC$と$VC^*$、$VC$は標準の$VC$-dimension、$VC^*$はその双対、その他の2つの尺度はMontasser et al. (2019)である。
堅牢なPAC学習で知られている最良のサンプルは$O(VC \cdot VC^*)$であり、我々のサンプル境界を、堅牢なPAC学習アルゴリズムに必要なラベル付きサンプルの最小数である$\Lambda$と比較する。
1) 実現可能な設定では、$O(VC_U)$ラベル付き例と$O(\Lambda)$ラベルなし例を持つことで十分です。
2) agnostic 設定では、$\eta$ を最小の agnostic エラーとする。
サンプルの複雑さは、結果のエラー率に依存する。
2\eta+\epsilon$のエラーを許せば、ラベル付き例は$O(VC_U)$、ラベルなし例は$O(\Lambda)$で十分である。
もし$\eta+\epsilon$のエラーを主張するなら、教師付きの場合のように$\omega(dim_u)$ラベル付き例が必要である。
上記の結果は、半教師付きロバスト学習には、$vc_u=0$ と $dim_u$ を持つ仮説クラスがあるため、大きな利点があることを示している。
教師付き学習では、ラベル付き例のみにアクセスするには、少なくとも$\Lambda \geq dim_U$ラベル付き例が必要である。
半教師はラベル付き例は$O(1)$とラベルなし例は$O(\Lambda)$である。
結果の副産物は、分布が仮説クラスによって堅牢に実現可能であると仮定すると、0-1の損失に対して$O(VC_U)$ラベル付き例だけで学習できるということである。
関連論文リスト
- Tight Time-Space Lower Bounds for Constant-Pass Learning [1.7387739961208148]
サンプルストリームを$q$で通過するパリティ学習アルゴリズムに対して,メモリサンプルの少ないバウンダリを厳密に証明する。
このような学習者には、メモリサイズが$Omega(n2)$か、少なくとも$Omega(n)$サンプルが必要である。
これまでの研究と同様に、この結果は、ほぼ直交的な概念を多く含んだ学習問題にまで及んでいる。
論文 参考訳(メタデータ) (2023-10-12T06:36:31Z) - Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic
Shortest Path [106.37656068276902]
本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。
学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。
我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
論文 参考訳(メタデータ) (2022-10-10T18:34:32Z) - Optimal algorithms for learning quantum phase states [8.736370689844682]
未知の次数$d$相状態を学ぶ際のサンプルの複雑さは、分離可能な測定を許せば$Theta(nd)$であることを示す。
また、f$がsparsity-$s$, degree-$d$を持つ場合の学習フェーズ状態も検討する。
論文 参考訳(メタデータ) (2022-08-16T17:15:06Z) - 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) - Semi-supervised Active Regression [21.51757844385258]
本稿では,学習課題における偏りのある部分ラベル付きデータの利用について検討する。
学習者は、追加のラベルクエリをほとんど行わずに、mathbbRd | X min_beta in mathbbRd | X beta - Y |2 end2 方程式でデータセット $X にアクセスすることができる。
論文 参考訳(メタデータ) (2021-06-12T03:28:43Z) - Agnostic learning with unknown utilities [70.14742836006042]
現実世界の多くの問題において、決定の効用は基礎となる文脈である$x$ と decision $y$ に依存する。
我々はこれを未知のユーティリティによる不可知学習として研究する。
サンプルされた点のみのユーティリティを推定することで、よく一般化した決定関数を学習できることを示す。
論文 参考訳(メタデータ) (2021-04-17T08:22:04Z) - Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。
DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
論文 参考訳(メタデータ) (2020-12-29T14:06:09Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。