1 Introduction↩︎

Differential privacy [1] has become a standard framework for reasoning about privacy, both in theory and in practice. In many applications, however, data arrive sequentially, and statistics must be released continually as the data stream evolves. This motivates the continual observation model of Dwork, Naor, Pitassi, and Rothblum [2], in which the privacy guarantee must hold for the entire sequence of outputs rather than for a single final release. One of the most fundamental problems in this model is private continual counting under pure differential privacy [1], [2]. Given a binary stream \(x_1,\ldots,x_n \in \{0,1\}\) of sensitive updates, the goal is to release, at each time \(t\), an approximation to the prefix sum \(\sum_{i=1}^t x_i\), while ensuring that the entire output sequence satisfies \(\epsilon\)-differential privacy. Continual counting and its variants serve as building blocks in a range of private streaming algorithms, including continual mean estimation [3], quantile estimation [4], continual histograms [5]–[8], continual clustering [9], graph algorithms [10]–[12], and continual distinct-elements counting [13], [14]. Thus, improvements to continual counting can benefit a broad range of higher-level private streaming algorithms.

The classical solution to continual counting is the binary tree mechanism [2], [15]. In this mechanism, the stream is represented by the leaves of a binary tree, and noisy partial sums are stored at internal nodes. Each update affects only logarithmically many nodes, which controls the privacy cost, and each prefix sum can be reconstructed from logarithmically many noisy measurements, which controls the error. Combined with the Laplace mechanism, the binary tree construction gives maximum expected squared error at most \(2\log_2^3(n)/\epsilon^2\) for streams of length \(n\). Since no asymptotic improvement over this upper bound is known for pure differential privacy, the leading constant has become an important measure of progress. The subtraction trick of Honaker [16] reduces the error by allowing a prefix sum to be represented using complementary intervals. Further improvements are obtained by replacing the binary tree with a \(k\)-ary tree [7], [17], thereby optimizing the tradeoff between privacy cost and reconstruction error. Combining these ideas, Andersson, Pagh, Steiner, and Torkamani [18] obtained the best known leading constants for pure-DP continual counting, reducing the error by more than a factor of \(8\) compared to the original binary tree mechanism. The construction can be further refined by averaging several estimators; we refer to the resulting method as the averaged \(k\)-ary tree with subtraction, which increases the improvement over the binary tree mechanism from a factor of \(8\) to a factor of \(17\).

The tree mechanisms above can all be viewed through the more general matrix mechanism framework [19]. In this framework, the mechanism first takes linear measurements of the stream, adds Laplace noise scaled to their sensitivity, and then uses these noisy measurements to linearly reconstruct the prefix sums. Matrix factorizations have been useful in the approximate DP setting with Gaussian noise [20]. For pure DP continual counting, however, they had not previously led to improvements beyond tree constructions. In this work, we show that a general matrix factorization can in fact improve the best-known bounds for pure-DP continual counting, reducing the error by a factor \(25\) over the binary tree mechanism.

The best known lower bounds are substantially smaller than the best known upper bounds: for both mean squared error [21] and maximum squared error [2], [22], the strongest known lower bounds are of order \(\Omega(\epsilon^{-2}\log^2 n)\), with analogous bounds holding even under approximate differential privacy. Thus, the asymptotic gap between upper and lower bounds remains open. Nevertheless, the lack of asymptotically better mechanisms has motivated the view that the current upper bound may be optimal [18]. In this work, we give partial evidence in this direction: we prove an \(\Omega(\epsilon^{-2}\log^3 n)\) lower bound for the class of matrix factorizations whose factors have all entries in \(\{0,1\}\). This class is rich enough to include the binary tree mechanism and the \(k\)-ary tree mechanisms without the subtraction trick. Hence, within this natural class of tree-like factorizations, the known upper bound is asymptotically tight.

1.1 Problem Statement↩︎

We consider continual counting over a stream \(x=(x_1,\ldots,x_n) \in \{0,1\}^n\). At each time \(t \in [n]\), the goal is to release a private estimate of \(\sum_{j=1}^t x_j\). Equivalently, the target output is \(T_n x\), where \(T_n \in \mathbb{R}^{n \times n}\) is the prefix-sum matrix defined by \((T_n)_{tj} = \mathbf{1}\{j \le t\}\) for \(t,j \in [n]\). Let \(\mathcal{M}\) be a randomized mechanism whose output \(\mathcal{M}(x) \in \mathbb{R}^n\) contains the estimate \(\mathcal{M}(x)_t\) at time \(t\). We assume that \(\mathcal{M}\) is \(\epsilon\)-differentially private with respect to neighboring streams, where \(x,x' \in \{0,1\}^n\) are neighbors if \(\|x-x'\|_1 \le 1\). To measure the utility of the mechanism, we use the maximum squared error and the mean squared error, defined as follows: \[\begin{align} &\operatorname{MaxSE}(\mathcal{M},n) := \max_{x \in \{0,1\}^n} \max_{t \in [n]} \mathbb{E}_{\mathcal{M}} \left[ \left( \mathcal{M}(x)_t - (T_nx)_t \right)^2 \right],\\ &\operatorname{MeanSE}(\mathcal{M},n) := \max_{x \in \{0,1\}^n} \mathbb{E}_{\mathcal{M}} \left[ \frac{1}{n} \left\| \mathcal{M}(x) - T_nx \right\|_2^2 \right]. \end{align}\] We formulate the differentially private continual counting problem as finding an \(\epsilon\)-DP mechanism \(\mathcal{M}\) that minimizes these errors. In particular, to establish upper bounds on these errors, we consider a specific family of mechanisms, namely matrix factorization mechanisms. Consider a factorization \(T_n = LR\), where \(L \in \mathbb{R}^{n \times r}\) and \(R \in \mathbb{R}^{r \times n}\). To make the product \(T_n x\) private, we first multiply \(x\) by \(R\), add Laplace noise to the resulting vector \(Rx\), and then postprocess the noisy vector by multiplying it by \(L\). The associated matrix mechanism is \[\mathcal{M}_{L,R}(x) := L(Rx + z),\] where \(z \in \mathbb{R}^r\) has independent Laplace coordinates with scale \(\max_{i \in [n]}\|R_{:,i}\|_{1}/\epsilon\), i.e., the maximum \(\ell_1\) norm of a column of \(R\) divided by \(\epsilon\). For this mechanism, the errors can be computed as \[\operatorname{MaxSE}(\mathcal{M}_{L,R},n) = \frac{2}{\epsilon^2} \|L\|_{2 \to \infty}^2 \|R\|_{1 \to 1}^2, \qquad \operatorname{MeanSE}(\mathcal{M}_{L,R},n) = \frac{2}{\epsilon^2} \frac{1}{n} \|L\|_F^2 \|R\|_{1 \to 1}^2,\] where \(\|\cdot\|_{2 \to \infty}\) denotes the maximum \(\ell_2\) norm of the rows, and \(\|\cdot\|_{1 \to 1}\) denotes the maximum \(\ell_1\) norm of the columns. To simplify notation, we introduce max-error and mean-error factorization costs³ which can be defined for a general matrix \(M \in \mathbb{R}^{n \times n}\) as follows: \[\begin{align} &c_2(M) := \inf_{\substack{ r \ge 1,\, L \in \mathbb{R}^{n \times r},\, R \in \mathbb{R}^{r \times n} \\ LR = M }} \|L\|_{2 \to \infty}\,\|R\|_{1 \to 1},\\ &c_F(M) := \inf_{\substack{ r \ge 1,\, L \in \mathbb{R}^{n \times r},\, R \in \mathbb{R}^{r \times n} \\ LR = M }} \frac{1}{\sqrt n}\, \|L\|_F\,\|R\|_{1 \to 1}. \end{align}\]

