論文の概要: Efficient Kernel UCB for Contextual Bandits
- arxiv url: http://arxiv.org/abs/2202.05638v1
- Date: Fri, 11 Feb 2022 14:28:03 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-14 22:56:21.423769
- Title: Efficient Kernel UCB for Contextual Bandits
- Title（参考訳）: コンテキスト帯域に対する効率的なカーネルUCB
- Authors: Houssam Zenati, Alberto Bietti, Eustache Diemert, Julien Mairal,
Matthieu Martin, Pierre Gaillard
- Abstract要約: 大規模問題に対する効率的な文脈的アルゴリズムを提案する。
本手法は,コンテクストとアクションの融合カーネルのインクリメンタルなNystrom近似に依存する。
- 参考スコア（独自算出の注目度）: 43.98627992122642
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we tackle the computational efficiency of kernelized UCB
algorithms in contextual bandits. While standard methods require a O(CT^3)
complexity where T is the horizon and the constant C is related to optimizing
the UCB rule, we propose an efficient contextual algorithm for large-scale
problems. Specifically, our method relies on incremental Nystrom approximations
of the joint kernel embedding of contexts and actions. This allows us to
achieve a complexity of O(CTm^2) where m is the number of Nystrom points. To
recover the same regret as the standard kernelized UCB algorithm, m needs to be
of order of the effective dimension of the problem, which is at most
O(\sqrt(T)) and nearly constant in some cases.
- Abstract（参考訳）: 本稿では,文脈バンディットにおけるカーネル化ucbアルゴリズムの計算効率について検討する。
標準手法では、T が水平線であり、定数 C が UCB 規則の最適化に関連する O(CT^3) の複雑さを必要とするが、大規模問題に対する効率的な文脈アルゴリズムを提案する。
特に, この手法は, 文脈と動作の結合核埋め込みのインクリメンタルなナイストロム近似に依存する。
これにより、m がナイストローム点の数である O(CTm^2) の複雑性を達成することができる。
標準的な核化 UCB アルゴリズムと同じ後悔を取り戻すためには、m は O(\sqrt(T)) であり、場合によってはほぼ一定である問題の有効次元の順序である必要がある。
関連論文リスト
- Optimal Coherent Quantum Phase Estimation via Tapering [0.0]
量子位相推定は、多くの量子アルゴリズムを支える基本的なプリミティブの1つである。
我々は,テープ型量子位相推定アルゴリズムと呼ばれる標準アルゴリズムの改良版を提案する。
提案アルゴリズムは,高コストなコヒーレント中央値手法を必要とせず,最適なクエリ複雑性を実現する。
論文 参考訳（メタデータ） (2024-03-27T18:17:23Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Lifelong Bandit Optimization: No Prior and No Regret [70.94238868711952]
我々は,過去の経験から学習することで環境に適応するアルゴリズムであるLIBOを開発した。
カーネルが未知だが、すべてのタスク間で共有されるカーネル構造を仮定する。
我々のアルゴリズムは、任意のカーネル化または線形バンディットアルゴリズムと組み合わせて、最適な性能を保証できる。
論文 参考訳（メタデータ） (2022-10-27T14:48:49Z) - Large-scale Optimization of Partial AUC in a Range of False Positive
Rates [51.12047280149546]
ROC曲線 (AUC) の下の領域は、機械学習において最も広く使われている分類モデルのパフォーマンス指標の1つである。
近年の封筒平滑化技術に基づく効率的な近似勾配降下法を開発した。
提案アルゴリズムは,効率のよい解法を欠くランク付けされた範囲損失の和を最小化するためにも利用できる。
論文 参考訳（メタデータ） (2022-03-03T03:46:18Z) - Practical, Provably-Correct Interactive Learning in the Realizable
Setting: The Power of True Believers [12.09273192079783]
我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。
我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-11-09T02:33:36Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Benchmark Study of Quantum Algorithms for Combinatorial Optimization:
Unitary versus Dissipative [0.0]
最適化のための3つの量子アルゴリズムの性能スケーリングについて検討する。
MFB-CIM、離散断熱量子計算(DAQC)、量子最小探索(DH-QMF)のためのD"urr-Hoyerアルゴリズム
論文 参考訳（メタデータ） (2021-05-07T22:35:02Z) - Bayesian Algorithm Execution: Estimating Computable Properties of
Black-box Functions Using Mutual Information [78.78486761923855]
多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。
本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。
これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
論文 参考訳（メタデータ） (2021-04-19T17:22:11Z) - Towards Solving Large-scale Expensive Optimization Problems Efficiently
Using Coordinate Descent Algorithm [3.1600708674008393]
計算予算が限られているLSEGO問題に対処するために,修正された座標 Descent アルゴリズム (MCD) を提案する。
提案アルゴリズムは,関心領域の探索と,指数速度で半分に折り畳むことで検索空間の縮小という,2つの主要なステップの恩恵を受ける。
提案アルゴリズムは,次元1000の20個のベンチマーク関数上でのデルタグルーピングと協調的共進化との比較を行った。
論文 参考訳（メタデータ） (2020-03-07T22:48:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。