論文の概要: Online Covariance Matrix Estimation in Sketched Newton Methods

• arxiv url: http://arxiv.org/abs/2502.07114v1
• Date: Mon, 10 Feb 2025 23:11:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-12 14:08:26.620712
• Title: Online Covariance Matrix Estimation in Sketched Newton Methods
• Title（参考訳）: スケッチされたニュートン法におけるオンライン共分散行列推定
• Authors: Wei Kuang, Mihai Anitescu, Sen Na,
• Abstract要約: ランダム化されたスケッチ技術を利用して各イテレーションで近似したニュートンステップを実行するオンラインスケッチNewton法について検討する。 また、制約された問題に対する推定器の拡張についても論じ、回帰問題に対する優れた性能を示す。
• 参考スコア（独自算出の注目度）: 7.441891256588546
• License:
• Abstract: Given the ubiquity of streaming data, online algorithms have been widely used for parameter estimation, with second-order methods particularly standing out for their efficiency and robustness. In this paper, we study an online sketched Newton method that leverages a randomized sketching technique to perform an approximate Newton step in each iteration, thereby eliminating the computational bottleneck of second-order methods. While existing studies have established the asymptotic normality of sketched Newton methods, a consistent estimator of the limiting covariance matrix remains an open problem. We propose a fully online covariance matrix estimator that is constructed entirely from the Newton iterates and requires no matrix factorization. Compared to covariance estimators for first-order online methods, our estimator for second-order methods is batch-free. We establish the consistency and convergence rate of our estimator, and coupled with asymptotic normality results, we can then perform online statistical inference for the model parameters based on sketched Newton methods. We also discuss the extension of our estimator to constrained problems, and demonstrate its superior performance on regression problems as well as benchmark problems in the CUTEst set.
• Abstract（参考訳）: ストリーミングデータの多様さを考えると、オンラインアルゴリズムはパラメータ推定に広く使われており、特に2階法はその効率と堅牢性で際立っている。 本稿では,ランダムなスケッチ手法を利用して各イテレーションで近似したニュートンステップを実行するオンラインスケッチNewton法について検討し,第2次手法の計算ボトルネックを解消する。 既存の研究では、スケッチされたニュートン法の漸近正規性を確立しているが、制限共分散行列の一貫した推定器は未解決の問題のままである。 本稿では,ニュートンイテレートから完全に構成され,行列分解を必要としない完全オンライン共分散行列推定器を提案する。 一階オンライン手法の共分散推定器と比較して、二階オンライン手法の共分散推定器はバッチフリーである。 我々は推定器の一貫性と収束率を確立し、漸近的正規性の結果と組み合わせることで、スケッチされたニュートン法に基づくモデルパラメータのオンライン統計的推測を行うことができる。 また、制約された問題に対する推定器の拡張についても検討し、CUTEstセットのベンチマーク問題と同様に回帰問題に対する優れた性能を示す。

関連論文リスト

• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• Efficient Graph Laplacian Estimation by Proximal Newton [12.05527862797306]
  グラフ学習問題は、精度行列の最大極大推定(MLE)として定式化することができる。 いくつかのアルゴリズム的特徴を利用した効率的な解法を得るための2次手法を開発した。
  論文  参考訳（メタデータ） (2023-02-13T15:13:22Z)
• 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)
• Robust online joint state/input/parameter estimation of linear systems [0.0]
  本稿では,線形システムの状態,入力,パラメータをオンライン形式で共同で推定する手法を提案する。 この方法は、非ガウス雑音や外れ値で劣化した測定のために特別に設計されている。
  論文  参考訳（メタデータ） (2022-04-12T09:41:28Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  均質な分散凸最適化のためのNewtonアルゴリズムを解析し、各マシンが同じ人口目標の勾配を計算する。 提案手法は,既存の手法と比較して,性能を損なうことなく,必要な通信ラウンドの数,頻度を低減できることを示す。
  論文  参考訳（メタデータ） (2021-10-07T17:51:10Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。 本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。 ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
  論文  参考訳（メタデータ） (2021-07-15T17:33:05Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  我々は高次元単一インデックスモデルのための正規化自由アルゴリズムを設計する。 暗黙正則化現象の理論的保証を提供する。
  論文  参考訳（メタデータ） (2020-07-16T13:27:47Z)
• Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
  我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。 本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
  論文  参考訳（メタデータ） (2020-05-22T22:30:52Z)

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

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