論文の概要: Efficient Minimax Optimal Global Optimization of Lipschitz Continuous Multivariate Functions

• arxiv url: http://arxiv.org/abs/2206.02383v1
• Date: Mon, 6 Jun 2022 06:28:38 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-07 15:23:33.063446
• Title: Efficient Minimax Optimal Global Optimization of Lipschitz Continuous Multivariate Functions
• Title（参考訳）: リプシッツ連続多変量関数の高効率ミニマックス最適大域最適化
• Authors: Kaan Gokcesu, Hakan Gokcesu
• Abstract要約: 我々は,このアルゴリズムがリプシッツ連続函数の地平線に対して平均的後悔O(LstnT-frac1n)$を達成することを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we propose an efficient minimax optimal global optimization algorithm for multivariate Lipschitz continuous functions. To evaluate the performance of our approach, we utilize the average regret instead of the traditional simple regret, which, as we show, is not suitable for use in the multivariate non-convex optimization because of the inherent hardness of the problem itself. Since we study the average regret of the algorithm, our results directly imply a bound for the simple regret as well. Instead of constructing lower bounding proxy functions, our method utilizes a predetermined query creation rule, which makes it computationally superior to the Piyavskii-Shubert variants. We show that our algorithm achieves an average regret bound of $O(L\sqrt{n}T^{-\frac{1}{n}})$ for the optimization of an $n$-dimensional $L$-Lipschitz continuous objective in a time horizon $T$, which we show to be minimax optimal.
• Abstract（参考訳）: 本研究では,多変量リプシッツ連続関数に対する最適最小大域最適化アルゴリズムを提案する。 提案手法の性能を評価するために,従来の単純な後悔ではなく平均的な後悔を用いることで,問題自体が本質的に困難であるため,多変量非凸最適化には適さないことを示した。 我々はアルゴリズムの平均的な後悔を研究するので、結果が単純な後悔にも結びつくことを直接示します。 提案手法は,下位境界プロキシ関数を構築する代わりに,所定のクエリ生成規則を用いて,ピヤフスキ・シュベルト変種よりも計算的に優れている。 提案アルゴリズムは, 時間的地平線上での$n$-次元$L$-Lipschitz連続目標の最適化に対して, 平均後悔境界の$O(L\sqrt{n}T^{-\frac{1}{n}})$を達成することを示す。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• 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)
• 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)
• Stochastic Bias-Reduced Gradient Methods [44.35885731095432]
  モロー・吉田関数の任意の有界な$x_star$の低バイアスで低コストな平滑化である。
  論文  参考訳（メタデータ） (2021-06-17T13:33:05Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)

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

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