論文の概要: Learning Linear Models Using Distributed Iterative Hessian Sketching

• arxiv url: http://arxiv.org/abs/2112.04101v1
• Date: Wed, 8 Dec 2021 04:07:23 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-09 16:42:18.898962
• Title: Learning Linear Models Using Distributed Iterative Hessian Sketching
• Title（参考訳）: 分散反復ヘッシアンスケッチを用いた線形モデル学習
• Authors: Han Wang and James Anderson
• Abstract要約: 観測データから線形システムのマルコフパラメータを学習する問題を考察する。 Hessian-Sketchingに基づくランダムに分散されたニュートンアルゴリズムは、$epsilon$-optimal Solutionを生成可能であることを示す。
• 参考スコア（独自算出の注目度）: 4.567810220723372
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: This work considers the problem of learning the Markov parameters of a linear system from observed data. Recent non-asymptotic system identification results have characterized the sample complexity of this problem in the single and multi-rollout setting. In both instances, the number of samples required in order to obtain acceptable estimates can produce optimization problems with an intractably large number of decision variables for a second-order algorithm. We show that a randomized and distributed Newton algorithm based on Hessian-sketching can produce $\epsilon$-optimal solutions and converges geometrically. Moreover, the algorithm is trivially parallelizable. Our results hold for a variety of sketching matrices and we illustrate the theory with numerical examples.
• Abstract（参考訳）: 本研究では,観測データから線形システムのマルコフパラメータを学習する問題を考察する。 最近の非漸近的システム同定の結果は、単一および複数ロールアウト設定におけるこの問題のサンプル複雑さを特徴付けている。 どちらの場合も、許容可能な推定値を得るために必要となるサンプルの数は、2次アルゴリズムに対する決定変数の難易度の高い数で最適化問題を生み出すことができる。 ヘッシアン・スケッチングに基づくランダム化分散ニュートンアルゴリズムは,$\epsilon$-optimal 解を生成でき,幾何学的に収束する。 さらに、アルゴリズムは自明に並列化可能である。 その結果,様々なスケッチ行列が得られ,その理論を数値的な例で示す。

関連論文リスト

• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。 この問題は楕円分布のペナルティ化された最大推定値として表される。 楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
  論文  参考訳（メタデータ） (2022-10-21T13:19:45Z)
• Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition [14.453949553412821]
  本研究では,スケッチ・アンド・プロジェクト手法の収束率の急激な保証を得るための理論的枠組みを開発する。 収束速度はスケッチサイズとともに少なくとも直線的に改善され、データ行列が特定のスペクトル崩壊を示すとさらに高速になることを示す。 我々の実験は、この理論を支持し、非常にスパースなスケッチでさえ、我々のフレームワークによって予測される収束特性を示すことを示した。
  論文  参考訳（メタデータ） (2022-08-20T03:11:13Z)
• Fast Projected Newton-like Method for Precision Matrix Estimation under Total Positivity [15.023842222803058]
  現在のアルゴリズムはブロック座標降下法や近点アルゴリズムを用いて設計されている。 本稿では,2次元投影法に基づく新しいアルゴリズムを提案し,慎重に設計された探索方向と変数分割方式を取り入れた。 合成および実世界のデータセットに対する実験結果から,提案アルゴリズムは最先端の手法と比較して計算効率を著しく向上させることを示した。
  論文  参考訳（メタデータ） (2021-12-03T14:39:10Z)
• Numerical Solution of Stiff Ordinary Differential Equations with Random Projection Neural Networks [0.0]
  正規微分方程式(ODE)の解に対する乱射影ニューラルネットワーク(RPNN)に基づく数値スキームを提案する。 提案手法は剛性の影響を受けずに高い数値近似精度を示し,textttode45 と textttode15s の関数よりも優れていた。
  論文  参考訳（メタデータ） (2021-08-03T15:49:17Z)
• Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector Problems [78.95866278697777]
  本研究では,多元的固有ベクトルを分散制約で同時に計算するTruncated Orthogonal Iterationの2つの変種を提案する。 次に,我々のアルゴリズムを適用して,幅広いテストデータセットに対するスパース原理成分分析問題を解く。
  論文  参考訳（メタデータ） (2021-03-24T23:11:32Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。 アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。 ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
  論文  参考訳（メタデータ） (2020-02-20T10:50:58Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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