論文の概要: Tight Regret Bounds for Noisy Optimization of a Brownian Motion

• arxiv url: http://arxiv.org/abs/2001.09327v2
• Date: Sat, 15 Jan 2022 12:02:33 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-07 00:07:40.706257
• Title: Tight Regret Bounds for Noisy Optimization of a Brownian Motion
• Title（参考訳）: ブラウン運動の雑音最適化のためのタイトレグレト境界
• Authors: Zexin Wang, Vincent Y. F. Tan, Jonathan Scarlett
• Abstract要約: 本稿では,1次元ブラウン運動のベイズ最適化の問題点について考察する。 Omega(sigmasqrtT cdot log T)$.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.
• 参考スコア（独自算出の注目度）: 118.65407541895851
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of Bayesian optimization of a one-dimensional Brownian motion in which the $T$ adaptively chosen observations are corrupted by Gaussian noise. We show that as the smallest possible expected cumulative regret and the smallest possible expected simple regret scale as $\Omega(\sigma\sqrt{T / \log (T)}) \cap \mathcal{O}(\sigma\sqrt{T} \cdot \log T)$ and $\Omega(\sigma / \sqrt{T \log (T)}) \cap \mathcal{O}(\sigma\log T / \sqrt{T})$ respectively, where $\sigma^2$ is the noise variance. Thus, our upper and lower bounds are tight up to a factor of $\mathcal{O}( (\log T)^{1.5} )$. The upper bound uses an algorithm based on confidence bounds and the Markov property of Brownian motion (among other useful properties), and the lower bound is based on a reduction to binary hypothesis testing.
• Abstract（参考訳）: 本稿では,1次元ブラウン運動のベイズ最適化の問題点について考察する。 可能な最小限の累積後悔と最小限の単純な後悔尺度として、$\Omega(\sigma\sqrt{T / \log (T)}) \cap \mathcal{O}(\sigma\sqrt{T} \cdot \log T)$と$\Omega(\sigma / \sqrt{T \log (T)}) \cap \mathcal{O}(\sigma\log T / \sqrt{T})$とすると、$\sigma^2$はノイズ分散である。 したがって、上界と下界は、$\mathcal{o}( (\log t)^{1.5} )$ の係数に密接である。 上界は信頼境界とブラウン運動のマルコフ特性(他の有用な性質と同様に)に基づくアルゴリズムを使用し、下界は二元仮説検定への還元に基づいている。

関連論文リスト

• Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD [16.019880089338383]
  Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsff
  論文  参考訳（メタデータ） (2024-10-26T10:14:17Z)
• Batched Stochastic Bandit for Nondegenerate Functions [8.015503209312786]
  本稿では,非退化関数に対するバッチ帯域学習問題について検討する。 本稿では,非退化関数に対するバッチバンドイット問題をほぼ最適に解くアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-09T12:50:16Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Best-of-Both-Worlds Algorithms for Partial Monitoring [34.37963000493442]
  非退化したグローバル可観測ゲームでは、レジームの後悔は$O(k3 m2 log(k_Pi T) / Delta_min2)$で制限される。 我々のアルゴリズムは、フィードバックグラフを用いたオンライン学習の分野におけるアルゴリズムにインスパイアされた、フォロー・ザ・レギュラライズド・リーダー・フレームワークに基づいている。
  論文  参考訳（メタデータ） (2022-07-29T08:40:05Z)
• Order-Optimal Error Bounds for Noisy Kernel-Based Bayesian Quadrature [42.129843613950285]
  我々は、Match'ern-$nu$ kernel を用いて、Em Reproduction Kernel Hilbert Space (RKHS) の関数を考える。 ブラックボックスクエリが分散$sigma2$のガウスノイズを受ける場合、最大で$T$のアルゴリズムは平均絶対誤差$Omega(T-fracnud-1 + sigma T-frac12)$を発生しなければならない。
  論文  参考訳（メタデータ） (2022-02-22T01:49:41Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。 一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
  論文  参考訳（メタデータ） (2020-10-22T19:14:37Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)

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

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