PaperlayerView exact revision on arXiv

Source-linked AI summary

Differentially Private Preconditioned Power Iteration Method for Principal Component Analysis that Adapts to the Coherence

Duy V. Le, Ta Duy Nguyen, Alina Ene, Huy L. Nguyen

arXiv:2610.36691v1cs.DS

TL;DR

Releasing a PCA subspace can reveal an individual's row, and coherence-adaptive row-level ℓ2 privacy had not covered the top-k subspace. The paper uses preconditioned, clipped block power iteration to estimate it privately. Its utility improves on low-coherence inputs and remains near optimal across spectral-ratio regimes.

  • Problem

    Prior coherence-adaptive utility guarantees under row-level ℓ2 privacy addressed leading singular-vector estimation, not the top-k subspace, while releasing a subspace can reveal an individual's row.

    Source: §1 · pp. 1–2

  • Method

    A preconditioned, clipped block power iteration estimates the top-k right-singular subspace under row-level ℓ2 differential privacy.

    Source: §1 · p. 2

  • Results

    The utility improves on low-coherence inputs, and the algorithm remains near optimal across all regimes of σ²_{k+1}/σ²_k.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The algorithm extends coherence-adaptive private PCA from a leading singular vector to the top-k subspace without requiring coherence or σ²_{k+1}/σ²_k as input.

    Source: §1 · p. 2

    The analysis assumes n≥d and row ℓ2 norms at most 1; the authors state the norm bound is necessary for non-trivial utility.

    Source: §2 · p. 6

Abstract

from arXiv · show

In Principal Component Analysis (PCA), we are given as input a matrix $A\in\mathbb{R}^{n\times d}$ and an integer $k\leq d$, and the goal is to find the top $k$ right-singular vectors of $A$. We consider the setting where each row of $A$ is the private data of an individual, and we design an $(\epsilon,\delta)$-differentially private algorithm whose utility guarantee improves with the coherence of the input matrix. Prior works were either restricted to the case $k=1$ or ensured significantly weaker privacy protections. Our algorithm is based on a preconditioned variant of the power iteration method that is designed to significantly reduce the noise needed to ensure privacy.

1 Introduction

PCA targets the top-k right-singular subspace, but releasing it can expose an individual's row, motivating row-level differential privacy. This paper extends coherence-adaptive private PCA to rank k using preconditioned, clipped block power iteration.

1.1 Our contributions

  • The algorithm estimates the top-k right singular subspace under row-level ℓ2 privacy, extending Nguyen et al. [2026] beyond the leading singular vector.Source: §1 · p. 2
  • The utility improves on low-coherence inputs, and the algorithm remains near optimal across all regimes of σ²_{k+1}/σ²_k.Source: §1 · p. 2

1.2 Comparison with prior works

  • The bound replaces the worst-case dependence on d with input coherence, while Analyze Gauss needs no low-coherence condition and can be stronger outside the regime where ours improves.Source: §1.2 · p. 3

1.3 Our approach and techniques

  • Preconditioning removes the Σ_k factor from each row's update contribution, allowing the final error bound to depend on σ_k rather than all leading singular values.Source: §1.3 · pp. 4–5
  • Clipping provides a worst-case sensitivity bound but is inactive with high probability under the main-result assumptions.Source: §1.3 · p. 5
  • Private initialization adds symmetric Gaussian noise to A^T A; private selection chooses R and T because they depend on private coherence and σ²_k.Source: §1.3 · p. 5
  • The analysis exploits cancellation across independent iteration noises and shows clipping stays inactive throughout the iterations.Source: §1.3 · p. 6

2 Preliminaries

The paper formulates PCA using the top-k singular subspaces and assumes bounded row norms, a positive eigengap, and row-level privacy. It defines coherence from the left singular vectors and specifies notation used in the analysis.

2 Preliminaries

  • The input has n ≥ d rows in R^d, each with ℓ2 norm at most 1, and the paper assumes a positive eigengap ∆k := σk² − σk+1².The thin SVD defines the top-k left- and right-singular subspaces, Uk and Vk.Source: §2 · p. 6
  • Coherence is ∥U∥∞, the maximum absolute entry of the left singular vectors, and it is not known to the algorithm.The paper relates Uij to the correlation between data rows and right-singular vectors.Source: §2 · p. 6
  • The notation eO and eΩ suppresses factors polylogarithmic in n, d, 1/ϵ, 1/δ, and 1/β.For a row vector, the paper introduces clipping at radius R and sets ClipR(0) = 0.Source: §2 · p. 6
  • Neighboring inputs differ in one row, and the algorithm targets (ϵ, δ)-differential privacy under this row-level model.The algorithm and analysis use the Gaussian mechanism and advanced composition.Source: §2 · p. 6

