論文の概要: Inference of Online Newton Methods with Nesterov's Accelerated Sketching

• arxiv url: http://arxiv.org/abs/2604.23436v1
• Date: Sat, 25 Apr 2026 20:43:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-28 17:12:07.338162
• Title: Inference of Online Newton Methods with Nesterov's Accelerated Sketching
• Title（参考訳）: Nesterovの高速化スケッチによるオンラインニュートン法の評価
• Authors: Haoxuan Wang, Xinchen Du, Sen Na,
• Abstract要約: 本稿では,ネステロフの加速度を用いたスケッチ・アンド・プロジェクト・ソルバを用いて,各ステップのニュートン方向を概算するヘッセン平均化を用いたオンラインニュートン法について検討する。 標準的な滑らかさとモーメント条件の下では、大域的概日収束を確立し、リアプノフ方程式による最後の反復の正規性を証明する。 また、ネステロフの加速度を伴わない正確かつスケッチされたニュートン法と結果の不確かさの定量化を結び付ける。
• 参考スコア（独自算出の注目度）: 4.1061984975990695
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reliable decision-making with streaming data requires principled uncertainty quantification of online methods. While first-order methods enable efficient iterate updates, their inference procedures still require updating proper (covariance) matrices, incurring $O(d^2)$ time and memory complexity, and are sensitive to ill-conditioning and noise heterogeneity of the problem. This costly inference task offers an opportunity for more robust second-order methods, which are, however, bottlenecked by solving Newton systems with $O(d^3)$ complexity. In this paper, we address this gap by studying an online Newton method with Hessian averaging, where the Newton direction at each step is approximately computed using a sketch-and-project solver with Nesterov's acceleration, matching $O(d^2)$ complexity of first-order methods. For the proposed method, we quantify its uncertainty arising from both random data and randomized computation. Under standard smoothness and moment conditions, we establish global almost-sure convergence, prove asymptotic normality of the last iterate with a limiting covariance characterized by a Lyapunov equation, and develop a fully online covariance estimator with non-asymptotic convergence guarantees. We also connect the resulting uncertainty quantification to that of exact and sketched Newton methods without Nesterov's acceleration. Extensive experiments on regression models demonstrate the superiority of the proposed method for online inference.
• Abstract（参考訳）: ストリーミングデータによる信頼性の高い意思決定には、オンライン手法の原理的な不確実性定量化が必要である。 一階法は効率的な反復更新を可能にするが、推論手順には適切な(共分散)行列の更新が必要であり、時間とメモリの複雑さは$O(d^2)であり、問題の条件やノイズの不均一性に敏感である。 このコストのかかる推論タスクは、より堅牢な2階法のための機会を提供するが、しかしながら、$O(d^3)$複雑さを持つニュートン系を解くことでボトルネックとなる。 本稿では,Nesterovの加速度によるスケッチ・アンド・プロジェクト・ソルバを用いて各ステップのニュートン方向を近似計算し,一階法の複雑さを$O(d^2)$とすることで,このギャップを解消する。 提案手法では,ランダムデータとランダム化計算の両方から生じる不確実性を定量化する。 標準の滑らかさとモーメント条件の下では、大域的な概日収束を確立し、リアプノフ方程式によって特徴づけられる限定共分散で最後の反復の漸近正規性を証明し、非漸近収束を保証する完全オンライン共分散推定器を開発する。 また、ネステロフの加速度を伴わない正確かつスケッチされたニュートン法と結果の不確かさの定量化を結び付ける。 回帰モデルに対する大規模な実験は,オンライン推論における提案手法の優位性を実証している。

関連論文リスト

• Refining Covariance Matrix Estimation in Stochastic Gradient Descent Through Bias Reduction [9.294518380204154]
  勾配降下(SGD)アルゴリズムのオンライン推論と共分散推定について検討する。 提案手法は,既存のヘッセン自由代替品よりも優れた収差率$n(-1)/2 sqrtlog n$を達成するために,バイアス低減手法を用いている。
  論文  参考訳（メタデータ） (2026-04-23T01:48:08Z)
• VFOG: Variance-Reduced Fast Optimistic Gradient Methods for a Class of Nonmonotone Generalized Equations [3.6997773420183866]
  我々は,Nesterovの加速度と分散還元技術を組み合わせた,新しい楽観的勾配型アルゴリズムフレームワークを開発した。 この手法はリプシッツ連続性の下で残余の平方ノルムを期待して$mathcalO (1/k2)$収束率を達成することを示す。 提案手法の反復列は根本問題の解にほぼ確実に収束することを示す。
  論文  参考訳（メタデータ） (2025-08-22T20:46:29Z)
• Variance-Reduced Fast Operator Splitting Methods for Generalized Equations [8.0153031008486]
  一般化方程式のクラスの解を近似する2つの分散還元高速演算子分割法を開発した。 提案手法は, 加速演算子分割法, 固定点法, 共高調波性, 分散低減の最近の進歩を取り入れたものである。
  論文  参考訳（メタデータ） (2025-04-17T16:02:20Z)
• Online Covariance Matrix Estimation in Sketched Newton Methods [7.441891256588546]
  ランダム化されたスケッチ技術を利用して各イテレーションで近似したニュートンステップを実行するオンラインスケッチNewton法について検討する。 また、制約された問題に対する推定器の拡張についても論じ、回帰問題に対する優れた性能を示す。
  論文  参考訳（メタデータ） (2025-02-10T23:11:02Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• 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)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Fast Projected Newton-like Method for Precision Matrix Estimation under Total Positivity [15.023842222803058]
  現在のアルゴリズムはブロック座標降下法や近点アルゴリズムを用いて設計されている。 本稿では,2次元投影法に基づく新しいアルゴリズムを提案し,慎重に設計された探索方向と変数分割方式を取り入れた。 合成および実世界のデータセットに対する実験結果から,提案アルゴリズムは最先端の手法と比較して計算効率を著しく向上させることを示した。
  論文  参考訳（メタデータ） (2021-12-03T14:39:10Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)

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

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