論文の概要: Fast Projection onto the Capped Simplex withApplications to Sparse Regression in Bioinformatics

• arxiv url: http://arxiv.org/abs/2110.08471v2
• Date: Tue, 19 Oct 2021 01:42:06 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-21 17:25:57.010183
• Title: Fast Projection onto the Capped Simplex withApplications to Sparse Regression in Bioinformatics
• Title（参考訳）: 字幕上への高速投射とバイオインフォマティクスのスパース回帰への応用
• Authors: Andersen Ang, Jianzhu Ma, Nianjun Liu, Kun Huang, Yijie Wang
• Abstract要約: ニュートン法に基づく単純なアルゴリズムは、射影問題を高精度に解くことができる。 提案アルゴリズムは,大規模データセット上で高い精度で予測問題の解を導出できることを実証する。
• 参考スコア（独自算出の注目度）: 6.6371396313325075
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of projecting a vector onto the so-called k-capped simplex, which is a hyper-cube cut by a hyperplane. For an n-dimensional input vector with bounded elements, we found that a simple algorithm based on Newton's method is able to solve the projection problem to high precision with a complexity roughly about O(n), which has a much lower computational cost compared with the existing sorting-based methods proposed in the literature. We provide a theory for partial explanation and justification of the method. We demonstrate that the proposed algorithm can produce a solution of the projection problem with high precision on large scale datasets, and the algorithm is able to significantly outperform the state-of-the-art methods in terms of runtime (about 6-8 times faster than a commercial software with respect to CPU time for input vector with 1 million variables or more). We further illustrate the effectiveness of the proposed algorithm on solving sparse regression in a bioinformatics problem. Empirical results on the GWAS dataset (with 1,500,000 single-nucleotide polymorphisms) show that, when using the proposed method to accelerate the Projected Quasi-Newton (PQN) method, the accelerated PQN algorithm is able to handle huge-scale regression problem and it is more efficient (about 3-6 times faster) than the current state-of-the-art methods.
• Abstract（参考訳）: ベクトルを、超平面によって切断された超キューブであるいわゆる k-キャッピング・シンプレックスに投影する問題を考える。 有界要素を持つn次元入力ベクトルに対して,ニュートン法に基づく単純なアルゴリズムは,従来のソートベース手法に比べて計算コストがはるかに低いo(n)前後の複雑性で,高い精度で投影問題を解くことができることがわかった。 我々は,その方法の部分的説明と正当化の理論を提供する。 提案アルゴリズムは,大規模データセット上で高い精度でプロジェクション問題の解を生成できることを示すとともに,実行時(100万変数以上の入力ベクトルのCPU時間に対して,商用ソフトウェアよりも約6～8倍高速)で最先端の手法を大幅に上回っていることを示す。 さらに,バイオインフォマティクス問題における疎回帰問題に対する提案アルゴリズムの有効性について述べる。 gwasデータセット(シングルヌクレオチド多型1,500,000)の実証結果から,提案手法を用いて投影型準ニュートン法(pqn)を高速化した場合,pqnアルゴリズムは大規模回帰問題に対処でき,現在の手法よりも効率的(約3～6倍高速)であることが示された。

関連論文リスト

• Randomized Algorithms for Symmetric Nonnegative Matrix Factorization [2.1753766244387402]
  対称非負行列因子化(SymNMF)は、データ解析と機械学習における技術である。 計算のためのランダム化アルゴリズムを2つ開発した。 提案手法は, 解法の品質を概ね維持し, 大規模疎水化問題と大規模疎水化問題の両方に対して, 大幅な高速化を実現する。
  論文  参考訳（メタデータ） (2024-02-13T00:02:05Z)
• Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching [53.91395791840179]
  我々は、大規模なSDPを解くための、証明可能な正確で高速でスケーラブルなアルゴリズムであるUnified Spectral Bundling with Sketching (USBS)を提案する。 USBSは、20億以上の決定変数を持つインスタンス上で、最先端のスケーラブルなSDP解決器よりも500倍のスピードアップを提供する。
  論文  参考訳（メタデータ） (2023-12-19T02:27:22Z)
• Efficient Numerical Algorithm for Large-Scale Damped Natural Gradient Descent [7.368877979221163]
  本研究では,パラメータ数が利用可能なサンプル数を大幅に上回る大規模シナリオにおいて,減衰したフィッシャー行列を効率的に解くアルゴリズムを提案する。 アルゴリズムはColesky分解に基づいており、一般に適用可能である。ベンチマークの結果、既存の手法よりもかなり高速であることが示されている。
  論文  参考訳（メタデータ） (2023-10-26T16:46:13Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Fast Projected Newton-like Method for Precision Matrix Estimation under Total Positivity [15.023842222803058]
  現在のアルゴリズムはブロック座標降下法や近点アルゴリズムを用いて設計されている。 本稿では,2次元投影法に基づく新しいアルゴリズムを提案し,慎重に設計された探索方向と変数分割方式を取り入れた。 合成および実世界のデータセットに対する実験結果から,提案アルゴリズムは最先端の手法と比較して計算効率を著しく向上させることを示した。
  論文  参考訳（メタデータ） (2021-12-03T14:39:10Z)
• Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector Problems [78.95866278697777]
  本研究では,多元的固有ベクトルを分散制約で同時に計算するTruncated Orthogonal Iterationの2つの変種を提案する。 次に,我々のアルゴリズムを適用して,幅広いテストデータセットに対するスパース原理成分分析問題を解く。
  論文  参考訳（メタデータ） (2021-03-24T23:11:32Z)
• Slowly Varying Regression under Sparsity [5.22980614912553]
  本稿では, 緩やかな過度回帰の枠組みを提示し, 回帰モデルが緩やかかつスパースな変動を示すようにした。 本稿では,バイナリ凸アルゴリズムとして再構成する手法を提案する。 結果として得られたモデルは、様々なデータセット間で競合する定式化よりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-02-22T04:51:44Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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