論文の概要: A Near-Optimal Algorithm for Univariate Zeroth-Order Budget Convex Optimization

• arxiv url: http://arxiv.org/abs/2208.06720v1
• Date: Sat, 13 Aug 2022 19:57:04 GMT
• ステータス: 処理完了
• システム内更新日: 2022-08-16 14:57:22.031167
• Title: A Near-Optimal Algorithm for Univariate Zeroth-Order Budget Convex Optimization
• Title（参考訳）: 一様ゼロ階予算凸最適化のための近似アルゴリズム
• Authors: Fran\c{c}ois Bachoc, Tommaso Cesari, Roberto Colomboni, Andrea Paudice
• Abstract要約: 我々は、Dy Searchのほぼ最適最適化誤差を保証する。 誤差境界における大域リプシッツ定数への古典的依存は、予算の粒度のアーティファクトであることを示す。
• 参考スコア（独自算出の注目度）: 4.608510640547952
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies a natural generalization of the problem of minimizing a univariate convex function $f$ by querying its values sequentially. At each time-step $t$, the optimizer can invest a budget $b_t$ in a query point $X_t$ of their choice to obtain a fuzzy evaluation of $f$ at $X_t$ whose accuracy depends on the amount of budget invested in $X_t$ across times. This setting is motivated by the minimization of objectives whose values can only be determined approximately through lengthy or expensive computations. We design an any-time parameter-free algorithm called Dyadic Search, for which we prove near-optimal optimization error guarantees. As a byproduct of our analysis, we show that the classical dependence on the global Lipschitz constant in the error bounds is an artifact of the granularity of the budget. Finally, we illustrate our theoretical findings with numerical simulations.
• Abstract（参考訳）: 本稿では,不定凸関数 $f$ を逐次クエリすることで最小化する問題を自然に一般化する。 各タイムステップ$t$ に対して、オプティマイザは、選択したクエリポイント $x_t$ に予算 $b_t$ を投資して、その精度が $x_t$ に投じられた予算の量に依存する$f$ のファジィ評価を得ることができる。 この設定は、値がほぼ長さまたは高価な計算によってのみ決定できる目的の最小化によって動機づけられる。 我々はDyadic Searchと呼ばれるパラメータフリーなアルゴリズムを設計し、ほぼ最適な最適化誤差を保証する。 この分析の副産物として,誤差境界におけるグローバルリプシッツ定数に対する古典的依存は,予算の粒度の成果物であることを示す。 最後に,数値シミュレーションにより理論的知見を示す。

関連論文リスト

• Time-Varying Convex Optimization with $O(n)$ Computational Complexity [0.0]
  コスト関数が時間とともに変化する非拘束凸最適化の問題を考える。 提案アルゴリズムは,決定変数に対するコスト関数の1次微分のみを必要とする。 具体的には、提案アルゴリズムは、計算コストを1タイムステップあたり$(n3)$から$O(n)$に削減する。
  論文  参考訳（メタデータ） (2024-10-19T06:45:05Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Certified Multi-Fidelity Zeroth-Order Optimization [4.450536872346658]
  様々な近似レベルで関数を$f$で評価できる多要素ゼロ階最適化の問題を考察する。 我々は、MFDOOアルゴリズムの証明された変種を提案し、そのコスト複雑性を任意のリプシッツ関数$f$に対して有界に導出する。 また、このアルゴリズムがほぼ最適コストの複雑さを持つことを示す$f$-dependent lower boundも証明する。
  論文  参考訳（メタデータ） (2023-08-02T07:20:37Z)
• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
  リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。 私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。 非滑らかな非最適化
  論文  参考訳（メタデータ） (2023-07-10T11:56:04Z)
• Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• 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)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)

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

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