論文の概要: Jointly Efficient and Optimal Algorithms for Logistic Bandits
- arxiv url: http://arxiv.org/abs/2201.01985v1
- Date: Thu, 6 Jan 2022 09:23:52 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-07 15:15:55.911041
- Title: Jointly Efficient and Optimal Algorithms for Logistic Bandits
- Title（参考訳）: ロジスティック帯域に対する結合効率と最適アルゴリズム
- Authors: Louis Faury, Marc Abeille, Kwang-Sung Jun, Cl\'ement Calauz\`enes
- Abstract要約: 我々はロジスティックバンドのための新しい学習手順を導入する。
統計的厳密さを犠牲にすることなく、十分な統計がオンラインで容易に維持できる信頼セットが得られる。
我々の知る限りでは、これらは統計と計算の効率を同時に享受する最初のロジスティック・バンディットアルゴリズムである。
- 参考スコア（独自算出の注目度）: 17.826401899956604
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Logistic Bandits have recently undergone careful scrutiny by virtue of their
combined theoretical and practical relevance. This research effort delivered
statistically efficient algorithms, improving the regret of previous strategies
by exponentially large factors. Such algorithms are however strikingly costly
as they require $\Omega(t)$ operations at each round. On the other hand, a
different line of research focused on computational efficiency
($\mathcal{O}(1)$ per-round cost), but at the cost of letting go of the
aforementioned exponential improvements. Obtaining the best of both world is
unfortunately not a matter of marrying both approaches. Instead we introduce a
new learning procedure for Logistic Bandits. It yields confidence sets which
sufficient statistics can be easily maintained online without sacrificing
statistical tightness. Combined with efficient planning mechanisms we design
fast algorithms which regret performance still match the problem-dependent
lower-bound of Abeille et al. (2021). To the best of our knowledge, those are
the first Logistic Bandit algorithms that simultaneously enjoy statistical and
computational efficiency.
- Abstract（参考訳）: ロジスティック・バンドは近年、理論的および実践的関連性の組み合わせにより慎重に精査されている。
この研究は統計的に効率的なアルゴリズムを提供し、指数関数的に大きな要因によって以前の戦略の後悔を改善した。
しかし、このようなアルゴリズムは、各ラウンドで$\Omega(t)$演算を必要とするため、著しくコストがかかる。
一方、別の研究は計算効率に焦点をあてる("\mathcal{o}(1)$ per-round cost")が、上記の指数関数的改善を放棄するコストを犠牲にしている。
両世界の最善を勝ち取ることは、残念ながら両者の結婚の問題ではない。
代わりに、ロジスティックバンドのための新しい学習手順を導入する。
統計的厳密性を犠牲にすることなく、十分な統計がオンラインで容易に維持できる信頼セットが得られる。
効率的な計画手法と組み合わさって,Abeille et al. (2021) の課題依存下界に相反する性能を後悔する高速アルゴリズムを設計する。
我々の知る限り、これらは統計と計算の効率を同時に享受する最初のロジスティック帯域幅アルゴリズムである。
関連論文リスト
- Safe and Efficient Online Convex Optimization with Linear Budget Constraints and Partial Feedback [3.5554907645160605]
本稿では,未知の線形予算制約を伴うオンライン凸最適化について検討する。
本稿では,安全かつ効率的なLyapunov-Optimizationアルゴリズム(SELO)を提案する。
論文 参考訳（メタデータ） (2024-12-05T08:58:41Z) - Faster WIND: Accelerating Iterative Best-of-$N$ Distillation for LLM Alignment [81.84950252537618]
本稿では,反復的BONDと自己プレイアライメントの統一的なゲーム理論接続を明らかにする。
WINレート支配(WIN rate Dominance, WIND)という新しいフレームワークを構築し, 正規化利率支配最適化のためのアルゴリズムを多数提案する。
論文 参考訳（メタデータ） (2024-10-28T04:47:39Z) - Efficient Methods for Non-stationary Online Learning [61.63338724659592]
本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。
また、さらに強化された測度、すなわち「インターバル・ダイナミック・リピート」を研究し、ラウンド当たりの射影数を$mathcalO(log2 T)$から$$$$に減らした。
論文 参考訳（メタデータ） (2023-09-16T07:30:12Z) - Representation Learning with Multi-Step Inverse Kinematics: An Efficient
and Optimal Approach to Rich-Observation RL [106.82295532402335]
既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。
所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。
我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
論文 参考訳（メタデータ） (2023-04-12T14:51:47Z) - Best Arm Identification in Stochastic Bandits: Beyond $\beta-$optimality [31.359578768463752]
本稿では,固定信頼設定における多腕バンディットにおけるベストアーム識別(BAI)の非装飾的側面について検討する。
帯域幅アルゴリズムを評価するための2つの重要な指標は、計算効率と性能最適性である。
本稿では,BAIのためのフレームワークとアルゴリズムを導入し,計算効率のよい決定ルールセットを用いて最適性能を実現する。
論文 参考訳（メタデータ） (2023-01-10T05:02:49Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳（メタデータ） (2021-11-24T07:14:57Z) - Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary
Dueling Bandits [27.279654173896372]
我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。
これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
論文 参考訳（メタデータ） (2021-11-06T16:46:55Z) - Efficient First-Order Contextual Bandits: Prediction, Allocation, and
Triangular Discrimination [82.52105963476703]
統計的学習、オンライン学習、その他における繰り返しのテーマは、低騒音の問題に対してより速い収束率が可能であることである。
1次保証は統計的およびオンライン学習において比較的よく理解されている。
三角識別と呼ばれる対数損失と情報理論量が一階保証を得る上で基本的な役割を担っていることを示す。
論文 参考訳（メタデータ） (2021-07-05T19:20:34Z) - Local Algorithms for Estimating Effective Resistance [26.54556748340991]
本研究では,大規模グラフ上での有効抵抗を推定するための複数のエンファンローカアルゴリズムを設計する。
主アルゴリズムは任意の頂点対 $s,t$ と任意に小さな加算誤差の間の有効抵抗を近似する。
いくつかのベンチマークデータセットについて広範な実験を行い、アルゴリズムを検証した。
論文 参考訳（メタデータ） (2021-06-07T10:08:12Z) - Safeguarded Learned Convex Optimization [106.81731132086851]
解析最適化アルゴリズムは、反復的な方法で問題を確実に解くために手作業で設計することができる。
データ駆動アルゴリズムは、汎用最適化アルゴリズムと同様のイテレーション当たりのコストと、はるかに少ないイテレーションで"L2O"を最適化する。
我々はこれらのアプローチの利点を融合させるSafe-L2Oフレームワークを提案する。
論文 参考訳（メタデータ） (2020-03-04T04:01:15Z) - How to Solve Fair $k$-Center in Massive Data Models [5.3283669037198615]
我々は、$k$-center問題に対して、新しいストリーミングおよび分散アルゴリズムを設計する。
主な貢献は、(a)最初の分散アルゴリズム、(b)証明可能な近似保証付き2パスストリーミングアルゴリズムである。
論文 参考訳（メタデータ） (2020-02-18T16:11:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。