論文の概要: Cumulative Regret Analysis of the Piyavskii--Shubert Algorithm and Its
Variants for Global Optimization
- arxiv url: http://arxiv.org/abs/2108.10859v2
- Date: Thu, 28 Dec 2023 16:37:20 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-30 00:06:01.396207
- Title: Cumulative Regret Analysis of the Piyavskii--Shubert Algorithm and Its
Variants for Global Optimization
- Title（参考訳）: Piyavskii-Shubertアルゴリズムの累積回帰解析と大域最適化のための変数
- Authors: Kaan Gokcesu, Hakan Gokcesu
- Abstract要約: We study the problem of global optimization, where we analyze the performance of the Piyavskii-Shubert algorithm and its variants。
その結果,提案アルゴリズムはクエリを効率よく決定し,最小限の(ログファクタまで)累積的後悔を実現する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of global optimization, where we analyze the performance
of the Piyavskii--Shubert algorithm and its variants. For any given time
duration $T$, instead of the extensively studied simple regret (which is the
difference of the losses between the best estimate up to $T$ and the global
minimum), we study the cumulative regret up to time $T$. For $L$-Lipschitz
continuous functions, we show that the cumulative regret is $O(L\log T)$. For
$H$-Lipschitz smooth functions, we show that the cumulative regret is $O(H)$.
We analytically extend our results for functions with Holder continuous
derivatives, which cover both the Lipschitz continuous and the Lipschitz smooth
functions, individually. We further show that a simpler variant of the
Piyavskii-Shubert algorithm performs just as well as the traditional variants
for the Lipschitz continuous or the Lipschitz smooth functions. We further
extend our results to broader classes of functions, and show that, our
algorithm efficiently determines its queries; and achieves nearly minimax
optimal (up to log factors) cumulative regret, for general convex or even
concave regularity conditions on the extrema of the objective (which
encompasses many preceding regularities). We consider further extensions by
investigating the performance of the Piyavskii-Shubert variants in the
scenarios with unknown regularity, noisy evaluation and multivariate domain.
- Abstract（参考訳）: 本研究では,piyavskii-shubertアルゴリズムとその変種の性能を解析し,大域的最適化の問題について検討する。
与えられた期間の任意の$T$に対して、広範囲に研究された単純な後悔(これは、最良の見積もりとグローバルな最小値の間の損失の差である)の代わりに、累積的後悔を時間$T$まで調べる。
L$-Lipschitz連続函数に対して、累積後悔は$O(L\log T)$であることを示す。
H$-Lipschitz の滑らかな函数に対して、累積後悔は$O(H)$であることを示す。
リプシッツ連続関数とリプシッツ滑らか関数の両方をカバーするホルダー連続微分関数について解析的に結果を拡張した。
さらに,piyavskii-shubertアルゴリズムの単純変種は,従来のリプシッツ連続関数やリプシッツ滑らか関数の変種と同様に動作することを示した。
我々はさらに,より広い関数のクラスに結果を拡張し,そのクエリを効率的に決定し,目的の極端(前述した多くの正規性を含む)上の一般凸あるいは凹凸正規性条件に対して,最小の最適(ログ係数まで)累積的後悔を達成することを示す。
我々は,未知の規則性,雑音評価,多変量領域におけるpiyavskii-shubert変種の性能について検討することで,さらなる拡張を検討する。
関連論文リスト
- 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) - On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。
本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
論文 参考訳（メタデータ） (2023-05-30T17:47:27Z) - 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) - A Near-Optimal Algorithm for Univariate Zeroth-Order Budget Convex
Optimization [4.608510640547952]
我々は、Dy Searchのほぼ最適最適化誤差を保証する。
誤差境界における大域リプシッツ定数への古典的依存は、予算の粒度のアーティファクトであることを示す。
論文 参考訳（メタデータ） (2022-08-13T19:57:04Z) - Efficient Minimax Optimal Global Optimization of Lipschitz Continuous
Multivariate Functions [0.0]
我々は,このアルゴリズムがリプシッツ連続函数の地平線に対して平均的後悔O(LstnT-frac1n)$を達成することを示す。
論文 参考訳（メタデータ） (2022-06-06T06:28:38Z) - Low Regret Binary Sampling Method for Efficient Global Optimization of
Univariate Functions [0.0]
最適クエリと目的関数の最適値との単純な後悔ではなく,アルゴリズムの累積的後悔について検討する。
提案手法は従来の下界アルゴリズムと類似しているが,計算コストの優位性は大きい。
論文 参考訳（メタデータ） (2022-01-18T18:11:48Z) - 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) - SGD with shuffling: optimal rates without component convexity and large
epoch requirements [60.65928290219793]
我々はRandomShuffle(各エポックの開始時のシャッフル)とSingleShuffle(1回だけシャッフル)を考える。
我々はこれらのアルゴリズムの最小収束速度をポリログ係数ギャップまで確立する。
我々は、すべての先行芸術に共通する欠点を取り除くことにより、RandomShuffleの厳密な収束結果をさらに強化する。
論文 参考訳（メタデータ） (2020-06-12T05:00:44Z) - Regret analysis of the Piyavskii-Shubert algorithm for global Lipschitz
optimization [1.6822770693792826]
ピヤフスキとシュベルトによって1972年に考案された自然アルゴリズムについて研究する。
我々は、与えられた最適化精度に到達または証明するために必要な関数の評価数に関する新しい境界を証明した。
論文 参考訳（メタデータ） (2020-02-06T17:31:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。