論文の概要: An Improved Frequent Directions Algorithm for Low-Rank Approximation via Block Krylov Iteration

• arxiv url: http://arxiv.org/abs/2109.11703v1
• Date: Fri, 24 Sep 2021 01:36:42 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-27 14:09:54.516682
• Title: An Improved Frequent Directions Algorithm for Low-Rank Approximation via Block Krylov Iteration
• Title（参考訳）: ブロッククリロフ反復による低ランク近似のための周波数方向アルゴリズムの改良
• Authors: Chenhao Wang, Qianxin Yi, Xiuwu Liao, Yao Wang
• Abstract要約: 本稿では,r-BKIFDという高速かつ高精度な周波数方向アルゴリズムを提案する。 提案したr-BKIFDは、元のFrequent Directionsと同等の誤差を持ち、反復回数が適切に選択された場合、近似誤差を任意に小さくすることができる。
• 参考スコア（独自算出の注目度）: 11.62834880315581
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Frequent Directions, as a deterministic matrix sketching technique, has been proposed for tackling low-rank approximation problems. This method has a high degree of accuracy and practicality, but experiences a lot of computational cost for large-scale data. Several recent works on the randomized version of Frequent Directions greatly improve the computational efficiency, but unfortunately sacrifice some precision. To remedy such issue, this paper aims to find a more accurate projection subspace to further improve the efficiency and effectiveness of the existing Frequent Directions techniques. Specifically, by utilizing the power of Block Krylov Iteration and random projection technique, this paper presents a fast and accurate Frequent Directions algorithm named as r-BKIFD. The rigorous theoretical analysis shows that the proposed r-BKIFD has a comparable error bound with original Frequent Directions, and the approximation error can be arbitrarily small when the number of iterations is chosen appropriately. Extensive experimental results on both synthetic and real data further demonstrate the superiority of r-BKIFD over several popular Frequent Directions algorithms, both in terms of computational efficiency and accuracy.
• Abstract（参考訳）: 低ランク近似問題に対処するための行列スケッチ手法として,周波数方向が提案されている。 この手法は高い精度と実用性を有するが、大規模データに対して多くの計算コストがかかる。 頻繁な方向のランダム化に関する最近のいくつかの研究は計算効率を大幅に向上させたが、残念ながらある程度の精度を犠牲にしている。 そこで本稿では,より正確な投影部分空間を見つけ,既存の頻出方向手法の効率と有効性をさらに高めることを目的としている。 具体的には,ブロッククリロフイテレーションとランダムプロジェクションのパワーを利用して,r-BKIFDという高速かつ高精度な周波数方向アルゴリズムを提案する。 厳密な理論解析により,提案するr-bkifdの誤差は元の頻繁な方向と同等であり,反復回数が適切に選択されると近似誤差が任意に小さくなることが示された。 合成データと実データの両方に対する大規模な実験結果は、計算効率と精度の両面で、いくつかの一般的な周波数方向アルゴリズムよりもr-BKIFDの方が優れていることを示す。

関連論文リスト

• Derivative-Free Optimization via Finite Difference Approximation: An Experimental Study [1.3886390523644807]
  微分自由最適化(DFO)は、関数評価のみをオラクルで利用できるような複雑な最適化問題の解決に不可欠である。 2つの古典的なイテレーションアプローチは、Kiefer-Wolfowitz (KW) と同時摂動近似 (SPSA) アルゴリズムである。 本稿では,これらの手法の総合的な比較実験を行う。
  論文  参考訳（メタデータ） (2024-10-31T18:07:44Z)
• Faster WIND: Accelerating Iterative Best-of-$N$ Distillation for LLM Alignment [81.84950252537618]
  本稿では,反復的BONDと自己プレイアライメントの統一的なゲーム理論接続を明らかにする。 WINレート支配(WIN rate Dominance, WIND)という新しいフレームワークを構築し, 正規化利率支配最適化のためのアルゴリズムを多数提案する。
  論文  参考訳（メタデータ） (2024-10-28T04:47:39Z)
• Machine Learning Training Optimization using the Barycentric Correction Procedure [0.0]
  本研究では,機械学習アルゴリズムとBCP(Barycentric correct procedure)と呼ばれる効率的な手法を組み合わせることを提案する。 この組み合わせによって、実データと合成データの時間に関する大きな利点が得られ、インスタンス数や次元が増加すると精度を損なうことなく得られることがわかった。
  論文  参考訳（メタデータ） (2024-03-01T13:56:36Z)
• Efficient Numerical Algorithm for Large-Scale Damped Natural Gradient Descent [7.368877979221163]
  本研究では,パラメータ数が利用可能なサンプル数を大幅に上回る大規模シナリオにおいて,減衰したフィッシャー行列を効率的に解くアルゴリズムを提案する。 アルゴリズムはColesky分解に基づいており、一般に適用可能である。ベンチマークの結果、既存の手法よりもかなり高速であることが示されている。
  論文  参考訳（メタデータ） (2023-10-26T16:46:13Z)
• Large-scale Optimization of Partial AUC in a Range of False Positive Rates [51.12047280149546]
  ROC曲線 (AUC) の下の領域は、機械学習において最も広く使われている分類モデルのパフォーマンス指標の1つである。 近年の封筒平滑化技術に基づく効率的な近似勾配降下法を開発した。 提案アルゴリズムは,効率のよい解法を欠くランク付けされた範囲損失の和を最小化するためにも利用できる。
  論文  参考訳（メタデータ） (2022-03-03T03:46:18Z)
• Effective Streaming Low-tubal-rank Tensor Approximation via Frequent Directions [9.43704219585568]
  本稿では,高速かつ高精度な低ツバルランクテンソル近似を構築するために,行列スケッチ技術である周波数方向( Frequent Directions)を拡張した。 具体的には、新しいアルゴリズムではテンソルデータをスライスごとにスライスすることができるが、より小さなスケッチをメンテナンスし、漸進的に更新するだけでよい。 厳密な理論解析により,スケッチサイズが線形に大きくなると,新しいアルゴリズムの近似誤差が任意に小さくなることを示した。
  論文  参考訳（メタデータ） (2021-08-23T12:53:44Z)
• Learned Block Iterative Shrinkage Thresholding Algorithm for Photothermal Super Resolution Imaging [52.42007686600479]
  深層ニューラルネットワークに展開する反復アルゴリズムを用いて,学習したブロックスパース最適化手法を提案する。 本稿では、正規化パラメータの選択を学ぶことができる学習ブロック反復収縮しきい値アルゴリズムを使用することの利点を示す。
  論文  参考訳（メタデータ） (2020-12-07T09:27:16Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。 スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。 本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-23T04:25:36Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)

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

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