Abstract
In this paper, we study the (sparse) Generalized Eigenvalue Problem (GEP), which arises in a number of modern statistical learning models, such as principal component analysis (PCA), canonical correlation analysis (CCA), Fisher’s discriminant analysis (FDA) and sliced inverse regression (SIR). We provide the first study on GEP in the differential privacy (DP) model under both deterministic and stochastic settings. In the low dimensional case, we provide a $\rho$-Concentrated DP (CDP) method namely DP-Rayleigh Flow and show if the initial vector is close enough to the optimal vector, its output has an $\ell_2$-norm estimation error of $\tilde{O}(\frac{d}{n}+\frac{d}{n^2\rho})$ (under some mild assumptions), where $d$ is the dimension and $n$ is the sample size. Next, we discuss how to find such a initial parameter privately. In the high dimensional sparse case where $d\gg n$, we propose the DP-Truncated Rayleigh Flow method whose output could achieve an error of $\tilde{O}(\frac{s\log d}{n}+\frac{s\log d}{n^2\rho})$ for various statistical models, where $s$ is the sparsity of the underlying parameter. Moreover, we show that these errors in the stochastic setting are optimal up to a factor of $\mathrm{Poly}(\log n)$ by providing the lower bounds of PCA and SIR under statistical setting and in the CDP model. Finally, to give a separation between $\epsilon$-DP and $\rho$-CDP for GEP, we also provide the lower bound $\Omega(\frac{d}{n}+\frac{d^2}{n^2\epsilon^2})$ and $\Omega(\frac{s\log d}{n}+\frac{s^2\log^2 d}{n^2\epsilon^2})$ of private minimax risk for PCA, under the statistical setting and $\epsilon$-DP model, in low and high dimensional sparse case respectively.
Introduction
The Generalized Eigenvalue Problem (GEP) is a fundamental mathematical framework underpinning several cornerstone techniques in statistical learning, including Principal Component Analysis (PCA), Canonical Correlation Analysis (CCA), Fisher’s Discriminant Analysis (FDA), and Sliced Inverse Regression (SIR). These methods are essential for dimensionality reduction and feature extraction in sensitive domains such as biomedical imaging and genomic analysis.
Despite the ubiquity of GEP, a unified approach to solving it under Differential Privacy (DP) constraints has been missing. Previous research has largely focused on specific instances like DP-PCA. This paper addresses this gap by providing the first comprehensive study of DP-GEP in both deterministic and stochastic settings, covering both low-dimensional and high-dimensional sparse scenarios.
The Challenge of Private GEP
The primary objective in GEP is to maximize the Rayleigh quotient. However, the gradient of the Rayleigh quotient can have unbounded sensitivity, making standard private optimization techniques like DP-SGD—which typically inject noise into gradients—ineffective or highly inaccurate. To overcome this, the authors propose a shift in strategy: perturbing the underlying covariance-like matrices rather than the iterative updates.
Methodology
The authors introduce two primary algorithms based on a "Rayleigh Flow" approach, utilizing $\rho$-Concentrated Differential Privacy ($\rho$-CDP).
1. DP-Rayleigh Flow (Low-Dimensional)
For low-dimensional settings, the DP-Rayleigh Flow algorithm adds Gaussian noise directly to the estimated matrices $\hat{A}$ and $\hat{B}$ at each iteration. This matrix perturbation approach bypasses the sensitivity issues inherent in the gradient, allowing for stable and private optimization.
2. DP-Truncated Rayleigh Flow (High-Dimensional Sparse)
In high-dimensional settings where the number of features $d$ significantly exceeds the sample size $n$, the authors introduce a truncation step. By maintaining only the top $k$ most significant entries in the eigenvector at each iteration, the algorithm effectively projects the problem onto a lower-dimensional space. This mitigation strategy limits the impact of privacy-induced noise on the final estimation.
3. Private Initialization
GEP is a non-convex problem, necessitating a high-quality initial starting point. The authors provide a method for private initialization by reformulating the GEP as a convex optimization problem with a LASSO penalty, ensuring the entire pipeline remains differentially private.
Theoretical Results and the Privacy Gap
A significant contribution of this work is the establishment of near-optimal error rates and the identification of a "privacy gap" between different DP models.
- Utility Guarantees: The proposed algorithms achieve an $\ell_2$-norm estimation error of roughly $\tilde{O}(\frac{d}{n} + \frac{d}{n^2\rho})$ in low dimensions and $\tilde{O}(\frac{s \log d}{n} + \frac{s \log d}{n^2\rho})$ in sparse high-dimensional settings.
- Optimality: By providing lower bounds for PCA and SIR, the authors demonstrate that their algorithms are optimal up to a factor of $\text{Poly}(\log n)$.
- $\epsilon$-DP vs. $\rho$-CDP Separation: The research reveals that $\rho$-CDP (a relaxed version of DP) allows for significantly better utility than pure $\epsilon$-DP. Specifically, the error in $\epsilon$-DP grows quadratically with the dimension ($d^2$), whereas in $\rho$-CDP, it grows only linearly ($d$). This suggests that $\rho$-CDP is a more suitable framework for generalized eigenvalue problems.
Conclusion
This work provides a robust theoretical and algorithmic foundation for privacy-preserving GEP. By moving beyond model-specific solutions to a general framework, it enables the private application of a wide array of statistical tools. Future research directions include closing the logarithmic gap between upper and lower bounds and developing formal private initialization guarantees for the high-dimensional sparse case.
Summary updated