論文の概要: Efficient and Optimal Fixed-Time Regret with Two Experts
- arxiv url: http://arxiv.org/abs/2203.07577v1
- Date: Tue, 15 Mar 2022 01:07:09 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-16 15:05:31.651148
- Title: Efficient and Optimal Fixed-Time Regret with Two Experts
- Title(参考訳): 2人の専門家による効率的かつ最適固定時間後悔
- Authors: Laura Greenstreet, Nicholas J. A. Harvey, Victor Sanches Portella
- Abstract要約: 専門家のアドバイスによる予測は、オンライン学習における基礎的な問題である。
T$のラウンドと$n$のエキスパートを持つ場合、古典的な乗法的重み更新法は、$T$が事前に知られているときに、少なくとも$sqrt(T/2)ln n$の後悔を被る。
専門家が$n$の数が小さい/固定された場合、より後悔する保証のあるアルゴリズムが存在する。
- 参考スコア(独自算出の注目度): 5.650647159993238
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Prediction with expert advice is a foundational problem in online learning.
In instances with $T$ rounds and $n$ experts, the classical Multiplicative
Weights Update method suffers at most $\sqrt{(T/2)\ln n}$ regret when $T$ is
known beforehand. Moreover, this is asymptotically optimal when both $T$ and
$n$ grow to infinity. However, when the number of experts $n$ is small/fixed,
algorithms with better regret guarantees exist. Cover showed in 1967 a dynamic
programming algorithm for the two-experts problem restricted to $\{0,1\}$ costs
that suffers at most $\sqrt{T/2\pi} + O(1)$ regret with $O(T^2)$ pre-processing
time. In this work, we propose an optimal algorithm for prediction with two
experts' advice that works even for costs in $[0,1]$ and with $O(1)$ processing
time per turn. Our algorithm builds up on recent work on the experts problem
based on techniques and tools from stochastic calculus.
- Abstract(参考訳): 専門家のアドバイスによる予測は、オンライン学習における基礎的な問題である。
t$ ラウンドと n$ エキスパートのインスタンスでは、classic multiplicative weights update メソッドは、事前に $t$ が知られている場合、最大$\sqrt{(t/2)\ln n}$ で苦しむ。
さらに、これは、$t$ と $n$ の両方が無限大に成長するときに漸近的に最適である。
しかし、n$が小さい/固定されている場合、より後悔する保証のあるアルゴリズムが存在する。
カバーは1967年に、2つの専門家問題に対する動的プログラミングアルゴリズムを、最大$\sqrt{t/2\pi} + o(1)$プリプロセス時間で後悔する$\{0,1\}$コストに制限した。
本研究では,[0,1]$ のコストと 1 ターンあたり $o(1)$ の処理時間という2つの専門家のアドバイスによる予測の最適アルゴリズムを提案する。
提案アルゴリズムは,確率計算の手法とツールに基づく専門家問題の最近の研究に基づいている。
関連論文リスト
- Streaming Algorithms for Learning with Experts: Deterministic Versus
Robust [62.98860182111096]
エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。
目標は最小限のコストで予測を行うことだ。
最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
論文 参考訳(メタデータ) (2023-03-03T04:39:53Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳(メタデータ) (2022-12-03T02:45:23Z) - 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) - Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。
当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
論文 参考訳(メタデータ) (2021-09-29T14:07:21Z) - 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) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳(メタデータ) (2020-03-04T07:36:38Z) - Optimal anytime regret with two experts [11.959180302329358]
我々は、いつでも後悔を最小限に抑えるために、最初のミニマックス最適アルゴリズムを設計する。
このアルゴリズムは、計算のアイデアを用いて解決した後悔問題の連続的な類似を考慮し、設計する。
論文 参考訳(メタデータ) (2020-02-20T20:04:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。