論文の概要: Lower Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient
- arxiv url: http://arxiv.org/abs/2303.03327v1
- Date: Mon, 6 Mar 2023 17:54:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-07 15:00:08.861676
- Title: Lower Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient
- Title（参考訳）: 決定-推定係数による$\gamma$-Regretの低境界
- Authors: Margalit Glasgow and Alexander Rakhlin
- Abstract要約: $gamma$-regretは、$f$の正確な最適値を求めるような構造化バンドイット問題に現れる。
我々の下限は、citetfoster2023tightの制約付き決定推定係数の修正という観点で与えられる。
この結果が$gamma = 1$の伝統的な後悔設定に制限されると、citetfoster2023tightの下限の対数要素を除去します。
- 参考スコア（独自算出の注目度）: 88.86699022151598
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this note, we give a new lower bound for the $\gamma$-regret in bandit
problems, the regret which arises when comparing against a benchmark that is
$\gamma$ times the optimal solution, i.e., $\mathsf{Reg}_{\gamma}(T) = \sum_{t
= 1}^T \gamma \max_{\pi} f(\pi) - f(\pi_t)$. The $\gamma$-regret arises in
structured bandit problems where finding an exact optimum of $f$ is
intractable. Our lower bound is given in terms of a modification of the
constrained Decision-Estimation Coefficient (DEC) of~\citet{foster2023tight}
(and closely related to the original offset DEC of
\citet{foster2021statistical}), which we term the $\gamma$-DEC. When restricted
to the traditional regret setting where $\gamma = 1$, our result removes the
logarithmic factors in the lower bound of \citet{foster2023tight}.
- Abstract（参考訳）: ここでは、バンディット問題における$\gamma$-regretに対する新しい下界を与えるが、これは、$\gamma$が最適解の$\gamma$倍であるベンチマーク、すなわち$\mathsf{Reg}_{\gamma}(T) = \sum_{t = 1}^T \gamma \max_{\pi} f(\pi) - f(\pi_t)$と比較する際に生じる後悔である。
$\gamma$-regretは、$f$の正確な最適値を求めるような構造化バンドイット問題に現れる。
我々の下限は、制約付き決定推定係数 (DEC) の~\citet{foster2023tight} (および$\gamma$-DEC を言う \citet{foster2021statistical} の元のオフセット DEC と密接に関連している) の修正によって与えられる。
$\gamma = 1$ の伝統的な後悔の設定に制限された場合、この結果は \citet{foster2023tight} の下限の対数要素を除去する。
関連論文リスト
- Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。
具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
論文 参考訳（メタデータ） (2024-08-21T01:39:42Z) - A simple and improved algorithm for noisy, convex, zeroth-order optimisation [59.51990161522328]
我々は、$f(hat x)$ ができるだけ小さいような点 $hat xin barmathcal X$ を返すアルゴリズムを構築している。
この方法は、$f(hat x) - min_xin barmathcal X f(x)$ が、多対数項まで$d2/sqrtn$ より小さい順序であることを証明する。
論文 参考訳（メタデータ） (2024-06-26T18:19:10Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - 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) - Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with
Error Certificates [0.0]
コンパクト部分集合 $mathcal X$ of $mathbb Rd$ 上で定義されるリプシッツ関数 $f$ のゼロ次(ブラックボックス)最適化の問題を研究する。
我々は、任意のリプシッツ関数 $f$ の評価の最適な個数を特徴付け、精度$varepsilon$ で$f$ の近似器を見つけて証明する。
論文 参考訳（メタデータ） (2021-02-03T09:51:03Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。