論文の概要: Regret analysis of the Piyavskii-Shubert algorithm for global Lipschitz
optimization
- arxiv url: http://arxiv.org/abs/2002.02390v4
- Date: Mon, 4 Jul 2022 22:26:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-03 10:11:21.810803
- Title: Regret analysis of the Piyavskii-Shubert algorithm for global Lipschitz
optimization
- Title（参考訳）: グローバルリプシッツ最適化のためのpiyavskii-shubertアルゴリズムの後悔解析
- Authors: Cl\'ement Bouttier, Tommaso Cesari (TSE), M\'elanie Ducoffe,
S\'ebastien Gerchinovitz (IMT)
- Abstract要約: ピヤフスキとシュベルトによって1972年に考案された自然アルゴリズムについて研究する。
我々は、与えられた最適化精度に到達または証明するために必要な関数の評価数に関する新しい境界を証明した。
- 参考スコア（独自算出の注目度）: 1.6822770693792826
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of maximizing a non-concave Lipschitz multivariate
function over a compact domain by sequentially querying its (possibly
perturbed) values. We study a natural algorithm designed originally by
Piyavskii and Shubert in 1972, for which we prove new bounds on the number of
evaluations of the function needed to reach or certify a given optimization
accuracy. Our analysis uses a bandit-optimization viewpoint and solves an open
problem from Hansen et al.\ (1991) by bounding the number of evaluations to
certify a given accuracy with a near-optimal sum of packing numbers.
- Abstract（参考訳）: コンパクト領域上での非凸リプシッツ多変量関数の最大化は、その(おそらく摂動された)値を逐次クエリすることで問題を考える。
1972年にPayavskii と Shubert によって設計された自然アルゴリズムについて検討し、与えられた最適化精度に到達または証明するのに必要な関数の評価の回数に関する新しい限界を証明した。
バンディット最適化の観点から分析を行い,ハンセンらによるオープンな問題を解き明かした。
\ (1991) は、与えられた精度をパッキング数のほぼ最適の和で証明する評価の個数を境界にしている。
関連論文リスト
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - Certified Multi-Fidelity Zeroth-Order Optimization [4.450536872346658]
様々な近似レベルで関数を$f$で評価できる多要素ゼロ階最適化の問題を考察する。
我々は、MFDOOアルゴリズムの証明された変種を提案し、そのコスト複雑性を任意のリプシッツ関数$f$に対して有界に導出する。
また、このアルゴリズムがほぼ最適コストの複雑さを持つことを示す$f$-dependent lower boundも証明する。
論文 参考訳（メタデータ） (2023-08-02T07:20:37Z) - Efficient Minimax Optimal Global Optimization of Lipschitz Continuous
Multivariate Functions [0.0]
我々は,このアルゴリズムがリプシッツ連続函数の地平線に対して平均的後悔O(LstnT-frac1n)$を達成することを示す。
論文 参考訳（メタデータ） (2022-06-06T06:28:38Z) - Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。
また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
論文 参考訳（メタデータ） (2022-05-05T06:43:46Z) - Non-Convex Optimization with Certificates and Fast Rates Through Kernel
Sums of Squares [68.8204255655161]
非最適化近似問題を考える。
本稿では,最優先計算を保証するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-04-11T09:37:04Z) - Low Regret Binary Sampling Method for Efficient Global Optimization of
Univariate Functions [0.0]
最適クエリと目的関数の最適値との単純な後悔ではなく,アルゴリズムの累積的後悔について検討する。
提案手法は従来の下界アルゴリズムと類似しているが,計算コストの優位性は大きい。
論文 参考訳（メタデータ） (2022-01-18T18:11:48Z) - 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) - Regret Bounds for Gaussian-Process Optimization in Large Domains [40.92207267407271]
最適化戦略から得られる解の準最適性(ベイズ的単純後悔)の上限を与える。
これらの後悔の境界は、評価の数、ドメインサイズ、および検索された関数値の最適性の関係を照らす。
特に、評価の数が小さすぎて大域的な最適値が見つからなかったとしても、非自明な関数値を見つけることができる。
論文 参考訳（メタデータ） (2021-04-29T05:19:03Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。