Fugu-MT 論文翻訳(概要): Efficient Sparse PCA via Block-Diagonalization

論文の概要: Efficient Sparse PCA via Block-Diagonalization

arxiv url: http://arxiv.org/abs/2410.14092v1
Date: Fri, 18 Oct 2024 00:16:10 GMT
ステータス: 翻訳完了
システム内更新日: 2024-10-21 14:26:18.608959
Title: Efficient Sparse PCA via Block-Diagonalization
Title（参考訳）: ブロック対角化による効率的なスパースPCA
Authors: Alberto Del Pia, Dekun Zhou, Yinglun Zhu,
Abstract要約: スパースPCAを効率的に近似する新しいフレームワークを提案する。既製のスパースPCAアルゴリズムを利用することができ、計算速度を大幅に向上させることができる。このアルゴリズムを統合すると、ランタイムを$mathcalOleft(fracddstar cdot g(k, dstar) + d2right)$に削減します。
参考スコア（独自算出の注目度）: 13.38174941551702
License:
Abstract: Sparse Principal Component Analysis (Sparse PCA) is a pivotal tool in data analysis and dimensionality reduction. However, Sparse PCA is a challenging problem in both theory and practice: it is known to be NP-hard and current exact methods generally require exponential runtime. In this paper, we propose a novel framework to efficiently approximate Sparse PCA by (i) approximating the general input covariance matrix with a re-sorted block-diagonal matrix, (ii) solving the Sparse PCA sub-problem in each block, and (iii) reconstructing the solution to the original problem. Our framework is simple and powerful: it can leverage any off-the-shelf Sparse PCA algorithm and achieve significant computational speedups, with a minor additive error that is linear in the approximation error of the block-diagonal matrix. Suppose $g(k, d)$ is the runtime of an algorithm (approximately) solving Sparse PCA in dimension $d$ and with sparsity value $k$. Our framework, when integrated with this algorithm, reduces the runtime to $\mathcal{O}\left(\frac{d}{d^\star} \cdot g(k, d^\star) + d^2\right)$, where $d^\star \leq d$ is the largest block size of the block-diagonal matrix. For instance, integrating our framework with the Branch-and-Bound algorithm reduces the complexity from $g(k, d) = \mathcal{O}(k^3\cdot d^k)$ to $\mathcal{O}(k^3\cdot d \cdot (d^\star)^{k-1})$, demonstrating exponential speedups if $d^\star$ is small. We perform large-scale evaluations on many real-world datasets: for exact Sparse PCA algorithm, our method achieves an average speedup factor of 93.77, while maintaining an average approximation error of 2.15%; for approximate Sparse PCA algorithm, our method achieves an average speedup factor of 6.77 and an average approximation error of merely 0.37%.
Abstract（参考訳）: Sparse principal Component Analysis (Sparse PCA) は、データ分析と次元削減において重要なツールである。しかし、スパースPCAは理論と実践の両方において難しい問題であり、NPハードであることが知られており、現在の正確な方法は指数的実行を必要とする。本稿では,スパースPCAを効率的に近似する新しいフレームワークを提案する。一一般入力共分散行列を再分類ブロック対角行列で近似すること。二各ブロックにおいてスパースPCAサブプロブレムを解くこと。三元の問題の解決を再建すること。我々のフレームワークは単純で強力で、既製のスパースPCAアルゴリズムを活用でき、ブロック対角行列の近似誤差に線形な小さな加算誤差を伴い、計算速度を大幅に向上できる。 g(k, d)$ を Sparse PCA を次元 $d$ で解いて、空間値 $k$ で解くアルゴリズムのランタイムとする。このアルゴリズムを統合すると、ランタイムを$\mathcal{O}\left(\frac{d}{d^\star} \cdot g(k, d^\star) + d^2\right)$に削減します。例えば、ブランチ・アンド・バウンドアルゴリズムと統合することで、複雑さを$g(k, d) = \mathcal{O}(k^3\cdot d^k)$から$\mathcal{O}(k^3\cdot d \cdot (d^\star)^{k-1})$に減らし、$d^\star$が小さい場合に指数的スピードアップを示す。 Sparse PCAアルゴリズムでは,平均近似誤差2.15%を維持しながら平均高速化係数93.77,近似Sparse PCAアルゴリズムでは平均高速化係数6.77,平均近似誤差0.37%を実現している。

関連論文リスト

Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文参考訳（メタデータ） (2024-10-03T15:04:01Z)
Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
我々は、スペクトルテール条件数である$kappa_ell$を、システムを表す行列の最小特異値と$ell$2の比として定義する。結果のいくつかの意味と$kappa_ell$の使用は、Conjugateメソッドのきめ細かい解析を直接改善することを含んでいる。
論文参考訳（メタデータ） (2024-05-09T14:56:49Z)
A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation [6.853165736531941]
逆数外乱の存在下でのスパース平均推定のアルゴリズム的問題について検討する。我々の主な貢献は、$mathrmpoly(k,log d,1/epsilon)$サンプルを用いて、エフェサブクアクラティック時間で実行される頑健なスパース平均推定アルゴリズムである。
論文参考訳（メタデータ） (2024-03-07T18:23:51Z)
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文参考訳（メタデータ） (2023-07-24T14:37:22Z)
Streaming Kernel PCA Algorithm With Small Space [24.003544967343615]
近年,大規模なデータセットを効率的に処理できるため,ストリーミングPCAが注目されている。我々はOjaの従来のスキームに基づくKernel問題に対するストリーミングアルゴリズムを提案する。提案アルゴリズムは,PCAのメモリ使用量を削減するとともに,その精度を維持するという課題に対処する。
論文参考訳（メタデータ） (2023-03-08T13:13:33Z)
Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-01-30T14:37:21Z)
Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文参考訳（メタデータ） (2022-06-17T09:24:41Z)
Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文参考訳（メタデータ） (2021-06-16T03:34:14Z)
List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文参考訳（メタデータ） (2020-11-19T17:21:37Z)
Approximate Multiplication of Sparse Matrices with Limited Space [24.517908972536432]
我々はスパース共起方向を開発し、期待値の$widetildeOleft((nnz(X)+nnz(Y))ell+nell2right)$に時間複雑性を減少させる。理論的解析により,我々のアルゴリズムの近似誤差はCODとほぼ同値であることが判明した。
論文参考訳（メタデータ） (2020-09-08T05:39:19Z)

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

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