論文の概要: Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling
- arxiv url: http://arxiv.org/abs/2609.12421v1
- Date: Fri, 11 Sep 2026 04:16:59 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-15 07:38:31.620455
- Title: Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling
- Title（参考訳）: ランダムスケーリングによる高速化されたスケッチ・アンド・プロジェクトによるニュートン手法の推論
- Abstract要約: 最新のスケッチ解法を用いて,各ステップのニュートン方向を近似したオンラインスケッチNewton法について検討した。
ランダムスケーリングに基づくオンライン推論手法を開発した。
- 参考スコア（独自算出の注目度）: 2.555435670606531
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study an online sketched Newton method that approximates the Newton direction at each step via a state-of-the-art sketching solver, called the generalized accelerated sketch-and-project solver (GAS), thereby mitigating the computational bottleneck of classical second-order methods. The GAS solver improves upon vanilla, unaccelerated sketch-and-project solvers by achieving accelerated convergence through Nesterov momentum updates, and accommodates a flexible projection metric whose proper choice further reduces computational cost. Building on this design, we establish asymptotic normality of the averaged sketched Newton iterates and characterize their limiting covariance matrix. The resulting covariance recovers that of the unaccelerated sketched Newton method under a specific choice of acceleration parameters, converges more rapidly (in the number of sketching steps) to the minimax-optimal covariance in general, and is smaller than that of the last iterate produced by the accelerated method. Finally, we strengthen these results by establishing a functional central limit theorem for the Newton iterates, which allows us to bypass explicit covariance estimation and develop an online inference procedure based on random scaling. Specifically, we construct a pivotal test statistic by appropriately rescaling the averaged iterates, so that its limiting distribution is free of any unknown parameters, enabling asymptotically valid online inference. Numerical experiments demonstrate superior performance of the proposed inference procedure.
- Abstract（参考訳）: 本稿では,従来の2次手法の計算ボトルネックを軽減するために,GAS (GeneralizedAccelerated sketch-and-project solver) と呼ばれる,最先端のスケッチ解法を用いて各ステップのニュートン方向を近似するオンラインスケッチNewton法について検討する。
GASソルバは、ネステロフ運動量更新による加速収束を達成することにより、バニラ、非加速スケッチ・アンド・プロジェクト・ソルバを改善し、適切な選択が計算コストをさらに削減するフレキシブル・プロジェクション・メトリックを適合させる。
この設計に基づいて、平均スケッチされたニュートンイテレートの漸近正規性を確立し、それらの制限共分散行列を特徴づける。
得られた共分散は、加速度パラメータの特定の選択の下で非加速スケッチニュートン法を回復し、より高速(スケッチステップの数)で最小値-最適共分散に収束し、加速された方法によって生成された最後の繰り返しよりも小さい。
最後に、ニュートンイテレートの関数的中心極限定理を確立し、明示的な共分散推定を回避し、ランダムスケーリングに基づくオンライン推論手順を開発することにより、これらの結果を強化する。
具体的には、平均的な反復を適切に再スケーリングすることにより、その制限分布が未知のパラメータを含まないようにし、漸近的に有効なオンライン推論を可能にする。
数値実験により提案手法の優れた性能を示す。
関連論文リスト
- Inference of Online Newton Methods with Nesterov's Accelerated Sketching [4.1061984975990695]
本稿では,ネステロフの加速度を用いたスケッチ・アンド・プロジェクト・ソルバを用いて,各ステップのニュートン方向を概算するヘッセン平均化を用いたオンラインニュートン法について検討する。
標準的な滑らかさとモーメント条件の下では、大域的概日収束を確立し、リアプノフ方程式による最後の反復の正規性を証明する。
また、ネステロフの加速度を伴わない正確かつスケッチされたニュートン法と結果の不確かさの定量化を結び付ける。
論文 参考訳（メタデータ） (2026-04-25T20:43:17Z) - Online Covariance Matrix Estimation in Sketched Newton Methods [7.441891256588546]
ランダム化されたスケッチ技術を利用して各イテレーションで近似したニュートンステップを実行するオンラインスケッチNewton法について検討する。
また、制約された問題に対する推定器の拡張についても論じ、回帰問題に対する優れた性能を示す。
論文 参考訳（メタデータ） (2025-02-10T23:11:02Z) - Incremental Quasi-Newton Methods with Faster Superlinear Convergence
Rates [50.36933471975506]
各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。
最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。
本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
論文 参考訳（メタデータ） (2024-02-04T05:54:51Z) - Constrained Optimization via Exact Augmented Lagrangian and Randomized
Iterative Sketching [55.28394191394675]
等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。
ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
論文 参考訳（メタデータ） (2023-05-28T06:33:37Z) - Robust empirical risk minimization via Newton's method [9.797319790710711]
実験的リスク最小化のためのニュートン法の新しい変種について検討した。
目的関数の勾配と Hessian は、ロバストな推定器に置き換えられる。
また,共役勾配法に基づくニュートン方向のロバストな解を求めるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T18:54:54Z) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文 参考訳（メタデータ） (2022-05-27T00:34:03Z) - Distributed Sketching for Randomized Optimization: Exact
Characterization, Concentration and Lower Bounds [54.51566432934556]
我々はヘシアンの形成が困難である問題に対する分散最適化法を検討する。
ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。
論文 参考訳（メタデータ） (2022-03-18T05:49:13Z) - Newton-LESS: Sparsification without Trade-offs for the Sketched Newton
Update [88.73437209862891]
2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。
本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。
ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
論文 参考訳（メタデータ） (2021-07-15T17:33:05Z) - Accelerated, Optimal, and Parallel: Some Results on Model-Based
Stochastic Optimization [33.71051480619541]
凸最適化問題を解決するためのモデルベース手法の近似近位点(aProx)ファミリを拡張します。
我々は、非漸近収束保証と、ミニバッチサイズの線形スピードアップを提供する加速スキームを提供する。
我々は,「補間」問題に対する新しい基本定数を同定し,収束率の改善と下界の整合性を示す。
論文 参考訳（メタデータ） (2021-01-07T18:58:39Z) - Distributed Averaging Methods for Randomized Second Order Optimization [54.51566432934556]
我々はヘッセン語の形成が計算的に困難であり、通信がボトルネックとなる分散最適化問題を考察する。
我々は、ヘッセンのサンプリングとスケッチを用いたランダム化二階最適化のための非バイアスパラメータ平均化手法を開発した。
また、不均一なコンピューティングシステムのための非バイアス分散最適化フレームワークを導入するために、二階平均化手法のフレームワークを拡張した。
論文 参考訳（メタデータ） (2020-02-16T09:01:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。