Consequently, optimizing over all factorizations \(T_n = LR\) reduces the problem to bounding the factorization costs \(c_2(T_n)\) and \(c_F(T_n)\).

1.2 Our contribution↩︎

Our main contribution is a new upper bound for pure-DP continual counting based on general matrix factorization.

Our construction starts from a good-quality factorization \(AB=T_k\) for some fixed \(k\), found numerically by gradient-based optimization, and lifts it to arbitrarily large dimensions by an explicit recursive operation on factorizations. More precisely, given factorizations \(AB = T_n\) and \(CD = T_k\), we can construct a factorization \(LR = T_{2kn+n+k}\) with \(c_2\) and \(c_F\) costs satisfying \[\begin{align} \left( \|L\|_{2 \to \infty} \|R\|_{1 \to 1} \right)^{2/3} &\leq \left( \|A\|_{2 \to \infty} \|B\|_{1 \to 1} \right)^{2/3} + \left( \|C\|_{2 \to \infty} \|D\|_{1 \to 1} \right)^{2/3}, \text{ or} \\ \left(\frac{1}{\sqrt{2kn+n+k}}\|L\|_{F} \|R\|_{1 \to 1} \right)^{2/3} &\leq \left(\frac{1}{\sqrt{n}} \|A\|_{F} \|B\|_{1 \to 1} \right)^{2/3} + \left(\frac{1}{\sqrt{k}} \|C\|_{F} \|D\|_{1 \to 1} \right)^{2/3}, \end{align}\] depending on which cost we are interested in. Iterating this operation gives asymptotically good factorizations of \(T_n\) for all \(n\).

These constants improve on the previous best pure-DP bounds of the \(k\)-ary tree mechanism with the subtraction trick. In particular, the leading constant for maximum squared error improves by a factor of about \(3\) in comparison to [18] and about \(1.5\) in comparison to the averaged \(k\)-ary tree mechanism with subtraction. The leading constant for mean squared error improves by a factor of about \(1.6\). The comparisons with other methods are given in Table 1. Some of the errors had not previously been computed in the pure-DP setting, we provide the missing entries of the table in Appendix 8.

We also show that the resulting mechanism can be implemented efficiently. Although the construction is described as a matrix factorization, the matrices obtained by the recursive construction are sparse and structured. This allows the correlated noise term \(Lz\) to be generated online, yielding an implementation with \(O_{A,B}(\log n)\) space and \(O_{A,B}(n\log n)\) total running time for any fixed base factorization \(AB=T_k\).

On the lower-bound side, we prove that the \(\Omega(\log^3 n)\) squared-error behavior is unavoidable for any matrix-factorization-based mechanism with factors being \(0/1\) matrices. Specifically, if \(L\) and \(R\) have entries in \(\{0,1\}\) and satisfy \(LR=T_n\), then \[\begin{align} \|L\|_{2\to\infty}\|R\|_{1\to 1} &\geq 0.290\,\log_2^{3/2}(n-1) = \Omega\left(\log^{3/2}n\right), \text{ and} \\ \frac{1}{\sqrt n}\|L\|_F\|R\|_{1\to 1} &\geq \left(\frac{\log 2}{6}\right)^{3/2} \sqrt{1-\frac{1}{n}}\,\log_2^{3/2}(n-1) = \Omega\left(\log^{3/2}n\right). \end{align}\] We prove this by reducing to the “skew Bollobás” inequalities from extremal combinatorics. The main idea is to interpret the matrices as encodings of collections of sets satisfying certain pairwise intersection properties. Consequently, every pure-DP matrix mechanism arising from such a \(0/1\) factorization has maximum and mean squared error at least \(\Omega(\epsilon^{-2}\log^3 n)\). This class includes the binary tree mechanism and the standard \(k\)-ary tree mechanisms without the subtraction trick. We point out that for \(\operatorname{MaxSE}\), our bound yields \(\operatorname{MaxSE}(\mathcal{M}_{L,R},n) \geq 0.168 \frac{\log_2^3 n}{\epsilon^2} (1+o(1))\) for any \(0/1\) factorization \(LR = T_n\), with the constant \(0.168\) being greater than the constant in our upper bound. Therefore, to further improve the leading constant for \(\operatorname{MaxSE}\), one cannot remain in the class of \(0/1\) factorizations. Previously known lower bounds for the factorization costs were of order \(\Omega(\log n)\).

Finally, we establish some structural facts about these factorization costs. In particular, we show that \(c_2\) and \(c_F\) are not matrix norms, since they fail the triangle inequality. This helps motivate why the pure-DP setting is not as well-behaved as the approximate-DP setting, where the analogous \(\ell_2\)-sensitivity factorization costs are matrix norms.

Our upper bound theorem depends on specific base factorizations. We provide both base factorizations, as well as code for verifying the claimed factorization norms using exact rational (fraction-based) arithmetic, via the following link.

https://github.com/npkalinin/Pure_DP_Continual_Counting_with_MF

1.3 Related Work↩︎

