Pith. sign in

REVIEW 2 minor 22 references

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

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

For the pure-DP Laplace matrix mechanism on prefix sums, the paper claims optimized maximum and mean squared errors of order Θ(log^3 n / ε^2) for arbitrary real factorizations, matching the best-known upper bound.

T0 review reviewed 2026-08-03 challenge →

load-bearing objection 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.

arxiv 2607.28703 v1 pith:P5MXZ2JU submitted 2026-07-30 cs.CR cs.DSmath.FA

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

Awnon Bhowmik , Mahmudul Hasan This is my paper
classification cs.CR cs.DSmath.FA MSC 15A2347B10
keywords continual countingdifferential privacymatrix factorizationLaplace mechanismprefix-sum matrixfactorization costsp-nuclearityapproximation numbers
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The prefix-sum matrix is the workload that returns every running total of a length-n stream. The paper tries to establish that any way of writing this matrix as a product of two real matrices—negative entries, dense factors, rectangular shapes, any internal dimension—must pay a factorization cost of order (log n)^{3/2}, and that a dyadic interval construction achieves the same order. If correct, this fixes the optimized mean and maximum per-coordinate squared errors of the pure-ε-differentially-private Laplace matrix mechanism for continual counting at Θ(ε^{-2} log^3 n), closing a logarithmic gap inside this mechanism class. The proof's engine is a p-nuclear obstruction at exponent p=2/3: a geometric width estimate for suffix vectors, converted through an approximation-space argument, turns low-rank approximation into a harmonic lower bound. The paper also evaluates the p-nuclear power of the prefix matrix for every fixed 0

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

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,

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.

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.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

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.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 2 minor

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)
  1. [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.
  2. [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

0 steps flagged

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.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

The central proof relies on classical inequalities (Bessel, Hölder, Pietsch transformation) and introduces no new entities or fitted parameters. However, the definition of D_k as a sum of squared distances is incompatible with its use as the nuclear-norm approximation number, which is a sum of distances; this is an internal inconsistency rather than an external assumption.

axioms (4)
  • standard math Bessel's inequality for orthonormal vectors in Euclidean space
    Used in Lemma A.1 to bound the sum of squared distances of orthonormal interval vectors to a k-dimensional subspace.
  • standard math Pietsch Transformation Theorem / Hinrichs–Pietsch Theorem 7.1 (operator-ideal inclusion)
    Cited in Remark B.1 as the classical conversion from p-summable rank-one coefficients to a weighted approximation-space profile. The paper relies on this inclusion to lower-bound n_p by weighted D_k, but D_k must be the nuclear-norm approximation number, which is a sum of distances, not sums of squares as defined.
  • standard math Hölder's inequality
    Used in Theorem C.2 to transfer the p-nuclear lower bound to the factorization costs.
  • domain assumption The 'factorization contract' of Arkhipov–Kalinin v1 (that the arbitrary-factor lower bound was open)
    The paper's framing assumes the cited v1 really states the extension is open; if the reference is mischaracterized, the novelty framing changes. Not load-bearing for the mathematical bounds themselves.

reviewed 2026-08-03 · how reviews work

0 comments
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}
}
Share X Bluesky LinkedIn Reddit HN
abstract

