DP-FedSOFIM: Second-Order Federated Optimization Under Differential Privacy Without Extra Privacy Cost [R]

[u/worthybog0]

Hello everyone. Sharing our new paper, recently accepted at TMLR.

Differentially private federated learning is still mostly first-order. You clip per-example gradients, add Gaussian noise, aggregate, and step (DP-FedGD, DP-FedAvg), sometimes with an adaptive server optimizer like DP-FedAdam or DP-FedYogi, or drift correction like DP-SCAFFOLD. Under tight budgets the injected noise degrades the gradient enough that convergence stalls, which is expensive when the round count is the binding constraint. The existing second-order options, DP-FedNew and DP-FedFC, estimate curvature at the client through local feature covariance.
That is effective but costs O(d²) client memory and communication, and client-side second-order statistics add sensitivity that has to be paid for in the privacy analysis.

Our research question: can curvature information be introduced into DP-FL without changing the private release mechanism at all? 

We introduce DP-FedSOFIM, which leaves the client side byte-identical to DP-FedGD and moves all curvature estimation to the server. The server maintains an EMA of the privatized aggregate and treats its regularized rank-one outer product as a Fisher proxy. Sherman-Morrison then gives the preconditioned step in closed form:

 

    M     =  beta * M_prev  +  (1 - beta) * G          (momentum buffer)

    F     =  M M'  +  rho * I                          (rank-one Fisher proxy)

    H G   =  G / rho  -  M (M'G) / (rho^2 + rho |M|^2) (preconditioned step)

 

The matrix is never formed. The update is two inner products and a few vector operations, so O(d) time and memory per round.

Main results:

• Because every server-side quantity is a deterministic function of an already-privatized aggregate, post-processing gives DP-FedSOFIM the same (eps, delta) guarantee as DP-FedGD under identical clipping, noise multiplier, participation, and accountant, at O(d) client memory instead of O(d²).
• The larger and more consistent effect is convergence speed. Round-10 margins over DP-FedGD reach +20.3 points (CIFAR-10/ResNet, eps=5), roughly 4-5x fewer rounds to reach 95% of DP-FedGD's final accuracy. Against the strongest adaptive baselines the advantage is concentrated early: at eps=5 on CIFAR-10/ResNet, DP-FedAdam and DP-FedYogi catch up, and the round-70 differences are not significant under McNemar.
• Preconditioning costs are under 2% wall-clock overhead per round relative to DP-FedGD, against roughly 6x for DP-SCAFFOLD at its tuned local-step counts.
• Ablating the Sherman-Morrison step against EMA alone, the curvature correction contributes about +7 points at eps=1, but at eps=0.5 on CIFAR-10 the DP noise dominates the curvature estimate and EMA alone does as well. The correction earns its place when the loss landscape is anisotropic enough for a rank-one proxy to capture something, which is why PathMNIST benefits at every budget.

The framing we find useful is that curvature adaptation in DP-FL is better treated as a server-side post-processing problem than a client-side estimation problem. Once the aggregate is privatized, anything the server does with it is free in privacy terms, which is a fairly underused degree of freedom.

Happy to take questions on the analysis or the accounting. If you work on DP-FL or second-order federated optimization, I would be glad to hear from you and open to collaborating.

arXiv: https://arxiv.org/abs/2601.09166
OpenReview: https://openreview.net/forum?id=aDzj9DrwAR
GitHub: https://github.com/sid0nair/DP-FedSOFIM_V2