論文の概要: Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy

• arxiv url: http://arxiv.org/abs/2510.25670v1
• Date: Wed, 29 Oct 2025 16:36:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-30 15:50:45.802952
• Title: Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy
• Title（参考訳）: 低域近似のためのスペクトル摂動境界とプライバシへの応用
• Authors: Phuc Tran, Nisheeth K. Vishnoi, Van H. Vu,
• Abstract要約: mathbbRn 倍 n$ の対称行列 $A と任意の対称摂動 E$ に対して、新しい高確率スペクトル-ノルム摂動境界を導入する。 穏やかな固有ギャップとノルム条件の下では、我々の境界は$|(A + E)_p - A_p|$に対して鋭い推定値を得るが、最大で$sqrtn$となる。 応用として,PCAの実用性保証の改善を導出し,文献の未解決問題を解消する。
• 参考スコア（独自算出の注目度）: 13.264499801590583
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A central challenge in machine learning is to understand how noise or measurement errors affect low-rank approximations, particularly in the spectral norm. This question is especially important in differentially private low-rank approximation, where one aims to preserve the top-$p$ structure of a data-derived matrix while ensuring privacy. Prior work often analyzes Frobenius norm error or changes in reconstruction quality, but these metrics can over- or under-estimate true subspace distortion. The spectral norm, by contrast, captures worst-case directional error and provides the strongest utility guarantees. We establish new high-probability spectral-norm perturbation bounds for symmetric matrices that refine the classical Eckart--Young--Mirsky theorem and explicitly capture interactions between a matrix $A \in \mathbb{R}^{n \times n}$ and an arbitrary symmetric perturbation $E$. Under mild eigengap and norm conditions, our bounds yield sharp estimates for $\|(A + E)_p - A_p\|$, where $A_p$ is the best rank-$p$ approximation of $A$, with improvements of up to a factor of $\sqrt{n}$. As an application, we derive improved utility guarantees for differentially private PCA, resolving an open problem in the literature. Our analysis relies on a novel contour bootstrapping method from complex analysis and extends it to a broad class of spectral functionals, including polynomials and matrix exponentials. Empirical results on real-world datasets confirm that our bounds closely track the actual spectral error under diverse perturbation regimes.
• Abstract（参考訳）: 機械学習における中心的な課題は、特にスペクトルノルムにおいて、ノイズや測定誤差が低ランク近似にどのように影響するかを理解することである。 この問題は、プライバシを確保しつつ、データ由来の行列のトップ$p$の構造を維持することを目的としている、微分的にプライベートな低ランク近似において特に重要である。 以前の研究はしばしばフロベニウスの標準誤差や復元品質の変化を分析するが、これらの指標は過度に、あるいは過小評価される真の部分空間歪みを引き起こす。 対照的に、スペクトルノルムは最悪のケースの方向誤差を捉え、最も強力なユーティリティ保証を提供する。 古典的エッカート-ヨン-ミルスキーの定理を洗練させる対称行列に対する新しい高確率スペクトル-ノルム摂動境界を確立し、行列 $A \in \mathbb{R}^{n \times n} と任意の対称摂動$E$ との相互作用を明示的に捉える。 穏やかな固有ギャップとノルム条件の下で、我々の境界は、$\|(A + E)_p - A_p\|$ に対して鋭い推定値を得る。 応用として,PCAの実用性保証の改善を導出し,文献の未解決問題を解消する。 解析は複素解析から新しい輪郭ブートストラッピング法に依存し、多項式や行列指数を含むスペクトル汎関数の幅広いクラスに拡張する。 実世界のデータセットにおける実験結果から、我々の境界は様々な摂動条件下での実際のスペクトル誤差を綿密に追跡していることが確認された。

関連論文リスト

• Perturbation Bounds for Low-Rank Inverse Approximations under Noise [14.907968476859219]
  スペクトルノルム誤差 $| (tildeA-1)_p - A_p-1 |$ for a $ntimes n$ symmetric matrix $A$, where $A_p-1$ is the best rank-(p) approximation of $A-1$, and $tildeA = A + E$ is a noisy observed。 ノイズの軽度な仮定の下で、固有ギャップ、スペクトル崩壊とどのように誤差がスケールするかを明らかにする鋭い非漸近境界を導出する。
  論文  参考訳（メタデータ） (2025-10-29T14:40:12Z)
• Spectral Graph Clustering under Differential Privacy: Balancing Privacy, Accuracy, and Efficiency [53.98433419539793]
  エッジ差分プライバシー(DP)下におけるスペクトルグラフクラスタリングの問題点について検討する。 具体的には, (i) エッジフリップによるグラフ摂動と, エッジプライバシを強制する隣接行列シャッフルを併用したグラフ摂動, (ii) 次元と複雑性の複雑さを低減するために低次元空間における加法的ガウス雑音を伴うプライベートグラフプロジェクション, (iii) 収束性を維持しながらエッジDPを確保するために反復的にガウス雑音を分散するノイズの多いパワーイテレーション手法である。
  論文  参考訳（メタデータ） (2025-10-08T15:30:27Z)
• Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data [33.082961718280245]
  p-ノルム正規化急勾配 (NSD) と運動量急勾配 (NMD) に対する暗黙的最適化バイアスの完全な特徴付けを行う。 これらのアルゴリズムは行列の p-ノルムに関してマージンを最大化する解に収束することを示した。
  論文  参考訳（メタデータ） (2025-02-07T05:09:32Z)
• Transformers as Support Vector Machines [54.642793677472724]
  自己アテンションの最適化幾何と厳密なSVM問題との間には,形式的等価性を確立する。 勾配降下に最適化された1層変圧器の暗黙バイアスを特徴付ける。 これらの発見は、最適なトークンを分離し選択するSVMの階層としてのトランスフォーマーの解釈を刺激していると信じている。
  論文  参考訳（メタデータ） (2023-08-31T17:57:50Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。 すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
  論文  参考訳（メタデータ） (2023-01-31T18:47:42Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nystr\"om method [76.73096213472897]
  我々は,データ行列のスペクトル特性を利用して近似保証を改良する手法を開発した。 我々のアプローチは、特異値減衰の既知の速度を持つデータセットのバウンダリが大幅に向上する。 RBFパラメータを変更すれば,改良された境界線と多重発振曲線の両方を実データセット上で観測できることが示される。
  論文  参考訳（メタデータ） (2020-02-21T00:43:06Z)

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

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