1.3.0.1 Upper bounds.

The first method for continual counting, and also the first use of the continual observation model, was the binary tree mechanism [2], [15]. Omitting lower-order terms, it gives MaxSE \(2\epsilon^{-2}\log_2(n)^3\) and MeanSE \(\epsilon^{-2}\log_2(n)^3\). There are several ways to improve it. First, one can generalize the binary tree mechanism to a \(k\)-ary tree, in which each node has \(k\) children [7], [17]. Optimizing over the choice of \(k\) decreases the error. Honaker [16] proposed using a subtraction trick, which changes how the prefix sum is decomposed into a sum of subintervals. This work also discussed the idea of using multiple weighted measurements to construct an estimator, which was later generalized to computing an optimal decoding matrix \(L\) based on the pseudoinverse of \(R\). Andersson and Pagh [23] proposed a smooth binary tree mechanism that addresses the discrepancy between MaxSE and MeanSE, reducing the MaxSE. Combining the subtraction trick with \(k\)-ary trees, Andersson, Pagh, Steiner, and Torkamani [18] achieved the best known constants for the problem. Finally, their construction was further refined in the implementation code for the paper by Imola, Boninsegna, Keller, Aamand, Chowdhury, and Pagh [4] on private quantile estimation. In particular, the code exploits the idea of averaging multiple decompositions of the prefix interval, empirically improving the constants. However, this method has not been formally described elsewhere. With the authors’ permission, we provide a description and error analysis for this method, which we refer to as the averaged \(k\)-ary tree with subtraction; see Subsection 8.3.

Matrix factorization has been proposed for general continual linear queries, with arbitrary weighted sums of the input stream, by Li, Miklau, Hay, McGregor, and Rastogi [19]. The optimal factorization was formulated as a semidefinite program with rank constraints, but without an upper bound on the running time. Numerically, we found it impractical to use, and instead used gradient optimization to find high-quality finite-dimensional factorizations.

We summarize the constants in Table 1. The proofs of the error terms for the related works are scattered across the literature: the MeanSE for the \(k\)-ary trees with and without subtraction was computed explicitly in [18], while the maximum squared error for the \(k\)-ary trees with subtraction was computed by Andersson, Jain, and Sivakumar [14] in Theorem 9.16, taking \(D=k=1\) in their notation. For completeness, we present the analysis of the missing entries in Appendix 8.

1.3.0.2 Lower bounds.

The best-known lower bounds for continual counting are of order \(\Omega(\log^2(n)/\epsilon^2)\), both for the mean squared error [21] and for the maximum squared error [2], [22]. Similar bounds hold under approximate differential privacy as well. In this work, we establish \(\Omega(\log^{3}(n)/\epsilon^{3})\) lower bounds in a specific setting of factorizations with \(0/1\) entries, using combinatorial techniques based on Bollobás-type inequalities [24]. To the best of our knowledge, this approach has not previously been used either in the context of matrix factorizations or generally in the differential privacy literature.

In concurrent work, Bairaktari and Larsen [25] prove a lower bound for pure DP continual counting of \(\Omega(\epsilon^{-2}\log^3(n))\) for the squared \(\ell_{\infty}\) metric. This metric is related to the metrics that we consider, \(\operatorname{MaxSE}\) and \(\operatorname{MeanSE}\). In general, being squared, the \(\ell_{\infty}\) metric upper bounds \(\operatorname{MaxSE}\) and \(\operatorname{MeanSE}\), and therefore their bounds do not directly transfer to the settings considered here. Nevertheless, their result gives hope that a similar lower bound may eventually be proved for \(\operatorname{MaxSE}\) and \(\operatorname{MeanSE}\).

1.3.0.3 Continual counting with approximate DP.

The problem under approximate differential privacy has received, perhaps, even more attention in recent years due to its applications to model training via DP-SGD [26]–[33]. For approximate DP, one commonly uses Gaussian noise for matrix factorization, which results in \(\ell_2\) sensitivity rather than \(\ell_1\) sensitivity. This setting is more theoretically amenable, since the costs corresponding to our \(c_2\) and \(c_F\), namely \(\gamma_2\) and \(\gamma_F\), obtained by replacing the \(\|.\|_{1\to 1}\) norm with the \(\|.\|_{1\to 2}\) norm, are in fact matrix norms. For these norms, the asymptotics are known and tight; moreover, the leading asymptotic term is known with the constant [34]. Several works have focused on refining the next asymptotic term [35], with the best bounds achieved by Henzinger, Kalinin, and Upadhyay [36].

The recent intensive progress in the approximate DP setting motivates the study of constants in the pure DP setting, which has proved to be more challenging. We remark that the constructions used to optimize the \(\gamma_2\) and \(\gamma_F\) norms would give the wrong asymptotics if applied to the pure DP case, thus calling for fundamentally new constructions.

1.4 Preliminaries↩︎

1.4.0.1 Notation.

For a matrix \(A \in \mathbb{R}^{m \times n}\) and \(p,q \in [1,\infty]\), we write \(\|A\|_{p \to q} := \sup_{\|x\|_p \le 1} \|Ax\|_q\) for the induced operator norm from \(\ell_p^n\) to \(\ell_q^m\). In particular, \(\|A\|_{2 \to \infty} = \max_{i \in [m]} \|A_{i,:}\|_2\) and \(\|A\|_{1 \to 1} = \max_{j \in [n]} \|A_{:,j}\|_1\), where \(A_{i,:}\) and \(A_{:,j}\) denote the \(i\)-th row and \(j\)-th column of \(A\), respectively. We also write \(\|A\|_F := (\sum_{i,j} A_{ij}^2)^{1/2}\) for the Frobenius norm. We use \(\log(.)\) for the natural logarithm and \(\log_2(.)\) for the binary logarithm. For two matrices \(A \in \mathbb{R}^{m \times n}\) and \(B \in \mathbb{R}^{p \times q}\), the Kronecker product of \(A\) and \(B\), denoted by \(A \otimes B\), is the matrix in \(\mathbb{R}^{mp \times nq}\) defined by \[A \otimes B = \begin{pmatrix} a_{11}B & a_{12}B & \cdots & a_{1n}B \\ a_{21}B & a_{22}B & \cdots & a_{2n}B \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1}B & a_{m2}B & \cdots & a_{mn}B \end{pmatrix}.\]

