論文の概要: On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA

• arxiv url: http://arxiv.org/abs/2606.21951v1
• Date: Sat, 20 Jun 2026 08:38:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-25 23:41:10.548126
• Title: On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA
• Title（参考訳）: プライベートスパース共分散推定における次元の曲線とPCAについて
• Authors: Syamantak Kumar, Shourya Pandey, Purnamrita Sarkar, Kevin Tian,
• Abstract要約: 作用素ノルムにおける高次元微分プライベート(DP)共分散推定と主成分分析(PCA)について検討する。 プライベートでない設定では、$mathsfpoly(k, log d)$ サンプルがこれら2つの問題を解決するのに十分であることが知られている。 DPの下では,PCAに対する$mathsfpoly(k, log d)$サンプル複雑性が可能であることを示す。
• 参考スコア（独自算出の注目度）: 20.109939947492954
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study high-dimensional differentially private (DP) covariance estimation in the operator norm, and principal component analysis (PCA), under $k$-row-column sparsity ($k$-RCS) of the covariance matrix. In the non-private setting, it is known that $\mathsf{poly}(k, \log d)$ samples suffice to solve both of these problems. However, the only comparable result known under DP (Wang et al. 2021) requires $Ω(d)$ samples under standard parameterizations of the problem. We investigate when this curse of dimensionality is inherent for sparse covariance estimation tasks under DP. On the upper bound front, we show that a $\mathsf{poly}(k, \log d)$ sample complexity for PCA is possible under DP, if we also posit sparsity of the leading eigenvector. We complement this result with $\mathsf{poly}(d)$ lower bounds under DP for both sparse covariance estimation and PCA, establishing an exponential gap between the private and non-private variants of these problems when $k = \mathsf{polylog}(d)$. To our knowledge, no such separation has previously been demonstrated for any sparse estimation problems in private high-dimensional statistics. Our techniques are flexible enough that they imply stronger lower bounds even for the well-studied problem of standard DP PCA, without sparsity assumptions.
• Abstract（参考訳）: 演算子ノルムにおける高次元微分プライベート(DP)共分散推定と主成分分析(PCA)を共分散行列の$k$-row-column間隔(k$-RCS)で検討した。 プライベートでない設定では、$\mathsf{poly}(k, \log d)$ サンプルがこれら2つの問題を解決するのに十分であることが知られている。 しかし、DP (Wang et al 2021) で知られている唯一の同等の結果は、問題の標準パラメータ化の下で$Ω(d)$サンプルを必要とする。 DP下での余分な共分散推定作業において,この次元の呪いがいつ自然であるかを考察する。 上限面上では、先頭固有ベクトルの空間性も仮定すれば、PCA に対する$\mathsf{poly}(k, \log d)$サンプル複雑性が DP の下で可能であることを示す。 この結果を、疎共分散推定とPCAの両方に対してDPの下限の$\mathsf{poly}(d)$で補い、$k = \mathsf{polylog}(d)$ のとき、これらの問題のプライベート変種と非プライベートな変種の間に指数的ギャップを確立する。 我々の知る限り、そのような分離は、これまでプライベートな高次元統計学におけるスパース推定問題に対して実証されていない。 提案手法は, 従来のDP PCA問題においても, 余剰な仮定を伴わずに, より強い下界を示唆するほど柔軟である。

関連論文リスト

• Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
  我々は、s-正方形および非正方形不確実性集合の下で、一般的な政策パラメータ化を伴うロバストマルコフ決定過程(RMDP)について検討する。 無限状態空間に拡張する一般政策パラメタライゼーションに対する新しいリプシッツ・リプシッツ・スムースネス特性を証明した。 本研究では,S-正方形不確かさに対する勾配降下アルゴリズムと非正方形不確かさに対するFrank-Wolfeアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2026-02-11T21:44:20Z)
• An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise [8.555773470114698]
  任意の$k leq d$に対してトップ$k$固有ベクトルを推定できるアルゴリズムを提案する。 我々のアルゴリズムは、$n = tilde!O(d)$ であっても、ほぼ最適統計誤差を達成する。
  論文  参考訳（メタデータ） (2025-08-14T17:48:45Z)
• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Private Mean Estimation with Person-Level Differential Privacy [6.621676316292624]
  複数のサンプルを持つ場合の個人レベルの個人別平均推定について検討した。 我々は、計算効率のよいアルゴリズムを、純粋DPで、計算効率の悪いアルゴリズムを、ほぼ一致する下界は、近似DPの最も寛容な場合を抑える。
  論文  参考訳（メタデータ） (2024-05-30T18:20:35Z)
• Sparse PCA with Oracle Property [115.72363972222622]
  新規な正規化を伴うスパースPCAの半定緩和に基づく推定器群を提案する。 我々は、家族内の別の推定器が、スパースPCAの標準半定緩和よりも、より急激な収束率を達成することを証明した。
  論文  参考訳（メタデータ） (2023-12-28T02:52:54Z)
• Privately Estimating a Gaussian: Efficient, Robust and Optimal [6.901744415870126]
  純微分プライバシー(DP)モデルと近似微分プライバシー(DP)モデルの両方において、ガウス分布をプライベートに推定する効率的なアルゴリズムを提供する。 純粋なDP設定では、未知の$d$次元ガウス分布を任意の全変分誤差まで推定する効率的なアルゴリズムを与える。 平均推定の特別な場合、我々のアルゴリズムは$widetilde O(d1.5)$の最適なサンプル複雑性を達成し、以前の作業から$widetilde O(d1.5)$のバウンドを改善する。
  論文  参考訳（メタデータ） (2022-12-15T18:27:39Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)

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

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