💻 computer science

Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting

This paper establishes that for pure- $\epsilon$ -differential privacy, the optimal mean and maximum per-coordinate squared errors in continual counting are both $\Theta(\epsilon^{-2}\log^3(n+1))$ , a result achieved by proving that the factorization costs of the prefix-sum matrix scale as $\Theta((\log(n+1))^{3/2})$ even without restrictions on sign, sparsity, or inner dimension.

Original authors: Awnon Bhowmik, Mahmudul Hasan

Published 2026-08-03

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Awnon Bhowmik, Mahmudul Hasan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a secret tally of votes in a long line of people, but you have a strict rule: you must reveal the running total after every single person, yet you cannot let anyone figure out how any specific individual voted. This is the world of continual counting in differential privacy. It's like a magician who must show the audience the total number of cards dealt after every single card, but must do it in a way that no one can guess if the last card was a King or a Two. To keep the secret, the magician has to add a little bit of "static" or noise to the numbers. The problem is, too much noise makes the final total useless, while too little noise breaks the secrecy.

Mathematicians have been trying to find the perfect recipe for this noise. They use a tool called a matrix mechanism, which is essentially a clever way of breaking down the counting problem into smaller, manageable chunks (like a puzzle). The goal is to find the most efficient way to split the puzzle so that the "static" needed to hide the secrets is as small as possible. For a long time, researchers thought they had found the best possible recipe, but only for a very specific, rigid type of puzzle piece (ones made of only zeros and ones). The big question was: if we allow ourselves to use any kind of puzzle piece—any real number, positive or negative, big or small—can we do better? Or is the old recipe actually the best we can ever hope for?

This paper, written by Awnon Bhowmik and Mahmudul Hasan, steps into that question and delivers a definitive answer. They prove that even if you are allowed to use the most flexible, wiggly, signed, and dense puzzle pieces imaginable, you cannot beat the existing recipe. The "cost" of keeping the secret remains exactly the same.

Here is the story of their discovery:

The Puzzle of the Prefix Sum

Imagine a stream of data, like a river flowing past a sensor. Every second, the sensor records a number, and we want to know the sum of all numbers from the start up to that second. In math, this is called a "prefix sum." If you have $n$ seconds, you have $n$ different sums to report.

To protect privacy, the researchers use a method where they split the job of calculating these sums into two parts, like a relay race. One runner (Matrix $L$ ) and another runner (Matrix $R$ ) work together. The second runner adds a little bit of random noise to the data before passing it to the first runner. The first runner then reconstructs the final answers. The "cost" of this system is how much noise is needed. If the cost is high, the answers are very blurry. If the cost is low, the answers are sharp.

For years, the best known way to do this (using only simple 0s and 1s) resulted in a cost that grew like the cube of the logarithm of the number of seconds ( $\log^3 n$ ). This means if you double the time, the noise doesn't double; it grows much slower, but it still grows.

The Big Question: Can We Do Better with Real Numbers?

Previous researchers, Arkhipov and Kalinin, had shown that if you stick to simple 0s and 1s, you can't do better than that $\log^3 n$ cost. But they left a door open. They asked: "What if we let the runners use any real numbers? What if they can use negative numbers to cancel things out, or huge numbers to amplify things? Maybe that flexibility will let us reduce the noise even further."

This paper slams that door shut. The authors prove that no matter how you choose your numbers, whether they are positive, negative, sparse, or dense, the cost remains stuck at that same $\log^3 n$ level. You cannot bypass the system by using more complex numbers.

How They Proved It: The "Nuclear" Trap

To prove this, the authors didn't just try a million different combinations of numbers (which would take forever). Instead, they used a clever mathematical trick involving something they call $p$ -nuclearity.

Think of the counting problem as a giant, heavy block of stone. To move it, you need to break it down into smaller pieces (rank-one factors). The "cost" is how heavy those pieces are. The authors looked at the shape of the stone and realized that no matter how you try to break it, there is a fundamental "width" to the stone that you can't ignore.

They found a specific "critical point" in the math (a value called $p = 2/3$ ). At this point, the math behaves like a harmonic series—a famous mathematical sequence that grows very slowly but never stops growing, like the sound of a bell that fades but never quite disappears.