For the \(d \times d\) identity matrix, we write \(I_d\). If the dimension is clear from the context, we may use just \(I\). The all-ones \(m \times k\) matrix is denoted as \(J_{m \times k}\), and the subscript is omitted if it is clear. We use the notation \(\mathbf{1}_n = J_{n \times 1}\) and \(\mathbf{1}_n^T = J_{1 \times n}\). Given a collection of matrices \(M_1, \ldots, M_k\) that are not necessarily square, we denote the block-diagonal matrix formed with \(M_i\) as \(\text{diag}(M_1, \ldots, M_k)\).

1.4.0.2 Differential privacy.

We use the standard notion of pure differential privacy and the Laplace mechanism of Dwork, McSherry, Nissim, and Smith [1]. Let \(\mathcal{X}\) be a data universe, and say that two datasets \(D,D' \in \mathcal{X}^n\) are neighboring, written \(D \sim D'\), if they differ in the data of at most one individual. A randomized mechanism \(\mathcal{M} : \mathcal{X}^n \to \mathcal{Y}\) is \(\epsilon\)-differentially private if, for every \(D \sim D'\) and every measurable \(S \subseteq \mathcal{Y}\), \[\Pr[\mathcal{M}(D) \in S] \le e^\epsilon \Pr[\mathcal{M}(D') \in S].\] For a query \(f : \mathcal{X}^n \to \mathbb{R}^k\), its \(\ell_1\)-sensitivity is \(\Delta_1(f) := \sup_{D \sim D'} \|f(D)-f(D')\|_1\). The Laplace mechanism outputs \(f(D)+z\), where the coordinates of \(z\) are independent \(\mathrm{Laplace}(\Delta_1(f)/\epsilon)\) random variables, and the resulting mechanism is \(\epsilon\)-differentially private.

2 Upper bound construction↩︎

We start with two inequalities that are going to be fundamental in this paper.

To establish these inequalities, we will describe a way to construct a factorization of \(T_{2kn + n + k}\) with low cost given factorizations of \(T_n\) and \(T_k\). The definition below is designed with Figure 1 in mind.

Notice that the matrix \(EA\) is \(A\) with rows in inverse order, and \(BE\) is \(B\) with columns in inverse order. The definition above may look somewhat complicated, but it makes sense in the context of matrix factorization, since it allows us to factorize \(T_{2kn+n+k}\) given factorizations for \(T_n\) and \(T_k\), as shown in the following lemma.

2.0.0.1 Proof of Theorem 2.

Let us analyze the quality of the factorization produced by the new \(\lozenge_\alpha\) factorization. Let \(AB = T_n\) and \(CD = T_k\), and let \((L, R) := (A, B) \lozenge_\alpha (C, D)\). We have shown that \(LR = T_{2kn + n + k}\). Clearly \(\|A\|_{2 \to \infty} = \|EA\|_{2 \to \infty}\), \(\|A\|_{F} = \|EA\|_{F}\), and \(\|B\|_{1 \to 1} = \|BE\|_{1 \to 1}\). We observe the following: \[\begin{align} \|L\|_{2 \to \infty} &= \sqrt{\|A\|_{2 \to \infty}^2 + \alpha^2 \|C\|_{2 \to \infty}^2}, \\ \frac{1}{\sqrt{2kn+n+k}} \|L\|_F &= \sqrt{\frac{(2k+1) \|A\|_F^2 + (2n+1) \alpha^2 \|C\|_F^2}{2kn+n+k}} < \sqrt{\frac{\|A\|_F^2}{n} + \frac{\alpha^2 \|C\|_F^2}{k}}, \\ \|R\|_{1 \to 1} &= \|B\|_{1 \to 1} + \frac{1}{\alpha} \|D\|_{1 \to 1}. \end{align}\] Then we can compute the \(LR\) factorization costs: \[\label{eq95quality95with95alpha} \begin{align} \|L\|_{2 \to \infty} \|R\|_{1 \to 1} &= \sqrt{\|A\|_{2 \to \infty}^2 + \alpha^2 \|C\|_{2 \to \infty}^2} \left( \|B\|_{1 \to 1} + \frac{1}{\alpha} \|D\|_{1 \to 1} \right), \\ \frac{1}{\sqrt{2kn + n + k}} \|L\|_F \|R\|_{1 \to 1} &< \sqrt{\frac{\|A\|_F^2}{n} + \frac{\alpha^2 \|C\|_F^2}{k}} \left( \|B\|_{1 \to 1} + \frac{1}{\alpha} \|D\|_{1 \to 1} \right). \end{align}\tag{2}\] We are free to choose the parameter \(\alpha\) as we wish. In particular, we can choose values that minimize the right-hand sides of the bounds in 2 . Setting the derivative to zero and carrying out a straightforward calculation yields the optimal values \[\label{eq95optimal95alpha} \begin{align} \alpha &= \left( \frac{\|A\|_{2 \to \infty}^2 \|D\|_{1 \to 1}}{\|C\|_{2 \to \infty}^2 \|B\|_{1 \to 1}} \right)^{1/3} \text{ for the c_2-cost, and} \\ \alpha &= \left( \frac{\frac{1}{n}\|A\|_{F}^2 \|D\|_{1 \to 1}}{\frac{1}{k}\|C\|_{F}^2 \|B\|_{1 \to 1}} \right)^{1/3} \text{ for the c_F-cost}. \end{align}\tag{3}\] Plugging in these values into inequalities 2 , we get \[\label{eq95lozenge95cost95bounds} \begin{align} \|L\|_{2 \to \infty} \|R\|_{1 \to 1} &\leq \left( \left( \|A\|_{2 \to \infty} \|B\|_{1 \to 1} \right)^{2/3} + \left( \|C\|_{2 \to \infty} \|D\|_{1 \to 1} \right)^{2/3} \right)^{3/2},\\ \frac{1}{\sqrt{2kn+n+k}} \|L\|_F \|R\|_{1 \to 1} &\leq \left( \left( \frac{1}{\sqrt{n}}\|A\|_{F} \|B\|_{1 \to 1} \right)^{2/3} + \left( \frac{1}{\sqrt{k}}\|C\|_{F} \|D\|_{1 \to 1} \right)^{2/3} \right)^{3/2}. \end{align}\tag{4}\] From now on, we will write \((A, B) \lozenge(C, D)\) without \(\alpha\) in the subscript, meaning that \(\alpha\) is chosen optimally for either \(c_2\)-cost or \(c_F\)-cost, when the cost is clear from the context.

