論文の概要: Primal Acceleration of Newton's Method
- arxiv url: http://arxiv.org/abs/2608.21359v1
- Date: Fri, 21 Aug 2026 17:59:37 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-24 14:49:32.673531
- Title: Primal Acceleration of Newton's Method
- Title（参考訳）: ニュートン法の初期加速
- Abstract要約: リプシッツ連続ヘッセンによる凸関数の最小化のための新しい直接加速ニュートン法を開発した。
このアルゴリズムは一次変数のみを使用し、反復ごとに1つの線形解のみを実行する。
提案手法は,高速なグローバルレートを維持しつつ,不正確な線形システム解法を用いて,ヘッセンフリーで実装することができる。
- 参考スコア（独自算出の注目度）: 7.919213739992464
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We develop a new direct accelerated Newton method for minimizing convex functions with Lipschitz continuous Hessian. The algorithm uses only primal variables and performs just one linear solve per iteration. With a simple predetermined choice of parameters, it achieves the global convergence rate of $O(1/k^3)$ in terms of the functional residual. To the best of our knowledge, this is the first second-order method for this problem class attaining this rate while relying solely on one linear system solve per iteration (without solving auxiliary nonlinear regularized subproblems, such as cubic regularization, performing nonlinear parameter searches, or using dual extragradient corrections). Our method can be implemented in a Hessian-free way, using an inexact linear system solver, while preserving the fast global rate. We further extend our construction to arbitrary geometry through Bregman divergence, and to composite optimization problems.
- Abstract（参考訳）: リプシッツ連続ヘッセンによる凸関数の最小化のための新しい直接加速ニュートン法を開発した。
このアルゴリズムは一次変数のみを使用し、反復ごとに1つの線形解のみを実行する。
パラメータの単純な所定の選択により、関数的残差の観点で、大域収束率$O(1/k^3)を達成できる。
我々の知る限り、これは1イテレーションごとに1つの線形系を解くことのみに頼りながら、この率を達成するための最初の2階法である(3次正則化、非線形パラメータ探索の実行、および2次外向き補正などの補助非線形正則化サブプロブレムを解くことなく)。
提案手法は,高速なグローバルレートを維持しつつ,不正確な線形システム解法を用いて,ヘッセンフリーで実装することができる。
さらに、ブレグマンの発散による任意の幾何や合成最適化問題にも拡張する。
関連論文リスト
- Learning features from Newton's algorithm: a way to accelerate nonlinear parametrized PDE solvers [1.5749416770494706]
ニュートンの法則は、最初の推測が非線形方程式系の根に近づくとより早く収束することが知られている。
本稿では、パラメータ空間サンプリングと事前計算された解のデータベースから特徴を学習することで、2段階のニュートン初期推定戦略を提案する。
論文 参考訳（メタデータ） (2026-07-30T11:18:30Z) - A Parameter-Free First-Order Algorithm for Non-Convex Optimization with $\tilde{\mkern1mu O}(ε^{-5/3})$ Global Rate [0.12744523252873352]
PF-AGDはパラメータフリーで高速化された最初の1次法で、スムーズな非ログ目的に対して$O(-5)$複雑性を実現する。
論文 参考訳（メタデータ） (2026-05-04T01:17:06Z) - Symmetric Rank-One Quasi-Newton Methods for Deep Learning Using Cubic Regularization [0.5120567378386615]
アダムやアダグラッドのような一階降下や他の一階変種は、ディープラーニングの分野で一般的に使われている。
しかし、これらの手法は曲率情報を活用しない。
準ニュートン法は、以前計算された低ヘッセン近似を再利用する。
論文 参考訳（メタデータ） (2025-02-17T20:20:11Z) - Alternating Iteratively Reweighted $\ell_1$ and Subspace Newton Algorithms for Nonconvex Sparse Optimization [11.56128809794923]
本稿では,可微分損失関数と非滑らか正規化関数の和を最小化する新しいハイブリッドアルゴリズムを提案する。
臨界点へのグローバル収束を証明し、適切な条件下では、アルゴリズムが既存の手法より優れていることを示す。
論文 参考訳（メタデータ） (2024-07-24T12:15:59Z) - First and zeroth-order implementations of the regularized Newton method
with lazy approximated Hessians [4.62316736194615]
我々は一般の非自由$ノルムフリー問題のリップオーダー(ヘシアン-O)とゼロオーダー(微分自由)の実装を開発する。
また、アルゴリズムに遅延バウンダリ更新を加えて、これまで計算されたヘッセン近似行列を数回繰り返し再利用する。
論文 参考訳（メタデータ） (2023-09-05T17:40:54Z) - Constrained Optimization via Exact Augmented Lagrangian and Randomized
Iterative Sketching [55.28394191394675]
等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。
ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
論文 参考訳（メタデータ） (2023-05-28T06:33:37Z) - Second-order optimization with lazy Hessians [55.51077907483634]
一般の非線形最適化問題を解くためにニュートンの遅延ヘッセン更新を解析する。
我々は、メソッドの各ステップで新しい勾配を計算しながら、これまで見られたヘッセン反復を再利用する。
論文 参考訳（メタデータ） (2022-12-01T18:58:26Z) - Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なNewton型手法をいくつか提案し,解析する。
提案手法は,Sur分解の必要回数の$O(log(1/eps)$因子をシェービングすることで,既存のライン検索に基づくmin-max最適化を改善する。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Super-Universal Regularized Newton Method [14.670197265564196]
第二導関数あるいは第三導関数のH"古い連続性によって特徴づけられる問題クラスの族を導入する。
本稿では,問題クラスに最適な大域的複雑性境界を持つ自動調整を行うための,簡単な適応探索手法を提案する。
論文 参考訳（メタデータ） (2022-08-11T15:44:56Z) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文 参考訳（メタデータ） (2022-05-27T00:34:03Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。