3 Our Algorithm

The algorithm combines a private initialization with iterative preconditioned power updates, selecting clipping and iteration parameters privately. Its analysis establishes privacy and tracks error progress under conditions that keep clipping inactive.

3 Our Algorithm

  • The main algorithm uses a private initial solution, then runs the preconditioned power method with clipping radius R and iteration count T.The paper describes private selection of R and T from public powers-of-two grids.Source: §3 · pp. 6, 8
  • The initialization uses the top-k eigenvectors of a Gaussian-perturbed A⊤A, while the main updates use Gaussian noise and advanced composition to establish (ϵ, δ)-DP.The clipping and iteration parameters are privately selected using Papernot and Steinke [2022].Source: §3 · p. 8
  • In the ideal update without clipping or privacy noise, the error decreases exponentially with the eigengap.The private analysis seeks to approximately preserve this decrease when clipping remains inactive and error terms are sufficiently small.Source: §3 · p. 8
  • The analysis bounds Gaussian-noise contributions with concentration and preconditioner properties, using a martingale argument for selected error terms.It also shows clipping remains inactive with high probability under a sufficient lower bound on R.Source: §3 · pp. 8–9

4 Related work

Related work spans multiple privacy models and approaches to coherence-sensitive PCA. The paper positions its method within row-level ℓ2 privacy, contrasts worst-case guarantees, and notes distinctions from oversampling and distributional methods.

4 Related work

  • Earlier coherence-sensitive guarantees use adjacency models that differ from row-level ℓ2 privacy, so their bounds are converted for comparison under the paper’s model.The paper contrasts entry-level adjacency [Hardt and Roth, 2013, Hardt and Price, 2014, Balcan et al., 2016] and structured alternatives [Nicolas et al., 2025, d’Orsi and Novikov, 2026].Source: §4 · pp. 9–10
  • Dwork et al. [2014] give a rank-k guarantee without any coherence assumption, a benchmark for coherence-independent k-PCA; under a gap condition, spectral-to-angle conversion recovers their bound up to logarithmic factors.The result converts a spectral-norm guarantee to principal-angle error.Source: §4 · p. 10
  • Repeated deflation can deteriorate when σ1/σk is large, while block power methods update k directions simultaneously [Hardt and Price, 2014, Balcan et al., 2016, Nicolas et al., 2025].Prior block methods use oversampling; this algorithm maintains exactly k vectors.Source: §4 · p. 10
  • Statistical private PCA work assumes i.i.d. samples from structured distributions, including sub-Gaussian data for top-singular-vector estimation [Liu et al., 2022] and its top-k generalization [Düngler and Sanyal, 2025].Source: §4 · p. 10

5 AI use statement

The authors report using generative AI tools for literature work, mathematical review, and manuscript drafting, while stating that the tools were not used for data analysis or algorithm implementation.

5 AI use statement

  • Generative AI assisted with literature retrieval, proof suggestions, guarantee comparisons, and manuscript editing; the authors reviewed the resulting text and mathematical content.They state that AI tools were not used to generate or analyze data, conduct experiments, or implement the algorithm.Source: §5 · p. 11

A Main Tools

The section assembles differential-privacy, Gaussian concentration, and spectral perturbation results used in the utility analysis.

A Main Tools

  • The utility analysis draws on sensitivity-based Gaussian mechanisms and advanced composition for differential privacy.The section defines ℓ2-sensitivity and states the Gaussian mechanism and composition results.Source: A Main Tools · p. 13
  • Gaussian concentration and Davidson–Szarek bounds control Gaussian quantities, with the matrix argument switching to G^T when k > q.The proof rescales G to match the theorem’s normalization when k ≤ q.Source: A Main Tools · p. 13
  • Weyl’s inequality and the Davis–Kahan sin Θ theorem are the spectral tools used to analyze perturbations of eigenspaces.The section also invokes a lemma derived from these theorems.Source: A Main Tools · p. 14
  • Principal angles between subspaces are defined as arccosines of the singular values of the cross-product of their orthonormal bases.The definition uses bases V and bV with orthonormal columns.Source: A Main Tools · p. 14
  • The perturbation lemma considers the top-k eigenspace of A^T A + W when the perturbation norm is below the spectral gap.Its proof applies Davis–Kahan to A^T A and A^T A + W.Source: A Main Tools · p. 14
  • A matrix M with spectral norm below 1 makes I + M invertible, as shown by ruling out any nonzero vector in its nullspace.The section also states a norm inequality for I + M.Source: A Main Tools · p. 15

