論文の概要: Improved Regret of Linear Ensemble Sampling

• arxiv url: http://arxiv.org/abs/2411.03932v1
• Date: Wed, 06 Nov 2024 14:09:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-07 19:24:35.260612
• Title: Improved Regret of Linear Ensemble Sampling
• Title（参考訳）: 線形アンサンブルサンプリングの改良
• Authors: Harin Lee, Min-hwan Oh,
• Abstract要約: アンサンブルサイズを$T$とすると、線形アンサンブルサンプリングは$tildemathcalO(d3/2sqrtT)$の頻繁な残差を達成できる。 我々の貢献は、アンサンブルサンプリングの理論的な基礎を前進させ、他のランダム化探索アルゴリズムの最もよく知られた境界と一致させた。
• 参考スコア（独自算出の注目度）: 9.410437324336275
• License:
• Abstract: In this work, we close the fundamental gap of theory and practice by providing an improved regret bound for linear ensemble sampling. We prove that with an ensemble size logarithmic in $T$, linear ensemble sampling can achieve a frequentist regret bound of $\tilde{\mathcal{O}}(d^{3/2}\sqrt{T})$, matching state-of-the-art results for randomized linear bandit algorithms, where $d$ and $T$ are the dimension of the parameter and the time horizon respectively. Our approach introduces a general regret analysis framework for linear bandit algorithms. Additionally, we reveal a significant relationship between linear ensemble sampling and Linear Perturbed-History Exploration (LinPHE), showing that LinPHE is a special case of linear ensemble sampling when the ensemble size equals $T$. This insight allows us to derive a new regret bound of $\tilde{\mathcal{O}}(d^{3/2}\sqrt{T})$ for LinPHE, independent of the number of arms. Our contributions advance the theoretical foundation of ensemble sampling, bringing its regret bounds in line with the best known bounds for other randomized exploration algorithms.
• Abstract（参考訳）: 本研究では,線形アンサンブルサンプリングのための改良された後悔境界を提供することにより,理論と実践の基本的なギャップを埋める。 アンサンブルサイズを$T$で対数化することにより、線形アンサンブルサンプリングは、パラメータの次元が$d$と$T$であるようなランダム化線形バンディットアルゴリズムの最先端結果に一致する$\tilde{\mathcal{O}}(d^{3/2}\sqrt{T})$の頻繁な残差を達成できることを示す。 本稿では,線形帯域幅アルゴリズムに対する一般的な後悔分析フレームワークを提案する。 また,線形アンサンブルサンプリングと線形摂動歴史探査(LinPHE)の有意な関係を明らかにし,LinPHEが線形アンサンブルサンプリングの特別な場合であることを示す。 この洞察により、武器の数に依存しないLinPHEに対して$\tilde{\mathcal{O}}(d^{3/2}\sqrt{T})$の新たな後悔境界を導出することができる。 我々の貢献は、アンサンブルサンプリングの理論的な基礎を前進させ、他のランダム化探索アルゴリズムの最もよく知られた境界と一致させた。

関連論文リスト

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Optimal Thresholding Linear Bandit [21.2523248114561]
  本稿では,線形帯域に一定の信頼を抱いた$epsilon$-Thresholding Bandit Problem (TBP) という新しい純粋探索問題について検討する。 我々は,この場合のベストアーム識別のために設計されたアルゴリズムを,複雑性に最適なTBPに拡張する。
  論文  参考訳（メタデータ） (2024-02-11T21:25:14Z)
• A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization [6.314057999212246]
  ランダムリシャッフル技術は、ニューラルネットワークのような大規模アプリケーションで使用される。 本稿では,ノルムPRRが生成するランダムリシャッフル型反復が線形設定に収束することを示す。 最後に,提案手法に適用可能な最終収束率を導出する。
  論文  参考訳（メタデータ） (2023-12-02T07:12:00Z)
• Ensemble sampling for linear bandits: small ensembles suffice [75.4286948336835]
  線形バンディット設定のためのアンサンブルサンプリングの最初の有用かつ厳密な解析を行う。 当社は、$T$で線形にスケールするためにアンサンブルのサイズを必要とせず、$smashsqrtT$の注文を後悔する、構造化された設定の最初の結果です。
  論文  参考訳（メタデータ） (2023-11-14T18:41:28Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• Optimal Scalarizations for Sublinear Hypervolume Regret [2.703970154550017]
  均一にランダムな重みを持つ超体積スカラー化は、O(T-1/k)$の最適サブボリューム超体積後悔境界が得られることを示す。 多目的線型包帯の設定のために、不必要な$textpoly(k)$依存を取り除くために$tildeO(d T-1/2 + T-1/k)$の後悔境界を得る新しい非ユークリッド解析を導出する。
  論文  参考訳（メタデータ） (2023-07-06T20:49:42Z)
• Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits [88.6139446295537]
  一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。 ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。 本稿では,FTRLに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-02-28T08:25:26Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。 我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-30T19:10:32Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model [0.0]
  このモデルに基づく最小二乗リスクに対する1パス, 固定段差勾配勾配の収束度を解析した。 特殊な場合として、ランダムなサンプリング点における値のノイズのない観測から単位区間上の実関数を推定するオンラインアルゴリズムを解析する。
  論文  参考訳（メタデータ） (2020-06-15T08:25:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。