Let \(T_n\) be the lower-triangular prefix-sum matrix and let \(\cfrob(T_n)\) and \(\ctwo(T_n)\) be the factorization costs that govern mean and maximum per-coordinate squared error of the Laplace matrix mechanism under pure \(\eps\)-differential privacy, for \(\eps>0\). We prove \(\cfrob(T_n),\ctwo(T_n)=\Theta\bigl((\log(n+1))^{3/2}\bigr)\) with no sign, sparsity, or squareness restriction and with arbitrary finite inner dimension. Consequently, within the pure-\(\eps\)-DP matrix-mechanism class the optimized maximum and mean squared errors are both \(\Theta(\eps^{-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 \(\nucpow_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-\(\eps\)-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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

22 extracted references · 11 canonical work pages · 3 internal anchors

  1. [1]

    J. D. Andersson, R. Pagh, T. A. Steiner, and S. Torkamani,Count on Your Elders: Laplace vs Gaussian Noise, 6th Symposium on Foundations of Responsible Computing (FORC), LIPIcs 329, 10:1–10:24, 2025. https://doi.org/10.4230/LIPIcs.FORC.20 25.10

    work page doi:10.4230/lipics.forc.20 2025

  2. [2]

    Improved Error Bounds for Pure Differentially Private Continual Counting via Matrix Factorization

    P. Arkhipov and N. P. Kalinin,Improved Error Bounds for Pure Differentially Private Continual Counting via Matrix Factorization, arXiv:2607.08963v1, 2026. DOI: https://doi.org/10.48550/arXiv.2607.08963; https://arxiv.org/abs/2607.08963 v1

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2607.08963 2026

  3. [3]

    The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting

    K. Bairaktari and K. G. Larsen,The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting, arXiv:2607.00876v2, 2026. DOI: https://doi.org/10.48550/arXiv.2607.00876; https://arxiv.org/abs/2607.00876v2

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2607.00876 2026

  4. [4]

    T.-H. H. Chan, E. Shi, and D. Song,Private and Continual Release of Statistics, ACM Transactions on Information and System Security 14 (2011), No. 3, Article 26. https://doi.org/10.1145/2043621.2043626

    arXiv 2011

  5. [5]

    Dwork, F

    C. Dwork, F. McSherry, K. Nissim, and A. Smith,Calibrating Noise to Sensitivity in Private Data Analysis, Theory of Cryptography Conference (TCC), 2006, 265–284. https://doi.org/10.1007/11681878_14

    doi:10.1007/11681878_14 2006

  6. [6]

    Denisov, H

    S. Denisov, H. B. McMahan, J. Rush, A. Smith, and A. G. Thakurta,Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams, Advances in Neural Information Processing Systems 35 (NeurIPS), 2022, 5910–5924. https://doi.org/10.52202/068431-0428

    work page doi:10.52202/068431-0428 2022

  7. [7]

    Dwork, M

    C. Dwork, M. Naor, T. Pitassi, and G. N. Rothblum,Differential Privacy under Continual Observation, Symposium on Theory of Computing (STOC), 2010, 715–724. https://doi.org/10.1145/1806689.1806787

    arXiv 2010

  8. [8]

    Edmonds, A

    A. Edmonds, A. Nikolov, and J. Ullman,The Power of Factorization Mechanisms in Local and Central Differential Privacy, Symposium on Theory of Computing (STOC), 2020, 425–438. https://doi.org/10.1145/3357713.3384297

    arXiv 2020

  9. [9]

    C. J. Fewster, I. Ojima, and M. Porrmann, p-Nuclearity in a New Perspective, Letters in Mathematical Physics 73 (2005), 1–15; arXiv:math-ph/0412027v3. https://doi.org/10.1007/s11005-005-8445-y

    Pith/arXiv arXiv 2005

  10. [10]

    Fichtenberger, M

    H. Fichtenberger, M. Henzinger, and J. Upadhyay,Constant Matters: Fine-Grained Error Bound on Differentially Private Continual Observation, International Conference on Machine Learning (ICML), PMLR 202, 10072–10092, 2023. https: //proceedings.mlr.press/v202/fichtenberger23a.html

    2023

  11. [11]

    Henzinger, N

    M. Henzinger, N. P. Kalinin, and J. Upadhyay,Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting, 7th Symposium on Foundations of Responsible Computing (FORC), LIPIcs 368, 5:1, 2026; full version arXiv:2509.14334v1. https://doi.org/10.4230/LIPIcs.FORC.2026.5

    arXiv 2026

  12. [12]

    Henzinger, J

    M. Henzinger, J. Upadhyay, and S. Upadhyay,Almost Tight Error Bounds on Differentially Private Continual Counting, Symposium on Discrete Algorithms (SODA), 2023, 5003–5039; arXiv:2211.05006v2. https://doi.org/10.1137/1.9781611977 554.ch183

    Pith/arXiv arXiv 2023

  13. [13]

    Hinrichs and A

    A. Hinrichs and A. Pietsch, p-Nuclear Operators in the Sense of Grothendieck, Mathematische Nachrichten 283 (2010), No. 2, 232–261. https://doi.org/10.1002/mana.200910128

    doi:10.1002/mana.200910128 2010

  14. [14]

    Kwapie´n and A

    S. Kwapie´n and A. Pełczy´nski,The Main Triangle Projection in Matrix Spaces and Its Applications, Studia Mathematica 34 (1970), 43–67. https://doi.org/10.4064/sm-34-1-43-67

    work page doi:10.4064/sm-34-1-43-67 1970

  15. [15]

    Lapresté,Opérateurs sommants et factorisations

    J.-T. Lapresté,Opérateurs sommants et factorisations. À travers les espaces Lp, Studia Mathematica 57 (1976), 47–83. https://doi.org/10.4064/sm-57-1-47-83

    work page doi:10.4064/sm-57-1-47-83 1976

  16. [16]

    C. Li, G. Miklau, M. Hay, A. McGregor, and V . Rastogi,The Matrix Mechanism: Optimizing Linear Counting Queries under Differential Privacy, The VLDB Journal 24 (2015), No. 6, 757–781. https://doi.org/10.1007/s00778-015-0398-x

    work page doi:10.1007/s00778-015-0398-x 2015

  17. [17]

    Matoušek, A

    J. Matoušek, A. Nikolov, and K. Talwar,Factorization Norms and Hereditary Discrepancy, International Mathematics Research Notices 2020, No. 3, 751–780. https://doi.org/10.1093/imrn/rny033

    doi:10.1093/imrn/rny033 2020

  18. [18]

    Mathias,The Hadamard Operator Norm of a Circulant and Applications, SIAM Journal on Matrix Analysis and Applications 14 (1993), No

    R. Mathias,The Hadamard Operator Norm of a Circulant and Applications, SIAM Journal on Matrix Analysis and Applications 14 (1993), No. 4, 1152–1167. https://doi.org/10.1137/0614080

    work page doi:10.1137/0614080 1993

  19. [19]

    Pietsch,Approximation Spaces, Journal of Approximation Theory 32 (1981), 115–134

    A. Pietsch,Approximation Spaces, Journal of Approximation Theory 32 (1981), 115–134. https://doi.org/10.1016/0021-904 5(81)90109-X

    work page doi:10.1016/0021-904 1981

  20. [20]

    Pietsch and J

    A. Pietsch and J. Wenzel,Orthonormal Systems and Banach Space Geometry, Encyclopedia of Mathematics and its Applica- tions 70, Cambridge University Press, 1998. https://doi.org/10.1017/CBO9780511526145

    work page doi:10.1017/cbo9780511526145 1998

  21. [21]

    Reinov,Approximation Properties Associated with Quasi-Normed Operator Ideals of (r, p, q)-Nuclear Operators, St

    O. Reinov,Approximation Properties Associated with Quasi-Normed Operator Ideals of (r, p, q)-Nuclear Operators, St. Petersburg Mathematical Society preprint 2017-08, 2017. https://www.mathsoc.spb.ru/preprint/2017/17-08.pdf

    2017

  22. [22]

    Uniformly convex operators and martingale type

    J. Wenzel,Uniformly Convex Operators and Martingale Type, arXiv:math/0202073v1, 2002. DOI: https://doi.org/10.48550/a rXiv.math/0202073; https://arxiv.org/abs/math/0202073 17

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.math/0202073 2002

This paper was first reviewed by deepseek-v4-flash on August 3, 2026.