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

• arxiv url: http://arxiv.org/abs/2308.08055v1
• Date: Tue, 15 Aug 2023 21:50:40 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-17 15:21:53.051959
• Title: Simple online learning with consistency oracle
• Title（参考訳）: oracleによるシンプルなオンライン学習
• Authors: Alexander Kozachinskiy, Tomasz Steifer
• Abstract要約: 学習アルゴリズムがオラクルの一貫性によってのみクラスにアクセスできるモデルにおけるオンライン学習について考察する。 我々は、少なくとも$O(256d)$ミスを犯す新しいアルゴリズムを与える。
• 参考スコア（独自算出の注目度）: 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 consistency 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 problem that is computationally intractable. 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 observe that there exists no algorithm in this model that makes at most $2^{d+1}-2$ mistakes. We also observe that our algorithm (as well as the algorithm of Assos et al.) solves an open problem by Hasrati and Ben-David (ALT'23). Namely, it demonstrates that every class of finite Littlestone dimension with recursively enumerable representation admits a computable online learner (that may be undefined on unrealizable samples).
• Abstract（参考訳）: オンライン学習は、学習アルゴリズムが一貫性の神託(oracle)を通じてのみクラスにアクセスすることができるモデルにおいて検討する。 このモデルはAssosらによって最近検討された(COLT'23)。 これは、オンライン学習の標準的な方法がサブクラスのリトルストーン次元の計算に依存しているという事実に動機づけられている。 assosらはこのモデルでオンライン学習アルゴリズムを提供し、リトルストーン次元のクラスに対して最大$c^d$の誤りを生じさせる。 我々は少なくとも$O(256^d)$ミスを犯す新しいアルゴリズムを与える。 この証明は非常に単純であり、リトルストーン次元の非常に基本的な性質のみを用いる。 また、このモデルには、少なくとも2^{d+1}-2$の誤りを犯すアルゴリズムが存在しないことも観察する。 また、我々のアルゴリズム(Assosらのアルゴリズムと同様に)がHasratiとBen-David(ALT'23)によるオープンな問題を解くことも観察した。 すなわち、再帰的可算表現を持つ有限小石次元のすべてのクラスは、計算可能なオンライン学習者(非実現可能なサンプルでは定義できないかもしれない)を認める。

関連論文リスト

• 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)

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

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