論文の概要: Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient
- arxiv url: http://arxiv.org/abs/2303.03327v2
- Date: Fri, 21 Jul 2023 17:54:14 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-24 16:07:15.700638
- Title: Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient
- Title（参考訳）: 決定推定係数による$\gamma$-regretの厳密な境界
- Authors: Margalit Glasgow and Alexander Rakhlin
- Abstract要約: 任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。
この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
- 参考スコア（独自算出の注目度）: 88.86699022151598
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we give a statistical characterization of the $\gamma$-regret
for arbitrary structured bandit problems, the regret which arises when
comparing against a benchmark that is $\gamma$ times the optimal solution. The
$\gamma$-regret emerges in structured bandit problems over a function class
$\mathcal{F}$ where finding an exact optimum of $f \in \mathcal{F}$ is
intractable. Our characterization is given in terms of the $\gamma$-DEC, a
statistical complexity parameter for the class $\mathcal{F}$, which is a
modification of the constrained Decision-Estimation Coefficient (DEC) of Foster
et al., 2023 (and closely related to the original offset DEC of Foster et al.,
2021). Our lower bound shows that the $\gamma$-DEC is a fundamental limit for
any model class $\mathcal{F}$: for any algorithm, there exists some $f \in
\mathcal{F}$ for which the $\gamma$-regret of that algorithm scales (nearly)
with the $\gamma$-DEC of $\mathcal{F}$. We provide an upper bound showing that
there exists an algorithm attaining a nearly matching $\gamma$-regret. Due to
significant challenges in applying the prior results on the DEC to the
$\gamma$-regret case, both our lower and upper bounds require novel techniques
and a new algorithm.
- Abstract（参考訳）: 本研究では、任意の構造化バンドイット問題に対する$\gamma$-regretの統計的特徴を与えるが、これは、$\gamma$-regretが最適解の$\gamma$のベンチマークと比較した場合に生じる後悔である。
$\gamma$-regret は、関数クラス $\mathcal{F}$ 上の構造化バンディット問題に現れ、$f \in \mathcal{F}$ の正確な最適値を見つけることは難解である。
我々の特徴付けは、foster et al., 2023の制約付き決定推定係数 (dec) の修正である$\mathcal{f}$ の統計複雑性パラメータである $\gamma$-dec の項で与えられる(そして、foster et al., 2021 のオリジナルのオフセット dec と密接に関連している)。
我々の下限は、$\gamma$-DEC が任意のモデルクラス $\mathcal{F}$ の基本極限であることを示している: 任意のアルゴリズムに対して、ある $f \in \mathcal{F}$ が存在し、そのアルゴリズムの $\gamma$-regret は $\mathcal{F}$ の $\gamma$-DEC と(ほぼ)スケールする。
我々は、ほぼ一致する$\gamma$-regretとなるアルゴリズムが存在することを示す上界を提供する。
DECの先行結果を$\gamma$-regretのケースに適用する上で大きな課題があるため、我々の下限と上限はどちらも新しい手法と新しいアルゴリズムを必要とする。
関連論文リスト
- 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) - Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets [27.913569257545554]
2つの一般的な近似仮定(textitadditive と textitmultiplicative gap error)は、我々の問題には有効ではない。
DMO(textitapproximate dual Oracle)が提案され、ギャップではなく内部積を近似する。
実験結果から,これらの改良された境界でさえ悲観的であり,グラフ構造を持つ実世界の画像に顕著な改善が認められたことが示唆された。
論文 参考訳（メタデータ） (2021-06-29T19:39:43Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。