Federated Differentially Private Optimization via Low-Rank Preconditioning

1 Introduction

• Covariance estimates can approximate Hessian information and accelerate first-order DP optimization, but estimating the covariance remains the computational and communication bottleneck.In federated learning, fewer optimization iterations directly reduce communication rounds.Source: §1 · p. 1
• Existing full-covariance central DP methods require O(p2) communication, while linear-communication federated covariance baselines use local DP and degrade in privacy-utility as client count grows.The paper identifies a gap in methods that combine communication-efficient low-rank covariance estimation, central DP, and end-to-end secure aggregation.Source: §1 · p. 2

1.1 Our Contributions

• The framework combines DP rank selection, a federated DP power method, and a noisy release of the covariance projected onto the selected subspace.Its stages use client-wise sums, making the pipeline compatible with secure aggregation; the covariance error bound separates subspace error from projected-covariance noise.Source: §1.1 · pp. 2–3
• A rank-k preconditioner acts approximately as a Newton step in the estimated subspace and a gradient step on its orthogonal complement, with an effective condition number governing convergence.The analysis reports a large explicit reduction in communication rounds relative to first-order DP-FL.Source: §1.1 · p. 3
• The covariance approximation matches or improves on the centralized O(p2) Analyze Gauss baseline at a fraction of the communication cost, while preconditioned fine-tuning improves the accuracy-communication trade-off.The reported optimization comparison is against vanilla federated DP-FC and first-order baselines on benchmark image datasets at moderate privacy budgets.Source: §1.1 · p. 3

The Problem

• PCA represents the leading directions of data variance by the first k left singular vectors, which are also the leading eigenvectors of XX⊤.These vectors provide the low-dimensional subspace for the covariance approximation.Source: §2 · p. 3
• The target is a private global rank-k covariance estimate with O(pk) rather than O(p2) communication.The paper treats the uncentered second moment XX⊤ as the covariance matrix.Source: §2 · pp. 3–4
• For GLM losses, the covariance-based matrix dominates the Hessian up to diagonal scaling, so using it in preconditioned gradient descent approximates a Newton iteration.The gradient and covariance are both sums of client-wise contributions.Source: §2 · p. 4
• The full-covariance Analyze Gauss baseline requires clients to upload and the server to broadcast O(p2) scalars.The low-rank approximation is introduced to reduce this communication cost.Source: §2 · p. 4
• The proposed factored estimate communicates O(pk) scalars per round and applies its inverse in O(pk + k2) operations without forming a p × p matrix.Each stage is a sum of client contributions plus Gaussian noise, supporting end-to-end secure aggregation and a composed record-level DP guarantee.Source: §2 · p. 4

Preliminaries of Differential Privacy

• The paper uses record-level add/remove adjacency: neighboring datasets differ by one record held by any client.When normalization is needed, the noisy sum is divided by the public total record count.Source: §3 · p. 4
• Differential privacy requires the randomized mechanism's output distributions on neighboring datasets to satisfy the stated (ε, δ) bound.The paper treats its algorithms as adaptive compositions of Gaussian mechanisms.Source: §3 · pp. 4–5
• For Gaussian mechanisms, the privacy analysis uses each mechanism's L2 sensitivity and noise scale to bound the guarantee of their composition.The composition can equivalently be expressed using µ-GDP, with the paper giving its (ε, δ) characterization.Source: §3 · p. 5
• The reported guarantees use add/remove adjacency and can be converted to substitute-one adjacency by adjusting the noise scales for matrix releases and gradient rounds.The passage specifies the respective scale adjustments for the DP-PCA stages and gradient rounds.Source: §3 · p. 5

4.1 Basis Computation with DP Power Method

• A noisy federated power method computes an orthonormal basis for the leading k-dimensional subspace by aggregating client contributions and orthogonalizing the result.Each iteration uses Gaussian noise calibrated to sensitivity C2 under the add/remove relation.Source: §4.1 · pp. 5–6

4.2 Private Covariance Matrix Estimation

