論文の概要: On the Minimax Regret of Sequential Probability Assignment via Square-Root Entropy

• arxiv url: http://arxiv.org/abs/2503.17823v1
• Date: Sat, 22 Mar 2025 17:26:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-25 14:37:42.874342
• Title: On the Minimax Regret of Sequential Probability Assignment via Square-Root Entropy
• Title（参考訳）: 平方根エントロピーによる逐次確率割り当てのミニマックスレギュレーションについて
• Authors: Zeyu Jia, Yury Polyanskiy, Alexander Rakhlin,
• Abstract要約: 側情報がない場合のミニマックス後悔は、逐次二乗根エントロピーの観点から上界化可能であることを示す。 側情報を用いた逐次確率割当問題では,上記のエントロピーに基づいて上界と下界の両方を発達させる。
• 参考スコア（独自算出の注目度）: 70.10668953625247
• License:
• Abstract: We study the problem of sequential probability assignment under logarithmic loss, both with and without side information. Our objective is to analyze the minimax regret -- a notion extensively studied in the literature -- in terms of geometric quantities, such as covering numbers and scale-sensitive dimensions. We show that the minimax regret for the case of no side information (equivalently, the Shtarkov sum) can be upper bounded in terms of sequential square-root entropy, a notion closely related to Hellinger distance. For the problem of sequential probability assignment with side information, we develop both upper and lower bounds based on the aforementioned entropy. The lower bound matches the upper bound, up to log factors, for classes in the Donsker regime (according to our definition of entropy).
• Abstract（参考訳）: 対数的損失の下での逐次確率割当の問題について,副次的情報と非論理的情報の両方を用いて検討する。 我々の目的は、数やスケールに敏感な次元などの幾何学的量の観点から、ミニマックスの後悔(文献で広く研究されている概念)を分析することである。 副次的情報がない場合(シュタルコフ和と同値)のミニマックス後悔は、シーケンシャルな平方根エントロピー(英語版)(Hellinger distance)の観点で上界化できることが示される。 側情報を用いた逐次確率割当問題では,上記のエントロピーに基づいて上界と下界の両方を発達させる。 下界は、(エントロピーの定義による)ドンスカー系におけるクラスに対して、対数因子までの上限と一致する。

関連論文リスト

• Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihood [28.94461817548213]
  多元的文脈木への射影後のシュタルコフ和に対応する新しい複雑性測度であるエンフコンテクスチュアルシュタルコフ和を導入する。 emph Normalized Maximum Likelihood (cNML) と呼ばれるミニマックス最適戦略を導出する。 私たちの結果は、バイナリラベルを超えて、シーケンシャルな専門家に当てはまります。
  論文  参考訳（メタデータ） (2024-10-04T18:31:12Z)
• Dimension reduction and the gradient flow of relative entropy [0.0]
  次元減少は科学で広く用いられ、高次元データを低次元空間にマッピングする。 本研究では,近傍埋め込み(SNE)技術の基礎となる基本的な数学的モデルと,その一般的な変種であるt-SNEについて検討する。 目的は、これらの点を最適な方法で低次元にマッピングし、類似点がより近いようにすることである。
  論文  参考訳（メタデータ） (2024-09-25T14:23:04Z)
• Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
  本稿では, 難易度の高い環境下での強化学習(RL)の基本的限界について検討する。 Emphmulti-steping POMDPs に対して、潜伏状態空間依存はサンプル複雑性において少なくとも$Omega(S1.5)$であることを示す。
  論文  参考訳（メタデータ） (2023-02-02T18:59:30Z)
• Expected Worst Case Regret via Stochastic Sequential Covering [14.834625066344582]
  我々は、既知のミニマックス後悔を一般化し包含する、予想される最悪のミニマックス後悔の概念を導入する。 そのようなミニマックスの後悔に対して、我々は上大域シーケンシャル被覆という新しい概念を通じて厳密な境界を確立する。 対数損失と一般に混合可能な損失に対する最小限の後悔に対する厳密な境界を確立することで,本手法の有効性を実証する。
  論文  参考訳（メタデータ） (2022-09-09T17:31:46Z)
• A Dimensionality Reduction Method for Finding Least Favorable Priors with a Focus on Bregman Divergence [108.28566246421742]
  そこで本研究では,次元に明示的な有界な有限次元設定に最適化を移動させることができる次元削減法を開発した。 この問題を進展させるため、比較的大きな損失関数、すなわちブレグマンの発散によって引き起こされるベイズ的リスクに限定する。
  論文  参考訳（メタデータ） (2022-02-23T16:22:28Z)
• Tight Exponential Analysis for Smoothing the Max-Relative Entropy and for Quantum Privacy Amplification [56.61325554836984]
  最大相対エントロピーとその滑らかなバージョンは、量子情報理論の基本的な道具である。 我々は、精製された距離に基づいて最大相対エントロピーを滑らかにする量子状態の小さな変化の崩壊の正確な指数を導出する。
  論文  参考訳（メタデータ） (2021-11-01T16:35:41Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)
• 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)

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

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