論文の概要: Statistical Complexity and Optimal Algorithms for Non-linear Ridge Bandits

• arxiv url: http://arxiv.org/abs/2302.06025v3
• Date: Wed, 10 Jan 2024 02:49:55 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-11 18:08:52.291689
• Title: Statistical Complexity and Optimal Algorithms for Non-linear Ridge Bandits
• Title（参考訳）: 非線形リッジバンディットの統計的複雑性と最適アルゴリズム
• Authors: Nived Rajaraman, Yanjun Han, Jiantao Jiao, Kannan Ramchandran
• Abstract要約: 選択した行動の非線形関数を平均結果とするシーケンシャルな意思決定問題を考える。 特に、まず良い初期作用を見つけ、次に問題を局所線型として扱う2段階のアルゴリズムは統計的に最適である。
• 参考スコア（独自算出の注目度）: 39.391636494257284
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the sequential decision-making problem where the mean outcome is a non-linear function of the chosen action. Compared with the linear model, two curious phenomena arise in non-linear models: first, in addition to the "learning phase" with a standard parametric rate for estimation or regret, there is an "burn-in period" with a fixed cost determined by the non-linear function; second, achieving the smallest burn-in cost requires new exploration algorithms. For a special family of non-linear functions named ridge functions in the literature, we derive upper and lower bounds on the optimal burn-in cost, and in addition, on the entire learning trajectory during the burn-in period via differential equations. In particular, a two-stage algorithm that first finds a good initial action and then treats the problem as locally linear is statistically optimal. In contrast, several classical algorithms, such as UCB and algorithms relying on regression oracles, are provably suboptimal.
• Abstract（参考訳）: 平均結果が選択された行動の非線形関数である逐次意思決定問題を考える。 線形モデルと比較すると、2つの興味深い現象が非線形モデルに現れる: 第一に、推定または後悔のための標準パラメトリックレートの「学習フェーズ」に加えて、非線形関数によって決定される固定コストの「バーンイン期間」が存在し、第二に、最小のバーンインコストを達成するためには新しい探索アルゴリズムが必要である。 文献におけるリッジ関数と呼ばれる非線形関数の特別な族について、最適なバーンインコストの上限と下限を導出し、さらに微分方程式を用いてバーンイン期間の学習軌跡全体を導出する。 特に、2段階のアルゴリズムはまず良い初期作用を見つけ、その問題を局所線型として扱うことは統計的に最適である。 対照的に、UTBや回帰オラクルに依存するアルゴリズムのような古典的なアルゴリズムは、明らかに準最適である。

関連論文リスト

• Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning [53.97335841137496]
  非線形関数近似を用いたオフラインRLにおけるPNLSVI(Pessimistic Least-Square Value Iteration)と呼ばれるオラクル効率のアルゴリズムを提案する。 本アルゴリズムは,関数クラスの複雑性に強く依存する後悔境界を享受し,線形関数近似に特化して最小限のインスタンス依存後悔を実現する。
  論文  参考訳（メタデータ） (2023-10-02T17:42:01Z)
• Online Learning Under A Separable Stochastic Approximation Framework [20.26530917721778]
  分離可能な近似フレームワークを用いて,機械学習モデルのクラスに対するオンライン学習アルゴリズムを提案する。 提案アルゴリズムは,他の一般的な学習アルゴリズムと比較して,より堅牢でテスト性能が高いことを示す。
  論文  参考訳（メタデータ） (2023-05-12T13:53:03Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes [80.89852729380425]
  そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。 我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
  論文  参考訳（メタデータ） (2022-12-12T18:58:59Z)
• Implicit Parameter-free Online Learning with Truncated Linear Models [51.71216912089413]
  パラメータフリーアルゴリズムは、設定された学習率を必要としないオンライン学習アルゴリズムである。 そこで我々は,「単純」なフレーバーを持つ新しい更新によって,切り離された線形モデルを活用できる新しいパラメータフリーアルゴリズムを提案する。 後悔の新たな分解に基づいて、新しい更新は効率的で、各ステップで1つの勾配しか必要とせず、切り捨てられたモデルの最小値をオーバーシュートすることはない。
  論文  参考訳（メタデータ） (2022-03-19T13:39:49Z)
• Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for Linear Programming [5.126924253766052]
  提案手法は,高い確率で鋭いインスタンスを解くための線形収束率を示す。 また、制約のない双線型問題に対する効率的な座標ベースのオラクルを提案する。
  論文  参考訳（メタデータ） (2021-11-10T04:56:38Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• A spectral algorithm for robust regression with subgaussian rates [0.0]
  本研究では, 試料の分布に強い仮定がない場合の線形回帰に対する2次時間に対する新しい線形アルゴリズムについて検討する。 目的は、データが有限モーメントしか持たなくても最適な準ガウス誤差を達成できる手順を設計することである。
  論文  参考訳（メタデータ） (2020-07-12T19:33:50Z)
• Resolving learning rates adaptively by locating Stochastic Non-Negative Associated Gradient Projection Points using line searches [0.0]
  ニューラルネットワークトレーニングにおける学習率は現在、高価なマニュアルや自動チューニングを使用したトレーニングの優先事項として決定されている。 本研究では,ニューラルネットワーク学習アルゴリズムの学習率を解くために,勾配のみの線探索を提案する。
  論文  参考訳（メタデータ） (2020-01-15T03:08:07Z)

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

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