論文の概要: Simple online learning with consistent oracle

• arxiv url: http://arxiv.org/abs/2308.08055v2
• Date: Tue, 6 Feb 2024 20:04:38 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-08 20:12:51.926655
• Title: Simple online learning with consistent oracle
• Title（参考訳）: 一貫性のあるoracleによるシンプルなオンライン学習
• Authors: Alexander Kozachinskiy, Tomasz Steifer
• Abstract要約: オンライン学習は、学習アルゴリズムが、どの時点でも、今まで見てきたすべての例に一致する関数をクラスから与えることができる、という、一貫性のあるオラクルを通じてのみクラスにアクセスすることができるモデルであると考えている。
• 参考スコア（独自算出の注目度）: 55.43220407902113
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider online learning in the model where a learning algorithm can access the class only via the \emph{consistent oracle} -- an oracle, that, at any moment, can give a function from the class that agrees with all examples seen so far. This model was recently considered by Assos et al.~(COLT'23). It is motivated by the fact that standard methods of online learning rely on computing the Littlestone dimension of subclasses, a computationally intractable problem. Assos et al.~gave an online learning algorithm in this model that makes at most $C^d$ mistakes on classes of Littlestone dimension $d$, for some absolute unspecified constant $C > 0$. We give a novel algorithm that makes at most $O(256^d)$ mistakes. Our proof is significantly simpler and uses only very basic properties of the Littlestone dimension. We also show that there exists no algorithm in this model that makes less than $3^d$ mistakes.
• Abstract（参考訳）: オンライン学習は,学習アルゴリズムがクラスにのみアクセス可能なモデルであり,そのモデルでは,任意の時点で,これまで見てきたすべての例に一致する関数をクラスから与えることができる,という,‘emph{consistent oracle}’(オラクル)を経由する。 このモデルはAssosらによって最近検討された。 ~(colt'23)であった。 オンライン学習の標準的な方法は、計算的に難解な問題であるサブクラスのリトルストーン次元の計算に依存しているという事実に動機づけられている。 アソスとアル。 このモデルのオンライン学習アルゴリズムは、Littlestone 次元のクラスで少なくとも$C^d$ のミスを犯し、絶対的でない定数 $C > 0$ に対して$d$ の間違いを犯す。 我々は少なくとも$O(256^d)$ミスを犯す新しいアルゴリズムを与える。 この証明は非常に単純であり、リトルストーン次元の非常に基本的な性質のみを用いる。 また、このモデルには3^d$の誤りを犯すアルゴリズムが存在しないことも示している。

関連論文リスト

• Decoupling Learning and Decision-Making: Breaking the $\mathcal{O}(\sqrt{T})$ Barrier in Online Resource Allocation with First-Order Methods [7.518108920887426]
  意思決定から学習を分離する新しいアルゴリズムフレームワークを導入する。 初めて、この新しいフレームワークで、一階述語メソッドが、$mathcalO(sqrtT)$を後悔できることを示す。
  論文  参考訳（メタデータ） (2024-02-11T05:35:50Z)
• A Trichotomy for Transductive Online Learning [32.03948071550447]
  我々は,Ben-David, Kushilevitz, Mansour (1997) のオンライン学習環境における学習者の誤り数に関する,新たな上限と下限を提示する。 この設定は標準的なオンライン学習と似ているが、敵はゲームの開始時にラベル付けされる一連のインスタンスを修正し、このシーケンスは学習者に知られている。
  論文  参考訳（メタデータ） (2023-11-10T23:27:23Z)
• Tight Time-Space Lower Bounds for Constant-Pass Learning [1.7387739961208148]
  サンプルストリームを$q$で通過するパリティ学習アルゴリズムに対して,メモリサンプルの少ないバウンダリを厳密に証明する。 このような学習者には、メモリサイズが$Omega(n2)$か、少なくとも$Omega(n)$サンプルが必要である。 これまでの研究と同様に、この結果は、ほぼ直交的な概念を多く含んだ学習問題にまで及んでいる。
  論文  参考訳（メタデータ） (2023-10-12T06:36:31Z)
• Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries [29.598518028635716]
  オンライン学習の最悪のケース分析を超越した,オラクル効率のアルゴリズムについて検討する。 このスムーズな分析設定のために,本研究は,スムーズな相手を持つオンライン学習のための最初のオラクル効率のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-02-17T09:49:40Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• 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)
• Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
  本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。 我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-06-09T05:39:05Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints [94.76881135901753]
  一般的な限定的適応モデルとして,バッチ学習モデルとレアポリシースイッチモデルがある。 提案したLSVI-UCB-Batchアルゴリズムは,$tilde O(sqrtd3H3T + dHT/B)$ regretを実現する。 まれなポリシスイッチモデルでは,提案されたLSVI-UCB-RareSwitchアルゴリズムは,$tilde O(sqrtd3H3T[1+T/(dH)]dH/B)$の後悔を享受する。
  論文  参考訳（メタデータ） (2021-01-06T18:56:07Z)
• Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learning [66.05472746340142]
  本稿では,SGD による階層的学習 _efficiently_ と _automatically_ を学習目標として,多層ニューラルネットワークがどのように行うかを分析する。 我々は、下位機能のエラーを上位層と共にトレーニングする際に自動的に修正できる"後方特徴補正"と呼ばれる新しい原則を確立する。
  論文  参考訳（メタデータ） (2020-01-13T17:28:29Z)

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

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