arXiv:2510.25670cs.LGcs.CR2025-10NeurIPS被引 9

提出更精确的低秩近似误差界,提升隐私保护主成分分析的实用性能。

Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy

  • 基于复分析的轮廓自举法,推导对称矩阵扰动的谱范数新界。
  • 在弱特征间距和范数条件下,误差估计精度提升至√n倍。
  • 适用于隐私保护主成分分析,解决领域内长期未解的效用保障难题。

机器学习中一个核心挑战是理解噪声或测量误差对低秩近似的影响,尤其在谱范数下。这一问题在差分隐私低秩近似中尤为关键,目标是在保护隐私的同时保留数据矩阵的前p个主成分结构。以往研究多关注弗罗贝尼乌斯范数误差或重构质量变化,但这些指标可能高估或低估真实子空间失真。相比之下,谱范数能捕捉最坏方向误差,提供最强效用保证。本文建立新的高概率谱范数扰动界,改进经典Eckart--Young--Mirsky定理,明确刻画了矩阵A∈ℝ^{n×n}与任意对称扰动E之间的交互作用。在弱特征间距和范数条件下,对‖(A + E)_p - A_p‖的估计达到尖锐水平,精度最高可提升√n倍。作为应用,我们推导出改进的差分隐私PCA效用保证,解决了文献中的开放问题。分析依赖于一种新颖的复分析轮廓自举方法,并将其扩展到包括多项式和矩阵指数在内的广泛谱函数类。在真实数据集上的实验表明,我们的边界在多种扰动情形下紧密跟踪实际谱误差。

原文摘要 · Abstract (English)

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.

低秩近似差分隐私谱范数

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。