• After basis computation, the method projects the global covariance into that subspace and releases the projected matrix with symmetric Gaussian noise.The release is assembled from local contributions, with clients adding noise to the sum.Source: §4.2 · p. 6
• The factored output keeps communication at O(pk) per round and O(Tpk + k2) in total, without transmitting the full covariance matrix.The two stages compose as T + 1 Gaussian mechanisms, and the stated privacy guarantee does not depend on client count.Source: §4.2 · pp. 6–7

4.3 Error Bound for Covariance Estimation

• The covariance error separates into a subspace term from the approximate basis and a noise term from the projected release; the subspace bound depends on the true covariance's spectral gap.The projected-noise term is governed by the spectral norm of a k × k symmetric Gaussian matrix.Source: §4.3 · p. 7
• Balancing the two error sources guides privacy-budget allocation, with a smaller spectral gap favoring a larger share for the basis-computation stage.The theorem's bound is stated under its iteration and probability conditions.Source: §4.3 · pp. 7–8

5 Private Rank Estimation

• A shared Gaussian projection compresses the covariance to an r×r matrix; clients clip projected data and securely aggregate noisy shares to release it.The projection matrix is generated from a common public seed.Source: §5 · p. 8
• The setup assumes clients’ data columns have bounded ℓ2 norm and that all clients share a public seed; clipping bounds each projected column’s ℓ2 norm by C̄.The clipping operation is applied column-wise.Source: §5 · p. 8
• Under an honest-but-curious server and secure aggregation with distributed Gaussian noise, the initialization stage obtains centralized DP guarantees at O(r^2) scalars per client per round.Each client adds a noise share scaled by σ√N to its local upload.Source: §5 · p. 8
• The released matrix has the Gaussian mechanism’s privacy guarantee: it is μ-GDP with μ = C̄₂/σ.Source: §5 · p. 9
• Thresholding the noisy matrix’s eigenvalues selects rank; with high probability, it lies between the clipped projected covariance’s eigenvalue counts above 2σb_r and above zero, preventing overestimation.The rank estimate is derived from the noisy matrix eC.Source: §5 · pp. 8–9

• A preconditioned step is an approximate Newton step within the span of V and a gradient step of size η/λ on its orthogonal complement.Source: §6 · p. 10
• The utility theorem bounds convergence when the generalized eigenvalues of (Cλ, P) lie in [a, b] and the step size satisfies 0 < η ≤ 1/b.Source: §6 · p. 11
• The preconditioner takes larger steps and injects more noise per round than DP-GD, but needs proportionally fewer rounds.The comparison uses DP-GD's rate of 1 − 1/κ0 and noise coefficient p/(λ1 + λ), versus the preconditioned method's rate 1 − 1/(bκk) and noise coefficient at most p/(λ + λk+1).Source: §6 · p. 11
• Ignoring log terms, at equal gradient-phase privacy the low-rank method matches DP-GD's privacy–utility bound up to a factor and can slightly improve it when γ and λp/λ are small.It does so in approximately bκk/κ0 of the rounds; the comparison excludes the preconditioner privacy budget and its construction rounds.Source: §6 · p. 11
• For convex GLMs with rescaled loss curvature in [c, 1] along the iterate path, the round comparison carries over, but the noise bound is looser and the stated corollary does not carry over directly.The analysis is for scalar-output GLMs and is directly generalizable to multiclass softmax loss.Source: §6 · p. 12

7 Experiments

• Results are means over five independent runs, with error bars showing ±1 empirical standard deviation.Source: §7 · p. 12

7.1 Illustration of Rank Estimation

• For MNIST, the dominant part of the singular-value spectrum is recovered accurately at projection dimensions r ∈ {20, 50, 80}.The comparison is between singular values of the feature matrix and square roots of eigenvalues of the DP covariance estimate.Source: §7.1 · p. 12, Figure 1 · p. 13

7.2 DP-PCA Comparison

• On UCI HAR, the proposed method improves on Analyze Gauss at every tested ε and k while requiring only O(Tpk + k2) communication.The comparison uses p = 561 features, k ∈ {10, 20, 40}, and T = 3 power iterations.Source: §7.2 · p. 12, Figure 2 · p. 13

7.3 Preconditioned DP Fine-Tuning

