論文の概要: Low Regret Binary Sampling Method for Efficient Global Optimization of
Univariate Functions
- arxiv url: http://arxiv.org/abs/2201.07164v1
- Date: Tue, 18 Jan 2022 18:11:48 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-19 14:41:37.834014
- Title: Low Regret Binary Sampling Method for Efficient Global Optimization of
Univariate Functions
- Title（参考訳）: 単変数関数の効率的な大域最適化のための低回帰二分サンプリング法
- Authors: Kaan Gokcesu, Hakan Gokcesu
- Abstract要約: 最適クエリと目的関数の最適値との単純な後悔ではなく,アルゴリズムの累積的後悔について検討する。
提案手法は従来の下界アルゴリズムと類似しているが,計算コストの優位性は大きい。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we propose a computationally efficient algorithm for the
problem of global optimization in univariate loss functions. For the
performance evaluation, we study the cumulative regret of the algorithm instead
of the simple regret between our best query and the optimal value of the
objective function. Although our approach has similar regret results with the
traditional lower-bounding algorithms such as the Piyavskii-Shubert method for
the Lipschitz continuous or Lipschitz smooth functions, it has a major
computational cost advantage. In Piyavskii-Shubert method, for certain types of
functions, the query points may be hard to determine (as they are solutions to
additional optimization problems). However, this issue is circumvented in our
binary sampling approach, where the sampling set is predetermined irrespective
of the function characteristics. For a search space of $[0,1]$, our approach
has at most $L\log (3T)$ and $2.25H$ regret for $L$-Lipschitz continuous and
$H$-Lipschitz smooth functions respectively. We also analytically extend our
results for a broader class of functions that covers more complex regularity
conditions.
- Abstract（参考訳）: 本研究では,一変量損失関数における大域最適化問題に対する計算効率のよいアルゴリズムを提案する。
性能評価のために, 最良問合せと目的関数の最適値との単純な後悔ではなく, アルゴリズムの累積後悔について検討した。
この手法は,リプシッツ連続関数やリプシッツ滑らか関数に対するpiyavskii-shubert法のような従来の低バウンドアルゴリズムでも同様に後悔する結果をもたらすが,計算コストの利点は大きい。
Piyavskii-Shubert 法では、ある種の関数に対して、クエリポイントは決定が難しい(それらがさらなる最適化問題の解であるから)。
しかし, この問題は, 関数特性に関わらずサンプリングセットが予め決められた二分サンプリング手法で回避される。
検索空間が$[0,1]$の場合、我々のアプローチは最大$L\log (3T)$と$2.25H$でそれぞれ$L$-Lipschitz連続と$H$-Lipschitz滑らかな関数を後悔する。
また、より複雑な正則性条件をカバーするより広範な関数のクラスに対して解析的に結果を拡張する。
関連論文リスト
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文 参考訳（メタデータ） (2023-06-03T17:05:13Z) - Efficient Lipschitzian Global Optimization of H\"older Continuous
Multivariate Functions [0.0]
本研究では,H"より古い連続な多変量関数に対して,効率的な大域的最適化手法を提案する。
このアルゴリズムは,H"older $alpha$でH"older連続目標関数を与えられた時間的地平線内の$n$次元空間で最適化するために,平均的残差$O(T-fracalphan)$に達することを示す。
論文 参考訳（メタデータ） (2023-03-24T22:29:35Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Efficient Minimax Optimal Global Optimization of Lipschitz Continuous
Multivariate Functions [0.0]
我々は,このアルゴリズムがリプシッツ連続函数の地平線に対して平均的後悔O(LstnT-frac1n)$を達成することを示す。
論文 参考訳（メタデータ） (2022-06-06T06:28:38Z) - Cumulative Regret Analysis of the Piyavskii--Shubert Algorithm and Its
Variants for Global Optimization [0.0]
We study the problem of global optimization, where we analyze the performance of the Piyavskii-Shubert algorithm and its variants。
その結果,提案アルゴリズムはクエリを効率よく決定し,最小限の(ログファクタまで)累積的後悔を実現する。
論文 参考訳（メタデータ） (2021-08-24T17:36:33Z) - Ada-BKB: Scalable Gaussian Process Optimization on Continuous Domain by
Adaptive Discretization [21.859940486704264]
GPUCBのようなアルゴリズムは計算の複雑さを禁止している。
関数のノアアルゴリズムは、連続最適化の真の問題を裏付ける。
論文 参考訳（メタデータ） (2021-06-16T07:55:45Z) - 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) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。