論文の概要: Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function

• arxiv url: http://arxiv.org/abs/2310.11866v1
• Date: Wed, 18 Oct 2023 10:29:58 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-19 16:55:40.094478
• Title: Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function
• Title（参考訳）: ヘッセン行列, 勾配, 関数を含む非凸問題に対する確率的最適化
• Authors: Liu Liu, Xuanqing Liu, Cho-Jui Hsieh, and Dacheng Tao
• Abstract要約: 信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
• 参考スコア（独自算出の注目度）: 99.31457740916815
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Trust-region (TR) and adaptive regularization using cubics (ARC) have proven to have some very appealing theoretical properties for non-convex optimization by concurrently computing function value, gradient, and Hessian matrix to obtain the next search direction and the adjusted parameters. Although stochastic approximations help largely reduce the computational cost, it is challenging to theoretically guarantee the convergence rate. In this paper, we explore a family of stochastic TR and ARC methods that can simultaneously provide inexact computations of the Hessian matrix, gradient, and function values. Our algorithms require much fewer propagations overhead per iteration than TR and ARC. We prove that the iteration complexity to achieve $\epsilon$-approximate second-order optimality is of the same order as the exact computations demonstrated in previous studies. Additionally, the mild conditions on inexactness can be met by leveraging a random sampling technology in the finite-sum minimization problem. Numerical experiments with a non-convex problem support these findings and demonstrate that, with the same or a similar number of iterations, our algorithms require less computational overhead per iteration than current second-order methods.
• Abstract（参考訳）: 立方体を用いた信頼領域(TR)と適応正則化(ARC)は、次の探索方向と調整されたパラメータを得るために、関数値、勾配、およびヘッセン行列を同時に計算することで、非凸最適化のための非常に魅力的な理論的特性を持つことが証明されている。 確率近似は計算コストを大幅に削減するが、理論的に収束率を保証することは困難である。 本稿では,ヘッセン行列,勾配,関数値の非コンパクトな計算を同時に行うことのできる確率的TR法とARC法のファミリーを探索する。 我々のアルゴリズムはTRやARCよりも1イテレーションあたりの伝搬オーバーヘッドをはるかに少なくする。 近似二階最適性を達成するためのイテレーションの複雑さは、以前の研究で示された正確な計算と同じ順序であることが証明される。 さらに、有限サム最小化問題におけるランダムサンプリング技術を活用することで、不完全性に関する穏やかな条件を満たすことができる。 非凸問題による数値実験はこれらの結果を支持し、同じあるいは類似の反復数で、我々のアルゴリズムは現在の2次法よりも反復当たりの計算オーバーヘッドを少なくすることを示した。

関連論文リスト

• Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization [26.36906884097317]
  我々は,リプシッツ,凸関数を次数次オラクルで最小化するための新しい並列アルゴリズムを開発した。 その結果,最もよく知られた問合せ深度と並列アルゴリズムの最もよく知られた計算深度とのギャップを埋めることができた。
  論文  参考訳（メタデータ） (2024-06-11T15:41:48Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Reducing the Variance of Gaussian Process Hyperparameter Optimization with Preconditioning [54.01682318834995]
  プレコンディショニングは、行列ベクトル乗算を含む反復的な方法にとって非常に効果的なステップである。 プレコンディショニングには、これまで検討されていなかった付加的なメリットがあることを実証する。 基本的に無視可能なコストで、同時に分散を低減することができる。
  論文  参考訳（メタデータ） (2021-07-01T06:43:11Z)
• Slowly Varying Regression under Sparsity [5.22980614912553]
  本稿では, 緩やかな過度回帰の枠組みを提示し, 回帰モデルが緩やかかつスパースな変動を示すようにした。 本稿では,バイナリ凸アルゴリズムとして再構成する手法を提案する。 結果として得られたモデルは、様々なデータセット間で競合する定式化よりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-02-22T04:51:44Z)
• Practical Precoding via Asynchronous Stochastic Successive Convex Approximation [8.808993671472349]
  凸非平滑正規化器を用いた滑らかな非研究損失関数の最適化について検討する。 本研究では、SCAアルゴリズムを詳しく検討し、無線ネットワークにおけるリソース割り当てのための非同期版を開発する。
  論文  参考訳（メタデータ） (2020-10-03T13:53:30Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
  本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。 その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
  論文  参考訳（メタデータ） (2020-06-24T07:40:31Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)

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

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