Here is the magic of their proof:

They showed that the "width" of the counting problem forces the pieces to have a certain total weight.
They used a mathematical rule (Hölder's inequality) to show that this weight translates directly into the noise cost.
Because of the harmonic nature at that critical point, the noise cost must grow as $(\log n)^{3/2}$ for the factors, which translates to a total error of $\log^3 n$ .

It's as if they proved that no matter how you try to fold a piece of paper, if you keep folding it in half, it will eventually become too thick to fit in your pocket. The thickness is a law of the universe for that specific type of paper.

What This Means for Privacy

The paper concludes that for the specific type of privacy mechanism they studied (the "Laplace matrix mechanism"), the current best methods are actually the best possible methods. If you want to count a stream of data privately, and you want the answers to be as accurate as possible, you are already at the limit of what is mathematically possible using this method.

The authors are very clear about what they didn't prove. They didn't say that no privacy method can ever be better. They only said that this specific family of methods (using matrix factorizations) cannot be improved by just using more complex numbers. There might be a completely different way to count privately that we haven't thought of yet, but if you are sticking to the matrix method, you are already at the finish line.

The Verdict

In the end, this paper is a "no-go" sign for anyone hoping to find a magic number trick to reduce noise in this specific privacy setup. It confirms that the $\log^3 n$ error rate is a hard wall, not just a temporary hurdle. The "cost" of keeping our secrets safe in a continuous stream of data is fixed, and we cannot bypass the system by changing the numbers we use. The math is solid, the proof is rigorous, and the answer is definitive: the best we can do is what we are already doing.

Technical Summary: Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting

Problem Statement
The paper addresses the problem of continual counting under pure $\epsilon$ -differential privacy (DP). In this setting, a mechanism must release every prefix sum of a data stream of length $n$ while protecting the privacy of individual updates. The workload is represented by the lower-triangular prefix-sum matrix $T_n$ , where $T_n(i, j) = 1$ if $j \le i$ and $0$ otherwise.

The focus is on the matrix mechanism class, where $T_n$ is factored as $T_n = LR$ . Independent Laplace noise is added to the transformed stream $Rx$, and the prefix answers are reconstructed via $L$ . Under pure $\epsilon$ -DP with unit $\ell_1$ adjacency, the sensitivity of the mechanism is governed by $\|R\|_{1 \to 1}$ (the maximum $\ell_1$ column norm of $R$ ). The paper investigates two specific factorization costs that determine the mean and maximum per-coordinate squared error of the resulting mechanism:

$c_F(T_n) = \inf_{T_n=LR} \frac{\|L\|_F}{\sqrt{n}} \|R\|_{1 \to 1}$
$c_2(T_n) = \inf_{T_n=LR} \|L\|_{2 \to \infty} \|R\|_{1 \to 1}$

Prior work by Arkhipov and Kalinin established upper bounds of order $(\log n)^{3/2}$ for these costs and proved matching lower bounds for factors restricted to entries in $\{0, 1\}$ . However, they left open the question of whether this lower bound holds for arbitrary real factors (allowing signed, dense, and rectangular matrices with arbitrary finite inner dimensions).

Methodology
The paper resolves the open problem by establishing a lower bound for arbitrary real factors using a geometric and functional-analytic approach centered on $p$ -nuclearity. The proof architecture consists of three main steps:

Aggregate Column Width Estimation: The authors derive a lower bound on the aggregate column width $D_k(T_n)$ , defined as the sum of squared Euclidean distances from the columns of $T_n$ to any $k$ -dimensional subspace. They prove that in the low-rank range $1 \le k \le n/16$ , $D_k(T_n) \asymp n^{3/2} k^{-1/2}$ . This is established by showing that a subspace cannot be close to more than half of the nested suffix indicators without violating Bessel's inequality.
Approximation-Space Conversion: The paper utilizes classical results from operator ideal theory (specifically the work of Pietsch and Hinrichs–Pietsch) to relate the aggregate widths to the $p$ -nuclear power $n_p(A)$ . For a matrix $A$ , $n_p(A)$ is defined via the infimum of $\sum (\|u_q\|_2 \|v_q\|_1)^p$ over finite rank-one decompositions $A = \sum u_q v_q^T$ . The authors provide a quantitative, finite-dimensional proof showing that $n_p(A)$ is bounded below by a weighted sum of the aggregate widths $D_k(A)$ .
Critical Exponent Analysis: The authors analyze the behavior of $n_p(T_n)$ at the critical exponent $p = 2/3$ . At this value, the series derived from the width estimates becomes harmonic, yielding a lower bound of order $n \log n$ . By applying Hölder's inequality, this $p$ -nuclear bound is transferred to the factorization costs $c_F(T_n)$ and $c_2(T_n)$ , converting the $n \log n$ term into the desired $(\log n)^{3/2}$ order.

For the upper bounds, the paper employs a classical Fenwick interval factorization (also known as a Binary Indexed Tree structure) to construct explicit factors $L$ and $R$ that achieve the matching upper bounds.

Key Contributions and Results

Main Theorem (Theorem 1.1): The paper proves that for arbitrary real factors with arbitrary finite inner dimension, the factorization costs satisfy:
$c(\log(n+1))^{3/2} \le c_F(T_n) \le c_2(T_n) \le C(\log(n+1))^{3/2}$
This confirms that the $(\log n)^{3/2}$ order is intrinsic to the matrix mechanism class, regardless of sign, sparsity, or squareness restrictions.
Optimized Error Orders (Corollary 1.2): Consequently, within the pure- $\epsilon$ -DP Laplace matrix-mechanism class, the optimized maximum and mean squared errors are both $\Theta(\epsilon^{-2} \log^3(n+1))$ . This closes the asymptotic gap between the known upper bounds and the lower bounds for this specific class of mechanisms.
Fixed- $p$ Phase Diagram (Theorem 1.3): The paper characterizes the $p$ -nuclear power $n_p(T_n)$ for all $0 < p < 1$ , revealing a phase transition at $p = 2/3$ :
- $n_p(T_n) = \Theta(n)$ for $0 < p < 2/3$
- $n_p(T_n) = \Theta(n \log n)$ for $p = 2/3$
- $n_p(T_n) = \Theta(n^{3p/2})$ for $2/3 < p < 1$
  The constants in these bounds are not uniform in $p$ and diverge as $p \to 2/3$ or $p \to 1$ .
Upper Bounds: The paper provides a self-contained proof that the Fenwick interval factorization achieves the matching upper bounds for both the factorization costs and the $p$ -nuclear powers across the entire phase diagram.

Significance and Claims
The paper explicitly frames its contribution as a resolution to a specific open problem posed by Arkhipov and Kalinin regarding the extension of lower bounds from binary factors to arbitrary real factors within the matrix mechanism framework.

Scope Limitations: The authors emphasize that their results are confined to the pure- $\epsilon$ -DP Laplace matrix-mechanism class. They do not claim to provide lower bounds for general continual counting mechanisms (including non-matrix or interactive mechanisms), nor do they address approximate-DP sensitivity or expected maxima across coordinates (which are governed by different functionals).
Theoretical Nature: The work is purely theoretical, focusing on asymptotic orders and the geometry of matrix factorizations. It does not propose new algorithms, empirical evaluations, or learning-theoretic applications.
Role of $p$ -Nuclearity: The paper highlights that the "extra" $\sqrt{\log n}$ factor in the error order (compared to the $\log n$ baseline for Euclidean sensitivity) arises specifically from the mixed-norm gap between $\|R\|_{1 \to 1}$ and $\|R\|_{1 \to 2}$ . This gap is captured by the $p$ -nuclear obstruction at $p < 1$ , a regime where standard norm-based lower bound proxies (which are capped at $\log n$ ) fail.

In summary, the paper establishes that the $(\log n)^{3/2}$ cost is a fundamental limit for pure-DP continual counting when restricted to matrix mechanisms with arbitrary real factors, resolving the open question of whether signed cancellations could improve upon the binary-factor lower bounds.