pith. sign in

arxiv: 2605.18379 · v1 · pith:LN5OBGBTnew · submitted 2026-05-18 · 💻 cs.LG

Beyond Square Roots: Explicit Memory-Efficient Factorization for Multi-Epoch Private Learning

Nikita P. Kalinin , Aki Rehn , Joel Daniel Andersson , Antti Honkela , Christoph H. Lampert This is my paper

Pith reviewed 2026-05-20 13:17 UTC · model grok-4.3

classification 💻 cs.LG
keywords differentially private learningcorrelated noisebanded inverse factorizationmemory efficiencymulti-epoch trainingnoise bufferroot mean square errorprivacy guarantees
0
0 comments X

The pith

γ-BIFR unifies prior factorizations to improve correlated noise for low-memory private training.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces γ-BIFR as a single tunable generalization of existing banded inverse factorizations for generating correlated noise in differentially private model training. It shows that this parameterization delivers lower root mean square error and better private training outcomes when memory forces a small correlation window, while also tightening the error bounds that arise from data reuse across multiple epochs. A reader would care because it directly tackles the resource-utility tradeoff that limits how much noise can be correlated without exceeding available buffer space or compute.

Core claim

The authors propose γ-BIFR, a unified generalization of the DP-λCGD one-step buffer and the BISR larger-window approach. This method supplies an explicit banded inverse factorization of the correlation matrix that remains computationally tractable, preserves the statistical properties needed for privacy analysis, and yields improved RMSE, amplified RMSE, and private training performance specifically in the low-bandwidth regime while producing tighter multi-participation error guarantees for multi-epoch training.

What carries the argument

γ-BIFR, a parameterized banded inverse factorization of the correlation matrix that interpolates between one-step and wider-window noise buffers while controlling memory via bandwidth.

If this is right

  • Lower RMSE and amplified RMSE when the noise buffer is restricted to a few steps.
  • Measurable gains in utility during actual private model training under tight memory limits.
  • Tighter analytic bounds on the extra error caused by repeated participation across epochs.
  • Practical deployment of correlated-noise mechanisms becomes feasible with smaller on-device buffers.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same parameterization could be tested for extending training epochs further without increasing memory footprint on edge devices.
  • Similar tunable factorizations might apply to other correlation structures arising in distributed or federated private optimization.
  • If the RMSE gains hold at scale, the method would reduce the number of epochs needed to reach a target accuracy under a fixed privacy budget.

Load-bearing premise

The correlation matrix admits an explicit banded inverse factorization controlled by γ that preserves the statistical properties required for differential privacy analysis.

What would settle it

An experiment at bandwidth one that measures RMSE and final model accuracy for γ-BIFR against DP-λCGD and BISR on a standard multi-epoch private training benchmark and finds no improvement would falsify the performance claim.

Figures

Figures reproduced from arXiv: 2605.18379 by Aki Rehn, Antti Honkela, Christoph H. Lampert, Joel Daniel Andersson, Nikita P. Kalinin.

