Private training methods that add correlated noise across steps, such as differentially private Follow-the-Regularized-Leader (DP-FTRL), all reduce to one subproblem. They must release running sums of gradients at every step, with noise added so that no single example's influence can be detected, while keeping the error in those running sums small. The field currently offers two kinds of answer and no middle ground. Tree-based mechanisms store only $O(\log T)$ noisy partial sums over $T$ steps and run in constant amortized time, but their error is several times larger than the best achievable. Dense matrix factorizations come close to the best achievable error, but they store $O(T)$ state per model coordinate, and computing them takes minutes to hours once $T$ reaches a few thousand.
We propose to close this gap using the recursive structure behind Reed–Muller codes, a family of error-correcting codes on $2^m$ coordinates built by repeatedly gluing two half-size codes together. The binary tree mechanism already is such a recursion: the prefix-sum matrix on $2T$ steps is two copies of the $T$-step matrix plus one block that carries the first half's total. We will parameterize noise mechanisms by a small learned "kernel" applied identically at every level of this recursion. The resulting mechanisms keep the tree's $O(\log T)$ memory and its streaming update. Their error can be evaluated and differentiated in closed recursive form, so the kernel can be optimized in seconds even at $T = 2^{20}$. Because the recursion nests, one mechanism serves every horizon. The core bet is that a kernel of size $2^k$ with $k$ around 3 to 5 recovers most of the factor-of-five variance gap that A Smooth Binary Mechanism for Efficient Private Continual Observation reports between its tree mechanism and dense factorizations.
Core Claim
The matrix mechanism releases $B(CG + Z)$. Here $G \in \mathbb{R}^{T\times d}$ stacks the $T$ gradients, $A = BC$ factors the lower-triangular query matrix $A$ (for plain running sums, the all-ones lower-triangular matrix $S_T$), and $Z$ is Gaussian noise. This can be read as a coding problem over a Gaussian channel. The matrix $C$ is a real-valued encoder. Its largest column norm is the privacy cost, because each step's data enters through one column, so this plays the role of a per-message power constraint. The matrix $B$ is a linear decoder, and the mean squared error is the decoding error. Private Online Prefix Sums via Optimal Matrix Factorizations shows the construction stays private under adaptive streams when it is lower-triangular with Gaussian noise. The quantity being minimized is
$$\mathrm{err}(B,C) = \frac{1}{T}\,\|B\|_F^2 \cdot \max_j \|C_{:,j}\|_2^2,$$
which is the average per-step variance after the noise is calibrated to sensitivity.
The prefix-sum matrix obeys a Plotkin-style recursion, the same "(u, u+v)" gluing used to build Reed–Muller codes and surveyed in Reed-Muller Codes: Theory and Algorithms:
$$S_{2T} = \begin{pmatrix} S_T & 0 \\ \mathbf{1}\mathbf{1}^\top & S_T \end{pmatrix},$$
where $\mathbf{1}\mathbf{1}^\top$ is the $T\times T$ all-ones block. Each later prefix sum equals the first half's total plus a prefix sum within the second half. The binary tree mechanism handles the all-ones block with one fresh noisy node per level and reuses the half-size mechanism twice.
We generalize in three ways. We group $k$ levels at a time into a block of $2^k$ steps. Within that block, a lower-triangular kernel $K \in \mathbb{R}^{2^k \times 2^k}$ mixes the block's noisy summaries. A second small decoder kernel decides how much each released sum relies on reused summaries versus fresh noise. The same pair of kernels is shared across all $\log_2 T / k$ levels. Because the recursion is self-similar, both $\|B\|_F^2$ and every column norm of $C$ satisfy linear recurrences in the kernel entries. The objective above can therefore be computed exactly in $O(4^k \log T)$ time and differentiated by automatic differentiation, with no $T\times T$ matrix ever formed.
Doubly transitive codes enter as a design constraint and as an analysis lens, not as the main mechanism. In Reed-Muller Codes Achieve Capacity on Erasure Channels, a symmetry group that can move any pair of coordinates to any other pair forces every coordinate to be equally vulnerable. In our setting, the corresponding requirement is that every step's data has identical sensitivity and every released sum has identical error.
The time ordering of prefix sums breaks full double transitivity, and we say so plainly. What survives is equal sensitivity across steps. Imposing it as a constraint is, by itself, a necessary optimality condition for the column-norm objective. A Smooth Binary Mechanism for Efficient Private Continual Observation obtains equal per-step error by restricting leaves to balanced binary indices. Those indices form one orbit under permutations of bit positions, which is exactly the coordinate-permutation symmetry of Reed–Muller codes. We treat that orbit construction as a special case of our family and test whether orbit-based leaf assignments combine with learned kernels.
Research Program
The first deliverable is the family itself, together with three proofs.
The first proof establishes online validity. Once rows are reordered by the time their support completes, the recursive $C$ is lower-triangular. The adaptive-stream guarantee of Private Online Prefix Sums via Optimal Matrix Factorizations then applies directly.
The second proof concerns streaming cost. Each coordinate needs only $O(2^k \log T)$ stored floats and $O(2^k)$ amortized work per step. This matters because $d$ is the model size, and $O(T)$ state per coordinate is what makes dense factorizations impractical for large models.
The third proof concerns nesting. The $2T$ mechanism contains the $T$ mechanism as its first half. This mirrors the nesting $\mathcal{RM}(m,r)\subset\mathcal{RM}(m+1,r+1)$ that Reed-Muller Codes on BMS Channels Achieve Vanishing Bit-Error Probability for all Rates Below Capacity uses to relate code behavior across lengths. Training can therefore start without fixing $T$.
The second deliverable is optimization of the kernel and an analysis of the result. We will minimize the recursive objective by gradient descent for $k \in \{1,\dots,6\}$ and report the fixed-point error constant as $T\to\infty$, which the recursion makes computable. We will compare this constant against the factorization-norm lower bound of Almost Tight Error Bounds on Differentially Private Continual Counting. That lower bound plays the role channel capacity plays in coding: a converse no mechanism can beat. The analysis we expect resembles a "gap to capacity" curve as a function of kernel size. We also expect the gap to shrink geometrically in $k$, because each extra level of mixing lets the kernel absorb one more scale of the Toeplitz-like correlation that the near-optimal square-root factorization exhibits. That expectation is a hypothesis to test, not a result.
The third deliverable extends the method to the query matrices that training actually uses. Momentum and learning-rate schedules change $A$ away from plain prefix sums; Private Online Prefix Sums via Optimal Matrix Factorizations folds momentum into $A$. Momentum with a geometric decay still satisfies a two-block recursion, with the all-ones block replaced by a rank-one block. We will derive the modified recurrence and optimize kernels for it. We will also check, as a secondary question, whether the equal-sensitivity symmetry lets the shuffling and sampling accountant of Privacy Amplification for Matrix Mechanisms analyze one representative column instead of all columns. That paper reports multi-hour runtimes beyond $n = 2000$, so a reduction there would be valuable, but we treat it as speculative until checked against the accountant's actual structure.
Baselines
The naive reference point is the standard binary tree mechanism as used inside DP-FTRL by Practical and Private (Deep) Learning Without Sampling or Shuffling. It is the $k=1$, untrained member of our family, so it anchors the error scale. We also include independent noise at each step with no correlation across steps, which is the true "do nothing" option. Both use the same calibrated noise and the same $T$.
The strongest low-memory competitor is the Smooth Binary Mechanism of A Smooth Binary Mechanism for Efficient Private Continual Observation. It reports reducing "the leading constant of the variance from 1 to 0.25 (a 4x improvement) compared to the standard binary mechanism," with $O(\log T)$ space and $O(1)$ average update time. This is the method to beat at matched memory. We will reimplement it, verify its 0.25 constant on synthetic counting streams at $T$ from $2^{10}$ to $2^{20}$, and require that our mechanism reach a strictly lower asymptotic constant at no more than four times its memory. Matching it at $k=1$ is a correctness check, not a result.
The strongest overall competitors are the dense and Toeplitz factorizations. Almost Tight Error Bounds on Differentially Private Continual Counting reports mean squared error "approximately 10.2 times smaller than the binary mechanism." Private Online Prefix Sums via Optimal Matrix Factorizations computes optimal factorizations, reducing a $2048\times 2048$ solve "from over 80 minutes to under 3 minutes." We will run both with their published procedures at the largest $T$ each can handle on one GPU, reporting error, solve time and per-coordinate memory. Beating them in error is not the goal. Success means coming within 20% of their mean squared error at $T = 2048$ while using $O(\log T)$ memory, and staying feasible at $T = 2^{20}$, where they are not.
One ablation isolates the recursion. A kernel optimized freely at each level, with no sharing, tests whether self-similarity costs accuracy. A shared kernel with the equal-sensitivity constraint removed tests whether the symmetry constraint helps optimization or merely restricts it. Balanced-orbit leaf assignment combined with learned kernels tests whether the two forms of symmetry add up.
Why not just…?
Why not just use the optimal dense factorization? At moderate $T$ it is the right answer, and we will use it as the target. Its problems are memory and solve time. Releasing $B(CG+Z)$ online requires $O(T)$ stored noise per coordinate. Solve times grow quickly beyond $T = 2048$, per Private Online Prefix Sums via Optimal Matrix Factorizations, and the accountant of Privacy Amplification for Matrix Mechanisms takes hours beyond $n > 2000$. The $T = 2048$ comparison tells us exactly how much accuracy our memory savings cost.
Why not just truncate or band the Toeplitz square-root factorization of Henzinger et al. to fit a memory budget? This is the most serious threat. It is simple, and the untruncated version is nearly optimal. The file contains no reported result for a memory-limited version, so we will implement one ourselves. Keeping only the first $M$ Toeplitz coefficients, with $M$ matched to our state size, gives a baseline at equal memory. If truncated Toeplitz matches the recursive mechanism at equal memory, the prefix-sum part of this proposal fails. In that case only the nesting property (horizon-free use) and the accountant question would remain as contributions, and we would report it that way.
Why not just reweight the nodes of an ordinary tree? A tree with optimized node weights is a subset of our family: the kernel is restricted to diagonal reweighting. The ablation that holds $k$ fixed and restricts $K$ to diagonal measures how much of the gain needs the off-diagonal mixing that the Reed–Muller recursion allows. If diagonal reweighting captures nearly all of the improvement, we will say that the coding view adds analysis but not mechanism.
Proposed Experiments
The synthetic experiments use continual counting on binary and real-valued streams, with $T$ from $2^{10}$ to $2^{20}$ and dimension up to $10^4$. This matches the $10^4 \times 10^4$ stream scale used by the Smooth Binary paper. We report the per-step variance constant, its spread across steps (equal error per step is a stated design goal), memory, and update time. We also report each mechanism's gap to the factorization-norm lower bound of Almost Tight Error Bounds on Differentially Private Continual Counting as a function of $k$.
The training experiments substitute our mechanism into DP-FTRL with momentum on CIFAR-10 and on StackOverflow next-word prediction under user-level privacy. These follow Practical and Private (Deep) Learning Without Sampling or Shuffling and Private Online Prefix Sums via Optimal Matrix Factorizations, with the same privacy budgets, model, rounds and tuning grid for every mechanism. On StackOverflow, the reference is the reported closure of "approximately 66% of the accuracy gap between previous private methods and non-private training" by optimal factorizations. On CIFAR-10, no reported result found on Lacuna for exact accuracies of DP-FTRL or the amplified matrix mechanism, so we rerun those baselines ourselves under a shared budget.
The decisive check has three parts. At $T = 2048$ the recursive mechanism must come within 20% of the optimal factorization's error and beat the Smooth Binary constant. It must hold that advantage over truncated Toeplitz at equal memory. Its kernel optimization must finish in seconds at $T = 2^{20}$. If the first part fails, the recursion is the wrong inductive bias. If the second fails, a simpler method already fills the gap.
References
- A Smooth Binary Mechanism for Efficient Private Continual Observation
- Private Online Prefix Sums via Optimal Matrix Factorizations
- Reed-Muller Codes: Theory and Algorithms
- Reed-Muller Codes Achieve Capacity on Erasure Channels
- Reed-Muller Codes on BMS Channels Achieve Vanishing Bit-Error Probability for all Rates Below Capacity
- Almost Tight Error Bounds on Differentially Private Continual Counting
- Privacy Amplification for Matrix Mechanisms
- Practical and Private (Deep) Learning Without Sampling or Shuffling