論文の概要: Statistically Efficient, Polynomial Time Algorithms for Combinatorial
Semi Bandits
- arxiv url: http://arxiv.org/abs/2002.07258v2
- Date: Wed, 13 Jan 2021 17:12:58 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-31 12:35:02.195360
- Title: Statistically Efficient, Polynomial Time Algorithms for Combinatorial
Semi Bandits
- Title（参考訳）: 組合せ半帯域に対する統計的に効率的な多項式時間アルゴリズム
- Authors: Thibaut Cuvelier and Richard Combes and Eric Gourdin
- Abstract要約: アームの集合である$cal X の部分集合 0,1d$ 上の半帯域を考える。
この問題に対して、ESCB アルゴリズムは最小の既約値 $R(T) = cal OBig(d (ln m)2 (ln T) over Delta_min Big)$ を生成するが、計算複雑性 $cal O(|cal X|)$ を持つ。
- 参考スコア（独自算出の注目度）: 3.9919781077062497
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider combinatorial semi-bandits over a set of arms ${\cal X} \subset
\{0,1\}^d$ where rewards are uncorrelated across items. For this problem, the
algorithm ESCB yields the smallest known regret bound $R(T) = {\cal O}\Big( {d
(\ln m)^2 (\ln T) \over \Delta_{\min} }\Big)$, but it has computational
complexity ${\cal O}(|{\cal X}|)$ which is typically exponential in $d$, and
cannot be used in large dimensions. We propose the first algorithm which is
both computationally and statistically efficient for this problem with regret
$R(T) = {\cal O} \Big({d (\ln m)^2 (\ln T)\over \Delta_{\min} }\Big)$ and
computational complexity ${\cal O}(T {\bf poly}(d))$. Our approach involves
carefully designing an approximate version of ESCB with the same regret
guarantees, showing that this approximate algorithm can be implemented in time
${\cal O}(T {\bf poly}(d))$ by repeatedly maximizing a linear function over
${\cal X}$ subject to a linear budget constraint, and showing how to solve this
maximization problems efficiently.
- Abstract（参考訳）: 我々は、集合のアーム上の組合せ半バンドを考える。${\cal x} \subset \{0,1\}^d$ ここで、報酬はアイテム間で無関係である。
この問題に対して、アルゴリズム escb は最小の後悔の束縛 $r(t) = {\cal o}\big( {d (\ln m)^2 (\ln t) \over \delta_{\min} }\big)$ を与えるが、計算複雑性 ${\cal o}(|{\cal x}|)$ は典型的には $d$ で指数関数的であり、大次元では使用できない。
本稿では,r(t) = {\cal o} \big({d (\ln m)^2 (\ln t)\over \delta_{\min} }\big)$ と計算複雑性 ${\cal o}(t {\bf poly}(d))$ を用いて,この問題に対して計算量的かつ統計的に効率的な最初のアルゴリズムを提案する。
我々のアプローチは、同じ後悔の保証を持つescbの近似バージョンを慎重に設計することを含み、この近似アルゴリズムは、線形予算制約の対象である${\cal x}$上の線型関数を繰り返し最大化することで、時間${\cal o}(t {\bf poly}(d))$で実装できることを示し、この最大化問題を効率的に解く方法を示す。
関連論文リスト
- Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models [39.33814194788341]
潜在変数モデル学習の課題について検討する。
このような応用により、暗黙のモーメント計算のための一般化されたアルゴリズムを開発した。
一般的なアルゴリズムを利用して, 以下のモデルに対する初等学習者を得る。
論文 参考訳（メタデータ） (2024-11-23T23:13:24Z) - Dueling Optimization with a Monotone Adversary [35.850072415395395]
凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。
目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
論文 参考訳（メタデータ） (2023-11-18T23:55:59Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Memory-Constrained Algorithms for Convex Optimization via Recursive
Cutting-Planes [23.94542304111204]
勾配降下法と切断平面法の間に正のトレードオフを与えるアルゴリズムの第一級は、$epsilonleq 1/sqrt d$である。
規則$epsilon leq d-Omega(d)$では、$p=d$のアルゴリズムが情報理論の最適メモリ利用を実現し、勾配降下のオラクル-複雑度を改善する。
論文 参考訳（メタデータ） (2023-06-16T17:00:51Z) - An Optimal Algorithm for Strongly Convex Min-min Optimization [79.11017157526815]
既存の最適な一階法には$mathcalO(sqrtmaxkappa_x,kappa_y log 1/epsilon)$nabla_x f(x,y)$と$nabla_y f(x,y)$の両方の計算が必要である。
我々は$mathcalO(sqrtkappa_x log 1/epsilon)$nabla_x f(x,
論文 参考訳（メタデータ） (2022-12-29T19:26:12Z) - Computational Complexity of Normalizing Constants for the Product of
Determinantal Point Processes [12.640283469603357]
正規化定数の計算における計算複雑性について検討する。
例えば、$sum_Sdet(bf A_S,S)p$は、すべての(固定された)正の偶数に対して、$p$ が UP-hard で Mod$_3$P-hard であることを示す。
論文 参考訳（メタデータ） (2021-11-28T14:08:25Z) - Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。
我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-09T05:39:05Z) - An Efficient Pessimistic-Optimistic Algorithm for Constrained Linear
Bandits [16.103685478563072]
本稿では,一般制約付き線形帯域について考察する。
目的は、各ラウンドにおける一連の制約の対象となる水平線上の累積報酬を最大化することである。
本稿では,この問題に対する悲観的最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-10T07:30:37Z) - 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) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。