Theorem 2 is almost immediately implied. Suppose \(AB\) and \(CD\) are factorizations of \(T_n\) and \(T_k\) respectively that are arbitrarily close to the corresponding infimums, so \((\|A\|_{2 \to \infty} \|B\|_{1 \to 1})^{2/3} \leq c_2(T_n)^{2/3} + \varepsilon\), and \((\|C\|_{2 \to \infty} \|D\|_{1 \to 1})^{2/3} \leq c_2(T_k)^{2/3} + \varepsilon\) for a positive \(\varepsilon\). Then, for \((L, R) = (A, B) \lozenge (C, D)\), we have \((\|L\|_{2 \to \infty} \|R\|_{1 \to 1})^{2/3} \leq c_2(T_n)^{2/3} + c_2(T_k)^{2/3} + 2 \varepsilon\). Taking \(\varepsilon\) arbitrarily small, we get \(c_2(T_{2kn + n + k})^{2/3} \leq c_2(T_n)^{2/3} + c_2(T_k)^{2/3}\), as claimed in Theorem 2. The \(c_F\) cost is similar.

Now we have a tool to construct factorizations with good asymptotic behavior.

In other words, if we have a good-quality factorization of \(T_k\) in some fixed dimension \(k\), then we can generate factorizations of \(T_n\) in arbitrarily high dimensions, with a strictly better constant in front of \((\log_2 n)^{3/2}\) in the asymptotics of the costs. For large \(k\), the factor \(\left( \frac{\log_2 k}{\log_2 (2k+1)} \right)^{3/2}\) is approximately \(\left( 1 - \frac{3/2}{\log_2 k} \right)\). In the next paragraph, we give intuition for Theorem 4 and defer the full proof to Appendix 6.

