Source-linked AI summary
Beyond Worst-Case Analysis in Private Singular Vector Computation
Moritz Hardt, Aaron Roth
TL;DR
Worst-case error bounds for differentially private singular-vector computation grow with dimension, which can hinder useful guarantees. This paper uses matrix coherence and a robust analysis of power iteration to obtain data-dependent bounds. The coherence dependence is nearly optimal for every setting, and the approach also improves worst-case bounds and spectral-norm low-rank approximations.
Problem
Worst-case differentially private singular-vector error scales with dimension, which can overwhelm the signal in bounded, sparse matrices.
Source: §1 · p. 2Method
The paper analyzes a robust power iteration method with per-round perturbations chosen to guarantee differential privacy.
Source: §1.3 · p. 4Results
The algorithm replaces dimension dependence with coherence-based error, with a nearly matching lower bound for every coherence setting up to logarithmic factors.
Source: §1 · p. 2, §1.1 · p. 3Takeaways & Limitations
The approach also yields improved worst-case bounds and spectral-norm low-rank approximations, with optimal quality for rank 1.
Source: §1 · p. 2, §7 · p. 20During deflation, incoherence can increase by up to √r, and the paper leaves open whether this factor is necessary.
Source: §1.3 · p. 5
Abstract
from arXiv · showhide
We consider differentially private approximate singular vector computation. Known worst-case lower bounds show that the error of any differentially private algorithm must scale polynomially with the dimension of the singular vector. We are able to replace this dependence on the dimension by a natural parameter known as the coherence of the matrix that is often observed to be significantly smaller than the dimension both theoretically and empirically. We also prove a matching lower bound showing that our guarantee is nearly optimal for every setting of the coherence parameter. Notably, we achieve our bounds by giving a robust analysis of the well-known power iteration algorithm, which may be of independent interest. Our algorithm also leads to improvements in worst-case settings and to better low-rank approximations in the spectral norm.
1 Introduction
Differentially private singular-vector algorithms face worst-case error that grows with dimension, potentially overwhelming the signal in bounded, sparse matrices. The paper replaces dimension dependence with coherence-based guarantees, analyzes a robust power iteration method, and extends the approach to low-rank approximation and worst-case settings.
1 Introduction
- Worst-case error can overwhelm the signal for bounded, sparse matrices, motivating guarantees that depend on the input rather than dimension alone.The paper situates this goal among applications of spectral methods to sensitive data, including user and movie-review records.Source: §1 · p. 2
1.1 Our Results
- Coherence-based error replaces dimension dependence, and a matching lower bound shows the dependence is nearly optimal for every coherence setting, up to logarithmic factors.The paper also gives rank-k spectral-norm approximations; rank-k bounds for k ≥ 2 depend on the matrix rank, while rank-1 quality is optimal.Source: §1 · p. 2, §1.1 · p. 3
1.2 More efficient and improved worst-case bounds
- For unit spectral-norm perturbations, the paper gives the first (ε,δ)-differential privacy bound and improves prior worst-case algorithmic results.The dependence on n matches randomized response for single-entry changes.Source: §1.2 · p. 4
1.3 Our Techniques
- Robust power iteration tolerates per-round perturbations under conditions that preserve a near-top singular-value guarantee after O(log n) rounds.The analysis supports choosing perturbations to guarantee privacy; during deflation, incoherence can increase by up to √r, and whether that factor is necessary remains open.Source: §1.3 · pp. 4–5
1.4 Related Work
- Low-coherence matrices can substantially improve on worst-case bounds, and the power-iteration variant runs nearly linearly in input sparsity.The paper contrasts its spectral-norm guarantees and direct singular-vector computation with prior Frobenius-norm work whose coherence dependence was not shown tight [HR12].Source: §1.4 · pp. 5–6
2 Preliminaries
The preliminaries set the paper’s privacy and matrix conventions, define coherence relative to a singular value decomposition, and reduce general matrices to a symmetric construction that preserves coherence.
2 Preliminaries
- Neighboring matrices differ in one entry by at most 1, and differential privacy bounds how much output probabilities can change between such inputs.The definition permits an additive δ alongside the multiplicative exp(ε) factor.Source: §2 · pp. 6–7
2.1 Matrix coherence
- The paper defines matrix coherence relative to a particular singular value decomposition, which matters because the decomposition need not be unique.Source: §2.1 · p. 8
2.2 Reduction to symmetric matrices
- A symmetric block matrix B represents a general matrix A while preserving its coherence and encoding each entry change in A as two entry changes in B.Its rank is 2r, and each singular value of A occurs twice in B.Source: §2.2 · p. 8
- The reduction lets an algorithm for B recover singular vectors of A with small parameter loss, while privacy on B transfers to A with halved privacy parameters.Source: §2.2 · p. 8
3 Robust convergence of power iteration
The section analyzes power iteration under perturbations that may be chosen adaptively and adversarially, then applies that robustness analysis to private power iteration. Under stated spectral and noise conditions, the private method has a high-probability convergence guarantee and satisfies differential privacy.
3 Robust convergence of power iteration
- Under the stated spectral-gap and perturbation conditions, robust power iteration outputs a vector meeting the lemma’s convergence guarantee.The analysis allows the perturbation to be chosen adaptively and adversarially at each round.Source: §3 · pp. 8, 10
3.1 Privacy-Preserving Power Iteration
- Private power iteration composes per-round privacy guarantees to obtain differential privacy for the full algorithm.Source: §3.1 · p. 11
4 Power Iteration and Incoherence
The section uses symmetry of the iterates’ signs to control their coordinate magnitudes in terms of coherence, establishing that PPI usually avoids premature termination. Combined with its convergence analysis, this yields the stated high-probability output guarantee.
4 Power Iteration and Incoherence
- For symmetric A, the signs of the iterates’ correlations with its eigenvectors are uniformly distributed over {−1,1}^n.This sign symmetry supports the subsequent control of intermediate-vector coordinate magnitudes.Source: §4 · p. 13
- With probability 1 − 1/n, PPI terminates successfully after T rounds when T ⩽ n and C ⩾ 16µ(A)log(n).Source: §4 · p. 14
- Combining successful termination with the convergence lemma gives PPI’s stated error guarantee with probability 8/10 under the theorem’s assumptions.Source: §4 · p. 14
5 Rank k approximations and Deflation
The section extends approximate rank-1 results to rank-k spectral-norm approximations by repeated deflation. Its analysis must control both approximation quality and coherence as deflation proceeds.
5 Rank k approximations and Deflation
- The rank-k result uses repeated rank-1 approximations of deflated matrices, requiring both approximately optimal rank-1 steps and propagated incoherence.The section identifies these as the two requirements for combining the approximations.Source: §5 · p. 15
- The analysis adapts matrix deflation to approximate eigenvectors, building on a modification of the lemma from [KT13].The section also invokes lemmas to argue that deflation preserves incoherence.Source: §5 · pp. 15–16
- Theorem 5.7 outputs a rank-1 matrix and Theorem 5.8 outputs a rank-k matrix, each with probability 7/10 under their stated spectral conditions; the latter assumes rank-r input.Source: §5 · pp. 17–18
- Rank-k approximation incurs a factor of √r from possible coherence degradation during deflation, and the section leaves open whether this loss is necessary.Here r is the rank of the initial matrix.Source: §5 · p. 17
6 Lower Bound
The lower-bound section constructs matrices across coherence settings to show that private singular-vector accuracy cannot substantially improve on the paper’s coherence-dependent guarantee, up to logarithmic factors.
6 Lower Bound
- For every coherence value C in [2,n], a family of n × n matrices establishes a lower bound for differentially private singular-vector computation.The theorem considers approximate top singular vectors under differential privacy.Source: §6 · p. 18
- The theorem’s bound is tight for rank-1 approximation across coherence values, up to logarithmic factors.The paper states this consequence in Remark 6.2.Source: §6 · p. 18
- The construction encodes a uniformly chosen bit-valued database in a matrix family, reducing private singular-vector computation to private database reconstruction.The database vectors have exactly n/2 nonzero entries, and the matrix construction repeats database rows.Source: §6 · pp. 18, 20
7 Conclusions and Open Problems
The conclusion summarizes coherence-dependent guarantees and identifies open questions about weaker coherence measures, rank dependence, and data-dependent privacy bounds beyond spectral analysis.
7 Conclusions and Open Problems
- The paper presents its top-singular-vector bounds in terms of coherence and identifies data-dependent accuracy as a broader research agenda for differential privacy.It points to natural data structure such as low coherence as a possible basis for more accurate private analyses in other domains.Source: §7 · pp. 20–21
- Whether µk-coherence, which constrains only the top k singular vectors, suffices to bound top-singular-vector approximation quality remains unresolved.The paper reports a bound on powering’s local sensitivity in terms of µk-coherence as evidence for the conjecture.Source: §7 · p. 20
- For k ≥ 2, rank-k bounds depend on matrix rank because deflation can incur a √r coherence loss; whether that factor is inherent remains open.The paper asks whether the factor can be removed.Source: §7 · p. 20
A Deviation bounds
This appendix collects deviation-bound results used in the paper, including Gaussian anti-concentration and a Chernoff bound.
A Deviation bounds
- The appendix states a Gaussian anti-concentration lemma for independent standard normal variables with nonnegative weights.The supplied passage gives the lemma’s setup but not its bound.Source: A Deviation bounds · p. 22
- A consequence for a Gaussian vector and a k-dimensional subspace is stated as Lemma A.2.The supplied passage does not expose the lemma’s conclusion.Source: A Deviation bounds · p. 22
- The appendix also states a Chernoff bound for a sum of independent random variables.The passage defines the sum and its variance before stating the bound.Source: A Deviation bounds · p. 22
B Proofs from Section 5
This section relates the algorithm’s norm guarantee to the Rayleigh quotient and modifies a deflation lemma to use a norm-based condition.
B Proofs from Section 5
- The norm-based condition is needed because the algorithm guarantees ∥Av∥ rather than the Rayleigh quotient v^T Av.The proof first relates these quantities, then applies the modified deflation lemma.Source: B Proofs from Section 5 · pp. 23–24
- A vector with ∥Ax∥ ≥ (1−α)λ1 has a Rayleigh quotient bounded below by (1−5α)λ1 in the proof.The argument separates eigenvalues near the top from the remaining spectrum to bound the contribution to x^T Ax.Source: B Proofs from Section 5 · p. 23
- The modified deflation lemma replaces a near-optimal Rayleigh-quotient condition with a near-optimal bound on ∥Ax∥.It assumes ∥Ax∥ ≥ (1−α/C)λ1 and sets the deflation scale t within a factor 1±α/C of ∥Ax∥.Source: B Proofs from Section 5 · pp. 23–24
C Perturbation bounds for matrix powers
This section bounds perturbations of matrix powers, interpreting the result as local sensitivity of power iteration. It introduces top-k coherence, a weaker coherence notion depending only on the top few singular vectors.
C Perturbation bounds for matrix powers
- Top-k coherence is a weaker coherence notion that depends only on the top few singular vectors.The definition is introduced for a matrix with singular value decomposition M = Σ σi u_i v_i^T.Source: C Perturbation bounds for matrix powers · p. 24
- Theorem C.2 gives a perturbation bound for matrix powers under stated spectral and power conditions.Its assumptions include σ1 ≥ 4q, σk+1 ≤ σ1/2, and q ≥ log n + 1, with g ∼ N(0,1)^n.Source: C Perturbation bounds for matrix powers · p. 24
- The proof expands (M + E)^q − M^q into terms formed from powers of M interspersed with E.It bounds the resulting terms and sums their error contributions to establish the theorem.Source: C Perturbation bounds for matrix powers · pp. 25–26