論文の概要: Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant
- arxiv url: http://arxiv.org/abs/2609.27206v1
- Date: Wed, 23 Sep 2026 01:13:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-25 00:05:17.81654
- Title: Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant
- Title（参考訳）: エキスパートアドバイザによる予測:多くのエキスパートによる任意のレグレットが固定時間定数に一致する
- Abstract要約: 時間軸の$T$が事前に知られている場合、$n$の専門家に対する最小の累積後悔は$sqrtfracT ln n2$である。
これはMultiplicative Weights Updateアルゴリズムによって実現され、学習レートは$T$に調整され、厳密であることが知られている。
各$t ge 1 に対して、累積的後悔が $R_t le bigl(sqrtln ln n / 2$) を同時に満たすような地平線についての知識を必要としないアルゴリズムを与える。
- 参考スコア（独自算出の注目度）: 20.721552392409013
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Prediction with expert advice is a fundamental problem in online learning. When the time horizon $T$ is known in advance, the minimax cumulative regret over $n$ experts is asymptotically $\sqrt{\frac{T \ln n}{2}}$. This is achieved by the Multiplicative Weights Update algorithm with a learning rate tuned to $T$, and is known to be tight. If instead the regret bound is required to hold simultaneously at every time $t$, the best known guarantee has been $\sqrt{t \ln n}$---a factor of $\sqrt{2}$ worse---and it has remained unknown whether this factor of $\sqrt{2}$ is necessary. We show that it is not. We give an algorithm, requiring no knowledge of the horizon, whose cumulative regret satisfies $R_t \le \bigl(1 + O(\sqrt{\ln \ln n / \ln n})\bigr)\sqrt{t \ln n / 2}$ simultaneously for every $t \ge 1$.
- Abstract（参考訳）: 専門家のアドバイスによる予測は、オンライン学習における根本的な問題である。
時間軸の$T$が事前に知られているとき、$n$専門家に対する最小の累積後悔は漸近的に$\sqrt{\frac{T \ln n}{2}}$である。
これはMultiplicative Weights Updateアルゴリズムによって実現され、学習レートは$T$に調整され、厳密であることが知られている。
代わりに、後悔のバウンドが$t$のたびに同時に保持されることが要求される場合、最もよく知られた保証は$\sqrt{t \ln n}$------------$\sqrt{2}$ worse---------------------------------この係数が$\sqrt{2}$ であるかどうかは不明のままである。
私たちはそうではないことを示します。
R_t \le \bigl(1 + O(\sqrt{\ln \ln n / \ln n})\bigr)\sqrt{t \ln n / 2}$をすべての$t \ge 1$に対して同時に満足する。
関連論文リスト
- Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。
失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
論文 参考訳（メタデータ） (2026-07-22T07:42:19Z) - Better Bounds for the Distributed Experts Problem [69.88181841362488]
我々は分散専門家の問題を調査し、$n$の専門家が$s$サーバに分散して$T$タイムステップを提供する。
約$Rgtrsimfrac1sqrtTcdottextpolylog(nsT)$, using $mathcalOleft(fracnR2+fracsR2right)cdotmax(s1-2/p, 1)cdottextpolylog(nsT)$
論文 参考訳（メタデータ） (2026-03-10T04:17:34Z) - High-Dimensional Calibration from Swap Regret [40.9736612423411]
任意の凸集合 $mathcalP 部分集合 mathbbRd$ 上での多次元予測のオンライン校正について検討する。
我々は、$O(sqrtrho T)$$$T$ラウンド後の最悪の後悔を保証できるならば、$T = exp(logd/epsilon2) の後、$epsilon$-calibrated 予測を得ることができることを示した。
論文 参考訳（メタデータ） (2025-05-27T17:31:47Z) - On the Minimax Regret for Online Learning with Feedback Graphs [5.721380617450645]
強く観察可能な無向フィードバックグラフを用いて,オンライン学習を後悔する上で,上層と下層の境界を改善した。
改良された上界$mathcalObigl(sqrtalpha T(ln K)/(lnalpha)bigr)$ hold for any $alpha$ and the lower bounds for bandits and experts。
論文 参考訳（メタデータ） (2023-05-24T17:40:57Z) - Efficient and Optimal Fixed-Time Regret with Two Experts [5.650647159993238]
専門家のアドバイスによる予測は、オンライン学習における基礎的な問題である。
T$のラウンドと$n$のエキスパートを持つ場合、古典的な乗法的重み更新法は、$T$が事前に知られているときに、少なくとも$sqrt(T/2)ln n$の後悔を被る。
専門家が$n$の数が小さい/固定された場合、より後悔する保証のあるアルゴリズムが存在する。
論文 参考訳（メタデータ） (2022-03-15T01:07:09Z) - 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) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。