論文の概要: When are Local Queries Useful for Robust Learning?
- arxiv url: http://arxiv.org/abs/2210.06089v1
- Date: Wed, 12 Oct 2022 11:04:22 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-13 15:24:39.199124
- Title: When are Local Queries Useful for Robust Learning?
- Title（参考訳）: ローカルクエリはいつ堅牢な学習に有用か?
- Authors: Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, James Worrell
- Abstract要約: 本研究では,学習者が局所的なクエリを用いてより多くのパワーを与えられる学習モデルについて検討する。
我々は、ロバストな経験的リスク最小化を行う最初の分布自由アルゴリズムを与える。
- 参考スコア（独自算出の注目度）: 25.832511407411637
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Distributional assumptions have been shown to be necessary for the robust
learnability of concept classes when considering the exact-in-the-ball robust
risk and access to random examples by Gourdeau et al. (2019). In this paper, we
study learning models where the learner is given more power through the use of
local queries, and give the first distribution-free algorithms that perform
robust empirical risk minimization (ERM) for this notion of robustness. The
first learning model we consider uses local membership queries (LMQ), where the
learner can query the label of points near the training sample. We show that,
under the uniform distribution, LMQs do not increase the robustness threshold
of conjunctions and any superclass, e.g., decision lists and halfspaces. Faced
with this negative result, we introduce the local equivalence query (LEQ)
oracle, which returns whether the hypothesis and target concept agree in the
perturbation region around a point in the training sample, as well as a
counterexample if it exists. We show a separation result: on one hand, if the
query radius $\lambda$ is strictly smaller than the adversary's perturbation
budget $\rho$, then distribution-free robust learning is impossible for a wide
variety of concept classes; on the other hand, the setting $\lambda=\rho$
allows us to develop robust ERM algorithms. We then bound the query complexity
of these algorithms based on online learning guarantees and further improve
these bounds for the special case of conjunctions. We finish by giving robust
learning algorithms for halfspaces with margins on both $\{0,1\}^n$ and
$\mathbb{R}^n$.
- Abstract（参考訳）: 正確なボール内ロバストリスクと、Gourdeau et al. (2019) によるランダムな例へのアクセスを考えると、概念クラスの堅牢な学習性には分布仮定が必要であることが示されている。
本稿では,局所的クエリを用いて学習者がより多くのパワーを与えられる学習モデルについて検討し,このロバスト性の概念に対してロバストな経験的リスク最小化(erm)を行う最初の分散フリーアルゴリズムを提案する。
私たちが検討する最初の学習モデルは、学習者がトレーニングサンプルの近くのポイントのラベルをクエリできるローカルメンバシップクエリ(LMQ)を使用する。
均一分布の下では、LMQ は接続の堅牢性しきい値や、決定リストやハーフスペースのような任意のスーパークラスを増大させません。
この負の結果に直面して、局所等価クエリー(LEQ)オラクルを導入する。これは、仮説と目標概念がトレーニングサンプルの点付近の摂動領域に一致するかどうかを返却し、もし存在するなら逆例を示す。
一方、クエリ半径$\lambda$が敵の摂動予算$\rho$より厳密に小さい場合、分散のない堅牢な学習は様々な概念クラスでは不可能であり、一方、$\lambda=\rho$の設定は堅牢なEMMアルゴリズムの開発を可能にします。
そして、オンライン学習保証に基づいてこれらのアルゴリズムの問合せ複雑性を制限し、特別な結合の場合にはこれらの境界をさらに改善します。
ハーフスペースに対して、$\{0,1\}^n$ と $\mathbb{R}^n$ の両方にマージンを持つ堅牢な学習アルゴリズムを与える。
関連論文リスト
- Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension [17.485243410774814]
教師付き学習の伝統的なモデルでは、学習者の目標は、あるクラスから最も適した概念の競争的($epsilon$以内)な仮説を出力することである。
学習者が最高の無知としか競合しないスムーズな分析フレームワークを導入する。
時間内に$k$-halfspacesの交点を前向きに学習する最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-07-01T04:58:36Z) - Testable Learning with Distribution Shift [9.036777309376697]
分散シフトを伴うテスト可能学習と呼ばれる新しいモデルを定義する。
テスト分布上の分類器の性能を証明可能なアルゴリズムを得る。
ハーフスペースやハーフスペースの交点,決定木といった概念クラスを学ぶ上で,いくつかの肯定的な結果が得られる。
論文 参考訳（メタデータ） (2023-11-25T23:57:45Z) - Sample Complexity of Robust Learning against Evasion Attacks [3.8888996044605855]
本研究では, 学習理論の観点から, サンプルの複雑さを考慮し, 逆向きの頑健な学習の実現可能性について検討する。
均一分布下では, 連接関係をしっかり学習する相手の予算への指数的依存は避けられないままである。
問合せ半径が敵の予算に等しければ、分布自由な環境で堅牢な経験的リスクアルゴリズムを開発できることを示す。
論文 参考訳（メタデータ） (2023-08-23T10:51:33Z) - 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) - Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a
Generative Model [50.38446482252857]
2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。
我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。
我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
論文 参考訳（メタデータ） (2022-08-22T17:24:55Z) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-01T14:10:38Z) - Sample Complexity of Adversarially Robust Linear Classification on
Separated Data [41.30425613353595]
対向的堅牢性を伴う学習の複雑さについて考察する。
非常に分離されたデータの場合、$o(frac1n)$の収束率は達成可能である。
論文 参考訳（メタデータ） (2020-12-19T22:04:59Z) - Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
Sample Complexity [67.02490430380415]
モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。
また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
論文 参考訳（メタデータ） (2020-07-15T03:25:24Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Distributionally Robust Weighted $k$-Nearest Neighbors [21.537952410507483]
少数のサンプルから堅牢な分類器を学ぶことは、マシンラーニングにおける重要な課題である。
本稿では, 重み付き$k$-アネレスト近傍のミニマックス分布に頑健な定式化について検討する。
我々は,この関数最適化問題を効率的に解くアルゴリズムである textttDr.k-NN を開発した。
論文 参考訳（メタデータ） (2020-06-07T00:34:33Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。