論文の概要: Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity

• arxiv url: http://arxiv.org/abs/2406.19617v1
• Date: Fri, 28 Jun 2024 02:56:22 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-01 18:00:20.155435
• Title: Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity
• Title（参考訳）: 強い凸性およびリプシッツ・ヘッセン性の下での確率ゼロ階最適化:ミニマックスサンプル複素度
• Authors: Qian Yu, Yining Wang, Baihe Huang, Qi Lei, Jason D. Lee,
• Abstract要約: 本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
• 参考スコア（独自算出の注目度）: 59.75300530380427
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Optimization of convex functions under stochastic zeroth-order feedback has been a major and challenging question in online learning. In this work, we consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds. We propose an algorithm that features a combination of a bootstrapping stage and a mirror-descent stage. Our main technical innovation consists of a sharp characterization for the spherical-sampling gradient estimator under higher-order smoothness conditions, which allows the algorithm to optimally balance the bias-variance tradeoff, and a new iterative method for the bootstrapping stage, which maintains the performance for unbounded Hessian.
• Abstract（参考訳）: 確率的ゼロ次フィードバックの下での凸関数の最適化は、オンライン学習において大きな問題であり、課題となっている。 本研究では,アルゴリズムが検索対象関数のノイズ評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。 本稿では,ブートストラッピングステージとミラー・ディフレッシュステージの組み合わせを特徴とするアルゴリズムを提案する。 我々の主な技術革新は、高次滑らか度条件下での球面サンプリング勾配推定器の鋭い評価と、バイアス分散トレードオフの最適バランスと、非有界ヘッセンに対する性能を維持するブートストラッピング段階の新たな反復的手法からなる。

関連論文リスト

• Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimization [55.115992622028685]
  以前の研究は、一階法はより良い収束率(漸進収束率)をトレードオフする必要があることを示唆している。 最適複雑性と準最適収束保証の両方を、滑らかな凸最小化と滑らかな凸最小化問題に対して達成できることを実証する。
  論文  参考訳（メタデータ） (2023-10-26T19:56:52Z)
• Efficient First-order Methods for Convex Optimization with Strongly Convex Function Constraints [3.667453772837954]
  強い凸関数制約を受ける凸関数を最小化する方法を示す。 有限個の結果に独立な意味を持つような空間パターンを同定する。
  論文  参考訳（メタデータ） (2022-12-21T16:04:53Z)
• High-Dimensional Simulation Optimization via Brownian Fields and Sparse Grids [14.15772050249329]
  高次元シミュレーションの最適化は、非常に難しい。 本稿では,大域的最適解に収束する新しいサンプリングアルゴリズムを提案する。 提案アルゴリズムは,現実の典型的な代替案よりも劇的に優れていることを示す。
  論文  参考訳（メタデータ） (2021-07-19T03:03:27Z)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。 2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
  論文  参考訳（メタデータ） (2021-06-29T09:48:46Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization [25.73397307080647]
  本稿では,汎用凸あるいは非汎用機械目標の新しいモデルを提案する。 本稿では,各サブプロブレムの点レベルを徐々に緩和した制約を解くアルゴリズムを提案する。 我々は,新しい数値スケール問題の有効性を実証する。
  論文  参考訳（メタデータ） (2020-10-23T05:24:05Z)
• 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)

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

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