論文の概要: Logarithmic Regret from Sublinear Hints

• arxiv url: http://arxiv.org/abs/2111.05257v1
• Date: Tue, 9 Nov 2021 16:50:18 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-10 15:11:19.373178
• Title: Logarithmic Regret from Sublinear Hints
• Title（参考訳）: 部分線形ヒントからの対数的後悔
• Authors: Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, Manish Purohit
• Abstract要約: 自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
• 参考スコア（独自算出の注目度）: 76.87432703516942
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the online linear optimization problem, where at every step the algorithm plays a point $x_t$ in the unit ball, and suffers loss $\langle c_t, x_t\rangle$ for some cost vector $c_t$ that is then revealed to the algorithm. Recent work showed that if an algorithm receives a hint $h_t$ that has non-trivial correlation with $c_t$ before it plays $x_t$, then it can achieve a regret guarantee of $O(\log T)$, improving on the bound of $\Theta(\sqrt{T})$ in the standard setting. In this work, we study the question of whether an algorithm really requires a hint at every time step. Somewhat surprisingly, we show that an algorithm can obtain $O(\log T)$ regret with just $O(\sqrt{T})$ hints under a natural query model; in contrast, we also show that $o(\sqrt{T})$ hints cannot guarantee better than $\Omega(\sqrt{T})$ regret. We give two applications of our result, to the well-studied setting of optimistic regret bounds and to the problem of online learning with abstention.
• Abstract（参考訳）: オンライン線形最適化の問題を考えると、各ステップでアルゴリズムが単位球の点$x_t$を演算し、損失$\langle c_t, x_t\rangle$を犠牲ベクトル$c_t$で処理し、アルゴリズムに露呈する。 最近の研究によると、アルゴリズムが$x_t$を再生する前に$c_t$と非自明な相関を持つヒント$h_t$を受け取ると、標準設定での$\Theta(\sqrt{T})$のバウンドを改善して、$O(\log T)$の後悔の保証を達成できる。 本研究では,アルゴリズムが時間ステップ毎にヒントを必要とするかどうかについて検討する。 やや意外なことに、アルゴリズムは自然問合せモデルの下で$o(\sqrt{t})$ hints だけで$o(\sqrt{t})$ regret を得られることを示し、それに対して$o(\sqrt{t})$ hints は$\omega(\sqrt{t})$ regret よりも良い保証はできないことを示した。 我々は,この結果の2つの応用を,楽観的な後悔境界の設定と,断固としたオンライン学習の問題に応用する。

関連論文リスト

• Improved Kernel Alignment Regret Bound for Online Kernel Learning [11.201662566974232]
  提案手法は, 既往の結果よりも, 計算量や計算量が多くなるアルゴリズムを提案する。 核行列の固有値が指数関数的に減衰すると、我々のアルゴリズムは$O(sqrtmathcalA_T)$の後悔を、$O(ln2T)$の計算複雑性で楽しむ。 我々はアルゴリズムをバッチ学習に拡張し、以前の$Oを改善した$O(frac1TsqrtmathbbE[mathcalA_T])$over risk boundを得る。
  論文  参考訳（メタデータ） (2022-12-26T02:32:20Z)
• Online Learning with Bounded Recall [11.046741824529107]
  本研究では,繰り返しゲーム研究に人気がある「バウンド・リコール」環境において,オンライン学習の完全情報化の課題について検討する。 オンライン学習アルゴリズム $mathcalA$ が$M$-$textitbounded-recall$ であるとき、$t$ の出力が$M$以前の報酬の関数として記述できる。
  論文  参考訳（メタデータ） (2022-05-28T20:52:52Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
  本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。 我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-06-09T05:39:05Z)
• 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)
• Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications [37.6975819766632]
  我々は、すべてのエキスパート$i$に対して、後悔の$Oleft(sqrt(ln d)sum_t ell_t,i2right)を同時に$T$ラウンド$d$-expert問題で達成できることを示します。 本アルゴリズムは,補正項と重み付きエントロピー正規化器を備えたミラー・ディキストリアル・フレームワークに基づいている。
  論文  参考訳（メタデータ） (2021-02-01T18:34:21Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• $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)
• Adaptive Online Learning with Varying Norms [45.11667443216861]
  オンライン凸最適化アルゴリズムは、あるドメインで$w_t$を出力する。 この結果を用いて新しい「完全行列」型後悔境界を得る。
  論文  参考訳（メタデータ） (2020-02-10T17:22:08Z)

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

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