REVIEW 2 minor
Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting
T0 review · 0 major / 2 minor · reviewed 2026-08-03 · deepseek-v4-flash
Pith's one-line read This paper proves that every real factorization of the prefix-sum matrix—signed, dense, rectangular, arbitrary inner dimension—has cost Θ((log n)^{3/2}) under the two squared-error objectives, and hence that the optimized pure-ε-DP Laplace
desk verdict A promising attack on the arbitrary-factor continual-counting lower bound, but the central quantity is misdefined: D_k is a sum of squared distances while the proofs and the nuclear-norm identification use a sum of distances, so the main theorem is not established as written. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Aggregate column width D_k(A)—the least total squared Euclidean distance of the matrix columns to a k-dimensional subspace—is the geometric input. The p-nuclear power ν_p(A)^p, the infimum over exact rank-one decompositions of Σ(‖u_q‖_2‖v_q‖_1)^p, treats the matrix as an operator from ℓ∞ to ℓ2 and is the analytic obstruction. An approximation-space conversion (with an explicit constant) bounds ν_p below by a weighted sum Σ k^{-p}D_k(A)^p; for the prefix matrix this sum is harmonic exactly at p=2/3. An exponent-transfer inequality shifts the resulting nuclear lower bound to the two factorization costs, and a dyadic interval factorization—each prefix decomposed into at most O(log n) intervals,
What would settle it
Compute, for n=64, D_1(T_n) = min over one-dimensional subspaces of the sum of squared distances of the n suffix-indicator columns, and a_2(T_n|N) = min over one-dimensional subspaces of the sum of plain distances of the same columns, as the paper's ν_1 norm defines it. If the ratio a_2/D_1 grows like n^{1/2} (so the two quantities have different orders, Θ(n^{3/2}) vs Θ(n^2)), then eq. (B.2) cannot hold as stated and the lower-bound proof needs a different step.
Extended reading notes
Core claim
In the paper's own terms, the discovery is a Θ((log(n+1))^{3/2}) two-sided bound on the factorization costs c_F(T_n) and c_2(T_n) for the lower-triangular prefix-sum matrix: the infimum over factorizations T_n=LR of (normalized Frobenius row energy)·(largest ℓ1 column norm of R), and the same with maximum-row energy in place of normalized Frobenius. No sign, sparsity, squareness, or finite-inner-dimension restriction is used. Because those costs square into the Laplace-mechanism error formulas, the optimized MaxSE and MeanSE are both Θ(ε^{-2} log^3(n+1)). The lower-bound chain: aggregate column widths D_k(T_n)≍n^{3/2}k^{-1/2} for k≤n/16; a conversion from p-summable rank-one decompositions t
Load-bearing premise
The load-bearing premise is the Appendix B equality between the squared-distance width D_k(T_n) and the nuclear-norm approximation number; because one side sums squared column distances and the other sums plain distances, the identification is not supported by the definitions as written, and without it the lower-bound chain has no bridge.
Editorial extensions
If this is right
- Arbitrary real factorizations are asymptotically no better than known constructions: the extra sqrt(log n) over the classical log n baseline comes from the mixed-norm gap between ℓ1 and ℓ2 column sensitivity, and it is unavoidable inside the matrix-mechanism class.
- Inside the pure-ε-DP Laplace matrix-mechanism class, both optimized MaxSE and MeanSE are Θ(ε^{-2} log^3(n+1)); the earlier uncertainty about improving the O(log^3 n) upper bound is resolved in that class.
- The p-nuclear power ν_p(T_n) is Θ(n) for p<2/3, Θ(n log n) at p=2/3, and Θ(n^{3p/2}) for p>2/3, with constants diverging as p→2/3.
- The lower bound applies even if the inner dimension is countable (as a cost inequality), and it covers signed, dense, rectangular factors.
- The theorem is confined to matrix mechanisms and to coordinatewise mean/max squared error; the expected-maximum-across-coordinates criterion is a different functional and is left open.
Reading between the lines
- Editorial inference: a reader should locate the step that identifies the squared-distance width D_k with a nuclear-norm approximation number; the former sums squared column distances and the latter sums plain distances, so the identification as printed in Appendix B is not automatic and the lower-bound argument depends on it.
- Editorial inference: if a corrected bridge is found, the same width-plus-nuclear template could transfer to other lower-triangular workloads, where the critical exponent may shift with the column geometry.
- Editorial inference: since the p-nuclear constants diverge near p=2/3, finite-n computations of optimized factorization cost may approach the log^{3/2} order slowly, so numerical tests on moderate n could be misleading.
- Editorial inference: the paper's own scope boundary implies that any mechanism outside the matrix class could still achieve lower error; the Θ(ε^{-2} log^3 n) order is a statement about factorization mechanisms, not about all pure-DP continual counting.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the two factorization costs c_F(T_n) and c_2(T_n) of Arkhipov–Kalinin, which govern the mean and maximum per-coordinate squared error of the pure-ε-DP Laplace matrix mechanism for the prefix-sum workload T_n. Theorem 1.1 claims that both costs are Θ((log(n+1))^{3/2}) for arbitrary real factors of arbitrary finite inner dimension, with matching explicit-constant bounds; Corollary 1.2 turns this into Θ(ε^{-2} log^3(n+1)) for the two optimized squared-error criteria. The lower bound is built from an aggregate column-width estimate D_k(T_n) = Θ(n^{3/2} k^{-1/2}) in the range k ≤ n/16, a quantitative approximation-space conversion from p-summable rank-one coefficients to weighted nuclear-norm approximation numbers, a critical p = 2/3 evaluation producing an Ω(n log n) nuclear-power lower bound, and a Hölder transfer to the factorization costs. A Fenwick interval factorization supplies the matching upper bounds and also yields the fixed-p phase diagram for n_p(T_n).
Significance. If the claimed order is correct, the paper resolves the arbitrary-real-factor extension stated as open in Arkhipov–Kalinin v1 for the two matrix factorization costs, and sharpens the pure-DP matrix-mechanism lower bound from the classical Ω(log n) baseline to the matching Ω(log^{3/2} n) order. The proof is essentially self-contained: it relies only on classical cited results (Bessel, Hölder, Pietsch/Hinrichs–Pietsch) and supplies explicit constants for the new finite-dimensional steps. The paper is also careful about its boundary: it claims results only for the Laplace matrix-mechanism class and the coordinatewise/mean squared-error functionals, not for general continual mechanisms or expected-maximum error, and it is explicit about which steps are classical. No parameter fitting or circular use of the authors' prior results is involved.
minor comments (2)
- [Definition 3.10 and (3.18)] The notation D_k(A) = inf_E Σ_j dist(a_j,E)_2 is easy to misread as a sum of squared distances, because the subscript 2 can look like a square in plain text. The intended reading is consistent with (3.18), (B.2), and the width estimates, which use sums of unsquared ℓ2 distances. I strongly recommend replacing the notation by d_E(a) = ||a - P_E a||_2 and D_k(A) = inf_E Σ_j d_E(a_j), or adding an explicit sentence that D_k is not a sum of squares. This will prevent a genuine misreading of the central proof chain.
- [Appendix A, Lemma A.1] The proof mixes expressions such as dist(y_ℓ,E)_2^2 and dist(x_ℓ,E)_2. A consistent convention—using d_E for the unsquared distance and d_E^2 for its square—would make the threshold argument in (A.7)–(A.9) easier to follow and would again remove any ambiguity about Definition 3.10.
Circularity Check
No circularity: the lower bound is derived from a direct width estimate plus an external classical approximation-space theorem, and the upper bound from an explicit Fenwick factorization.
full rationale
The derivation chain is not circular. Theorem 1.1's lower bound runs through Lemma A.1 (a self-contained width estimate for the suffix-indicator columns of T_n), the classical Pietsch / Hinrichs–Pietsch inclusion explicitly attributed in Remark B.1, and Hölder's inequality in Theorem C.2; no parameter is fitted to the target costs, and no claimed prediction is a renamed input. The upper bound is constructed explicitly via the Fenwick interval factorization in Lemma D.1, with direct bounds on ||R||_{1->1}, ||L||_{2->infty}, and ||L||_F. Citations to Arkhipov–Kalinin define the problem contract and record their open problem; they are not used as evidence for the new lower bound. The proof is otherwise self-contained, and there is no load-bearing self-citation. The reviewer's concern about Definition 3.10 versus equation (B.2) — that D_k sums squared distances while a_{k+1}(A|N) is a sum of unsquared column norms — is a potential mathematical defect in the proof, not a circularity: it does not make the conclusion equivalent by construction to an input or fitted parameter. Whether (B.2) is correct is a validity issue separate from circularity, so no circular step is identified.
Assumptions & free parameters
assumptions (4)
- standard math Bessel's inequality for orthonormal vectors in Euclidean space
- standard math Pietsch Transformation Theorem / Hinrichs–Pietsch Theorem 7.1 (operator-ideal inclusion)
- standard math Hölder's inequality
- domain assumption The 'factorization contract' of Arkhipov–Kalinin v1 (that the arbitrary-factor lower bound was open)
Cite this review
Pith. "Pith review of Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting." pith.science (2026). https://pith.science/paper/P5MXZ2JU
@misc{pith2026260728703,
author = {Pith},
title = {Pith review of: Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting},
year = {2026},
howpublished = {\url{https://pith.science/paper/P5MXZ2JU}},
note = {Machine review of arXiv:2607.28703}
}
abstract
Let $T_n$ be the lower-triangular prefix-sum matrix and let $c_{\mathrm{F}}(T_n)$ and $c_2(T_n)$ be the factorization costs that govern the mean and maximum per-coordinate squared error of the Laplace matrix mechanism under pure $\varepsilon$-differential privacy, for $\varepsilon>0$. We prove $c_{\mathrm{F}}(T_n),c_2(T_n)=\Theta((\log(n+1))^{3/2})$ with no sign, sparsity, or squareness restriction and with arbitrary finite inner dimension. Consequently, within the pure-$\varepsilon$-DP matrix-mechanism class, the optimized maximum and mean squared errors are both $\Theta(\varepsilon^{-2}\log^3(n+1))$. Under the factorization contract of Arkhipov and Kalinin (arXiv:2607.08963v1), who prove the matching lower order for factors with entries in $\{0,1\}$ and state the arbitrary-factor extension as open, the theorem below establishes the order for arbitrary real factors. The lower bound runs through a $p$-nuclear obstruction: an aggregate column-width estimate $D_k(T_n)\asymp n^{3/2}k^{-1/2}$, valid in the low-rank range $1\leq k\leq n/16$, for the prefix chain, fed into the classical approximation-space conversion of Pietsch and Hinrichs--Pietsch, becomes harmonic at the critical exponent $p=2/3$, and H\"older's inequality transfers it to both factorization costs. The same computation determines $\mathfrak{n}_p(T_n)$ for each fixed $0<p<1$: order $n$ below $2/3$, $n\log n$ at $2/3$, and $n^{3p/2}$ above. A Fenwick interval factorization supplies matching upper bounds. The claims are confined to pure-$\varepsilon$-DP Laplace matrix mechanisms and the two stated squared-error criteria; they do not cover non-matrix continual mechanisms, approximate-DP sensitivity, or expected maxima across coordinates.
Reviewed August 3, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.