• Fine-tuning experiments use DP linear classification heads on frozen ResNet-34 or ViT-B/16 features, with fixed rank k = ⌈1.2m⌉ and T = 2 power iterations.The evaluation includes FashionMNIST, CIFAR-10, and CIFAR-100; rank selection is not run in these experiments.Source: §7.3 · p. 14
• At ε = 2, both preconditioned methods converge faster and to higher accuracy than first-order baselines, while the low-rank method closely matches vanilla DP-FC.The low-rank preconditioner avoids transmitting the full p × p covariance.Source: §7.3 · p. 14
• The method reaches vanilla DP-FC’s final accuracy at a fraction of total communication and achieves the best accuracy–communication trade-off at this privacy level.The one-off covariance-estimation cost scales as O(Tpk + k2), rather than O(p2).Source: §7.3 · p. 14, Figure 3 · p. 15
• At the smallest tested budgets, first-order methods are competitive or better because noise in the estimated subspace can outweigh the curvature gain.The reported cases are FashionMNIST at ε = 0.5 and CIFAR-100 at ε = 1.Source: §7.3 · p. 14

8 Conclusions

• The proposed optimizer matches DP-GD utility in a fraction of the rounds, and DP-PCA matches the centralized O(p^2) baseline at a fraction of the communication cost.The framework uses DP rank selection, a federated DP power method, and an Analyze Gauss release on the projected covariance; its aggregation stages decompose into per-client sums.Source: §8 · p. 15
• The paper identifies streaming or random mini-batch sampling and covariance preconditioning in broader private training pipelines as natural next steps.The cited examples include multilayer neural networks.Source: §8 · pp. 15–16

A.1 Hockey-Stick Divergence, Dominating Pairs, and PRVs

• Adaptive privacy composition can be bounded by finding a dominating pair for each step, summing the corresponding PRVs, and evaluating the resulting expectation.The proof of Lemma 2 uses the hockey-stick divergence and PRV framework.Source: A Proof of Lemma 2 · p. 20, §A.1 · p. 21

A.2 The PRV of a Gaussian mechanism

• For a Gaussian mechanism, the corresponding PRV is Gaussian, and substituting it into the divergence expression yields the analytical Gaussian bound.The standard Gaussian cumulative distribution function appears in that bound.Source: §A.2 · p. 21

A.3 Proof of Lemma 2

• Each Gaussian mechanism has a tightly dominating pair, whose PRV is Gaussian; the product pair therefore yields a sum of independent Gaussian PRVs for adaptive composition.The proof uses the analytical privacy profile to obtain the claimed bound.Source: §A.3 · pp. 21–22
• A composition of T Gaussian mechanisms with common sensitivity Δ and noise standard deviation Δσ is (ε, δ)-DP under the stated range when σ = ε^-1√(4T log(1/δ)).The calibration is described as a conservative consequence of Lemma 2.Source: §A.3 · p. 22

B.1 Proof of Lemma 7

• For an add/remove change with clipped projection norm at most C̄, the released projected covariance changes by yy⊤, with Frobenius norm at most C̄².The upper-triangular vectorization has ℓ2 norm no greater than that Frobenius norm.Source: §B.1 · p. 22

B.2 Proof of Lemma 8

• With high probability, Weyl’s inequality bounds each released covariance eigenvalue’s deviation by σb_r, yielding upper and lower bounds for the retained rank.The lower bound applies when the released eigenvalue exceeds 2σb_r.Source: §B.2 · p. 22

C.1 Auxiliary Results

• The convergence result for the noisy power method supplies a projection-error bound, which is then translated into a covariance approximation bound.The proof combines the basis-computation and noisy projected-matrix error terms.Source: §C.1 · pp. 23, 25
• The noisy power method’s output is analyzed relative to the leading k eigenvectors, under a public iteration count and Gaussian noise calibrated using the public feature-norm bound.Theorem C.4 also states an (ε, δ)-DP guarantee under its stated parameter conditions.Source: §C.1 · pp. 23–24

C.2 The Proof of Theorem 6

• Theorem 6’s two stages compose their privacy guarantees: the noisy power-method output is post-processing, followed by a Gaussian mechanism for the projected release.The proof separately bounds the two error terms and combines the bounds using a union bound.Source: §C.2 · p. 26

D Proofs for Section 6

