論文の概要: Efficient Learning with Arbitrary Covariate Shift
- arxiv url: http://arxiv.org/abs/2102.07802v1
- Date: Mon, 15 Feb 2021 19:14:25 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-17 15:18:20.684033
- Title: Efficient Learning with Arbitrary Covariate Shift
- Title（参考訳）: 任意共変シフトによる効率的な学習
- Authors: Adam Kalai, Varun Kanade
- Abstract要約: 境界のあるVC次元のクラスCで2進関数を学習するための効率的なアルゴリズムを提供し、トレーニングデータはPに従って分散し、テストデータはQに従って分散する。
本研究では,信頼できる学習が片面ノイズによる学習のモデルであるCの"信頼できる学習者"に,オーラクルを用いた時間PQ学習アルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 19.230859892728784
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give an efficient algorithm for learning a binary function in a given
class C of bounded VC dimension, with training data distributed according to P
and test data according to Q, where P and Q may be arbitrary distributions over
X. This is the generic form of what is called covariate shift, which is
impossible in general as arbitrary P and Q may not even overlap. However,
recently guarantees were given in a model called PQ-learning (Goldwasser et
al., 2020) where the learner has: (a) access to unlabeled test examples from Q
(in addition to labeled samples from P, i.e., semi-supervised learning); and
(b) the option to reject any example and abstain from classifying it (i.e.,
selective classification). The algorithm of Goldwasser et al. (2020) requires
an (agnostic) noise tolerant learner for C. The present work gives a
polynomial-time PQ-learning algorithm that uses an oracle to a "reliable"
learner for C, where reliable learning (Kalai et al., 2012) is a model of
learning with one-sided noise. Furthermore, our reduction is optimal in the
sense that we show the equivalence of reliable and PQ learning.
- Abstract（参考訳）: 有界VC次元のクラスCのバイナリ関数を学習するための効率的なアルゴリズムを、Pに応じて分布するトレーニングデータと、Qに従って分布するテストデータとで、PとQはX上の任意の分布である。
これは、任意の P と Q が重複しなくてもよいので一般に不可能である共変シフトと呼ばれるものの一般的な形式である。
しかしながら、最近、PQラーニング(Goldwasser et al., 2020)と呼ばれるモデルでは、学習者が(a)Qからのラベル付きテスト例へのアクセス(Pからのラベル付きサンプルに加えて、半教師付き学習)、(b)任意の例を拒絶し、それを分類する(選択的分類)オプションが与えられた。
goldwasserらによるアルゴリズム。
本研究では,信頼性の高い学習(Kalai et al., 2012)が片面ノイズ学習のモデルであるCの「信頼できる」学習者に対して,オーラクルを用いた多項式時間PQ学習アルゴリズムを提供する。
さらに、信頼性とPQ学習の等価性を示すという意味で、当社の削減は最適です。
関連論文リスト
- Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
非対話的局所差分プライバシー(LDP)における2つの基本的な統計課題について検討する。
本研究の主な成果は,非対話型LDPプロトコルにおけるPAC学習の複雑さの完全な評価である。
論文 参考訳（メタデータ） (2022-10-26T03:19:24Z) - Sufficient Exploration for Convex Q-learning [10.75319149461189]
本稿では,マンヌの最適制御を線形プログラミング(LP)で定式化する。
原始版はロジスティックQラーニングと呼ばれ、二重版は凸Qラーニングである。
コンベックスQラーニングは,標準Qラーニングが分岐する場合に有効であることが示されている。
論文 参考訳（メタデータ） (2022-10-17T20:22:12Z) - q-Learning in Continuous Time [1.4213973379473654]
エントロピー規則化探索拡散過程の定式化による強化学習(RL)におけるQ-ラーニングの連続的対応について検討した。
我々は、時間離散化とは無関係なq-函数に関するq-ラーニング理論を開発する。
我々は、根底にある問題を解決するために、異なるアクター批判アルゴリズムを考案する。
論文 参考訳（メタデータ） (2022-07-02T02:20:41Z) - A Boosting Approach to Reinforcement Learning [59.46285581748018]
複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。
このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-08-22T16:00:45Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳（メタデータ） (2021-05-06T17:59:38Z) - Tightening the Dependence on Horizon in the Sample Complexity of
Q-Learning [59.71676469100807]
この研究は、同期Q-ラーニングのサンプルの複雑さを、任意の$0varepsilon 1$に対して$frac|mathcalS| (1-gamma)4varepsilon2$の順序に絞る。
計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
論文 参考訳（メタデータ） (2021-02-12T14:22:05Z) - A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。
我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
論文 参考訳（メタデータ） (2020-10-04T22:19:06Z) - Finite-Time Analysis for Double Q-learning [50.50058000948908]
二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。
同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
論文 参考訳（メタデータ） (2020-09-29T18:48:21Z) - When Hardness of Approximation Meets Hardness of Learning [35.39956227364153]
線形クラスと浅層ネットワークを用いた近似の硬さと,相関クエリと勾配差を用いた学習の硬さを両立させる単一の硬さ特性を示す。
これにより、パリティ関数、DNF式および$AC0$回路の近似の硬さと学習性に関する新たな結果が得られる。
論文 参考訳（メタデータ） (2020-08-18T17:41:28Z) - Convex Q-Learning, Part 1: Deterministic Optimal Control [5.685589351789462]
一般的な関数近似設定へのワトキンスアルゴリズムの拡張が困難であることはよく知られている。
論文は、線形プログラミングアプローチによる最適制御に関する簡単な調査から始まり、特にパラメータ化の過度化が強化学習の応用に繋がる。
凸 Q-ラーニングはベルマン方程式を近似する凸プログラムを解くが、DQNの理論は関数近似のワトキンスアルゴリズムよりも強いものではない。
論文 参考訳（メタデータ） (2020-08-08T17:17:42Z) - Q-Learning with Differential Entropy of Q-Tables [4.221871357181261]
我々は、Q-ラーニングの長期トレーニングセッションにおけるパフォーマンスの低下は、情報の喪失によって引き起こされると推測する。
本稿では,Q-ラーニングアルゴリズムに外部情報損失検出器として,Q-tables(DE-QT)の微分エントロピーを導入する。
論文 参考訳（メタデータ） (2020-06-26T04:37:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。