論文の概要: Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHS
- arxiv url: http://arxiv.org/abs/2005.04832v1
- Date: Mon, 11 May 2020 01:55:39 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-04 19:54:32.262256
- Title: Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHS
- Title（参考訳）: RKHSにおける滑らか関数のマルチスケールゼロ次最適化
- Authors: Shubhanshu Shekhar, Tara Javidi
- Abstract要約: ブラックボックス関数 $f:mathcalX mapto mathbbR$ は、$f$がよりスムーズで、与えられたカーネル $K$ に関連する RKHS の有界ノルムを持つという仮定の下で最適化される。
本稿では,H の局所多項式 (LP) 推定器を用いて通常の GP 代理モデルを拡張した新しいアルゴリズム (textttLP-GP-UCB) を提案する。
- 参考スコア（独自算出の注目度）: 19.252319300590653
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We aim to optimize a black-box function $f:\mathcal{X} \mapsto \mathbb{R}$
under the assumption that $f$ is H\"older smooth and has bounded norm in the
RKHS associated with a given kernel $K$. This problem is known to have an
agnostic Gaussian Process (GP) bandit interpretation in which an appropriately
constructed GP surrogate model with kernel $K$ is used to obtain an upper
confidence bound (UCB) algorithm. In this paper, we propose a new algorithm
(\texttt{LP-GP-UCB}) where the usual GP surrogate model is augmented with Local
Polynomial (LP) estimators of the H\"older smooth function $f$ to construct a
multi-scale UCB guiding the search for the optimizer. We analyze this algorithm
and derive high probability bounds on its simple and cumulative regret. We then
prove that the elements of many common RKHS are H\"older smooth and obtain the
corresponding H\"older smoothness parameters, and hence, specialize our regret
bounds for several commonly used kernels. When specialized to the Squared
Exponential (SE) kernel, \texttt{LP-GP-UCB} matches the optimal performance,
while for the case of Mat\'ern kernels $(K_{\nu})_{\nu>0}$, it results in
uniformly tighter regret bounds for all values of the smoothness parameter
$\nu>0$. Most notably, for certain ranges of $\nu$, the algorithm achieves
near-optimal bounds on simple and cumulative regrets, matching the
algorithm-independent lower bounds up to polylog factors, and thus closing the
large gap between the existing upper and lower bounds for these values of
$\nu$. Additionally, our analysis provides the first explicit regret bounds, in
terms of the budget $n$, for the Rational-Quadratic (RQ) and Gamma-Exponential
(GE). Finally, experiments with synthetic functions as well as a CNN
hyperparameter tuning task demonstrate the practical benefits of our
multi-scale partitioning approach over some existing algorithms numerically.
- Abstract（参考訳）: ブラックボックス関数 $f:\mathcal{x} \mapsto \mathbb{r}$ を最適化するために、$f$ が h\"old smooth であると仮定し、与えられたカーネル $k$ に関連付けられた rkhs において有界ノルムを持つ。
この問題は、カーネル$K$で適切に構築されたGPサロゲートモデルを用いて、上位信頼境界(UCB)アルゴリズムを得るような、非依存のガウス過程(GP)バンディット解釈を持つことが知られている。
本稿では,H\"older smooth function $f$ の局所多項式 (LP) 推定器で通常のGPサロゲートモデルを拡張した新しいアルゴリズム (\texttt{LP-GP-UCB}) を提案し,オプティマイザの探索を導くマルチスケール UCB を構築する。
このアルゴリズムを解析し,その単純かつ累積的後悔に基づいて高い確率境界を求める。
すると、多くの共通RKHSの元が H\ より滑らかであり、対応する H\ より古い滑らか度パラメータが得られ、したがって、いくつかのよく使われるカーネルに対する後悔境界を特殊化する。
2乗指数 (se) カーネルに特化した場合、 \texttt{lp-gp-ucb} は最適性能に合致するが、mat\'ern カーネルの場合は $(k_{\nu})_{\nu>0} である。
最も注目すべきは、ある範囲の$\nu$に対して、アルゴリズムは単純かつ累積的後悔に対する準最適境界を達成し、アルゴリズムに依存しない下界をポリログ因子に一致させ、これらの値に対して既存の上界と下界の間の大きなギャップを閉じる。
さらに、我々の分析は、RQ(Rational-Quadratic)とGE(Gamma-Exponential)の予算$n$という最初の明示的な後悔境界を提供する。
最後に、CNNハイパーパラメータチューニングタスクと同様に合成関数を用いた実験により、既存のアルゴリズムに対するマルチスケールパーティショニングアプローチの実用的利点を数値的に示す。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。
本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
論文 参考訳（メタデータ） (2023-05-30T17:47:27Z) - Lower Bounds on the Worst-Case Complexity of Efficient Global
Optimization [11.523746174066702]
我々は、その対応する再生核ヒルベルト空間(RKHS)における球の計量エントロピーの観点から、効率的な大域最適化の複雑さに対する統一された下界を導出する。
この下界は、一般に使用される2乗指数核とマタン核の非適応探索アルゴリズムによって達成された上界にほぼ一致することを示す。
論文 参考訳（メタデータ） (2022-09-20T11:57:13Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。
本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。
提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
論文 参考訳（メタデータ） (2021-11-09T09:00:02Z) - 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) - Optimal Order Simple Regret for Gaussian Process Bandits [6.84224661918159]
純粋な探索アルゴリズムは既存の境界よりもかなり厳密であることを示す。
この後悔は、カーネル上の低い境界が知られている場合に、対数的に最適であることを示す。
論文 参考訳（メタデータ） (2021-08-20T16:49:32Z) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07:44Z) - On Information Gain and Regret Bounds in Gaussian Process Bandits [8.499604625449907]
ノイズフィードバックの観測から、高い評価と、おそらくは非シーケンシャルな目的関数$f$の最適化を考える。
カーネルのMatern族では、$gamma_T$の低い境界と、頻繁な設定での後悔が知られている。
論文 参考訳（メタデータ） (2020-09-15T10:15:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。