論文の概要: Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits

• arxiv url: http://arxiv.org/abs/2006.07862v3
• Date: Mon, 4 Apr 2022 11:02:31 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-21 12:39:18.374227
• Title: Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits
• Title（参考訳）: 微分自由最適化と連続帯域における高次平滑化
• Authors: Arya Akhavan, Massimiliano Pontil, Alexandre B. Tsybakov
• Abstract要約: 強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
• 参考スコア（独自算出の注目度）: 99.70167985955352
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of zero-order optimization of a strongly convex function. The goal is to find the minimizer of the function by a sequential exploration of its values, under measurement noise. We study the impact of higher order smoothness properties of the function on the optimization error and on the cumulative regret. To solve this problem we consider a randomized approximation of the projected gradient descent algorithm. The gradient is estimated by a randomized procedure involving two function evaluations and a smoothing kernel. We derive upper bounds for this algorithm both in the constrained and unconstrained settings and prove minimax lower bounds for any sequential search method. Our results imply that the zero-order algorithm is nearly optimal in terms of sample complexity and the problem parameters. Based on this algorithm, we also propose an estimator of the minimum value of the function achieving almost sharp oracle behavior. We compare our results with the state-of-the-art, highlighting a number of key improvements.
• Abstract（参考訳）: 強凸関数のゼロ次最適化問題について検討する。 目標は、測定ノイズの下でその値の逐次探索によって関数の最小値を求めることである。 関数の高次滑らか度特性が最適化誤差および累積後悔に与える影響について検討した。 この問題を解決するために、予測勾配降下アルゴリズムのランダム化近似を考える。 勾配は、2つの関数評価と平滑化核を含むランダム化手順によって推定される。 このアルゴリズムの上限は制約付き設定と制約なし設定の両方において導出され、任意の逐次探索法において最小下限が証明される。 その結果,ゼロ次アルゴリズムはサンプル複雑性と問題パラメータの点でほぼ最適であることが示唆された。 また,本アルゴリズムを用いて,ほぼ鋭いオラクルの挙動を達成する関数の最小値の推定器を提案する。 結果と最先端の成果を比較し、いくつかの重要な改善点を強調した。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Ordering for Non-Replacement SGD [7.11967773739707]
  我々は,アルゴリズムの非置換形式に対する収束率を改善する順序付けを求める。 我々は,強い凸関数と凸関数のステップサイズを一定かつ小さくするための最適順序付けを開発する。 さらに、注文とミニバッチを組み合わせることで、より複雑なニューラルネットワークにも適用できます。
  論文  参考訳（メタデータ） (2023-06-28T00:46:58Z)
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
  この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。 ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
  論文  参考訳（メタデータ） (2023-06-03T17:05:13Z)
• Efficient First-order Methods for Convex Optimization with Strongly Convex Function Constraints [3.667453772837954]
  強い凸関数制約を受ける凸関数を最小化する方法を示す。 有限個の結果に独立な意味を持つような空間パターンを同定する。
  論文  参考訳（メタデータ） (2022-12-21T16:04:53Z)
• An Algebraically Converging Stochastic Gradient Descent Algorithm for Global Optimization [14.336473214524663]
  アルゴリズムの主要な構成要素は、目的関数の値に基づくランダム性である。 アルゴリズムの収束を代数学で証明し、パラメータ空間でチューニングする。 アルゴリズムの効率性とロバスト性を示す数値的な例をいくつか提示する。
  論文  参考訳（メタデータ） (2022-04-12T16:27:49Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• 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)

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

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