B.1 Privacy Analysis

The privacy analysis bounds the initialization and iterative releases, then composes their guarantees to establish differential privacy for the algorithms.

B.1 Privacy Analysis

  • Algorithm 1 is (ϵinit, δinit)-differentially private when every input row has ℓ2 norm at most 1.The theorem assumes ϵinit and δinit lie in (0, 1).Source: §B.1 · p. 15
  • The initialization adds symmetric Gaussian noise to A^T A, uses sensitivity at most 2, and computes X(0) by deterministic post-processing.The section identifies the Gaussian mechanism as providing the initialization privacy guarantee.Source: §B.1 · p. 15
  • For each H(t) release, the proof bounds a row’s contribution and replacement sensitivity; constructing B(t) is post-processing.The release is analyzed conditional on the preceding transcript because the algorithm is adaptive.Source: §B.1 · p. 16
  • For Z(t+1), clipped row contributions are combined with Gaussian noise, and QR factorization is post-processing.The proof bounds each row’s contribution using the norms of the vectors in its outer product.Source: §B.1 · p. 16
  • Sequential composition makes one iteration (2ϵiter, 2δiter)-differentially private, and advanced composition combines the T iterations.The section states the resulting total privacy parameters after composition.Source: §B.1 · p. 16
  • Lemma 11, Lemma 12, and sequential composition establish that Algorithm 3 is (ϵ, δ)-differentially private.Source: §B.1 · p. 17

B.2 Utility Analysis

The utility analysis establishes conditions for stable bounds by controlling initialization noise, ensuring clipping remains inactive so the iteration recurrence applies, and tracking convergence through Gaussian-noise and residual terms. It concludes with a corollary for ideal data-dependent choices of T and R and points to a private hyperparameter search for an analogous guarantee.

B.2 Utility Analysis

  • If s < 1, C is invertible; the analysis uses this condition to ensure the matrices E(t) are well-defined.The passage states that s < 1 suffices for invertibility.Source: §B.2 · p. 17
  • β/4 bounds the total failure probability for the stated high-probability conditions, including the row-wise bound.The row-wise bound is obtained with total failure probability β/16.Source: §B.2 · p. 19
  • Under the stated assumptions, the preconditioner roughly whitens the top-k component and makes P(t) = Σ_kC(t)B(t) invertible.The conditions include bounds on the noise and s_t, together with a lower bound on the eigengap.Source: §B.2 · pp. 19–20
  • When clipping is inactive, the next iterate remains invertible under the lemma’s condition, and E(t+1) satisfies a recurrence.The recurrence expresses E(t+1) in terms of the previous iterate and additional error terms.Source: §B.2 · pp. 20–21
  • The initialization analysis establishes Lipschitz control of E on a bounded perturbation region and uses symmetry to show a scalar function has zero mean.A Lipschitz extension supports the concentration analysis, while Claim 25 gives the zero-mean result.Source: §B.2 · pp. 23, 26

Convergence analysis

  • If clipping was inactive in iterations 0 through t−1, the inductive-step lemma shows it is inactive at iteration t as well.The argument also establishes invertibility of C(j+1) for the preceding iterations under its stated assumptions.Source: §B.2 · pp. 28–30
  • The induction starts with s0 ≤ 1/4 and m0 ≤ 1/√15, then proves the stated invariant holds through all iterations.The base case uses the initial-solution bound, and the inductive step relies on clipping remaining inactive.Source: §B.2 · pp. 30, 33, 36
  • Under Gclip, Ginit, Gmart, and the stated Lemma 21/29 event, every iteration keeps C(t) invertible, clipping inactive, and satisfies the main recurrence.The induction uses pR ≤ κk/16 < 1 and νR ≤ 1/8 as stated conditions.Source: §B.2 · pp. 32–33
  • The recurrence separates noise into a term linear in each Gaussian matrix, bounded with a martingale argument, and a more complex residual term bounded iteration by iteration.The linear term is handled by Lemma 30; the residual terms are bounded separately in norm.Source: §B.2 · p. 33

B.2 Utility Analysis

  • The main induction concludes by showing τ > t + 1, with τ = T when t + 1 = T.Source: §B.2 · p. 36
  • With probability at least 1 −β, the solution X(T) returned by Algorithm 3 satisfies the corollary’s guarantee for ideal choices of T and R.The supplied passage omits the guarantee’s formula.Source: §B.2 · p. 36
  • If the conditions of Theorem 31 are not satisfied, s2_T ≤ 1 ≤ 64ν2_R still yields the same asymptotic guarantee.Source: §B.2 · p. 37

