論文の概要: Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihood
- arxiv url: http://arxiv.org/abs/2410.03849v1
- Date: Fri, 4 Oct 2024 18:31:12 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-02 15:50:43.477414
- Title: Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihood
- Title（参考訳）: 文脈付き逐次確率割り当て:Minimax Regret、Contextual Shtarkov Sums、Contextual Normalized Maximum Likelihood
- Authors: Ziyi Liu, Idan Attias, Daniel M. Roy,
- Abstract要約: 多元的文脈木への射影後のシュタルコフ和に対応する新しい複雑性測度であるエンフコンテクスチュアルシュタルコフ和を導入する。
emph Normalized Maximum Likelihood (cNML) と呼ばれるミニマックス最適戦略を導出する。
私たちの結果は、バイナリラベルを超えて、シーケンシャルな専門家に当てはまります。
- 参考スコア（独自算出の注目度）: 28.94461817548213
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the fundamental problem of sequential probability assignment, also known as online learning with logarithmic loss, with respect to an arbitrary, possibly nonparametric hypothesis class. Our goal is to obtain a complexity measure for the hypothesis class that characterizes the minimax regret and to determine a general, minimax optimal algorithm. Notably, the sequential $\ell_{\infty}$ entropy, extensively studied in the literature (Rakhlin and Sridharan, 2015, Bilodeau et al., 2020, Wu et al., 2023), was shown to not characterize minimax risk in general. Inspired by the seminal work of Shtarkov (1987) and Rakhlin, Sridharan, and Tewari (2010), we introduce a novel complexity measure, the \emph{contextual Shtarkov sum}, corresponding to the Shtarkov sum after projection onto a multiary context tree, and show that the worst case log contextual Shtarkov sum equals the minimax regret. Using the contextual Shtarkov sum, we derive the minimax optimal strategy, dubbed \emph{contextual Normalized Maximum Likelihood} (cNML). Our results hold for sequential experts, beyond binary labels, which are settings rarely considered in prior work. To illustrate the utility of this characterization, we provide a short proof of a new regret upper bound in terms of sequential $\ell_{\infty}$ entropy, unifying and sharpening state-of-the-art bounds by Bilodeau et al. (2020) and Wu et al. (2023).
- Abstract（参考訳）: 我々は、任意の、おそらくは非パラメトリックな仮説クラスに関して、逐次確率代入の基本的問題(対数損失を伴うオンライン学習)について研究する。
我々のゴールは、ミニマックスの後悔を特徴づける仮説クラスに対する複雑さの測定と、一般化されたミニマックスの最適アルゴリズムを決定することである。
特に、連続$\ell_{\infty}$エントロピー(Rakhlin and Sridharan, 2015, Bilodeau et al , 2020, Wu et al , 2023)は、一般にミニマックスリスクを特徴づけないことを示した。
シュタルコフ (1987) とラフリン (Rakhlin)、スリダーラン (Sridharan)、テワリ (Tewari) (2010) のセミナルな研究から着想を得て、シュタルコフ和を多元的文脈木に射影した後のシュタルコフ和に対応する新しい複雑性測度 \emph{contextual Shtarkov sum} を導入し、最悪の場合の文脈的シュタルコフ和がミニマックス後悔と等しいことを示す。
文脈シュタルコフ和を用いて、極小極小戦略を導出し、これを 'emph{contextual Normalized Maximum Likelihood} (cNML) と呼ぶ。
私たちの結果は、バイナリラベルを超えて、シーケンシャルな専門家に当てはまります。
この特徴付けの有用性を説明するために、Blodeau et al (2020) と Wu et al (2023) によるシーケンシャル $\ell_{\infty}$ entropy による新しい後悔の上界の短い証明を与える。
関連論文リスト
- High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distributions [17.43748116766233]
クロスラーニング(クロスラーニング)による文脈的包帯の問題について検討し、学習者はあらゆる可能な文脈で行動に関連した損失を観察する。
我々の焦点は、損失が逆向きに選択され、特定の分布からコンテキストがサンプル化されるような設定である。
Schneider と Zimmert (2023) は先頃、ほぼ最適に期待された後悔を実現するアルゴリズムを提案した。
提案手法は,そのアルゴリズムの詳細な解析を行い,ほぼ最適の後悔を高い確率で実現できることを実証する。
論文 参考訳（メタデータ） (2024-10-05T08:19:54Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳（メタデータ） (2023-07-25T15:42:11Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳（メタデータ） (2022-11-03T12:40:24Z) - Expected Worst Case Regret via Stochastic Sequential Covering [14.834625066344582]
我々は、既知のミニマックス後悔を一般化し包含する、予想される最悪のミニマックス後悔の概念を導入する。
そのようなミニマックスの後悔に対して、我々は上大域シーケンシャル被覆という新しい概念を通じて厳密な境界を確立する。
対数損失と一般に混合可能な損失に対する最小限の後悔に対する厳密な境界を確立することで,本手法の有効性を実証する。
論文 参考訳（メタデータ） (2022-09-09T17:31:46Z) - Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm [14.834625066344582]
対数損失下での逐次的オンライン回帰(シーケンシャル確率代入)について検討する。
我々は、専門家のクラスで発生する過剰な損失として定義される連続したミニマックスの後悔に対して、厳密で、しばしば一致し、下限と上限を得ることに重点を置いている。
論文 参考訳（メタデータ） (2022-05-07T22:03:00Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z) - Nearly Dimension-Independent Sparse Linear Bandit over Small Action
Spaces via Best Subset Selection [71.9765117768556]
本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。
この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。
本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
論文 参考訳（メタデータ） (2020-09-04T04:10:39Z) - Tight Bounds on Minimax Regret under Logarithmic Loss via
Self-Concordance [37.0414602993676]
連続)計量エントロピー $mathcalO(gamma-p)$ at scale $gamma$ を持つ任意の専門家クラスに対して、ミニマックス後悔は $mathcalO(np/(p+1))$ であることを示す。
我々の手法の応用として、専門家の非パラメトリックリプシッツ類に対するミニマックス後悔を解消する。
論文 参考訳（メタデータ） (2020-07-02T14:47:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。