論文の概要: Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform

• arxiv url: http://arxiv.org/abs/2002.00864v5
• Date: Fri, 23 Oct 2020 12:35:02 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-04 09:22:35.524822
• Title: Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform
• Title（参考訳）: サンプル化ランダム化アダマール変換を用いた最適反復スケッチ
• Authors: Jonathan Lacotte, Sifan Liu, Edgar Dobriban and Mert Pilanci
• Abstract要約: 最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
• 参考スコア（独自算出の注目度）: 64.90148466525754
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Random projections or sketching are widely used in many algorithmic and learning contexts. Here we study the performance of iterative Hessian sketch for least-squares problems. By leveraging and extending recent results from random matrix theory on the limiting spectrum of matrices randomly projected with the subsampled randomized Hadamard transform, and truncated Haar matrices, we can study and compare the resulting algorithms to a level of precision that has not been possible before. Our technical contributions include a novel formula for the second moment of the inverse of projected matrices. We also find simple closed-form expressions for asymptotically optimal step-sizes and convergence rates. These show that the convergence rate for Haar and randomized Hadamard matrices are identical, and asymptotically improve upon Gaussian random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
• Abstract（参考訳）: ランダム投影やスケッチは多くのアルゴリズムや学習の文脈で広く使われている。 ここでは,最小二乗問題に対する反復ヘッセンスケッチの性能について検討する。 ランダムマトリクス理論の最近の結果を、ランダム化アダマール変換と断続ハール行列でランダムに投影された行列の限界スペクトルに利用し、拡張することにより、その結果得られるアルゴリズムを、これまで不可能だった精度のレベルと比較することができる。 我々の技術的な貢献には、射影行列の逆の第二の瞬間に対する新しい公式が含まれる。 また,漸近的に最適なステップサイズと収束率に対する単純な閉形式式を求める。 これらの結果は、ハール行列とランダムアダマール行列の収束率は同一であり、ガウスランダム射影によって漸近的に改善されることを示している。 これらの手法は、ランダム次元還元を用いる他のアルゴリズムにも適用できる。

関連論文リスト

• Randomized Algorithms for Symmetric Nonnegative Matrix Factorization [2.1753766244387402]
  対称非負行列因子化(SymNMF)は、データ解析と機械学習における技術である。 計算のためのランダム化アルゴリズムを2つ開発した。 提案手法は, 解法の品質を概ね維持し, 大規模疎水化問題と大規模疎水化問題の両方に対して, 大幅な高速化を実現する。
  論文  参考訳（メタデータ） (2024-02-13T00:02:05Z)
• A fixed-point algorithm for matrix projections with applications in quantum information [7.988085110283119]
  このアルゴリズムは反復数において最適解に指数関数的に収束することを示す。 量子資源理論および量子シャノン理論における我々のアルゴリズムのいくつかの応用について論じる。
  論文  参考訳（メタデータ） (2023-12-22T11:16:11Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Fast Projected Newton-like Method for Precision Matrix Estimation under Total Positivity [15.023842222803058]
  現在のアルゴリズムはブロック座標降下法や近点アルゴリズムを用いて設計されている。 本稿では,2次元投影法に基づく新しいアルゴリズムを提案し,慎重に設計された探索方向と変数分割方式を取り入れた。 合成および実世界のデータセットに対する実験結果から,提案アルゴリズムは最先端の手法と比較して計算効率を著しく向上させることを示した。
  論文  参考訳（メタデータ） (2021-12-03T14:39:10Z)
• Learning-Augmented Sketches for Hessians [54.97773807211337]
  第二次手法の文脈でヘッセンの学習スケッチを設計する方法を紹介します。 学習したスケッチは,「学習されていない」スケッチと比較して,重要な問題に対する近似精度が向上することを示す。
  論文  参考訳（メタデータ） (2021-02-24T14:50:59Z)
• Precise expressions for random projections: Low-rank approximation and randomized Newton [63.68433510953756]
  マトリックススケッチは、そのような次元削減を非常に効率的に行うための強力な技術として登場した。 本研究では,スケッチによって得られたランダムな投影行列の予測値に対して,確率的に正確な表現を提供する手法を開発した。 これらの表現は、様々な機械学習タスクにおける次元削減のパフォーマンスを特徴付けるのに使うことができる。
  論文  参考訳（メタデータ） (2020-06-18T16:23:00Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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