論文の概要: Ada-BKB: Scalable Gaussian Process Optimization on Continuous Domain by Adaptive Discretization

• arxiv url: http://arxiv.org/abs/2106.08598v1
• Date: Wed, 16 Jun 2021 07:55:45 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-17 17:38:43.529332
• Title: Ada-BKB: Scalable Gaussian Process Optimization on Continuous Domain by Adaptive Discretization
• Title（参考訳）: Ada-BKB: 適応離散化による連続領域のスケーラブルガウスプロセス最適化
• Authors: Marco Rando, Luigi Carratino, Silvia Villa and Lorenzo Rosasco
• Abstract要約: GPUCBのようなアルゴリズムは計算の複雑さを禁止している。 関数のノアアルゴリズムは、連続最適化の真の問題を裏付ける。
• 参考スコア（独自算出の注目度）: 21.859940486704264
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Gaussian process optimization is a successful class of algorithms (e.g. GP-UCB) to optimize a black-box function through sequential evaluations. However, when the domain of the function is continuous, Gaussian process optimization has to either rely on a fixed discretization of the space, or solve a non-convex optimization subproblem at each evaluation. The first approach can negatively affect performance, while the second one puts a heavy computational burden on the algorithm. A third option, that only recently has been theoretically studied, is to adaptively discretize the function domain. Even though this approach avoids the extra non-convex optimization costs, the overall computational complexity is still prohibitive. An algorithm such as GP-UCB has a runtime of $O(T^4)$, where $T$ is the number of iterations. In this paper, we introduce Ada-BKB (Adaptive Budgeted Kernelized Bandit), a no-regret Gaussian process optimization algorithm for functions on continuous domains, that provably runs in $O(T^2 d_\text{eff}^2)$, where $d_\text{eff}$ is the effective dimension of the explored space, and which is typically much smaller than $T$. We corroborate our findings with experiments on synthetic non-convex functions and on the real-world problem of hyper-parameter optimization.
• Abstract（参考訳）: ガウス過程最適化は成功したアルゴリズムのクラス(例)である。 GP-UCB) は逐次評価によりブラックボックス関数を最適化する。 しかし、関数の領域が連続であるとき、ガウス過程の最適化は空間の固定離散化に依存するか、各評価で非凸最適化部分問題を解く必要がある。 第1のアプローチは性能に悪影響を及ぼすが,第2のアプローチはアルゴリズムに計算負荷を強いる。 理論的に研究されたばかりの第3の選択肢は、適応的に関数領域を識別することである。 このアプローチは、余分な非凸最適化コストを回避するが、全体的な計算複雑性は禁じられている。 GP-UCBのようなアルゴリズムは、$O(T^4)$のランタイムを持ち、$T$は反復数である。 本稿では,Ada-BKB(Adaptive Budgeted Kernelized Bandit)を導入する。これは連続領域上の関数に対する非回帰ガウスプロセス最適化アルゴリズムで,$O(T^2 d_\text{eff}^2)$で確実に動作し,$d_\text{eff}$は探索空間の有効次元であり,典型的には$T$よりもはるかに小さい。 我々は, 合成非凸関数とハイパーパラメータ最適化の実世界問題について実験を行い, この知見を裏付ける。

関連論文リスト

• Two-step Lookahead Bayesian Optimization with Inequality Constraints [21.703234193908038]
  本稿では,2段階の制約付きベイズ最適化獲得関数 (2-OPT-C) を提案する。 数値実験では、2-OPT-Cは従来の手法よりも2倍以上のクエリ効率が向上し、場合によっては10倍以上のクエリ効率が向上する。
  論文  参考訳（メタデータ） (2021-12-06T07:40:54Z)
• Reducing the Variance of Gaussian Process Hyperparameter Optimization with Preconditioning [54.01682318834995]
  プレコンディショニングは、行列ベクトル乗算を含む反復的な方法にとって非常に効果的なステップである。 プレコンディショニングには、これまで検討されていなかった付加的なメリットがあることを実証する。 基本的に無視可能なコストで、同時に分散を低減することができる。
  論文  参考訳（メタデータ） (2021-07-01T06:43:11Z)
• 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)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。 本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。 これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
  論文  参考訳（メタデータ） (2021-04-19T17:22:11Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance [16.0251555430107]
  これはGPに基づく最初のアルゴリズムであり、順序最適化された後悔の保証がある。 GP-UCB系のアルゴリズムと比較して,提案アルゴリズムは計算複雑性を$O(T2d-1)$で低減する。
  論文  参考訳（メタデータ） (2020-10-27T02:15:15Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)

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

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