論文の概要: Solving Large-Scale Sparse PCA to Certifiable (Near) Optimality

• arxiv url: http://arxiv.org/abs/2005.05195v4
• Date: Wed, 25 Aug 2021 15:42:09 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-04 21:02:56.545394
• Title: Solving Large-Scale Sparse PCA to Certifiable (Near) Optimality
• Title（参考訳）: 大規模スパースPCAの認証(外)最適化
• Authors: Dimitris Bertsimas, Ryan Cory-Wright, Jean Pauphilet
• Abstract要約: 既存のアプローチでは、$p=100s$以上の変数を持つ最適の主成分を供給できない。 凹凸混合整数半定値最適化問題としてスパースPCAを再構成することにより、証明可能な最適性に問題を解く切削平面法を設計する。 また,p=100$s,あるいはp=1,000$sの時間に,実際に1～2%のギャップを分単位で有界に与える凸緩和および欲求円周スキームを提案する。
• 参考スコア（独自算出の注目度）: 3.179831861897336
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Sparse principal component analysis (PCA) is a popular dimensionality reduction technique for obtaining principal components which are linear combinations of a small subset of the original features. Existing approaches cannot supply certifiably optimal principal components with more than $p=100s$ of variables. By reformulating sparse PCA as a convex mixed-integer semidefinite optimization problem, we design a cutting-plane method which solves the problem to certifiable optimality at the scale of selecting k=5 covariates from p=300 variables, and provides small bound gaps at a larger scale. We also propose a convex relaxation and greedy rounding scheme that provides bound gaps of $1-2\%$ in practice within minutes for $p=100$s or hours for $p=1,000$s and is therefore a viable alternative to the exact method at scale. Using real-world financial and medical datasets, we illustrate our approach's ability to derive interpretable principal components tractably at scale.
• Abstract（参考訳）: スパース主成分分析(PCA)は、元の特徴の小さな部分集合の線形結合である主成分を得るための一般的な次元削減手法である。 既存のアプローチでは、$p=100s$以上の変数を持つ最適の主成分を供給できない。 スパースpcaを凸混合整数半定値最適化問題として再構成することにより、p=300変数からk=5共変量を選択するスケールで検証可能な最適性を解き、より大きなスケールで小さなバウンドギャップを提供する切断平面法を考案する。 また,p=100$s の場合や,p=1,000$s の場合の時間帯において,実際に1-2\%$ となるような凸緩和とグリーディ丸め方式を提案する。 実世界の金融と医療のデータセットを用いて、大規模に解釈可能な主成分を抽出できるアプローチの能力について説明する。

関連論文リスト

• The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysis [6.996002801232415]
  平均回帰マルコフ決定過程において,$varepsilon$-optimal Policyを学習するためのプラグインアプローチのサンプル複雑性について検討した。 この問題の最も単純なアルゴリズムであるにもかかわらず、プラグインのアプローチは理論上は分析されていない。
  論文  参考訳（メタデータ） (2024-10-10T05:08:14Z)
• Black-Box $k$-to-$1$-PCA Reductions: Theory and Applications [19.714951004096996]
  ブラックボックスデフレ法を$k$-PCAアルゴリズムを設計するためのフレームワークとして分析する。 我々の主な貢献は、$k$-PCAのデフレ法における近似パラメータの劣化に対する、よりシャープな境界である。 我々は,最先端の$k$-PCAアルゴリズムをデータセット汚染に頑健にするために,我々のフレームワークを適用した。
  論文  参考訳（メタデータ） (2024-03-06T18:07:20Z)
• Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives [8.403841349300103]
  本研究では,無向ガウス図形モデルに基づくスパースグラフの学習問題を考察する。 擬似微分関数の $ell_0$-penalized バージョンに基づく新しい推定器 GraphL0BnB を提案する。 実/合成データセットに関する数値実験により,本手法がほぼ最適に,p = 104$の問題を解けることが示唆された。
  論文  参考訳（メタデータ） (2023-07-18T15:49:02Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes [80.89852729380425]
  そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。 我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
  論文  参考訳（メタデータ） (2022-12-12T18:58:59Z)
• 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)
• Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling [64.31011847952006]
  我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。 我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。 我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
  論文  参考訳（メタデータ） (2022-06-05T21:32:33Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization [104.96004056928474]
  本稿では,非コンケーブ最小値問題に対する高速適応勾配降下法を提案する。 我々は,本手法が,ミニバッチサイズが$O(kappa2.5epsilon-3)$のより低いサンプル複雑性に達することを示す。
  論文  参考訳（メタデータ） (2021-06-30T14:47:09Z)
• Sparse online variational Bayesian regression [0.0]
  完全ベイズアプローチに代わる安価でスケーラブルな代替手段としてのバリエーションベイズ推論。 線形モデルの場合、この方法は決定論的最小二乗問題の反復解のみを必要とする。 大きな p の場合、近似は計算とメモリの両方において o(p) のコストの有望な結果が得られる。
  論文  参考訳（メタデータ） (2021-02-24T12:49:42Z)
• A New Basis for Sparse Principal Component Analysis [5.258928416164104]
  以前のスパース主成分分析では、固有基底 ($p 倍 k$ 行列) がほぼスパースであると仮定されていた。 我々は、$p × k$ 行列が、$k × k$ 回転の後にほぼスパースとなると仮定する手法を提案する。 同レベルの疎度では,提案したスパースPCA法の方が安定であり,代替手法よりも分散を説明できることを示す。
  論文  参考訳（メタデータ） (2020-07-01T16:32:22Z)
• FANOK: Knockoffs in Linear Time [73.5154025911318]
  本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。 当社のメソッドは、最大50,000ドルという問題でテストしています。
  論文  参考訳（メタデータ） (2020-06-15T21:55:34Z)

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

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