Fugu-MT 論文翻訳(概要): Testable Learning with Distribution Shift

論文の概要: Testable Learning with Distribution Shift

arxiv url: http://arxiv.org/abs/2311.15142v2
Date: Mon, 20 May 2024 18:16:12 GMT
ステータス: 処理完了
システム内更新日: 2024-05-22 19:01:09.276029
Title: Testable Learning with Distribution Shift
Title（参考訳）: 分散シフトによるテスト可能な学習
Authors: Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan,
Abstract要約: 分散シフトを伴うテスト可能学習と呼ばれる新しいモデルを定義する。テスト分布上の分類器の性能を証明可能なアルゴリズムを得る。ハーフスペースやハーフスペースの交点,決定木といった概念クラスを学ぶ上で,いくつかの肯定的な結果が得られる。
参考スコア（独自算出の注目度）: 9.036777309376697
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We revisit the fundamental problem of learning with distribution shift, in which a learner is given labeled samples from training distribution $D$, unlabeled samples from test distribution $D'$ and is asked to output a classifier with low test error. The standard approach in this setting is to bound the loss of a classifier in terms of some notion of distance between $D$ and $D'$. These distances, however, seem difficult to compute and do not lead to efficient algorithms. We depart from this paradigm and define a new model called testable learning with distribution shift, where we can obtain provably efficient algorithms for certifying the performance of a classifier on a test distribution. In this model, a learner outputs a classifier with low test error whenever samples from $D$ and $D'$ pass an associated test; moreover, the test must accept if the marginal of $D$ equals the marginal of $D'$. We give several positive results for learning well-studied concept classes such as halfspaces, intersections of halfspaces, and decision trees when the marginal of $D$ is Gaussian or uniform on $\{\pm 1\}^d$. Prior to our work, no efficient algorithms for these basic cases were known without strong assumptions on $D'$. For halfspaces in the realizable case (where there exists a halfspace consistent with both $D$ and $D'$), we combine a moment-matching approach with ideas from active learning to simulate an efficient oracle for estimating disagreement regions. To extend to the non-realizable setting, we apply recent work from testable (agnostic) learning. More generally, we prove that any function class with low-degree $L_2$-sandwiching polynomial approximators can be learned in our model. We apply constructions from the pseudorandomness literature to obtain the required approximators.
Abstract（参考訳）: そこで本研究では,学習者が学習ディストリビューションからラベル付きサンプルに$D$,テストディストリビューションから$D’$のラベル付きサンプルを付与し,テストエラーの少ない分類器を出力する,分散シフトによる学習の基本的な問題を再検討する。この設定における標準的なアプローチは、$D$ と $D'$ の間の距離の概念によって分類器の損失を限定することである。しかし、これらの距離は計算が難しく、効率的なアルゴリズムに繋がらない。我々はこのパラダイムから離れ、分散シフトを伴うテスト可能学習と呼ばれる新しいモデルを定義し、テスト分布上での分類器の性能を証明可能なアルゴリズムを得る。このモデルでは、学習者は、$D$と$D’$のサンプルが関連するテストに合格するたびに、低いテストエラーの分類器を出力する。ハーフ空間、ハーフ空間の交叉、決定木などのよく研究された概念クラスを学習するために、D$の限界がガウス的あるいは一様であるとき、いくつかの肯定的な結果を与える。我々の研究に先立ち、これらの基本事例に対する効率的なアルゴリズムは、$D'$に関する強い仮定なしでは知られていなかった。実現可能な場合($D$と$D’$の両方に整合したハーフスペースが存在する場合)のハーフスペースに対しては、モーメントマッチングアプローチとアクティブラーニングのアイデアを組み合わせて、不一致領域を推定するための効率的なオラクルをシミュレートする。実現不可能な設定にまで拡張するために、テスト可能な(不可知な)学習から最近の研究を適用する。より一般的には、低次$L_2$サンドウィッチ多項式近似器を持つ任意の関数クラスが、我々のモデルで学習できることが証明される。我々は,必要な近似値を得るために擬似ランダム性文献から構成を適用した。

関連論文リスト

Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [65.8915778873691]
条件分布は機械学習の中心的な問題ですペアデータとペアデータの両方を統合する新しい学習パラダイムを提案する。我々のアプローチはまた、興味深いことに逆エントロピー最適輸送(OT)と結びついている。
論文参考訳（メタデータ） (2024-10-03T16:12:59Z)
Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds [9.036777309376697]
Klivans、Stavropoulos、Vasilyanは、分散シフトを伴うテスト可能な学習の研究を始めた。それらのモデルは、$mathcalD'$に仮定されないという点で、以前のすべての作業から逸脱している。
論文参考訳（メタデータ） (2024-04-02T23:34:39Z)
Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文参考訳（メタデータ） (2023-07-13T18:59:28Z)
Efficient Testable Learning of Halfspaces with Adversarial Label Noise [44.32410859776227]
最近導入されたテスト可能な学習モデルでは、データがテスタを通過すると、データに対する堅牢な学習者の出力を信頼するように、テスタ-ラーナーを作成する必要がある。テストラナーは、時間$poly(d/eps)$を実行し、ミス分類エラー$O(opt)+eps$でハーフスペースを出力します。
論文参考訳（メタデータ） (2023-03-09T18:38:46Z)
An Efficient Tester-Learner for Halfspaces [13.13131953359806]
本稿では、Rubinfeld と Vasilyan が最近定義したテスト可能な学習モデルにおいて、ハーフスペースを学習するための最初の効率的なアルゴリズムを提案する(2023)。このモデルでは、学習者は、トレーニングセットがテストに合格するたびに、その出力仮説の精度がほぼ最適であると認定する。
論文参考訳（メタデータ） (2023-02-28T18:51:55Z)
Generalized Differentiable RANSAC [95.95627475224231]
$nabla$-RANSACは、ランダム化された堅牢な推定パイプライン全体を学ぶことができる、微分可能なRANSACである。 $nabla$-RANSACは、精度という点では最先端のシステムよりも優れているが、精度は低い。
論文参考訳（メタデータ） (2022-12-26T15:13:13Z)
When are Local Queries Useful for Robust Learning? [25.832511407411637]
本研究では,学習者が局所的なクエリを用いてより多くのパワーを与えられる学習モデルについて検討する。我々は、ロバストな経験的リスク最小化を行う最初の分布自由アルゴリズムを与える。我々は、0,1n$でハーフスペースに対してロバストな学習アルゴリズムを与え、その後、精度に縛られた敵に対して$mathbbRn$でハーフスペースに対してロバスト性を保証する。
論文参考訳（メタデータ） (2022-10-12T11:04:22Z)
Testing distributional assumptions of learning algorithms [5.204779946147061]
テストレーナー対 $(mathcalA,mathcalT)$ の設計について検討する。データ中の例の分布がテスタを$mathcalT$に渡せば、データ上の非依存な$mathcalA$の出力を安全に信頼できることを示す。
論文参考訳（メタデータ） (2022-04-14T19:10:53Z)
Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文参考訳（メタデータ） (2021-09-01T14:10:38Z)
Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文参考訳（メタデータ） (2020-06-11T14:25:02Z)
Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文参考訳（メタデータ） (2020-05-26T17:53:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。