論文の概要: A Second-Order Method for Stochastic Bandit Convex Optimisation
- arxiv url: http://arxiv.org/abs/2302.05371v1
- Date: Fri, 10 Feb 2023 16:49:58 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-13 15:14:55.406889
- Title: A Second-Order Method for Stochastic Bandit Convex Optimisation
- Title(参考訳): 確率帯域凸最適化のための2次法
- Authors: Tor Lattimore and Andr\'as Gy\"orgy
- Abstract要約: 制約のないゼロ階凸包帯に対する単純かつ効率的なアルゴリズムを提案する。
1 + r/d)[d1.5 sqrtn + d3] polylog(n, d, r)$ ここで$n$は地平線、$d$は次元、$r$は損失の最小値を含む既知の球の半径である。
- 参考スコア(独自算出の注目度): 28.93486346263364
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce a simple and efficient algorithm for unconstrained zeroth-order
stochastic convex bandits and prove its regret is at most $(1 + r/d)[d^{1.5}
\sqrt{n} + d^3] polylog(n, d, r)$ where $n$ is the horizon, $d$ the dimension
and $r$ is the radius of a known ball containing the minimiser of the loss.
- Abstract(参考訳): 制約のないゼロ次確率凸バンドに対する単純かつ効率的なアルゴリズムを導入し、その後悔が最大で$(1 + r/d)[d^{1.5} \sqrt{n} + d^3] polylog(n, d, r)$ ここで$n$は地平線、$d$は次元、$r$は損失のミニミセルを含む既知のボールの半径であることが証明する。
関連論文リスト
- Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [48.92318828548911]
本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。
政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。
提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
論文 参考訳(メタデータ) (2024-02-24T06:36:08Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。
我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
論文 参考訳(メタデータ) (2023-12-24T08:27:30Z) - A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and
Minimizing the Maximum of Smooth Functions [44.655316553524855]
我々は,$d$次元ユークリッド領域あるいは単純領域上で$max_iin[n] f_i(x) を最小化するアルゴリズムを設計する。
それぞれの$f_i$が1ドルLipschitzと1ドルSmoothのとき、我々の手法は$epsilon-approximateの解を計算する。
論文 参考訳(メタデータ) (2023-11-17T22:07:18Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。
ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。
我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文 参考訳(メタデータ) (2022-05-26T15:55:44Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳(メタデータ) (2021-03-02T06:53:44Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳(メタデータ) (2020-06-24T04:41:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。