Fugu-MT 論文翻訳(概要): Optimal Randomized Proper Online Learning

論文の概要: Optimal Randomized Proper Online Learning

arxiv url: http://arxiv.org/abs/2609.21445v1
Date: Fri, 18 Sep 2026 07:58:19 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-21 18:40:16.922806
Title: Optimal Randomized Proper Online Learning
Title（参考訳）: ランダム化された最適オンライン学習
Abstract要約: ランダムな固有学習アルゴリズムによるオンライン学習の最適誤差は$O(mathttL(mathcalH) log T)$であることを示す。
参考スコア（独自算出の注目度）: 2.964978357715084
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We prove that the optimal expected mistake bound of online learning a function class $\mathcal{H}$ by a randomized proper learning algorithm is $O(\mathtt{L}(\mathcal{H}) \log T)$, where $\mathtt{L}(\mathcal{H})$ is the Littlestone dimension of $\mathcal{H}$ and $T$ is the time horizon. Our result improves upon the previously best known bound of $O(\mathtt{L}(\mathcal{H}) \log^6 T)$ given by Daskalakis and Golowich (STOC 2022), and is optimal up to a universal constant for worst-case classes.
Abstract（参考訳）: オンライン学習の最適期待誤差は、ランダムな固有学習アルゴリズムによる関数クラス$\mathcal{H}$が$O(\mathtt{L}(\mathcal{H}) \log T)$であり、$\matht{L}(\mathcal{H})$が$\mathcal{H}$のリトルストーン次元であり、$T$が時間軸であることを証明する。我々の結果は、ダスカラキスとゴロービッチ(STOC 2022)が与えた$O(\mathtt{L}(\mathcal{H}) \log^6T)$の既知境界を改善し、最悪の場合のクラスに対する普遍定数まで最適である。

関連論文リスト

Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
$Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
論文参考訳（メタデータ） (2025-02-25T19:08:26Z)
Near-Optimal Algorithms for Omniprediction [6.874077229518565]
オンライン設定とオフライン設定の両方で、オムニプレディションのためのほぼ最適学習アルゴリズムを提供します。オンライン学習アルゴリズムは、様々な尺度でほぼ最適な複雑さを実現する。オフライン学習アルゴリズムは効率的な$(mathcalL_mathrmBV,mathcalH,varepsilon(m)$)を返す
論文参考訳（メタデータ） (2025-01-28T02:58:37Z)
Deterministic Apple Tasting [2.4554686192257424]
我々は、初めて広く適用可能な決定論的リンゴテイスティング学習者を提供する。すべてのクラス $mathcalH$ は簡単、困難、あるいは学習不能でなければならない、という三分法を証明します。我々の上限は、リンゴの味付けフィードバックに関する専門家のアドバイスから学ぶための決定論的アルゴリズムに基づいている。
論文参考訳（メタデータ） (2024-10-14T11:54:46Z)
Revisiting Agnostic PAC Learning [30.67561230812141]
PAC学習は、Valiant'84とVapnik and Chervonenkis'64,'74にさかのぼる、教師あり学習を研究するための古典的なモデルである。経験的リスク最小化(英: Empirical Risk Minimization、ERM)は、訓練データに最も少ない誤りを犯すために$mathcalH$から仮説を出力する自然学習アルゴリズムである。私たちはPAC学習を再考し、最良仮説の性能を$tau:=Pr_mathcalD[hstar_mathと表すと、ERMが実際は準最適であることを示す。
論文参考訳（メタデータ） (2024-07-29T08:20:49Z)
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 Optimal Learning Under Targeted Data Poisoning [48.907813854832206]
本研究は,学習者によって達成可能な最小のエラー$epsilon=epsilon(eta)$を,そのような敵の存在下で特徴付けることを目的とする。注目すべきは,上界が決定論的学習者によって達成できることである。
論文参考訳（メタデータ） (2022-10-06T06:49:48Z)
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)
Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文参考訳（メタデータ） (2021-02-15T08:16:51Z)

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