論文の概要: PAC Learning with Improvements
- arxiv url: http://arxiv.org/abs/2503.03184v1
- Date: Wed, 05 Mar 2025 05:03:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-06 15:53:08.765433
- Title: PAC Learning with Improvements
- Title（参考訳）: 改善したPAC学習
- Authors: Idan Attias, Avrim Blum, Keziah Naggita, Donya Saless, Dravyansh Sharma, Matthew Walter,
- Abstract要約: エラーを学習するためには、少なくとも$textit 1/epsilon$サンプルが必要だ。
だけで、$textitzero$エラーを達成できるかもしれません。
- 参考スコア（独自算出の注目度）: 17.501680004311577
- License:
- Abstract: One of the most basic lower bounds in machine learning is that in nearly any nontrivial setting, it takes $\textit{at least}$ $1/\epsilon$ samples to learn to error $\epsilon$ (and more, if the classifier being learned is complex). However, suppose that data points are agents who have the ability to improve by a small amount if doing so will allow them to receive a (desired) positive classification. In that case, we may actually be able to achieve $\textit{zero}$ error by just being "close enough". For example, imagine a hiring test used to measure an agent's skill at some job such that for some threshold $\theta$, agents who score above $\theta$ will be successful and those who score below $\theta$ will not (i.e., learning a threshold on the line). Suppose also that by putting in effort, agents can improve their skill level by some small amount $r$. In that case, if we learn an approximation $\hat{\theta}$ of $\theta$ such that $\theta \leq \hat{\theta} \leq \theta + r$ and use it for hiring, we can actually achieve error zero, in the sense that (a) any agent classified as positive is truly qualified, and (b) any agent who truly is qualified can be classified as positive by putting in effort. Thus, the ability for agents to improve has the potential to allow for a goal one could not hope to achieve in standard models, namely zero error. In this paper, we explore this phenomenon more broadly, giving general results and examining under what conditions the ability of agents to improve can allow for a reduction in the sample complexity of learning, or alternatively, can make learning harder. We also examine both theoretically and empirically what kinds of improvement-aware algorithms can take into account agents who have the ability to improve to a limited extent when it is in their interest to do so.
- Abstract（参考訳）: 機械学習における最も基本的な下限の1つは、ほとんどどんな非自明な設定でも、$\textit{at least}$ $1/\epsilon$サンプルをエラーで学ぶのに$\epsilon$(さらに、学習対象の分類器が複雑であれば)が必要であることである。
しかし、データポイントが、もしそうなれば、少量で改善する能力を持つエージェントであると仮定すると、彼らは(望まれる)肯定的な分類を受けることができる。
その場合、"十分近い"だけで$\textit{zero}$エラーを実現できるかもしれません。
例えば、ある仕事におけるエージェントのスキルを測定するために使用される採用テストについて考えてみましょう。例えば、あるしきい値$\theta$以上のエージェントは成功し、$\theta$以下のエージェントは成功しない(つまり、ライン上のしきい値を学ぶ)。
努力することで、エージェントはスキルレベルを少しの$r$で改善できると仮定する。
この場合、$\hat{\theta}$ of $\theta$を学習して、$\theta \leq \hat{\theta} \leq \theta + r$ とすると、実際にエラーゼロを達成することができる。
(a)正に分類されたエージェントは、真に資格があり、
b) 真に資格を有する代理人は,努力することにより,肯定的に分類することができる。
したがって、エージェントが改善できる能力は、標準モデル、すなわちゼロエラーで達成できない目標を達成する可能性を持っている。
本稿では、この現象をより広範囲に探求し、一般的な結果を与え、エージェントが改善できる能力が、学習のサンプルの複雑さを減らし、学習を困難にすることができるかを調べる。
また、興味のある場合に限られた範囲で改善できるエージェントを考慮に入れ、理論的にも実証的にも検討する。
関連論文リスト
- On the ERM Principle in Meta-Learning [35.32637037177801]
1タスクあたりのサンプル数が少ないことは、学習を成功させるのに十分であることを示す。
また、各$varepsilon$に対して、$varepsilon$のエラーを達成するためにタスク毎の例がいくつ必要かを特定します。
この設定は、コンテキスト内学習、ハイパーネットワーク、学習から学習への学習など、現代の多くの問題に適用できる。
論文 参考訳（メタデータ） (2024-11-26T21:27:14Z) - Impact of Decentralized Learning on Player Utilities in Stackelberg Games [57.08270857260131]
多くの2エージェントシステムでは、各エージェントは別々に学習し、2つのエージェントの報酬は完全に一致しない。
分散学習を用いたStackelbergゲームとしてこれらのシステムをモデル化し、標準後悔ベンチマークが少なくとも1人のプレイヤーにとって最悪の線形後悔をもたらすことを示す。
我々は,これらのベンチマークに関して,両プレイヤーにとってほぼ最適な$O(T2/3)を後悔するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-02-29T23:38:28Z) - Learning Thresholds with Latent Values and Censored Feedback [18.129896050051432]
未知の報酬$g(gamma, v)$が提案されたしきい値$gamma$と潜伏値$v$に依存する問題を示し、そのしきい値が未知の潜伏値よりも低い場合のみ$$を達成できる。
この問題は、オンラインオークションにおける予約価格の最適化、クラウドソーシングにおけるオンラインタスクの割り当て、雇用におけるリクルートバーの設定など、現実的なシナリオにおける幅広い応用がある。
論文 参考訳（メタデータ） (2023-12-07T19:30:08Z) - Policy Mirror Ascent for Efficient and Independent Learning in Mean
Field Games [35.86199604587823]
平均場ゲームは対称および匿名の$N$-playerゲームに対して近似的なナッシュ均衡を得るための理論的ツールとして使われてきた。
ポリシーミラーを実行する$N$エージェントは、$widetildemathcalO(varepsilon-2)$サンプル内で正規化ゲームのナッシュ平衡に収束することを示す。
論文 参考訳（メタデータ） (2022-12-29T20:25:18Z) - On Optimal Learning Under Targeted Data Poisoning [48.907813854832206]
本研究は,学習者によって達成可能な最小のエラー$epsilon=epsilon(eta)$を,そのような敵の存在下で特徴付けることを目的とする。
注目すべきは,上界が決定論的学習者によって達成できることである。
論文 参考訳（メタデータ） (2022-10-06T06:49:48Z) - 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) - There is no Accuracy-Interpretability Tradeoff in Reinforcement Learning
for Mazes [64.05903267230467]
相互理解性は,強化学習システムにおける信頼性に不可欠なビルディングブロックである。
場合によっては、最適性を保ちつつ、政策の解釈可能性を達成することができることを示す。
論文 参考訳（メタデータ） (2022-06-09T04:23:26Z) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-01T14:10:38Z) - Agnostic learning with unknown utilities [70.14742836006042]
現実世界の多くの問題において、決定の効用は基礎となる文脈である$x$ と decision $y$ に依存する。
我々はこれを未知のユーティリティによる不可知学習として研究する。
サンプルされた点のみのユーティリティを推定することで、よく一般化した決定関数を学習できることを示す。
論文 参考訳（メタデータ） (2021-04-17T08:22:04Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。