論文の概要: Fast Unconstrained Optimization via Hessian Averaging and Adaptive Gradient Sampling Methods

• arxiv url: http://arxiv.org/abs/2408.07268v1
• Date: Wed, 14 Aug 2024 03:27:48 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-15 14:25:39.945987
• Title: Fast Unconstrained Optimization via Hessian Averaging and Adaptive Gradient Sampling Methods
• Title（参考訳）: ヘッセン平均化と適応型勾配サンプリング法による高速非拘束最適化
• Authors: Thomas O'Leary-Roseberry, Raghu Bollapragada,
• Abstract要約: ヘシアン・アブラッシングに基づくサブサンプルニュートン法による有限サム予測対象関数の最小化について検討する。 これらの方法は不有効であり、ヘッセン近似の固定コストがかかる。 本稿では,新しい解析手法を提案し,その実用化に向けた課題を提案する。
• 参考スコア（独自算出の注目度）: 0.3222802562733786
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider minimizing finite-sum and expectation objective functions via Hessian-averaging based subsampled Newton methods. These methods allow for gradient inexactness and have fixed per-iteration Hessian approximation costs. The recent work (Na et al. 2023) demonstrated that Hessian averaging can be utilized to achieve fast $\mathcal{O}\left(\sqrt{\tfrac{\log k}{k}}\right)$ local superlinear convergence for strongly convex functions in high probability, while maintaining fixed per-iteration Hessian costs. These methods, however, require gradient exactness and strong convexity, which poses challenges for their practical implementation. To address this concern we consider Hessian-averaged methods that allow gradient inexactness via norm condition based adaptive-sampling strategies. For the finite-sum problem we utilize deterministic sampling techniques which lead to global linear and sublinear convergence rates for strongly convex and nonconvex functions respectively. In this setting we are able to derive an improved deterministic local superlinear convergence rate of $\mathcal{O}\left(\tfrac{1}{k}\right)$. For the %expected risk expectation problem we utilize stochastic sampling techniques, and derive global linear and sublinear rates for strongly convex and nonconvex functions, as well as a $\mathcal{O}\left(\tfrac{1}{\sqrt{k}}\right)$ local superlinear convergence rate, all in expectation. We present novel analysis techniques that differ from the previous probabilistic results. Additionally, we propose scalable and efficient variations of these methods via diagonal approximations and derive the novel diagonally-averaged Newton (Dan) method for large-scale problems. Our numerical results demonstrate that the Hessian averaging not only helps with convergence, but can lead to state-of-the-art performance on difficult problems such as CIFAR100 classification with ResNets.
• Abstract（参考訳）: 我々はヘシアン・アブラッシングに基づくサブサンプルニュートン法による有限サム関数と期待対象関数の最小化を検討する。 これらの手法は勾配の不等式を許容し、ヘッセン近似の固定コストを持つ。 最近の研究 (Na et al 2023) では、ヘッセン平均化は高速な$\mathcal{O}\left(\sqrt {\tfrac {\log k}{k}}\right)$局所超線型収束を高い確率で実現し、固定された点当たりのヘッセンコストを維持できることを示した。 しかし、これらの手法は勾配の正確さと強い凸性を必要とし、実際的な実装に挑戦する。 この問題に対処するために、標準条件に基づく適応サンプリング戦略を通した勾配不完全性を許容するヘッセン平均法を考える。 有限サム問題に対して、強い凸関数と非凸関数に対する大域線型収束率と部分線型収束率をもたらす決定論的サンプリング手法を用いる。 この設定では、改善された決定論的局所超線型収束率$\mathcal{O}\left(\tfrac{1}{k}\right)$を導出することができる。 %予測されるリスク予測問題に対して、確率的サンプリング手法を用い、強い凸関数と非凸関数に対する大域線型および部分線型率を導出し、$\mathcal{O}\left(\tfrac{1}{\sqrt{k}}\right)$局所超線型収束率を期待して導出する。 本稿では,従来の確率的結果とは異なる新しい解析手法を提案する。 さらに, 対角近似を用いて, これらの手法のスケーラブルかつ効率的なバリエーションを提案し, 大規模問題に対する新しい対角平均ニュートン法(Dan)を導出する。 数値計算の結果,ヘッセン平均化は収束の助けとなるだけでなく,CIFAR100 の ResNets を用いた分類のような難解な問題に対して,最先端の性能をもたらす可能性が示唆された。

関連論文リスト

• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。 特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
  論文  参考訳（メタデータ） (2024-09-23T13:11:37Z)
• An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizes [17.804065824245402]
  機械学習の応用では、各損失関数は非負であり、平方根とその実数値平方根の構成として表すことができる。 本稿では, ガウス・ニュートン法やレフスカルト法を適用して, 滑らかだが非負な関数の平均を最小化する方法を示す。
  論文  参考訳（メタデータ） (2024-07-05T08:53:06Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Robust Stochastic Optimization via Gradient Quantile Clipping [6.2844649973308835]
  グラディエントDescent(SGD)のための量子クリッピング戦略を導入する。 通常のクリッピングチェーンとして、グラデーション・ニュー・アウトリージを使用します。 本稿では,Huberiles を用いたアルゴリズムの実装を提案する。
  論文  参考訳（メタデータ） (2023-09-29T15:24:48Z)
• Variance reduction techniques for stochastic proximal point algorithms [5.374800961359305]
  そこで本研究では,近点アルゴリズムにおける分散低減手法の統一化研究を提案する。 我々は,SVRG,SAGA,およびそれらの変種の近位バージョンを提供するために特定可能な,汎用的近位アルゴリズムを提案する。 本実験は, 勾配法よりも近似分散還元法の利点を実証する。
  論文  参考訳（メタデータ） (2023-08-18T05:11:50Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。 ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
  論文  参考訳（メタデータ） (2023-05-28T06:33:37Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods [26.328847475942894]
  準ニュートンアルゴリズムのブロイデン級の非漸近超線型収束速度を証明した。 この結果は, 準ニュートン法に対する非漸近超線形収束率を示すのが最初である。
  論文  参考訳（メタデータ） (2020-03-30T16:42:41Z)

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

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