Private Continual Counting of Unbounded Streams
summary
The gist
Private continual counting of unbounded streams studies the problem of differentially private continual counting in an unbounded setting where the input size n is not known in advance The resulting…
In short
This research develops a matrix-based algorithm for privately counting items in an infinite stream where the total size is unknown beforehand. The method achieves smooth error and estimates the sum of any initial segment with low variance, offering a near-optimal asymptotic error compared to existing methods.
Key concepts
- Differentially Private Continual Counting
- This is the problem of keeping track of running totals from an endless stream while ensuring privacy. The algorithm must provide accurate counts while preventing attackers from learning sensitive information about individual data points in the stream.
- Matrix Factorization (LTToep)
- The core technique involves using specific types of infinite lower-triangular Toeplitz matrices to model the counting process. These matrices are constructed using functions like $f_1(z)$ and $f_2(z)$, which help manage the structure of the stream data in a way that allows for privacy guarantees.
- Smooth Error
- The resulting algorithm has smooth error, meaning its estimation accuracy changes gradually rather than jumping abruptly. This is a desirable property for streaming applications where continuous, predictable performance is needed over time.
Terminology used across episodes
This episode discusses
- Private Continual Counting of Unbounded Streams · Paper Radio
- Practical Considerations for Differential Privacy
- Streaming Private Continual Counting via Binning
- On the Space Complexity of Online Convolution
- DMM: Distributed Matrix Mechanism for Differentially-Private Federated Learning Based on Constant-Overhead Linear Secret Resharing
- Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learning
- The Power of Factorization Mechanisms in Local and Central Differential Privacy
- An Inversion Theorem for Buffered Linear Toeplitz (BLT) Matrices and Applications to Streaming Differential Privacy
- A Hassle-free Algorithm for Private Learning in Practice: Don't Use Tree Aggregation, Use BLTs
- Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12
- Convex Optimization for Linear Query Processing under Approximate Differential Privacy
The paper
Private Continual Counting of Unbounded Streams · Read on arXiv
Ben Jacobsen, Kassem Fawaz
University of Wisconsin — Madison
We study the problem of differentially private continual counting in the unbounded setting where the input size n is not known in advance. Current state-of-the-art algorithms based on optimal instantiations of the matrix mechanism cannot be directly applied here because their privacy guarantees only hold when key parameters are tuned to n. Using the common `doubling trick' avoids knowledge of n but leads to suboptimal and non-smooth error. We solve this problem by introducing novel matrix factorizations based on logarithmic perturbations of the function 1 over sqrt 1-z studied in prior works, which may be of independent interest. The resulting algorithm has smooth error, and for any α> 0 and t at most n, it is able to privately estimate the sum of the first t data points with O(squared(t)(t) 1+2α) variance. It requires O(t) space and amortized O(t) time per round, compared to O((n) (t)) variance, O(n) space and O(n n) pre-processing time for the nearly-optimal bounded-input algorithm of Henzinger et al. Empirically, we find that our algorithm's performance is also comparable to theirs in absolute terms: with optimized parameters, our variance is less than 2 times theirs for t as large as 2 32.
Transcript
Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.
Nadia: I'm Nadia.
Elias: And I'm Elias, here with Priya.
Nadia: We're looking at the paper: "Private Continual Counting of Unbounded Streams".
Elias: Here's the gist of the paper. Private continual counting of unbounded streams studies the problem of differentially private continual counting in an unbounded setting where the input size n is not known in advance The resulting algorithm has smooth error, and for any α > 0 and t ≤ n it is able to privately estimate the sum of the first t data points with O(log2+2α(t)) variance It requires O(t) space and amortized O(log t) time per round, compared to O(n log n) pre-processing time for the nearly-optimal bounded-input algorithm of Henzinger et al.
27: Empirically, we find that our algorithm’s performance is also comparable to theirs in absolute terms: our variance is less than 1.5× theirs for t as large as 2 4 Problem Statement and Motivation Differentially private counting under continual observation refers to the problem of maintaining accurate running totals over streams of sensitive data It has attracted a great deal of attention in recent years for its wide-ranging applications in optimization, online learning and the private analysis of streaming data more broadly One challenge when applying matrix-based algorithms to streaming settings is that they largely assume access to the input size n as a parameter Simple solutions to this problem all carry fundamental tradeoffs Algorithm Design and Matrix Factorization The main contribution in this paper is a matrix-based algorithm that overcomes this trilemma: to the best of our knowledge, it is the first private counting algorithm that is simultaneously smooth and unbounded with almost-optimal asymptotic error The resulting algorithm has smooth error, and for any α > 0 and t ≤ n it is able to privately estimate the sum of the first t data points with O(log2+2α(t)) variance The matrix decompositions we consider are of the form L = LTToep(f(z; −γ, −δ)), R = LTToep(f(z; γ, δ)), where f1(z):= 1/√1−z, f2(z; γ):= 1/z ln 1/(1−z) γ, and f3(z; δ):= 2/z ln 1/(z ln 1−zδ) Theoretical Guarantees Theorem 1 states that for all α > 0, there exists an infinite lower-triangular Toeplitz matrix factorization L, R ∈ R∞×∞ with the following properties: Joint Validity: For all n ∈ Z+,
L: n
R: n =
Mcount: n Bounded Sensitivity: limn→∞∥
R: n∥1→2 = C < ∞ for some computable constant C Near-Optimal Asymptotic Error: ∥
L: n∥2→∞ = O(log1+α(n)) Corollary 1 states that for all ε, δpriv, α > 0 there exists an unbounded streaming algorithm for continual counting, described in Algorithm 1, which has the same complexity as in Theorem 1 and satisfies (ε, δpriv)-DP in the continual release model Implementation Details and Extensions Algorithm 1 requires computing next t coefficients of L = LTToep(f(z; −γ, −δ)) in O(tlog t) time with an FFT The total cost over the entire input is 12P⌈log2 n⌉ k=1 M(2k) ∼ 12P⌈log2 n⌉ k=1 2−k+1M(n) ≤ 24M(n), which can be cut down to 17.5M(n) if δ = −γ, or 13M(n) when δ = 0 Algorithm 2 introduces an order K approximation to improve running time by switching from exact computations to order K approximations once the relative error of the approximation falls below some threshold η We have shown for the first time that the classic matrix factorization method
33: can be efficiently extended to online settings with unknown input size without the use of doubling tricks The only algorithms we are aware of that exactly achieve asymptotically optimal O(log2 t) variance in the unbounded setting rely on some form of doubling trick Open Question 1 asks whether there exist LTToep matrices L, R such that
L: n
R: n =
Mcount: n, limn→∞∥
R: n∥1→2 < ∞, and ∥
L: n∥2→∞ = Θ(log2 n)?
Elias: Technical Details for Computing Sensitivity To actually compute the sensitivity, we make use of Parseval’s theorem, which gives us: X∞ m=0 (
z m: fR)2 = 1/2π Z 2π 0 fR(e iθ)2 dθ = 2(2δ/4) Z π/3 0 I1(ω) −1 I2(ω) −1/2−α (I3(ω) + I4(ω)) squared δ dω + Z π/2 π/3 I1(ω) −1 I2(ω) −1/2−α (I3(ω) + (I4(ω) − π) 2) δ dω The integrands are sufficiently smooth to be numerically integrated to high precision Empirical Findings We have also shown empirically that it enjoys excellent constants when its parameters are set correctly, with variance that is uniformly less than 1.5× that of Henzinger et al.
27: for inputs as large as n = 224 The Hybrid mechanism using Algorithm 1 for the unbounded component outperforms the variant using independent noise as in Chan et al.
Paper summary: Nadia: So we’re looking at this paper, "Private Continual Counting of Unbounded Streams." It tackles differentially private continual counting when you don't even know the total size of the stream in advance.
Elias: Right. The core idea they’re pushing is that current methods that rely on knowing the input size n just don't work in this unbounded setting because their privacy guarantees only hold when you tune those parameters to n.
Priya: So what's the main claim here about how they solve this? What are they actually proposing instead of just using some noise trick?
Nadia: They introduce a new matrix-based algorithm that aims to be both smooth and unbounded at the same time with almost optimal asymptotic error. It’s a matrix factorization approach based on logarithmic perturbations of the function root one over one minus z, which they studied in prior work.
Elias: And what’s the specific performance metric they claim for this new method? They say that for any alpha greater than zero and any t less than or equal to n, you can privately estimate the sum of the first t data points with an error variance of two plus alpha t over log two plus two alpha t.
Priya: That sounds like a specific bound. So, what’s the cost? Because when you're dealing with streaming data, space and time complexity are huge concerns for real-world deployment.
Nadia: They say it requires space proportional to t, which is O of t space, and the time per round is amortized O of log t time. This is significantly better than the nearly optimal bounded-input algorithm by Henzinger et al., which takes O of n log n pre-processing time.
Elias: They also note that they have smooth error, which means the variance is a smooth function of t. That smoothness, combined with being unbounded, is what they call their main contribution over simpler methods like just adding independent noise to each data point.
Priya: But the paper mentions that this approach isn't truly unbounded in a strict sense; it's still linked to n in some way, and they admit that it might not be satisfying for practical use. That’s a caveat we should keep in mind.
Paper summary: Nadia: Exactly. They also compare their performance empirically to the Henzinger et al. work, saying their variance is less than one point five times theirs when t is as large as two to the power of four.
Elias: It sounds like they’re trying to solve a trilemma: getting smoothness, staying unbounded, and achieving almost optimal asymptotic error all at once. They found a way around that trade-off using these specific matrix factorizations L and R.
Priya: If we look at the complexity again, they mention that computing the next t coefficients of L requires FFT time which is O of t log t. So, if you’re processing a stream, that means each step costs about t log t operations.
Nadia: That’s the computational trade-off for getting this performance level. They also mention an order K approximation in Algorithm two to try and speed things up by switching to approximations once the relative error of that approximation drops below some threshold eta <ref:2506.15018#pg1>.
Elias: And that leads us into a question about what they’re trying to achieve with these matrix decompositions L and R. They define them using functions f1, f2, and f3 involving logarithms of one over one minus z, which are related to prior work in the area.
Priya: I wonder if we can simplify what this means for someone who just needs a running total estimate for their data stream without knowing its final size. It suggests a way to get good privacy guarantees even when the data never ends.
Nadia: It really does. The whole point of the paper, "Private Continual Counting of Unbounded Streams," is that it provides a matrix-based solution that overcomes the limitations of previous algorithms in this area regarding smoothness and unboundedness simultaneously.
Elias: And looking at the conclusion, they aren't claiming a perfect solution yet because they acknowledge that their specific matrix factorization isn't truly unbounded and might not be practical in every scenario.
Priya: So, what’s the big picture implication here for applications? Is this something we can actually rely on for sensitive data streams?
Nadia: It shows that a method exists with a very low variance bound, O of log two plus two alpha t, compared to the previous logarithmic variance bounds. It's a significant step forward in achieving better privacy guarantees in online learning and streaming data analysis.
Paper summary: Elias: They’ve also shown that their hybrid mechanism outperforms variants using independent noise for the unbounded component, but they admit both variants can have very erratic performance when t is close to a power of two. That’s a practical warning about implementation choices.
Priya: So, while the theoretical bounds look good, we still have to worry about those practical performance dips based on how t relates to powers of two. It’s not just smooth math; it has real-world quirks.
Nadia: Precisely. The paper gives us a concrete algorithm that's much more powerful than just adding independent noise, but we need to be careful with the tuning parameters like delta and gamma they use in their functions f1, f2, and f3.
Elias: And if you want to know what they’re really asking for in terms of future work, there’s an open question about whether there exist LTToep matrices L and R such that their product relates to the count matrix in a way that keeps the norm of R bounded while the norm of L stays logarithmically bounded by n.
Priya: That open question points toward understanding if we can find a factorization that maintains both the required privacy bound and truly unbounded behavior without needing those doubling tricks they mentioned earlier.
Nadia: It’s a good direction for future research, pushing towards a more robust mathematical structure for these private counting problems in the unbounded setting.
Elias: So, to wrap up this discussion on "Private Continual Counting of Unbounded Streams," the paper presents a matrix-based algorithm that offers smooth error and almost optimal asymptotic error variance O of log two plus two alpha t, which is better than previous methods.
Priya: It’s a step in the right direction for privacy research, but we still need to see how robust these solutions are when you move from theoretical bounds to actual deployment on real data streams.
Nadia: The key thing is that they’ve provided a concrete mechanism that addresses the trilemma of smoothness, unboundedness, and error bound simultaneously in a way that’s practically implementable with O of t space and time.
Conclusion: Nadia: So we're wrapping up this look at "Private Continual Counting of Unbounded Streams." Basically, they’ve developed a way to keep running totals private even when you don't know how big the total stream is.
Elias: Exactly. They use some specific matrix math—logarithms and Toeplitz matrices—to handle that unknown size problem without needing to pre-know the whole thing in advance.
Priya: From a privacy standpoint, what does that actually mean for someone tracking sensitive data over time? Does it offer a real improvement over just adding random noise to every single piece of data?
Nadia: It offers a different kind of bound. They show that you can estimate the sum of the first t items with an error variance tied to log two plus alpha times t. That means for a fixed privacy level, the error gets much smaller as you look at more items, which is pretty good for long-term tracking.
Elias: But there's a catch in their math. They admit that this approach isn't perfectly unbounded in the strictest sense of the problem they set up initially, so it’s not a magic solution for every single streaming scenario.
Priya: I see what you mean about the catch. So we’re looking at a method that performs really well asymptotically, but maybe it breaks down when you hit certain thresholds with t?
Nadia: That's right. They did show empirically that their performance is comparable to other methods, better than some by a factor of one point five times for large inputs. It’s solid work for the theoretical foundation.
Elias: The authors are asking a big question about whether we can ever find these perfect Toeplitz matrices where the norm stays bounded while still getting that optimal logarithmic error scaling with n.
Priya: That's a tough ask, Elias. If they can nail that, it would mean we could have truly robust continual counting systems for anything from online learning to monitoring public data streams without those tricky limitations.
More episodes
- 2608.27496-ROPE: Routed Origin Policy Enforcement against Indirect Prompt Injection
- Daily Summary for 2026-11-19
- 2607.07085-Is Randomness Necessary for Adaptive Data Analysis?
- The day in conversation for 2026-11-19
- Daily Summary for 2026-11-19
- 2609.10601-Threshold Choice, Not Sample Size, Bounds Trustless Verification of Nondeterministic Compound AI Workflows
- 2610.38786-Adversarial Process Disturbances at a Deployable Alarm Budget: Detector Evaluation on a Simulator and a Real Plant
- 2511.08660-Binary and Multiclass Cyberattack Classification on GeNIS Dataset
- 2604.27302-Static Attribution of Android Residential Proxy Malware Using Graph Kernels
- Daily Summary for 2026-11-18