論文の概要: Approximation Algorithms for Sparse Principal Component Analysis

• arxiv url: http://arxiv.org/abs/2006.12748v2
• Date: Fri, 4 Jun 2021 16:25:42 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-17 23:44:25.515071
• Title: Approximation Algorithms for Sparse Principal Component Analysis
• Title（参考訳）: スパース主成分分析のための近似アルゴリズム
• Authors: Agniva Chowdhury, Petros Drineas, David P. Woodruff, Samson Zhou
• Abstract要約: 主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。 スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。 本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 57.5357874512594
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Principal component analysis (PCA) is a widely used dimension reduction technique in machine learning and multivariate statistics. To improve the interpretability of PCA, various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis (SPCA). In this paper, we present thresholding as a provably accurate, polynomial time, approximation algorithm for the SPCA problem, without imposing any restrictive assumptions on the input covariance matrix. Our first thresholding algorithm using the Singular Value Decomposition is conceptually simple; is faster than current state-of-the-art; and performs well in practice. On the negative side, our (novel) theoretical bounds do not accurately predict the strong practical performance of this approach. The second algorithm solves a well-known semidefinite programming relaxation and then uses a novel, two step, deterministic thresholding scheme to compute a sparse principal vector. It works very well in practice and, remarkably, this solid practical performance is accurately predicted by our theoretical bounds, which bridge the theory-practice gap better than current state-of-the-art.
• Abstract（参考訳）: 主成分分析(PCA)は、機械学習と多変量統計学において広く使われている次元削減手法である。 PCAの解釈性を改善するために,スパース主成分分析 (SPCA) と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。 本稿では、入力共分散行列に制限的な仮定を課すことなく、SPCA問題に対する精度の高い多項式時間近似アルゴリズムとしてしきい値を提示する。 特異値分解を用いた最初のしきい値化アルゴリズムは概念的に単純であり、現在の最先端よりも高速であり、実際よく機能する。 負の面では、我々の(ノーベルな)理論的境界は、このアプローチの強い実用性能を正確に予測しない。 第2のアルゴリズムは、よく知られた半定義のプログラミング緩和を解き、スパース主ベクトルを計算するために、新しい2段階決定論的しきい値スキームを用いる。 実際に非常にうまく機能し、そして驚くべきことに、この堅実な実用性能は我々の理論的境界によって正確に予測され、現在の最先端技術よりも理論と実践のギャップを橋渡しする。

関連論文リスト

• From Optimization to Control: Quasi Policy Iteration [3.4376560669160394]
  準政治反復(QPI)と呼ばれる新しい制御アルゴリズムを提案する。 QPIは、政策反復アルゴリズムにおける「ヘシアン」行列の新たな近似に基づいて、MDPに特有の2つの線形構造制約を利用する。 これは、割引係数に対する感度が極めて低い政策反復と同様の実証的な収束挙動を示す。
  論文  参考訳（メタデータ） (2023-11-18T21:00:14Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。 既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。 本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
  論文  参考訳（メタデータ） (2022-10-08T08:26:22Z)
• Making Linear MDPs Practical via Contrastive Representation Learning [101.75885788118131]
  マルコフ決定過程(MDP)における次元性の呪いに、低ランク表現を利用することで対処することが一般的である。 本稿では,効率的な表現学習を可能にしつつ,正規化を自動的に保証する線形MDPの代替的定義について考察する。 いくつかのベンチマークにおいて、既存の最先端モデルベースおよびモデルフリーアルゴリズムよりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-07-14T18:18:02Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。 これらの問題に対する新規で簡単な最適化法を開発した。 結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2021-09-23T17:38:24Z)
• Dual Optimization for Kolmogorov Model Learning Using Enhanced Gradient Descent [8.714458129632158]
  コルモゴロフモデル(コルモゴロフモデル、英: Kolmogorov model、KM)は、確率変数の集合の基本的な確率構造を学ぶための解釈可能で予測可能な表現手法である。 正規化双対最適化と拡張勾配降下法(GD)を併用した計算スケーラブルなKM学習アルゴリズムを提案する。 提案したKM学習アルゴリズムを用いた論理的関係マイニングの精度は80%以上である。
  論文  参考訳（メタデータ） (2021-07-11T10:33:02Z)
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality [131.45028999325797]
  ディスカウント型MDPのための2倍堅牢なオフポリチックAC(DR-Off-PAC)を開発した。 DR-Off-PACは、俳優と批評家の両方が一定のステップで同時に更新される単一のタイムスケール構造を採用しています。 有限時間収束速度を研究し, dr-off-pac のサンプル複雑性を特徴とし, $epsilon$-accurate optimal policy を得る。
  論文  参考訳（メタデータ） (2021-02-23T18:56:13Z)
• Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization [21.64869023699999]
  本研究では, 試料が逆向きに破壊されたり, 分布が重くなったりした場合に, 分布の平均を高次元で推定する問題について検討する。 メタプロブレムと双対性定理は、高次元におけるロバストで重み付き平均推定に関する新しい統一的な見解をもたらす。
  論文  参考訳（メタデータ） (2020-07-31T04:18:32Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)
• On the Convergence of the Dynamic Inner PCA Algorithm [5.9931120596636935]
  DiPCAは時間依存データ解析のための強力な手法である。 これは座標分解アルゴリズムの特殊な変種であることを示す。 分解戦略のパフォーマンスを既成のそれと比較する。
  論文  参考訳（メタデータ） (2020-03-12T17:50:34Z)
• Adaptive Approximate Policy Iteration [22.915651391812187]
  均一なエルゴディックMDPの学習を継続する学習方法として,$tildeO(T2/3)$ regret bound for undiscounted, continuing learning in uniformly ergodic MDPを提案する。 これは、関数近似を持つ平均逆ケースに対する$tildeO(T3/4)$の最良の既存の境界よりも改善されている。
  論文  参考訳（メタデータ） (2020-02-08T02:27:03Z)

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

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