論文の概要: A Trichotomy for Transductive Online Learning
- arxiv url: http://arxiv.org/abs/2311.06428v1
- Date: Fri, 10 Nov 2023 23:27:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-14 18:31:57.447590
- Title: A Trichotomy for Transductive Online Learning
- Title（参考訳）: トランスダクティブオンライン学習のためのトリコトミー
- Authors: Steve Hanneke, Shay Moran, Jonathan Shafer
- Abstract要約: 我々は,Ben-David, Kushilevitz, Mansour (1997) のオンライン学習環境における学習者の誤り数に関する,新たな上限と下限を提示する。
この設定は標準的なオンライン学習と似ているが、敵はゲームの開始時にラベル付けされる一連のインスタンスを修正し、このシーケンスは学習者に知られている。
- 参考スコア（独自算出の注目度）: 32.03948071550447
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present new upper and lower bounds on the number of learner mistakes in
the `transductive' online learning setting of Ben-David, Kushilevitz and
Mansour (1997). This setting is similar to standard online learning, except
that the adversary fixes a sequence of instances $x_1,\dots,x_n$ to be labeled
at the start of the game, and this sequence is known to the learner.
Qualitatively, we prove a trichotomy, stating that the minimal number of
mistakes made by the learner as $n$ grows can take only one of precisely three
possible values: $n$, $\Theta\left(\log (n)\right)$, or $\Theta(1)$.
Furthermore, this behavior is determined by a combination of the VC dimension
and the Littlestone dimension. Quantitatively, we show a variety of bounds
relating the number of mistakes to well-known combinatorial dimensions. In
particular, we improve the known lower bound on the constant in the $\Theta(1)$
case from $\Omega\left(\sqrt{\log(d)}\right)$ to $\Omega(\log(d))$ where $d$ is
the Littlestone dimension. Finally, we extend our results to cover multiclass
classification and the agnostic setting.
- Abstract（参考訳）: 本稿は,Ben-David, Kushilevitz, Mansour (1997) のオンライン学習環境における学習者の誤り数に関する,新たな上限と下限を提示する。
この設定は標準的なオンライン学習と似ているが、敵はゲームの開始時にラベル付けされるインスタンスのシーケンスを$x_1,\dots,x_n$で修正し、このシーケンスは学習者に知られている。
定性的に、我々は三分法を証明し、学習者が$n$の増大で犯す誤りの最小数は、正確に3つの可能な値のうち、$n$、$\theta\left(\log (n)\right)$、$\theta(1)$のいずれかしか受け取らないことを述べる。
さらに、この挙動はVC次元とリトルストーン次元の組み合わせによって決定される。
定量的に、よく知られた組合せ次元に対する誤りの数に関連する様々な境界を示す。
特に、$\theta(1)$ の定数の既知の下限を$\omega\left(\sqrt{\log(d)}\right)$ から$\omega(\log(d))$ に改善し、ここで$d$ はリトルストーン次元である。
最後に、結果を多クラス分類と不可知設定に拡張する。
関連論文リスト
- Online Learning of Halfspaces with Massart Noise [47.71073318490341]
我々はMassartノイズの存在下でのオンライン学習の課題について検討する。
計算効率のよいアルゴリズムで, 誤り境界が$eta T + o(T)$であることを示す。
我々はMassartオンライン学習者を用いて、任意のラウンドでランダムなアクションを選択するよりも、少なくとも$(1-1/k) Delta T - o(T)$の報酬を得られる効率的なバンディットアルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-05-21T17:31:10Z) - On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective [8.104151304193216]
我々は、差分的プライベート(DP)オンライン学習アルゴリズムに対して、より低いバウンダリを提供する。
我々の研究は、DP-オンライン学習の下位境界の設定に向けた最初の成果である。
論文 参考訳（メタデータ） (2024-02-26T17:49:37Z) - Apple Tasting: Combinatorial Dimensions and Minimax Rates [16.52706654413988]
エンファップル味覚フィードバックに基づくオンライン二項分類では、学習者は1を予測した場合のみ真のラベルを観察する。
実現可能な設定では、期待されるミスの回数が$Theta$または$Theta(T)$であることを示す。
論文 参考訳（メタデータ） (2023-10-29T16:37:51Z) - Simple online learning with consistent oracle [55.43220407902113]
オンライン学習は、学習アルゴリズムが、どの時点でも、今まで見てきたすべての例に一致する関数をクラスから与えることができる、という、一貫性のあるオラクルを通じてのみクラスにアクセスすることができるモデルであると考えている。
論文 参考訳（メタデータ） (2023-08-15T21:50:40Z) - Self-Directed Linear Classification [50.659479930171585]
オンライン分類では、学習者は、誤りの総数を最小限に抑えるために、オンラインでラベルを予測することを目的としている。
そこで本研究では,予測順序の選択能力について検討し,最低次学習とランダム次学習の分離を初めて確立する。
論文 参考訳（メタデータ） (2023-08-06T15:38:44Z) - On Optimal Learning Under Targeted Data Poisoning [48.907813854832206]
本研究は,学習者によって達成可能な最小のエラー$epsilon=epsilon(eta)$を,そのような敵の存在下で特徴付けることを目的とする。
注目すべきは,上界が決定論的学習者によって達成できることである。
論文 参考訳（メタデータ） (2022-10-06T06:49:48Z) - Fast Rates for Nonparametric Online Learning: From Realizability to
Learning in Games [36.969021834291745]
本稿では,仮説クラスの逐次的脂肪散乱次元の観点から,ほぼ最適誤差を導出する固有学習アルゴリズムを提案する。
この結果は、適切な学習者が準最適誤り境界を達成できるかどうかという疑問に答える。
実数値(回帰)設定では、最適誤り境界は不適切な学習者にさえ知られていなかった。
論文 参考訳（メタデータ） (2021-11-17T05:24:21Z) - Littlestone Classes are Privately Online Learnable [28.04975353867202]
プライバシー制約下でのオンライン分類の問題点を考察する。
この設定では、学習者はラベル付き例のストリームを$(x_t, y_t)$, for $1 leq t leq T$で順次観察し、各イテレーションで新しい例のラベルを予測するために使用される仮説$h_t$を返す。
学習者のパフォーマンスは、既知の仮説クラスである$mathcalH$に対する後悔によって測定される。
論文 参考訳（メタデータ） (2021-06-25T09:08:33Z) - Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。
線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。
線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文 参考訳（メタデータ） (2021-01-29T18:57:52Z) - $Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文 参考訳（メタデータ） (2020-06-16T13:01:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。