論文の概要: Almost Free: Self-concordance in Natural Exponential Families and an Application to Bandits
- arxiv url: http://arxiv.org/abs/2410.01112v1
- Date: Tue, 1 Oct 2024 22:42:19 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-04 23:10:15.038485
- Title: Almost Free: Self-concordance in Natural Exponential Families and an Application to Bandits
- Title(参考訳): ほぼ自由:自然指数家庭における自己一致とバンドへの応用
- Authors: Shuai Liu, Alex Ayoub, Flore Sentenac, Xiaoqi Tan, Csaba Szepesvári,
- Abstract要約: 一般化された線形帯域に対する楽観的なアルゴリズムは、2階とも2階とも、先行項における問題パラメータの境界への指数的依存のない後悔境界を楽しむことを示す。
我々の定理は、半指数的尾を持つ一般化線型バンドイットに対する最初の後悔であり、ポアソン、指数的およびガンマバンドイットを含む問題のクラスを広げるものである。
- 参考スコア(独自算出の注目度): 32.10916558109406
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We prove that single-parameter natural exponential families with subexponential tails are self-concordant with polynomial-sized parameters. For subgaussian natural exponential families we establish an exact characterization of the growth rate of the self-concordance parameter. Applying these findings to bandits allows us to fill gaps in the literature: We show that optimistic algorithms for generalized linear bandits enjoy regret bounds that are both second-order (scale with the variance of the optimal arm's reward distribution) and free of an exponential dependence on the bound of the problem parameter in the leading term. To the best of our knowledge, ours is the first regret bound for generalized linear bandits with subexponential tails, broadening the class of problems to include Poisson, exponential and gamma bandits.
- Abstract(参考訳): 部分指数尾を持つ単パラメータ自然指数族が多項式サイズのパラメータと自己一致していることを証明する。
亜ガウスの自然指数族に対しては、自己一致パラメータの成長速度を正確に評価する。
一般化された線形包帯に対する楽観的なアルゴリズムは、2階目(最適腕の報酬分布のばらつきによるスケール)と、先行項における問題パラメータの境界への指数的依存のない後悔境界を楽しむことを示す。
我々の知識を最大限に活用するために、我々の研究は、偏見的な尾を持つ一般化線型バンドイットに対する最初の後悔であり、ポアソン、指数的およびガンマバンドイットを含む問題のクラスを広げている。
関連論文リスト
- Source Condition Double Robust Inference on Functionals of Inverse
Problems [71.42652863687117]
線形逆問題に対する解の線形汎関数として定義されるパラメータの推定を考察する。
本稿では,第1のソース条件である二重ロバスト推論法を提案する。
論文 参考訳(メタデータ) (2023-07-25T19:54:46Z) - Clustering above Exponential Families with Tempered Exponential Measures [28.532545355403123]
指数関数族とのリンクにより、$k$-meansクラスタリングは、幅広いデータ生成分布に一般化できるようになった。
指数族を超えて働くための枠組みは、公理化で彫られた人口最小化の頑丈さが欠如しているなど、道路ブロックを持ち上げるために重要である。
論文 参考訳(メタデータ) (2022-11-04T21:58:40Z) - Reproducible Bandits [95.8830340560603]
バンディット環境におけるポリシーは、2つの異なる実行において全く同じ腕列を高い確率で引き出すと再現可能と呼ばれる。
再現可能なポリシが存在するだけでなく、時間的地平線の観点から、ほぼ同じ(再現不可能な)後悔境界を達成することを示す。
以上の結果から,無作為化が探索・探索トレードオフに不可欠であるにもかかわらず,同一の腕を2回の異なるラウンドで引き抜いて最適なバランスをとれることが示唆された。
論文 参考訳(メタデータ) (2022-10-04T20:36:45Z) - Finite-Time Regret of Thompson Sampling Algorithms for Exponential
Family Multi-Armed Bandits [88.21288104408556]
本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。
最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
論文 参考訳(メタデータ) (2022-06-07T18:08:21Z) - From Optimality to Robustness: Dirichlet Sampling Strategies in
Stochastic Bandits [0.0]
本研究では、腕の観察を再サンプリングした経験的指標のペア比較に基づいて、ジェネリックディリクレサンプリング(DS)アルゴリズムについて検討する。
この戦略の異なる変種は、分布が有界であるときに証明可能な最適後悔保証と、半有界分布に対して軽度量子状態の対数後悔を実現することを示す。
論文 参考訳(メタデータ) (2021-11-18T14:34:21Z) - Bias-Robust Bayesian Optimization via Dueling Bandit [57.82422045437126]
ベイジアン最適化は、観測が逆偏りとなるような環境において考慮する。
情報指向サンプリング(IDS)に基づくダリングバンディットの新しい手法を提案する。
これにより、累積的後悔保証を伴う帯域幅の並列化のための、最初の効率的なカーネル化アルゴリズムが得られる。
論文 参考訳(メタデータ) (2021-05-25T10:08:41Z) - Adversarial Estimation of Riesz Representers [21.510036777607397]
一般関数空間を用いてRiesz表現子を推定する逆フレームワークを提案する。
臨界半径(Critical radius)と呼ばれる抽象的な量で非漸近平均平方レートを証明し、ニューラルネットワーク、ランダムな森林、カーネルヒルベルト空間を主要なケースとして再現する。
論文 参考訳(メタデータ) (2020-12-30T19:46:57Z) - Relative Deviation Margin Bounds [55.22251993239944]
我々はRademacher複雑性の観点から、分布依存と一般家庭に有効な2種類の学習境界を与える。
有限モーメントの仮定の下で、非有界な損失関数に対する分布依存的一般化境界を導出する。
論文 参考訳(メタデータ) (2020-06-26T12:37:17Z) - Finite-Time Analysis of Round-Robin Kullback-Leibler Upper Confidence
Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian
Rewards [10.66048003460524]
本稿では,複数の演奏とマルコフ報酬を含む古典的マルチアームバンディット問題の拡張について検討する。
この問題に対処するために、各段階において、全てのアームのサンプル手段からの情報と、ラウンドロビン方式で選択された単一アームのクルバック・リーバー上信頼境界とを結合する適応的アロケーションルールを検討する。
論文 参考訳(メタデータ) (2020-01-30T08:09:01Z) - Naive Feature Selection: a Nearly Tight Convex Relaxation for Sparse Naive Bayes [51.55826927508311]
そこで本稿では,特徴選択に使用可能なnaive Bayesのスパースバージョンを提案する。
余剰特徴の余剰寄与が減少するにつれて凸緩和境界が厳密になることを示す。
二項スパースモデルと多項スパースモデルの両方は、問題サイズにおいてほぼ線形な時間で解決可能である。
論文 参考訳(メタデータ) (2019-05-23T19:30:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。