論文の概要: Regret Analysis of Global Optimization in Univariate Functions with Lipschitz Derivatives

• arxiv url: http://arxiv.org/abs/2108.10859v1
• Date: Tue, 24 Aug 2021 17:36:33 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-25 14:07:39.432792
• Title: Regret Analysis of Global Optimization in Univariate Functions with Lipschitz Derivatives
• Title（参考訳）: リプシッツ誘導体を用いた一変量関数の大域的最適化の回帰解析
• Authors: Kaan Gokcesu, Hakan Gokcesu
• Abstract要約: 関数の異なるクラスに対して満足な累積的後悔境界を達成できることが示される。 我々は、リプシッツ連続函数と滑らか函数の両方を個別にカバーするより広範な関数のクラスについて、解析的に結果を拡張した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we study the problem of global optimization in univariate loss functions, where we analyze the regret of the popular lower bounding algorithms (e.g., Piyavskii-Shubert algorithm). For any given time $T$, instead of the widely available simple regret (which is the difference of the losses between the best estimation up to $T$ and the global optimizer), we study the cumulative regret up to that time. With a suitable lower bounding algorithm, we show that it is possible to achieve satisfactory cumulative regret bounds for different classes of functions. For Lipschitz continuous functions with the parameter $L$, we show that the cumulative regret is $O(L\log T)$. For Lipschitz smooth functions with the parameter $H$, we show that the cumulative regret is $O(H)$. We also analytically extend our results for a broader class of functions that covers both the Lipschitz continuous and smooth functions individually.
• Abstract（参考訳）: 本研究では,不定損失関数における大域的最適化の問題について検討し,一般的な下限アルゴリズム(例えばpiyavskii-shubertアルゴリズム)の後悔を分析する。 任意の時間に$T$(これは最高の見積とグローバルオプティマイザの間の損失の差である)という広く利用可能な単純な後悔の代わりに、累積的後悔をその時点まで調査する。 適切な下限アルゴリズムを用いることで、異なる関数のクラスに対して満足のいく累積後悔境界を実現できることを示す。 パラメータ $L$ を持つリプシッツ連続函数に対して、累積後悔は$O(L\log T)$であることを示す。 パラメータ $H$ を持つ滑らかなリプシッツ函数に対して、累積後悔は $O(H)$ であることを示す。 また、リプシッツ連続函数と滑らか函数の両方を個別にカバーするより広範な関数のクラスについて解析的に結果を拡張する。

関連論文リスト

• 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)

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

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