Consider the case when the matrices \((L', R') = \underbrace{(A,B) \lozenge \ldots \lozenge (A, B)}_{p \text{ times}}\) have size of \(L'R'\) equal to \(n\). In this case, \(L = L'\) and \(R = R'\). Notice that \(n = \Theta\left( (2k+1)^p \right)\), implying \(p = \frac{\log_2 n}{\log_2 (2k+1)} (1+o(1))\). Then we can apply equation 4 \(p-1\) times and get \[\begin{align} (\|L'\|_{2 \to \infty} \|R'\|_{1 \to 1})^{2/3} \leq \left( C_2 (\log_2 k)^{3/2} \right)^{2/3} \cdot p = C_2^{2/3} \frac{\log_2 k}{\log_2 (2k+1)} (\log_2 n) (1+o(1)), \end{align}\] and similarly \[\left( \frac{1}{\sqrt{N}} \|L'\|_{F} \|R'\|_{1 \to 1} \right)^{2/3} \leq C_F^{2/3} \frac{\log_2 k}{\log_2 (2k+1)} (\log_2 n) (1+o(1)).\] These give us the claim of the theorem. What is left to analyze is the case where \(n\) is not exactly the size of \(L'R'\). One would expect the same asymptotic bounds for these “non-round” \(n\). There, the \(c_2\) cost follows easily, but the \(c_F\) needs a more careful argument. We bound the parameters \(\alpha\) and exploit the recursive structure of \(L'\). A complete analysis is given in Appendix 6.

2.0.0.2 Remark on the construction.

The idea of constructing high-dimensional factorizations from lower-dimensional building blocks has appeared previously in the literature. Dvijotham, McMahan, Pillutla, Steinke, and Thakurta [37] introduce the “Recursive Matrix Factorization” for the problem of memory-efficient approximate DP counting. The construction in [37] takes factorizations of \(T_n\) and \(T_k\) and produces a factorization of \(T_{kn}\). Thus, the logarithms of the dimensions are added: \(\log n + \log k = \log(kn)\). In the resulting factorization, the quantities \(\|.\|_{2 \to \infty}^2\) and \(\|.\|_{1 \to 1}\) would also be added. In this way, one could start from a single good factorization and lift it to arbitrarily high dimensions while preserving the constant in the asymptotics. We improve upon this approach by constructing a factorization of \(T_{2kn+n+k}\), obtaining \(\log n + \log k + \log 2 \approx \log(2kn+n+k)\). This additional \(\log 2\) term allows us to achieve a better constant in our bounds.

2.1 Explicit factorizations and numerical results↩︎

We perform numerical optimization to minimize the costs \(c_2(T_k)\) and \(c_F(T_k)\) over finite-dimensional matrices \(L \in \mathbb{R}^{k \times s}\) and \(R \in \mathbb{R}^{s \times k}\). In particular, we run \(5\times 10^{4}\) iterations of the Adam optimizer [38], followed by \(300\) steps of the L-BFGS optimizer [39]. In Table 2, we report the constants for MaxSE and MeanSE. Specifically, we compute \(C_2\) and \(C_F\) from Theorem 4 and report \(2C_2^2\) and \(2C_F^2\), which correspond to the constants in Table 1. Theorem 4 shows that, by recursively lifting the dimension, the cost can be further improved by a factor of \(\left(\frac{\log_2(k)}{\log_2(2k+1)}\right)^{3/2}\). This yields a larger improvement for smaller values of \(k\). Taking the square of this improvement factor, we report the final MaxSE and MeanSE constants in the last two columns. The best performance was achieved by matrices of size \(1024\times 1024\).

The matrices are, however, computed in finite precision and, by themselves, do not constitute a rigorous upper bound. In fact, strictly speaking, we do not obtain an exact factorization, since the product \(LR\) is only approximately equal to \(T_k\). To make the resulting bound rigorous, we provide the following reasoning.

For MeanSE, we provide the corresponding floating-point matrix \(R\) at the same repository.⁶ The adjustments for floating-point errors are the same as in Proposition 5, with \(\|L\|_F\) computed instead of \(\|L\|_{2\to \infty}\). Repeating the same steps, we obtain \[\begin{align} &\|R\|_{1\to 1} \le 14.3098, \qquad \|\tilde{L}\|_{F} \le 15.3624, \qquad \|\Delta L\|_F \le 0.0037, \qquad \|L\|_F \le 15.3661, \\ &2C_F^2 = \frac{2\|L\|_F^2\|R\|_{1\to 1}^2}{k\log_2(k)^3} \le 0.0945, \qquad 2C_F^2 \left(\frac{\log_2(k)}{\log_2(2k + 1)}\right)^3 \le 0.0710. \end{align}\] This gives the constants in Theorem 1. At the same link, we provide code for verifying the stated bounds using the SymPy library [40] for symbolic computation.

3 Memory efficient noise correlation↩︎

In this section, we prove the space and time complexity of the matrix factorization mechanism, with the corresponding factorization given by Construction 3. Since the resulting matrices are sparse and recursively constructed, the factorization naturally yields a recursively described algorithm that uses \(O(\log n)\) memory and runs in \(O(n \log n)\) time, matching the complexity of previous tree-based algorithms.

Recall that the output of the matrix mechanism is \[\mathcal{M}_{L,R}(x) := L(Rx + z) = T_n x + Lz,\] where \(z\) is the noise vector with coordinates sampled independently from the Laplace distribution with scale \(\|R\|_{1 \to 1}/\epsilon\).

In this section, we fix a base factorization \(AB = T_k\) for Construction 3, with \(A \in \mathbb{R}^{k \times r}\), \(B \in \mathbb{R}^{r \times k}\). If \(p\) is the number of terms in the product \((A,B) \lozenge \ldots \lozenge (A,B) = (L', R')\), then the matrix \(L'\) has size \(\frac{(2k+1)^p - 1}{2} =: N_p\) times \(\left( r + \frac{k+r}{2k} \right)(2k+1)^{p-1} - \frac{k+r}{2k} =: M_p\), which can be verified inductively. We denote \(L_1 = A\), \(R_1 = B\), and \((L_{i+1}, R_{i+1}) = (L_i, R_i) \lozenge (A, B)\). In this notation, \(L' = L_p\), \(R' = R_p\). The main ingredient is an algorithm that streams the correlated noise \(Lz\). Notice that the stream \(Lz\) is just a prefix of a stream \(L'z\). The noise-streaming algorithm is presented as Algorithm 2.

In Algorithm 2, NoiseReversed streams the same correlated noise, but in the reversed order, the procedure is implemented in Algorithm 3 in a similar recursive way. \(\alpha_{p-1}\) is the optimal parameter in the operation \((\underbrace{(A,B) \lozenge \ldots \lozenge (A,B)}_{p-1 \text{ times}}) \lozenge_{\alpha_{p-1}} (A, B) = (L', R')\). We prove that Noise indeed streams the values of \(L'z\), by induction: when \(p=1\) we output \(Az\) by construction, and when \(p > 1\) the output is \(\begin{pmatrix} L_{p-1} & 0_{N_{p-1} \times k(2M_{p-1}+1)} & 0_{N_{p-1} \times s}\\ 0_{k(2N_{p-1}+1) \times M_{p-1}} & I_{k} \otimes \widetilde{L}_{p-1} & \alpha_{p-1} A \otimes \mathbf{1}_{2N_{p-1}+1} \end{pmatrix} z\), which agrees with our recursive Construction 3. Similarly, NoiseReversed steams the values of \(L'z\) in reverse. The final mechanism is now straightforward: compute the prefix sums and add the values from the Noise stream.

In the algorithms, we use the values \(\alpha_{p-1}\), \(N_p\), \(\|R'\|_{1 \to 1}\). Notice that these values can be computed recursively in \(O(p)\) arithmetic operations.

4 Lower bounds for 0/1 factorizations↩︎

In this section, we discuss lower bounds on \(c_2(T_n)\) and \(c_F(T_n)\). All known constructions for these factorization costs show the behavior \(\Theta \left( \log n \right)^{3/2}\); however, the lower bounds remain \(\Omega(\log n)\). In the next two theorems, we show that if one considers the factorizations \(LR = T_n\) such that the entries of \(L\) and \(R\) are in \(\{0, 1\}\), then both factorization costs must be \(\Omega(\log^{3/2} n)\). Notice that the cases of binary tree factorizations and \(k\)-ary tree factorizations fall into this category of \(0/1\) factorizations. Indeed, computing a sum of a segment that corresponds to a node in the tree yields a row of the form \((0, \ldots, 0, 1, \ldots, 1, 0, \ldots, 0)\) in \(R\). Adding several such sums to get a prefix sum means a row with zeros and ones in \(L\).

It would be interesting to generalize these two theorems to obtain a true lower bound of \(\Omega(\log^{3/2} n)\) on \(c_2(T_n)\) and \(c_F(T_n)\), without the restriction to 0/1 factorizations. However, such generalization remains elusive.

5 Additional results on factorization costs↩︎

Our factorization costs \(c_2\) and \(c_F\) are defined as \(c_2(M) = \inf \{\|L\|_{2 \to \infty} \|R\|_{1 \to 1} \; | \; M=LR\}\) and \(c_F(M) = \inf \{\frac{1}{\sqrt{n}}\|L\|_{F} \|R\|_{1 \to 1} \; | \; M=LR\}\) for an \(n \times n\) matrix \(M\). One would have a reasonable hope that \(c_2\) and \(c_F\) could be factorization norms. For example, their well-behaved and well-studied counterparts, the \(\gamma_2\) and \(\gamma_F\) norms, look very similar: \[\begin{align} \gamma_2(M) = \inf \{\|L\|_{2 \to \infty} \|R\|_{1 \to 2} \; | \; M=LR\},\\ \gamma_F(M) = \inf \{\tfrac{1}{\sqrt{n}}\|L\|_{F} \|R\|_{1 \to 2} \; | \; M=LR\}. \end{align}\] In this section, we prove that neither \(c_2\) nor \(c_F\) is a norm, because they fail the triangle inequality. Our counterexample is the matrix decomposition \(2T_2 = \begin{pmatrix} 2 & 0 \\ 2 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 1\\1 & 1 \end{pmatrix}+\begin{pmatrix} 1 & -1 \\ 1 & 1 \end{pmatrix}\). We will show that \[\label{eq95counterexample} \begin{align} c_2 \begin{pmatrix}2 & 0\\2 & 2\end{pmatrix} &> c_2 \begin{pmatrix}1 & 1\\1 & 1\end{pmatrix} + c_2 \begin{pmatrix}1 & -1\\1 & 1\end{pmatrix} \text{ and} \\ c_F \begin{pmatrix}2 & 0\\2 & 2\end{pmatrix} &> c_F \begin{pmatrix}1 & 1\\1 & 1\end{pmatrix} + c_F \begin{pmatrix}1 & -1\\1 & 1\end{pmatrix}, \end{align}\tag{7}\] which disproves the triangle inequality for \(c_2\) and \(c_F\). The two matrices on the right-hand side can be factorized as \(\begin{pmatrix}1 & 1\\1 & 1\end{pmatrix} = \begin{pmatrix}1 \\ 1\end{pmatrix} \begin{pmatrix}1 & 1\end{pmatrix}\) and \(\begin{pmatrix}1 & -1\\1 & 1\end{pmatrix} = \begin{pmatrix}1 & -1\\1 & 1\end{pmatrix} \begin{pmatrix}1 & 0\\0 & 1\end{pmatrix}\). This implies \[\begin{align} c_2 \begin{pmatrix}1 & 1\\1 & 1\end{pmatrix} + c_2 \begin{pmatrix}1 & -1\\1 & 1\end{pmatrix} \leq 1 + \sqrt{2}, \\ c_F \begin{pmatrix}1 & 1\\1 & 1\end{pmatrix} + c_F \begin{pmatrix}1 & -1\\1 & 1\end{pmatrix} \leq 1 + \sqrt{2}. \end{align}\] Thus, it is enough to prove \(c_2(T_2) > \frac{1 + \sqrt{2}}{2}\) and \(c_F(T_2) > \frac{1 + \sqrt{2}}{2}\). The rest of this section studies \(c_2(T_2)\) and \(c_F(T_2)\) to prove these inequalities.

First, we bound the inner dimension. We have the infimums taken over factorizations \(T_2 = LR\) with \(L \in \mathbb{R}^{2 \times r}\), \(R \in \mathbb{R}^{r \times 2}\). We show in the next lemma that without loss of generality we can fix \(r = 2\).

The proofs in this section are technical and moved to Appendix 7.

The main idea of the proof is to act on the rows of \(L\) and columns of \(R\) with a suitable rotation. This preserves the dot products of the rows of \(L\) and the columns of \(R\), so the factorization remains valid. The task is to choose the rotation such that it does not stretch the columns of \(R\) in terms of the \(\ell_1\) norm, and also maps them into the span of the first two basis vectors. The complete proof is in Appendix 7.

Now we can find \(c_2(T_2)\) and \(c_F(T_2)\), limiting ourselves to \(2 \times 2\) factors.

For both lemmas above, we show that the trivial factorization \(T_2 = T_2 I_2\) is optimal. A useful trick for the proofs is that in two dimensions, the rotation by \(45^\circ\) turns \(\ell_1\) norms into \(\ell_\infty\) norms, scaled by \(\sqrt{2}\), which are easier to analyze. Both proofs essentially boil down to case studies. The proofs can be found in Appendix 7.

Both \(\sqrt{2}\) and \(\sqrt{3/2}\) are greater than \(\frac{1 + \sqrt{2}}{2}\), so inequalities 7 hold.

5.1 General upper bound for matrix norms↩︎

We have shown that \(c_2\) and \(c_F\) are not norms. Philosophically, this is part of the reason why we could not get \(c_2(T_n)\) and \(c_F(T_n)\) down to \(O(\log n)\). In this section we show that if \(c_2\) and \(c_F\) were norms, then \(O(\log n)\) would be the right answer. We make the following general observation.

We do not claim much novelty in this statement. For example, it can be deduced from Proposition 1.1 in [43]. However, we find our proof above to be more elegant.

5.1.0.1 AI Declaration.

The authors used AI tools to assist in drafting the subsection “Our contribution” as a summary of the other sections; in drafting proofs of Lemmas 2, 3, and 4; in drafting technical parts of the proof of Theorem 4; and in preparing the code accompanying Lemma 5.

The authors have reviewed, edited, proofread, and verified all AI-assisted text, proofs, and code, and take full responsibility for the content of the manuscript and accompanying materials.

5.1.0.2 Acknowledgment.

We thank Rasmus Pagh and Joel Andersson for their valuable feedback on an earlier version of the draft, as well as for referring us to some related work. We additionally thank Rasmus for referring us to the code for averaged k-ary trees with subtraction.

Nikita Kalinin is supported in part by the Austrian Science Fund (FWF) [10.55776/COE12].

6 Proof of the upper bound (Theorem 4)↩︎

7 Proofs of the additional results↩︎

8 Factorization costs for tree-based methods↩︎

Table 1 reports the \(\operatorname{MaxSE}\) and \(\operatorname{MeanSE}\) errors for several continual counting mechanisms, including smooth binary trees, \(k\)-ary trees with and without subtraction, and averaged \(k\)-ary trees with subtraction. Some of these mechanisms were not developed for the pure-DP setting and therefore did not explicitly state \(\operatorname{MaxSE}\) and \(\operatorname{MeanSE}\). For completeness, we provide calculations of these quantities for all mechanisms considered.

8.1 Smooth binary trees↩︎

Consider the factorization \(T_n=LR\) yielded by the smooth binary tree mechanism [23]. Take a tree of height \(h\), and let the active leaves be the \(h\)-bit strings with exactly \(k\) zeros. The construction uses \(k=h/2\).

The key combinatorial facts are the following. The sum values are stored only in the tree nodes that are left children. Then, each input coordinate contributes to exactly \(k\) stored tree sums, so every column of \(R\) has \(\ell_1\)-norm \(k\). Hence \(\|R\|_{1\to 1}=k\). Also, each prefix query is recovered as a sum of exactly \(h-k\) stored tree sums, so every row of \(L\) has \(h-k\) nonzero entries, all equal to \(1\). Therefore \(\|L\|_{2\to\infty}=\sqrt{h-k}\), and \(\|L\|_F^2=n(h-k)\).

For the choice \(k=h/2\), we have \(h\) such that \({h \choose h/2} \geq n\), implying \(h = (1+o(1))\log_2 n\). Then \[\|L\|_{2\to\infty}\|R\|_{1\to 1} = \sqrt{h/2}\cdot h/2 = \left(\frac{\log_2 n}{2}\right)^{3/2} (1+o(1)), \quad \operatorname{MaxSE}= \frac{\log_2^3 n}{4} (1+o(1)).\]

Similarly, since \(\frac{1}{n}\|L\|_F^2\) coincides with \(\|L\|_{2\to\infty}^2\) for this factorization, we have \[\frac{1}{\sqrt{n}} \|L\|_{F}\|R\|_{1\to 1} = \left(\frac{\log_2 n}{2}\right)^{3/2} (1+o(1)), \quad \operatorname{MeanSE}= \frac{\log_2^3 n}{4} (1+o(1)).\]

8.2 \(k\)-ary trees↩︎

Let \(LR = T_n\) be a decomposition corresponding to the \(k\)-ary tree mechanism.

The depth of the tree is \(h = (1+o(1)) \log_k n = \frac{\log_2 n}{\log_2 k} (1+o(1))\). Thus, for the right matrix, we have \(\|R\|_{1 \to 1} = h = \frac{\log_2 n}{\log_2 k}(1 + o(1))\).

In the worst case, we need to sum about \((k-1) h = \frac{k-1}{\log_2 k} \log_2 n\) nodes from the tree to get a given prefix sum. Thus \(\|L\|_{2 \to \infty} = \sqrt{\frac{k-1}{\log_2 k} \log_2 n} (1 + o(1))\). Then \[\|L\|_{2\to\infty}\|R\|_{1\to 1} = (1+o(1)) \frac{\sqrt{k-1}}{\log_2^{3/2} k}\log_2^{3/2} n , \quad \operatorname{MaxSE}= (1+o(1)) \frac{2(k-1)}{\log_2^{3} k}\log_2^{3} n.\]

The function \(\frac{2(k-1)}{\log_2^{3} k}\) over integer \(k\) has a minimum at \(k=17\) with the value \(\frac{32}{\log_2^{3} 17} \approx 0.4686\).

8.3 Averaged \(k\)-ary trees with subtraction↩︎

In this subsection, we describe a new variant of the \(k\)-ary tree mechanism with subtraction, obtained by averaging two different decompositions of the prefix interval. This method appeared in the implementation code for the paper by Imola, Boninsegna, Keller, Aamand, Chowdhury, and Pagh [4] on private quantile estimation. However, it has not been described in that paper or elsewhere, except in the form of Python code. With the authors’ permission, we provide a description and error analysis of the method.

Fix the value \(k\). Let \(h := \lceil \log_k n \rceil\). A complete \(k\)-ary tree of height \(h\) is built on top of the input vector \(x\). Every node of this tree holds a sum of a segment of the input vector, as in the usual \(k\)-ary tree mechanism.

One can express the prefix sum \(x_1 + \ldots + x_t\) as a suitable linear combination of the node values. Notice that \[[x_1, \ldots, x_t] = \frac{1}{2} \left([x_1, \ldots, x_n] + [x_1, \ldots, x_t] - [x_{t+1}, \ldots, x_n] \right), \label{eq95averaged95trees95subtraction95trick}\tag{13}\] where we mean addition and subtraction of intervals in terms of their indicator functions. Figures 5 and 6 illustrate this equality.

This gives the way to compute the prefix sum \([x_1, \ldots, x_t]\). First, compute \([x_1, \ldots, x_t]\) as in the usual \(k\)-ary tree (red nodes in Figure 5). Then compute \([x_{t+1}, \ldots, x_n]\) similarly (black nodes in Figure 5). Then express \([x_1, \ldots, x_t]\) as in Eq. 13 : the root node plus the red nodes minus the black nodes, all divided by two.

Now let us analyze the corresponding factorization costs. The right matrix is the usual \(k\)-ary tree matrix, with \(\|R\|_{1 \to 1} = h + 1\). Consider the rows of the left matrix. In an easy case when the row index is \(t=n=k^h\), this row has a single “1” corresponding to the root of the tree, and the 2-norm of the row is 1. Every other row has entries in \(\{-1/2, 0, 1/2\}\). Suppose that colored vertices are present in the tree at levels \(\{1, \ldots, h'\}\), where the root is considered level \(0\). Notice that \(h'\) does not have to coincide with \(h\) if \(t\) is divisible by \(k\). Then every level in \(\{1, \ldots, h'-1\}\) contains exactly \(k-1\) colored nodes, and the level \(h'\) contains \(k\) colored nodes. Every row of \(L\) uses red nodes, black nodes, and the root, and thus its 2-norm is at most \(\frac{1}{2} \sqrt{(k-1)(h-1) + 1 + k} = \frac{1}{2} \sqrt{(k-1)h} \cdot (1+o(1))\). This gives us \[\|L\|_{2\to\infty}\|R\|_{1\to 1} = \frac{\sqrt{k-1} \cdot h^{3/2}}{2} (1+o(1)), \quad \operatorname{MaxSE}= \frac{(k-1) \log_2^3 n}{2 \log_2^3 k} (1+o(1)),\] \[\frac{1}{\sqrt{n}} \|L\|_{F}\|R\|_{1\to 1} = \frac{\sqrt{k-1} \cdot h^{3/2}}{2} (1+o(1)), \quad \operatorname{MeanSE}= \frac{(k-1) \log_2^3 n}{2 \log_2^3 k} (1+o(1)).\]

Notice that the values for \(\operatorname{MaxSE}\) and \(\operatorname{MeanSE}\) coincide. The best coefficient is attained at \(k = 17\) and equals \(\frac{8}{\log_2^3 17} \approx 0.1171\).

References↩︎

---

1. Institute of Science and Technology Austria, pavel.arkhipov@ist.ac.at↩︎

2. Institute of Science and Technology Austria, nikita.kalinin@ist.ac.at↩︎

3. We call \(c_2(M)\) and \(c_F(M)\) factorization costs rather than norms, since we do not claim that they satisfy a triangle inequality.↩︎

4. https://github.com/npkalinin/Pure_DP_Continual_Counting_with_MF↩︎

5. We found the matrices too large to compute \(R^{-1}\) symbolically, and therefore rely on bounding the errors introduced by floating-point arithmetic.↩︎

6. https://github.com/npkalinin/Pure_DP_Continual_Counting_with_MF↩︎

7. If the reader is interested in a sharper value for \(C\), numerical analysis shows that the function \(\log \left( (1 + a + b_i) {a + b_i \choose a} \right) / (a^{2/3} b_i^{1/3})\) over positive integers \(a\), \(b_i\) has a global maximum at \(a = 1\), \(b_i = 13\) with value \(2.27407\). Then we can take \(C = 2.275\). This yields the final bound of \(\frac{1}{\sqrt{n}} \|L\|_F \|R\|_{1 \to 1} \geq 0.168 \sqrt{1 - \frac{1}{n}} \log_2^{3/2}(n-1)\).↩︎