論文の概要: Curvature-Aware Derivative-Free Optimization

• arxiv url: http://arxiv.org/abs/2109.13391v2
• Date: Wed, 12 Apr 2023 04:55:01 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-13 19:30:32.944453
• Title: Curvature-Aware Derivative-Free Optimization
• Title（参考訳）: 曲率アウェアデリバティブフリー最適化
• Authors: Bumsu Kim, HanQin Cai, Daniel McKenzie, Wotao Yin
• Abstract要約: ゼロ階法におけるステップサイズ$alpha_k$の選択に焦点を当てた。 提案手法は、Curvature-Aware Random Search (CARS) と呼ばれ、一階と二階の差分近似を用いる。 本研究では, 強凸目的関数に対して, 探索方向が極めて穏やかな条件を満たす分布から引き出されることを条件として, CARSが線形収束することを証明した。 また、CARS の立方正規化変種である CARS-CR も、仮定なしで$mathcalO(k-1)$ の速度で収束する。
• 参考スコア（独自算出の注目度）: 29.26506668095518
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The paper discusses derivative-free optimization (DFO), which involves minimizing a function without access to gradients or directional derivatives, only function evaluations. Classical DFO methods, which mimic gradient-based methods, such as Nelder-Mead and direct search have limited scalability for high-dimensional problems. Zeroth-order methods have been gaining popularity due to the demands of large-scale machine learning applications, and the paper focuses on the selection of the step size $\alpha_k$ in these methods. The proposed approach, called Curvature-Aware Random Search (CARS), uses first- and second-order finite difference approximations to compute a candidate $\alpha_{+}$. We prove that for strongly convex objective functions, CARS converges linearly provided that the search direction is drawn from a distribution satisfying very mild conditions. We also present a Cubic Regularized variant of CARS, named CARS-CR, which converges in a rate of $\mathcal{O}(k^{-1})$ without the assumption of strong convexity. Numerical experiments show that CARS and CARS-CR match or exceed the state-of-the-arts on benchmark problem sets.
• Abstract（参考訳）: 本稿では、勾配や方向微分へのアクセスを伴わない関数の最小化を伴う微分自由最適化(DFO)について論じる。 Nelder-Meadやダイレクトサーチといった勾配に基づく手法を模倣した古典的なDFO法は、高次元問題に対するスケーラビリティを制限している。 大規模機械学習アプリケーションの需要により,ゼロオーダー法が人気を集めており,本研究ではステップサイズ$\alpha_k$を選択することに焦点を当てている。 提案手法はCurvature-Aware Random Search (CARS) と呼ばれ, 1階と2階の差分近似を用いて候補の$\alpha_{+}$を計算する。 強凸対象関数に対しては, 探索方向が極めて穏やかな条件を満たす分布から引き出されるように, 車体が線形収束することを示す。 また、CARS の立方正規化変種である CARS-CR も、強い凸性の仮定なしで$\mathcal{O}(k^{-1})$ の速度で収束する。 数値実験により、CARSとCARS-CRは、ベンチマーク問題セットの最先端と一致するか、あるいは超えることを示した。

関連論文リスト

• Fast Unconstrained Optimization via Hessian Averaging and Adaptive Gradient Sampling Methods [0.3222802562733786]
  ヘシアン・アブラッシングに基づくサブサンプルニュートン法による有限サム予測対象関数の最小化について検討する。 これらの方法は不有効であり、ヘッセン近似の固定コストがかかる。 本稿では,新しい解析手法を提案し,その実用化に向けた課題を提案する。
  論文  参考訳（メタデータ） (2024-08-14T03:27:48Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• A simple uniformly optimal method without line search for convex optimization [9.280355951055865]
  パラメータが優先されていない凸最適化問題の解法として最適収束率を得るには,線探索が過剰であることを示す。 滑らかな凸最適化のために最適な$mathcalO (1/k2)$収束率を達成できるAC-FGMと呼ばれる新しい勾配降下型アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-16T05:26:03Z)
• Orthogonal Directions Constrained Gradient Method: from non-linear equality constraints to Stiefel manifold [16.099883128428054]
  直交方向制約法(ODCGM)という新しいアルゴリズムを提案する。 ODCGMはベクトル空間へのプロジェクションのみを必要とする。 以上より, ODCGMは, ほぼ最適のオラクル複合体を呈することを示した。
  論文  参考訳（メタデータ） (2023-03-16T12:25:53Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• DRSOM: A Dimension Reduced Second-Order Method [13.778619250890406]
  信頼的な枠組みの下では,2次法の収束を保ちながら,数方向の情報のみを用いる。 理論的には,この手法は局所収束率と大域収束率が$O(epsilon-3/2)$であり,第1次条件と第2次条件を満たすことを示す。
  論文  参考訳（メタデータ） (2022-07-30T13:05:01Z)
• Accelerated first-order methods for convex optimization with locally Lipschitz continuous gradient [0.0]
  まず,Lipschitz連続勾配 (LLCG) を用いた非拘束凸最適化について検討し,それを解決するための加速近位勾配 (APG) 法を提案する。 提案手法は検証可能な終端基準を備えており、演算複雑性は$cal O(varepsilon-1/2log varepsilon-1)$である。 提案手法の性能を実証するために,予備的な数値計算結果を示す。
  論文  参考訳（メタデータ） (2022-06-02T10:34:26Z)
• 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)
• 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)

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

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