論文の概要: Black-Box $k$-to-$1$-PCA Reductions: Theory and Applications
- arxiv url: http://arxiv.org/abs/2403.03905v1
- Date: Wed, 6 Mar 2024 18:07:20 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-07 14:05:05.924652
- Title: Black-Box $k$-to-$1$-PCA Reductions: Theory and Applications
- Title（参考訳）: Black-Box $k$-to-1$-PCAの削減:理論と応用
- Authors: Arun Jambulapati, Syamantak Kumar, Jerry Li, Shourya Pandey, Ankit
Pensia, Kevin Tian
- Abstract要約: ブラックボックスデフレ法を$k$-PCAアルゴリズムを設計するためのフレームワークとして分析する。
我々はデフレアルゴリズムが定数$k$に対してパラメータ損失を負わないことを示した。
我々は,最先端の$k$-PCAアルゴリズムをデータセット汚染に頑健にするために,我々のフレームワークを適用した。
- 参考スコア（独自算出の注目度）: 20.70357142968864
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The $k$-principal component analysis ($k$-PCA) problem is a fundamental
algorithmic primitive that is widely-used in data analysis and dimensionality
reduction applications. In statistical settings, the goal of $k$-PCA is to
identify a top eigenspace of the covariance matrix of a distribution, which we
only have implicit access to via samples. Motivated by these implicit settings,
we analyze black-box deflation methods as a framework for designing $k$-PCA
algorithms, where we model access to the unknown target matrix via a black-box
$1$-PCA oracle which returns an approximate top eigenvector, under two popular
notions of approximation. Despite being arguably the most natural
reduction-based approach to $k$-PCA algorithm design, such black-box methods,
which recursively call a $1$-PCA oracle $k$ times, were previously
poorly-understood.
Our main contribution is significantly sharper bounds on the approximation
parameter degradation of deflation methods for $k$-PCA. For a quadratic form
notion of approximation we term ePCA (energy PCA), we show deflation methods
suffer no parameter loss. For an alternative well-studied approximation notion
we term cPCA (correlation PCA), we tightly characterize the parameter regimes
where deflation methods are feasible. Moreover, we show that in all feasible
regimes, $k$-cPCA deflation algorithms suffer no asymptotic parameter loss for
any constant $k$. We apply our framework to obtain state-of-the-art $k$-PCA
algorithms robust to dataset contamination, improving prior work both in sample
complexity and approximation quality.
- Abstract（参考訳）: k$-principal component analysis(k$-PCA)問題は基本的なアルゴリズムプリミティブであり、データ解析や次元減少アプリケーションで広く利用されている。
統計的設定では、$k$-PCA の目標は、分布の共分散行列のトップ固有空間を特定することである。
これらの暗黙的な設定により、ブラックボックスデフレ法を$k$-PCAアルゴリズムを設計するためのフレームワークとして分析し、近似近似の2つの一般的な概念の下で、ブラックボックスの1ドル$-PCAオーラクルを介して未知のターゲット行列へのアクセスをモデル化する。
k$-pcaアルゴリズム設計に対する最も自然な還元ベースのアプローチであるにもかかわらず、このようなブラックボックスメソッドは再帰的に1$-pca oracle $k$ timesと呼ばれ、以前はあまり理解されていなかった。
我々の主な貢献は、$k$-pcaのデフレ法における近似パラメータの分解に関するかなり鋭い境界である。
ePCA (Energy PCA) と呼ぶ近似の二次形式として、デフレ法はパラメータ損失を伴わないことを示す。
cPCA(correlation PCA)という別のよく研究された近似概念に対して、デフレ法が実現可能なパラメータ構造を厳しく特徴づける。
さらに、全ての実現可能なレシエーションにおいて、$k$-cPCAデフレアルゴリズムは、任意の定数$k$に対して漸近パラメータ損失を生じないことを示す。
我々は,最先端の$k$-PCAアルゴリズムを用いて,汚染を解析し,サンプルの複雑さと近似品質の両方において先行作業を改善する。
関連論文リスト
- Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation [53.17668583030862]
一般関数近似の文脈において,無限水平平均逆マルコフ決定過程(AMDP)について検討する。
最適化最適化(LOOP)と呼ばれる新しいアルゴリズムフレームワークを提案する。
我々は LOOP がサブ線形 $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret を達成することを示す。
論文 参考訳（メタデータ） (2024-04-19T06:24:22Z) - Sparse PCA with Oracle Property [115.72363972222622]
新規な正規化を伴うスパースPCAの半定緩和に基づく推定器群を提案する。
我々は、家族内の別の推定器が、スパースPCAの標準半定緩和よりも、より急激な収束率を達成することを証明した。
論文 参考訳（メタデータ） (2023-12-28T02:52:54Z) - A Theoretical Analysis of Optimistic Proximal Policy Optimization in
Linear Markov Decision Processes [13.466249082564213]
本稿では,全情報フィードバックを用いた表層線形MDPに対するPPOの楽観的変種を提案する。
既存のポリシーベースのアルゴリズムと比較して, 線形MDPと逆線形MDPの双方において, 完全な情報付きで, 最先端の後悔点を達成している。
論文 参考訳（メタデータ） (2023-05-15T17:55:24Z) - Fair principal component analysis (PCA): minorization-maximization
algorithms for Fair PCA, Fair Robust PCA and Fair Sparse PCA [6.974999794070285]
公平なPCA(FPCA)問題を解決するために,新しい反復アルゴリズムを提案する。
提案アルゴリズムはアルゴリズムの反復ごとに厳密であることが証明された半直交制約の緩和に依存する。
本稿では,提案手法の性能を,合成データセットと実生活データセットの2つの最先端手法と比較する。
論文 参考訳（メタデータ） (2023-05-10T08:14:32Z) - Human-in-the-loop: Provably Efficient Preference-based Reinforcement
Learning with General Function Approximation [107.54516740713969]
本研究は,RL(Human-in-the-loop reinforcement learning)を軌道的嗜好で検討する。
各ステップで数値的な報酬を受ける代わりに、エージェントは人間の監督者から軌道上のペアよりも優先される。
一般関数近似を用いたPbRLの楽観的モデルベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-05-23T09:03:24Z) - AgFlow: Fast Model Selection of Penalized PCA via Implicit
Regularization Effects of Gradient Flow [64.81110234990888]
主成分分析(PCA)は特徴抽出と次元減少の有効な手法として広く用いられている。
High Dimension Low Sample Size (HDLSS) 設定では、ペナル化ロードを備えた修正主成分が好まれる。
ペナル化PCAの高速モデル選択法として近似勾配流(AgFlow)を提案する。
論文 参考訳（メタデータ） (2021-10-07T08:57:46Z) - An Online Riemannian PCA for Stochastic Canonical Correlation Analysis [37.8212762083567]
投影行列の再パラメータ化を用いた正準相関解析(CCA)のための効率的なアルゴリズム(RSG+)を提案する。
本論文は,その特性の定式化と技術的解析に主眼を置いているが,本実験により,一般的なデータセットに対する経験的挙動が極めて有望であることが確認された。
論文 参考訳（メタデータ） (2021-06-08T23:38:29Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z) - Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。
スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。
本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-23T04:25:36Z) - Solving Large-Scale Sparse PCA to Certifiable (Near) Optimality [3.179831861897336]
既存のアプローチでは、$p=100s$以上の変数を持つ最適の主成分を供給できない。
凹凸混合整数半定値最適化問題としてスパースPCAを再構成することにより、証明可能な最適性に問題を解く切削平面法を設計する。
また,p=100$s,あるいはp=1,000$sの時間に,実際に1～2%のギャップを分単位で有界に与える凸緩和および欲求円周スキームを提案する。
論文 参考訳（メタデータ） (2020-05-11T15:39:23Z) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。
そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文 参考訳（メタデータ） (2020-03-11T23:23:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。