Figure 1
Figure 1. Figure 1: Comparison of the proposed γ-BIFR and γ-BFR factorizations with the explicit BSR and BISR factorizations, as well as the zeroth-order banded factorization 1/j + c, where c is optimized to minimize the RMSE. All plots use n = 1024 iterations for different number of participations k and no amplification by subsampling. We observe that γ-BIFR is consistently much closer to the optimal banded inverse factoriza… view at source ↗
Figure 2
Figure 2. Figure 2: (a) Balls-in-Bins amplified RMSE for the proposed [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Validation accuracy on CIFAR-10 for different values of [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Test accuracy on CIFAR-10 in the low- (p [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Test accuracy of BERT-base fine-tuning on IMDb dataset in the low- (p [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗
read the original abstract

Correlated-noise mechanisms are among the most promising approaches for improving the utility of differentially private model training, but rigorous guarantees require explicit, analyzable factorizations, and practical deployment requires memory efficiency. Recent works have developed banded inverse factorizations, which address both requirements by exploiting a banded structure in the correlation matrix. The bandwidth controls the size of the noise buffer used to correlate noise across iterations, and thus governs the tradeoff between utility and memory cost. Existing factorizations highlight this tradeoff: DP-$\lambda$CGD achieves high memory efficiency by using only a one-step noise buffer, but this limits its utility gains, while the banded inverse square root (BISR) factorization exploits larger correlation windows and is asymptotically optimal for large bandwidths but performs poorly at low bandwidths. We propose $\gamma$-BIFR, a unified generalization of both factorizations. In the low-memory, low-bandwidth regime, $\gamma$-BIFR significantly improves RMSE, amplified RMSE, and private training performance, while yielding tighter theoretical guarantees for multi-participation error in multi-epoch training.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes γ-BIFR, a parameterized generalization of banded inverse factorizations for generating correlated noise in differentially private multi-epoch training. It unifies DP-λCGD at γ=0 (one-step buffer) and BISR at γ=1 (larger correlation windows), claiming that intermediate γ values yield improved RMSE, amplified RMSE, and private training performance in the low-memory low-bandwidth regime while providing tighter theoretical guarantees on multi-participation error.

Significance. If the algebraic construction is exact and the reported gains are reproducible, the work strengthens the practical toolkit for memory-efficient correlated-noise mechanisms in DP-SGD by offering a tunable tradeoff that improves upon the utility limits of one-step buffers without incurring the low-bandwidth degradation of full BISR.

major comments (2)
  1. [Derivation of the γ-BIFR factorization (likely §3 or §4)] The central claim that γ-BIFR exactly reproduces the target covariance (or its inverse) for 0<γ<1 at small bandwidths is load-bearing for all reported RMSE and multi-participation improvements. The manuscript must supply an explicit algebraic verification or closed-form proof that the γ-parameterized entries of L satisfy L L^T equal to the desired correlation matrix while preserving exact noise variance and positive-definiteness; boundary cases are clear but intermediate values require demonstration rather than assertion.
  2. [Experimental results on RMSE (likely §5)] Table or figure reporting low-bandwidth RMSE and amplified RMSE: the quantitative gains attributed to intermediate γ must be accompanied by a direct comparison showing that the observed improvement is not an artifact of the specific correlation matrix chosen; if the factorization deviates from the target covariance, the utility numbers cannot be interpreted as evidence for the method.
minor comments (2)
  1. [Throughout] Notation for the bandwidth parameter and the precise definition of the noise buffer size should be made consistent between the abstract, the factorization equations, and the experimental setup.
  2. [Theoretical analysis section] The abstract states 'tighter theoretical guarantees' for multi-participation error; the corresponding theorem statement should explicitly compare the new bound to the prior DP-λCGD and BISR bounds rather than only to the non-correlated baseline.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments on the manuscript. We address each major comment below and describe the revisions we will make to strengthen the algebraic presentation and experimental controls.

read point-by-point responses

  1. Referee: [Derivation of the γ-BIFR factorization (likely §3 or §4)] The central claim that γ-BIFR exactly reproduces the target covariance (or its inverse) for 0<γ<1 at small bandwidths is load-bearing for all reported RMSE and multi-participation improvements. The manuscript must supply an explicit algebraic verification or closed-form proof that the γ-parameterized entries of L satisfy L L^T equal to the desired correlation matrix while preserving exact noise variance and positive-definiteness; boundary cases are clear but intermediate values require demonstration rather than assertion.

    Authors: We agree that an explicit algebraic verification is necessary for rigor. Section 3 derives γ-BIFR by parameterizing the inverse factorization of the banded correlation matrix to interpolate between DP-λCGD (γ=0) and BISR (γ=1). In the revision we will add a dedicated subsection containing the closed-form expressions for the entries of L, a direct computation showing L L^T recovers the target matrix for any γ ∈ [0,1], and a short argument confirming that noise variance is preserved and positive-definiteness follows from the construction. The verification will be illustrated for small bandwidths to make the intermediate case transparent. revision: yes

  2. Referee: [Experimental results on RMSE (likely §5)] Table or figure reporting low-bandwidth RMSE and amplified RMSE: the quantitative gains attributed to intermediate γ must be accompanied by a direct comparison showing that the observed improvement is not an artifact of the specific correlation matrix chosen; if the factorization deviates from the target covariance, the utility numbers cannot be interpreted as evidence for the method.

    Authors: We accept the need for an explicit control to rule out artifacts. Because γ-BIFR is constructed to match the target covariance exactly (as will be shown in the added algebraic verification), the reported RMSE improvements are not due to deviation. In the revised Section 5 we will add a table that directly compares (i) the RMSE achieved by γ-BIFR, (ii) the RMSE obtained from a dense Cholesky factorization of the same target matrix (used as ground truth on small instances), and (iii) the boundary cases γ=0 and γ=1. This comparison will confirm that the gains arise from the tunable intermediate γ values. revision: yes

Circularity Check

0 steps flagged

No significant circularity; explicit new parameterization introduced without reduction to fitted inputs or self-citation chains

full rationale

The paper proposes γ-BIFR as an explicit unified generalization of prior banded inverse factorizations (DP-λCGD at γ=0 and BISR at γ=1), with the central construction being a new γ-parameterized form for the banded inverse that is presented as directly satisfying the required correlation and noise properties by algebraic design rather than by fitting to target RMSE or error metrics. No load-bearing step reduces a claimed performance gain or theoretical guarantee back to a self-citation or to a parameter fitted on the evaluation data itself. The derivation chain remains self-contained against the stated assumptions about the correlation matrix admitting such a factorization.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The central claim rests on the existence of an explicit, memory-efficient banded inverse factorization for the correlation matrix that can be generalized via a single parameter γ while preserving differential privacy properties.

free parameters (1)
  • γ
    Tunable generalization parameter introduced to interpolate between prior factorizations; its specific value selection is not detailed in the abstract.
axioms (1)
  • domain assumption The noise correlation matrix possesses a banded structure that admits an explicit inverse factorization.
    Invoked to enable memory-efficient noise generation across iterations.

pith-pipeline@v0.9.0 · 5737 in / 1217 out tokens · 37133 ms · 2026-05-20T13:17:52.879753+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

95 extracted references · 95 canonical work pages

  1. [1]

    Ponomareva, Natalia and Hazimeh, Hussein and Kurakin, Alex and Xu, Zheng and Denison, Carson and McMahan, H Brendan and Vassilvitskii, Sergei and Chien, Steve and Thakurta, Abhradeep Guha , journal=JAIR, volume=. How to

    work page

  2. [2]

    Gradient Perturbation is Underrated for Differentially Private Convex Optimization , author=

    work page

  3. [3]

    Theory of Cryptography Conference (TCC) , nopages=

    Calibrating noise to sensitivity in private data analysis , author=. Theory of Cryptography Conference (TCC) , nopages=. 2006 , noorganization=

    work page 2006

  4. [4]

    Hyperparameter Tuning with Renyi Differential Privacy , author=

    work page

  5. [5]

    Large Language Models Can Be Strong Differentially Private Learners , author=

    work page

  6. [6]

    Toward training at imagenet scale with differential privacy , author=

    work page

  7. [7]

    Adaptive privacy preserving deep learning algorithms for medical data , author=

    work page

  8. [8]

    Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy , author=

    work page

  9. [9]

    and McMahan, H

    Denisov, S. and McMahan, H. B. and Rush, J. and Smith, A. and Thakurta, G. A. , booktitle=NeurIPS, year=. Improved

    work page

  10. [10]

    Spectral properties of banded

    B. Spectral properties of banded. 2005 , publisher=

    work page 2005

  11. [11]

    D. A. Lavis and B. W. Southern , journal=. The inverse of a symmetric banded. 1997 , nopublisher=

    work page 1997

  12. [12]

    2001 , nourl =

    Marc Van Barel and Georg Heinig and Peter Kravanja , title =. 2001 , nourl =

    work page 2001

  13. [13]

    Choquette-Choo, C. A. and Ganesh, A. and McKenna, R. and McMahan, H. B. and Rush, J. K. and Thakurta, A. G. and Zheng, X. , title =

    work page

  14. [14]

    Linear and Multilinear Algebra , volume=

    Some singular value inequalities via convexity , author=. Linear and Multilinear Algebra , volume=. 2019 , publisher=

    work page 2019

  15. [15]

    and Upadhyay, J

    Henzinger, M. and Upadhyay, J. and Upadhyay, S. , title =

    work page

  16. [16]

    and McMahan, B

    Kairouz, P. and McMahan, B. and Song, S. and Thakkar, O. and Thakurta, A. and Xu, Z. , title =

    work page

  17. [17]

    and Miklau, G

    Li, C. and Miklau, G. and Hay, M. and McGregor, A. and Rastogi, V. , title =

    work page

  18. [18]

    IEEE Transactions on Knowledge and Data Engineering , volume=

    Privacy enhanced matrix factorization for recommendation with local differential privacy , author=. IEEE Transactions on Knowledge and Data Engineering , volume=. 2018 , publisher=

    work page 2018

  19. [19]

    Federated matrix factorization with privacy guarantee , author=

    work page

  20. [20]

    Choquette-Choo, C. A. and McMahan, H. B. and Rush, K. and Thakurta, A. , title =

    work page

  21. [21]

    and Henzinger, M

    Fichtenberger, H. and Henzinger, M. and Upadhyay, J. , title =

    work page

  22. [22]

    and Grudsky, S

    Böttcher, A. and Grudsky, S. M. , title =

    work page

  23. [23]

    MacWilliams, F. J. and Sloane, N. J. A. , title =

    work page

  24. [24]

    Choquette-Choo, C. A. and Ganesh, A. and Steinke, T. and Thakurta, A. , title =

    work page

  25. [25]

    Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy , author=

    work page

  26. [26]

    Choquette-Choo, C. A. and Dvijotham, K. and Pillutla, K. and Ganesh, A. and Steinke, T. and Thakurta, A. , title =

    work page

  27. [27]

    and Chu, A

    Abadi, M. and Chu, A. and Goodfellow, I. and McMahan, H. B. and Mironov, I. and Talwar, K. and Zhang, L. , title =. ACM Special Interest Group on Security, Audit and Control (SIGSAC) , year =

    work page

  28. [28]

    Linear Algebra and its Applications , year=

    A. Linear Algebra and its Applications , year=

    work page

  29. [29]

    International Workshop on Applied Parallel Computing (PARA) , nopages=

    Blocked Schur algorithms for computing the matrix square root , author=. International Workshop on Applied Parallel Computing (PARA) , nopages=. 2012 , noorganization=

    work page 2012

  30. [30]

    , title =

    Jury, E.I. , title =

    work page

  31. [31]

    Relaxed monotonic conditions for

    Nguyen, Thang V and Mori, Yoshihiro and Mori, Takehiro , journal=. Relaxed monotonic conditions for. 2007 , nopublisher=

    work page 2007

  32. [32]

    N. V. Thang and Y. Mori and T. Mori , title =. IEICE transactions on fundamentals of electronics, communications and computer sciences , year =

    work page

  33. [33]

    K. H. Rosen , title =

    work page

  34. [34]

    Mathematics for the Analysis of Algorithms , author=

    work page

  35. [35]

    1931 , nopublisher=

    Gershgorin, Semyon Aranovich , journal=. 1931 , nopublisher=

    work page 1931

  36. [36]

    and Kücük, H

    Batir, N. and Kücük, H. and Sorgun, S. , title =. Transactions on Combinatorics , year =

    work page

  37. [37]

    and Gardner, R

    Carney, N. and Gardner, R. and Keaton, R. and Powers, A. , title =. Journal of Approximation Theory , year =

    work page

  38. [38]

    A new algorithm for solving

    de Hoog, Frank , journal=. A new algorithm for solving. 1987 , nopublisher=

    work page 1987

  39. [39]

    , title =

    Dwork, C. , title =. International colloquium on automata, languages, and programming (ICALP) , year =

    work page

  40. [40]

    and Roth, A

    Dwork, C. and Roth, A. , title =

    work page

  41. [41]

    , title =

    Vadhan, S. , title =

    work page

  42. [42]

    McMahan, H. B. and Xu, Z. and Zhang, Y. , year=. A Hassle-free Algorithm for Private Learning in Practice: Don't Use Tree Aggregation, Use

    work page

  43. [43]

    McKenna, R. , year=. Scaling up the Banded Matrix Factorization Mechanism for Differentially Private

    work page

  44. [44]

    2024 , note=

    pfl-research: simulation framework for accelerating research in Private Federated Learning , author=. 2024 , note=

    work page 2024

  45. [45]

    1953 , note=

    The Characteristic Roots of Certain Real Symmetric Matrices , author=. 1953 , note=

    work page 1953

  46. [46]

    and Lampert, C

    Kalinin, N. and Lampert, C. H. , title =

    work page

  47. [47]

    Balle, Borja and Berrada, Leonard and Charles, Zachary and Choquette-Choo, Christopher A and De, Soham and Doroshenko, Vadym and Dvijotham, Dj and Galen, Andrew and Ganesh, Arun and Ghalebikesabi, Sahra and Hayes, Jamie and Kairouz, Peter and McKenna, Ryan and McMahan, Brendan and Pappu, Aneesh and Ponomareva, Natalia and Pravilov, Mikhail and Rush, Keith...

    work page

  48. [48]

    Near exact privacy amplification for matrix mechanisms , author=

    work page

  49. [49]

    A proposal for

    Strang, Gilbert , journal=. A proposal for. 1986 , publisher=

    work page 1986

  50. [50]

    Andersson, Joel Daniel and Yehudayoff, Amir , title =

    work page

  51. [51]

    IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) , year=

    Streaming Private Continual Counting via Binning , author=. IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) , year=

    work page

  52. [52]

    Binned Group Algebra Factorization for Differentially Private Continual Counting , author=

    work page

  53. [53]

    Improved differentially private continual observation using group algebra , author=

    work page

  54. [54]

    A smooth binary mechanism for efficient private continual observation , author=

    work page

  55. [55]

    Almost tight error bounds on differentially private continual counting , author=

    work page

  56. [56]

    Chua, Lynn and Ghazi, Badih and Harrison, Charlie and Leeman, Ethan and Kamath, Pritish and Kumar, Ravi and Manurangsi, Pasin and Sinha, Amer and Zhang, Chiyuan , booktitle=AISTATS, year=

    work page

  57. [57]

    Privacy amplification for matrix mechanisms , author=

    work page

  58. [58]

    An Inversion Theorem for

    McMahan, H Brendan and Pillutla, Krishna , note=. An Inversion Theorem for

    work page

  59. [59]

    Advances in private training for production on-device language models , author=

    work page

  60. [60]

    Improving the

    Balle, Borja and Wang, Yu-Xiang , booktitle=ICML, year=. Improving the

    work page

  61. [61]

    Correlated Noise Mechanisms for Differentially Private Learning , author=

    work page

  62. [62]

    Multi-epoch matrix factorization mechanisms for private machine learning , author=

    work page

  63. [63]

    2026 , booktitle=

    Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting , author=. 2026 , booktitle=

    work page 2026

  64. [64]

    Continual release moment estimation with differential privacy , author=

    work page

  65. [65]

    Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private

    Kalinin, Nikita P and McKenna, Ryan and Upadhyay, Jalaj and Lampert, Christoph H , booktitle=ICLR, year=. Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private

    work page

  66. [66]

    Correlated noise provably beats independent noise for differentially private learning , author=

    work page

  67. [67]

    Correlating Cross-Iteration Noise for

    Gu, Xin and Xiao, Yingtai and He, Guanlin and Bai, Jiamu and Kifer, Daniel and Maeng, Kiwan , note=. Correlating Cross-Iteration Noise for

    work page

  68. [68]

    Privacy amplification by random allocation , author=

    work page

  69. [69]

    Leveraging randomness in model and data partitioning for privacy amplification , author=

    work page

  70. [70]

    Optimal Accounting of Differential Privacy via Characteristic Function , author =

    work page

  71. [71]

    2017 , noorganization=

    Mironov, Ilya , booktitle=. 2017 , noorganization=

    work page 2017

  72. [72]

    Computing tight differential privacy guarantees using

    Koskela, Antti and J. Computing tight differential privacy guarantees using

    work page

  73. [73]

    Conference on Secure and Trustworthy Machine Learning (SaTML) , year=

    Avoiding pitfalls for privacy accounting of subsampled mechanisms under composition , author=. Conference on Secure and Trustworthy Machine Learning (SaTML) , year=

    work page

  74. [74]

    Towards efficient and scalable training of differentially private deep learning , author=

    work page

  75. [75]

    , author=

    Learning Rate Scheduling with Matrix Factorization for Private Training. , author=. Foundations of Responsible Computing (FORC) , year=

    work page

  76. [76]

    Proceedings of international conference for high performance computing, networking, storage and analysis (SC) , year=

    Parallel random numbers: as easy as 1, 2, 3 , author=. Proceedings of international conference for high performance computing, networking, storage and analysis (SC) , year=

    work page

  77. [77]

    High-speed random number generator co-processors for machine learning and

    Shannon Egan , booktitle=. High-speed random number generator co-processors for machine learning and

    work page

  78. [78]

    Devlin, Jacob and Chang, Ming-Wei and Lee, Kenton and Toutanova, Kristina , booktitle=

    work page

  79. [79]

    An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale , author =

    work page

  80. [80]

    Kalinin, Nikita P and McKenna, Ryan and Pagh, Rasmus and Lampert, Christoph H , note=

    work page

Showing first 80 references.