論文の概要: High-Dimensional Simulation Optimization via Brownian Fields and Sparse
Grids
- arxiv url: http://arxiv.org/abs/2107.08595v1
- Date: Mon, 19 Jul 2021 03:03:27 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-20 15:06:53.726943
- Title: High-Dimensional Simulation Optimization via Brownian Fields and Sparse
Grids
- Title(参考訳): ブラウン場とスパース格子による高次元シミュレーション最適化
- Authors: Liang Ding, Rui Tuo, Xiaowei Zhang
- Abstract要約: 高次元シミュレーションの最適化は、非常に難しい。
本稿では,大域的最適解に収束する新しいサンプリングアルゴリズムを提案する。
提案アルゴリズムは,現実の典型的な代替案よりも劇的に優れていることを示す。
- 参考スコア(独自算出の注目度): 14.15772050249329
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: High-dimensional simulation optimization is notoriously challenging. We
propose a new sampling algorithm that converges to a global optimal solution
and suffers minimally from the curse of dimensionality. The algorithm consists
of two stages. First, we take samples following a sparse grid experimental
design and approximate the response surface via kernel ridge regression with a
Brownian field kernel. Second, we follow the expected improvement strategy --
with critical modifications that boost the algorithm's sample efficiency -- to
iteratively sample from the next level of the sparse grid. Under mild
conditions on the smoothness of the response surface and the simulation noise,
we establish upper bounds on the convergence rate for both noise-free and noisy
simulation samples. These upper rates deteriorate only slightly in the
dimension of the feasible set, and they can be improved if the objective
function is known be of a higher-order smoothness. Extensive numerical
experiments demonstrate that the proposed algorithm dramatically outperforms
typical alternatives in practice.
- Abstract(参考訳): 高次元シミュレーション最適化は、非常に難しい。
本稿では,大域的最適解に収束し,次元の呪いを最小に抑える新しいサンプリングアルゴリズムを提案する。
アルゴリズムは2つの段階からなる。
まず、スパースグリッド実験設計に従ってサンプルを採取し、ブラウン場カーネルを用いたカーネルリッジ回帰により応答面を近似する。
第2に,スパースグリッドの次のレベルからの反復的なサンプリングに,アルゴリズムのサンプリング効率を高める重要な修正を加えて,期待される改善戦略に従う。
応答面の平滑さとシミュレーションノイズの穏やかな条件下において,無騒音および無騒音シミュレーション試料の収束率の上界を定式化する。
これらの上限速度は、実現可能な集合の次元においてわずかにしか劣化せず、目的関数が高次の滑らかさであることが分かっていれば改善することができる。
広範な数値実験により,提案手法が従来の代替案を劇的に上回っていることが示された。
関連論文リスト
- Improving sample efficiency of high dimensional Bayesian optimization
with MCMC [7.241485121318798]
本稿ではマルコフ・チェイン・モンテカルロに基づく新しい手法を提案する。
提案アルゴリズムのMetropolis-HastingsとLangevin Dynamicsの両バージョンは、高次元逐次最適化および強化学習ベンチマークにおいて最先端の手法より優れていることを示す。
論文 参考訳(メタデータ) (2024-01-05T05:56:42Z) - Optimal Guarantees for Algorithmic Reproducibility and Gradient
Complexity in Convex Optimization [55.115992622028685]
以前の研究は、一階法はより良い収束率(漸進収束率)をトレードオフする必要があることを示唆している。
最適複雑性と準最適収束保証の両方を、滑らかな凸最小化と滑らかな凸最小化問題に対して達成できることを実証する。
論文 参考訳(メタデータ) (2023-10-26T19:56:52Z) - Adaptive Zeroth-Order Optimisation of Nonconvex Composite Objectives [1.7640556247739623]
ゼロ階エントロピー合成目的のためのアルゴリズムを解析し,次元依存性に着目した。
これは、ミラー降下法と推定類似関数を用いて、決定セットの低次元構造を利用して達成される。
勾配を改善するため、Rademacherに基づく古典的なサンプリング法を置き換え、ミニバッチ法が非ユークリ幾何学に対処することを示す。
論文 参考訳(メタデータ) (2022-08-09T07:36:25Z) - Adaptive Sampling Quasi-Newton Methods for Zeroth-Order Stochastic
Optimization [1.7513645771137178]
勾配情報のない制約のない最適化問題を考察する。
適応的なサンプリング準ニュートン法を提案し、共通乱数フレームワーク内の有限差を用いてシミュレーション関数の勾配を推定する。
そこで本研究では, 標準試験と内積準ニュートン試験の修正版を開発し, 近似に使用する試料サイズを制御し, 最適解の近傍に大域収束結果を与える。
論文 参考訳(メタデータ) (2021-09-24T21:49:25Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳(メタデータ) (2020-12-21T17:29:58Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳(メタデータ) (2020-06-14T10:42:23Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳(メタデータ) (2020-06-11T17:43:19Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳(メタデータ) (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。