C Private selection of the clipping radius R and iteration count T

The section privately selects the clipping radius R and iteration count T by comparing runs over a public grid, while preserving a guarantee against the best eligible pair.

C Private selection of the clipping radius R and iteration count T

  • The private hyperparameter-selection method jointly chooses R and T by comparing candidate runs against the best pair satisfying the utility hypotheses on a public grid.Each candidate consists of a pair (R, T) and the subspace produced by that run.Source: C Private selection of the clipping… · p. 37
  • Each run receives the same total Rényi privacy budget, so runs with fewer iterations use smaller per-iteration noise.Source: C Private selection of the clipping… · p. 37
  • The grid endpoints are fixed independently of the data, and the stated warm-start gap condition constrains the datasets covered by the selection guarantee.The passage gives the condition as Δk ≥ 16Δinit.Source: C Private selection of the clipping… · p. 37

C.1 A private score for comparing candidate subspaces

The section defines a smoothed spectral score for comparing candidate subspaces, designed to reduce sensitivity when the eigenvalue gap is small. When the estimated gap is sufficiently large, that score equals the candidate’s true top-k subspace error.

C.1 A private score for comparing candidate subspaces

  • If h ≤ 0, the procedure returns the initialization immediately rather than using the filtered comparison score.The text associates this case with an eigenvalue gap too small relative to the noise.Source: §C.1 · p. 38
  • The score applies a piecewise-linear spectral filter to the estimated covariance, then measures the candidate subspace’s residual against the filtered matrix.The filter is zero below a threshold, ramps between thresholds, and is one above the upper threshold.Source: §C.1 · p. 38
  • When the estimated covariance is within ew of A⊤A and Δk ≥ 8ew, the filtered score equals the true top-k subspace error for every candidate X.Under this condition, Weyl’s inequality places the top-k eigenvalues above the filter’s upper threshold and the remaining eigenvalues below its lower threshold.Source: §C.1 · pp. 38–39
  • For fixed initialization with h > 0, the score’s replacement sensitivity is at most 2/h, including when the input has a small eigenvalue gap.The section motivates this robust score as an alternative to directly comparing candidate subspaces, whose sensitivity can be large when the gap is small.Source: §C.1 · p. 38

C.2 Joint random search and its privacy cost

The algorithm jointly searches over iteration counts and clipping radii by running independent trials from one shared private initialization and releasing the candidate with the best noisy score. Its privacy analysis accounts for the trials and initialization through composition and converts the resulting Rényi-DP bound to an (ε, δ)-DP bound.

C.2 Joint random search and its privacy cost

  • Each base trial samples an iteration count and radius uniformly, runs the power-iteration algorithm from the shared initialization, and forms a noisy candidate score.The output tuple includes the radius, iteration count, candidate subspace, and noisy score.Source: §C.2 · p. 39
  • The search repeats independent base trials a geometrically distributed number of times and releases the candidate with the smallest noisy score.The trials use independent iteration noises; the shared initialization’s privacy cost is not charged again for each trial.Source: §C.2 · pp. 39–40
  • The privacy analysis bounds the selection procedure’s Rényi-DP cost and combines it with initialization cost before conversion to (ε, δ)-DP.The conversion adds a log(1/δ)/(λ − 1) term, and the text verifies the resulting bound under its stated calibration.Source: §C.2 · pp. 39–40

C.3 Utility guarantee from hyperparameter search

The utility analysis shows that the algorithm can recover a good solution under the utility-proof assumptions without prior knowledge of κk or ∥U∥∞. It searches a parameter grid, and with probability at least 1 − β its selected candidate has error at most e† + 2tval when a sufficiently good candidate is found and the noisy scores are accurate.

C.3 Utility guarantee from hyperparameter search

  • The guarantee applies under the assumptions used in the utility proof without requiring the algorithm to know κk or ∥U∥∞ in advance.The analysis uses a grid containing suitable iteration-count and radius choices under those assumptions.Source: §C.3 · p. 40
  • For a trial with suitable parameters, the clipping and martingale events jointly hold with conditional probability at least 1/2, yielding a candidate with error at most e†.Each independent base trial samples the relevant radius and iteration count with probability 1/m, so the probability of producing such a candidate is at least 1/(2m).Source: §C.3 · p. 41
  • With probability at least 1 − β, the selected candidate’s error is at most e† + 2tval when the search finds a candidate of error at most e† and all noisy scores are within tval of their true scores.The search-success and score-accuracy events, together with initialization, have total failure probability at most β.Source: §C.3 · p. 42
Loading 2610.36691v1…