Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy

Krishnamurthy Dvijotham, H. Brendan McMahan, Krishna Pillutla, Thomas Steinke, Abhradeep Thakurta

This paper, recently updated in May 2024, tackles a fundamental challenge in privacy-preserving data analysis: how to release a running total of a data stream without leaking individual secrets, all while keeping the computational overhead manageable.

TL;DR

The authors introduce "Buffered Linear Toeplitz" (BLT) mechanisms, a new class of algorithms for differentially private continual counting that achieve near-optimal utility with minimal memory. By combining rational function approximation with direct numerical optimization, they provide a practical way to generate high-quality privacy noise for massive data streams using only logarithmic or polylogarithmic space.

What Problem Does This Paper Address?

In the world of Differential Privacy (DP), "continual counting" is the task of releasing a running sum of increments (like gradients in a machine learning model) such that no single increment can be easily identified. To do this effectively, researchers add carefully correlated Gaussian noise to the sums.

The challenge is a classic three-way trade-off between privacy, utility (how little noise you add), and efficiency (memory and time).

  • Simple methods (like adding independent noise) are fast but destroy utility as the stream grows.
  • The Binary Tree mechanism is efficient but adds roughly 4.5 times more noise than theoretically necessary.
  • Optimal matrix factorizations provide the best utility but are computationally "heavy," often requiring memory that scales linearly with the length of the stream. For modern AI models with billions of parameters and millions of training steps, storing this noise would require petabytes of memory—a complete non-starter.

Methods

The authors frame the problem as factoring the "all-ones" lower triangular matrix $A$ (which computes prefix sums) into two factors, $B$ and $C$, such that $A=BC$. Their core innovation lies in restricting these factors to a specific structure:

  1. Buffered Linear Toeplitz (BLT) Matrices: They focus on matrices where the sequence of coefficients follows a linear recurrence. This allows the next noise value in a stream to be computed using only a small number of "buffers" (state variables), rather than looking back at the entire history.
  2. Rational Function Approximation: They prove that these efficient BLT matrices correspond to rational generating functions. By finding a low-degree rational function that approximates $1/\sqrt{1-x}$ on a circle in the complex plane, they can instantiate a streaming algorithm that is both space-efficient and near-optimal in utility.
  3. Direct Optimization: Beyond theoretical closed-form solutions, the authors use gradient-based optimization (specifically L-BFGS) to fine-tune the parameters of these BLT matrices for specific stream lengths $n$.
  4. Recursive Construction: For even better asymptotic performance, they combine their BLT approach with a recursive structure similar to the binary tree mechanism to achieve $\tilde{O}(\log n)$ space complexity.

Datasets

Not discussed in the paper. The evaluation is performed via numerical simulations and mathematical proofs based on the "MaxErr" objective across various stream lengths $n$ (up to $10^8$).

Key Insights and Ideas

  • The Rational Link: The most elegant "aha" moment is the realization that a noise sequence satisfying a linear recurrence is mathematically equivalent to its generating function being rational. This bridges the gap between approximation theory and streaming algorithms.
  • Toeplitz Power: The authors show that you lose very little utility by restricting yourself to Toeplitz matrices (matrices with constant diagonals). The gap between the best possible Toeplitz factorization and the absolute theoretical optimum is a tiny constant ($\le 0.365$).
  • Optimization over Theory: While the paper provides strong theoretical bounds, it shows that "direct numerical optimization yields a highly practical solution." In practice, an optimized mechanism with just a few buffers can outperform a more complex theoretical one.

Key Results

  • Near-Optimal Utility: The proposed mechanisms achieve a noise scale that is within a small additive constant of the optimal (but inefficient) Toeplitz mechanism.
  • Massive Efficiency Gains: The algorithms require only $O(\log^2 n)$ or $\tilde{O}(\log n)$ space.
  • Practical Superiority: As shown in Figure 1, the "Opt-BLT" method with a degree of just 5 (meaning only 5 memory buffers per dimension) is within 1% of the optimal utility even for streams of 10 million steps.
Ratio of MaxErr(B, C) of the proposed RA-BLT and Opt-BLT mechanisms over the optimal (but inefficient) Toeplitz mechanism.
  • Comparison to Baselines: The authors demonstrate that their approach significantly outperforms the standard binary tree mechanism, which is the current industry workhorse for efficient continual counting.

Limitations and Future Work

  • Space Complexity Gap: While the authors achieve $O(\log^2 n)$ space for near-optimal Toeplitz factorizations, they leave it as an open problem whether this can be improved to $O(\log n)$ while maintaining the same utility.
  • Convergence Proofs: The direct optimization method works exceptionally well in practice, but the authors do not yet have a formal proof that this optimization procedure will always converge to the global optimum.
  • Non-Square Factorizations: Their secondary result (Theorem 1.2) achieves better asymptotics but doesn't produce a square Toeplitz factorization, which might limit its use in certain specific mathematical frameworks.

Summary updated

Abstract

In the task of differentially private (DP) continual counting, we receive a stream of increments and our goal is to output an approximate running total of these increments, without revealing too much about any specific increment. Despite its simplicity, differentially private continual counting has attracted significant attention both in theory and in practice. Existing algorithms for differentially private continual counting are either inefficient in terms of their space usage or add an excessive amount of noise, inducing suboptimal utility. The most practical DP continual counting algorithms add carefully correlated Gaussian noise to the values. The task of choosing the covariance for this noise can be expressed in terms of factoring the lower-triangular matrix of ones (which computes prefix sums). We present two approaches from this class (for different parameter regimes) that achieve near-optimal utility for DP continual counting and only require logarithmic or polylogarithmic space (and time). Our first approach is based on a space-efficient streaming matrix multiplication algorithm for a class of Toeplitz matrices. We show that to instantiate this algorithm for DP continual counting, it is sufficient to find a low-degree rational function that approximates the square root on a circle in the complex plane. We then apply and extend tools from approximation theory to achieve this. We also derive efficient closed-forms for the objective function for arbitrarily many steps, and show direct numerical optimization yields a highly practical solution to the problem. Our second approach combines our first approach with a recursive construction similar to the binary tree mechanism.
BibTeX
@misc{dvijotham2024efficient,
  author = {Krishnamurthy Dvijotham and H. Brendan McMahan and Krishna Pillutla and Thomas Steinke and Abhradeep Thakurta},
  title = {{Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy}},
  year = {2024},
  eprint = {2404.16706},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2404.16706},
}
Figure