• The error recursion for preconditioned gradient descent is governed by the spectrum of P^-1Cλ, whose extreme generalized eigenvalues can be characterized by a Rayleigh quotient.The proof uses this characterization to analyze convergence.Source: D Proofs for Section 6 · p. 26

D.1 Auxiliary Lemma

• For V equal to the leading eigenvectors and zero projected noise, the generalized eigenvalues are 1 in the retained subspace and (λ_i + λ)/λ outside it.They lie in [1, κ_k], and the trace of the inverse preconditioner is given by the sum of reciprocal diagonal entries.Source: §D.1 · p. 27

D.2 Proof of Lemma 9

• The proof bounds the preconditioner approximation using the subspace projector error and projected-matrix noise; the subspace error is the sine of the largest principal angle.A matrix sandwich yields bounds on the inverse and its trace when γ < 1.Source: §D.2 · p. 27

D.3 Proof of Theorem 10

• The convergence proof bounds the spectrum of the transformed update and uses it to control the error recursion.The update contracts when ηb ≤ 1, under the stated spectral bounds.Source: §D.3 · pp. 27–28

D.4 Proof of Corollary 11

• The corollary proof compares the DP-GD condition number with the preconditioned bound and uses the trace bound for the approximate preconditioner.It sets η = 1/b and κ = b/a in the convergence result.Source: §D.4 · p. 28

E Extension of the Convergence Analysis to Generalized Linear Models

• Because the iteration matrices vary and do not commute, the analysis bounds their product in the fixed preconditioner metric.The matrices vary across iterations because they depend on the iterate.Source: E Extension of the Convergence… · p. 29
• For logistic loss, the curvature condition holds when logits along the iterate path are bounded; projected iterations can provide that bound.Without projection, bounded logits are an assumption because DP noise is unbounded and regularization alone does not ensure bounded iterates.Source: E Extension of the Convergence… · p. 29
• Under the two-sided curvature condition, every eigenvalue of the preconditioned Hessian lies between c/(1 + γ) and κ_k/(1 − γ).The theorem applies when γ < 1.Source: E Extension of the Convergence… · p. 29
• The extension bounds loss suboptimality by κ_k/[2(1 − γ)] times the squared preconditioner-metric distance to the optimum.The bound is stated for the iterate’s loss relative to the optimum.Source: E Extension of the Convergence… · p. 30

F.2 Comparison to Locally DP Baseline (Method of Grammenos et al. (2020))

• Grammenos et al.’s relative error increases as clients grow from 4 to 16, while our aggregated-noise design keeps its privacy–utility trade-off independent of client count.Their local randomization occurs before truncated SVD; our per-client noise variance scales as σ²/N.Source: §F.2 · p. 31

F.3 Qualitative Illustration: Private Covariance Heatmaps

• Our method preserves WISDM covariance block-correlation structure at ε = 0.16 and rank 20, while Analyze Gauss produces a noise-dominated heatmap.Figure 7 provides a similar qualitative comparison for UCI HAR.Source: §F.3 · p. 32, Figure 6 · p. 32, Figure 7 · p. 32

F.4 Additional DP-PCA Comparison: SVHN

• The SVHN figure compares rank-k covariance approximation relative Frobenius error against ε for our method and Analyze Gauss.It covers p = 3072, k ∈ {10, 20, 40}, δ = 10^-5, and means over five runs.Source: Figure 8 · p. 33, §F.4 · p. 33

G.1 Number of Communication Rounds vs. Final Accuracy

• The accuracy figures plot total communication rounds against accuracy for CIFAR-10, CIFAR-100, and FashionMNIST.Source: Figure 9 · p. 34, Figure 10 · p. 35, Figure 11 · p. 36

G.2 Total Transmitted Parameters vs. Final Accuracy

• The transmitted-parameter figures plot total communication against accuracy for CIFAR-10, CIFAR-100, and FashionMNIST.Source: Figure 12 · p. 37, Figure 13 · p. 38, Figure 14 · p. 39

H Pseudocodes for Algorithms

• The pseudocode appendix includes a federated DP power method, a Gaussian-mechanism covariance estimator, and private rank selection via random projection.Source: H Pseudocodes for Algorithms · pp. 41–43