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

• URL: http://arxiv.org/abs/2607.28703v2
• Date: Thu, 06 Aug 2026 12:24:59 GMT
• Title: Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting
• Abstract summary: We prove $c_mathrmF(T_n),c_2(T_n)=(log(n+1)3/2)$ with no sign, sparsity, or squareness restriction.<n>Within the pure-$varepsilon$-DP matrix-mechanism class, the optimized maximum and mean squared errors are both $(varepsilon-2log3(n+1))$.
• Score: 0.9023847175654603
• License: http://creativecommons.org/licenses/by/4.0/
• 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)=Θ((\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 $Θ(\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ölder'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.

Related papers

• Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
  For singleton queries, Chamfer becomes maximum inner product similarity (MAX-IP)<n>For every fixed $in(0,1)$, there are constants $A_,c_>0$.<n>Unit-sphere MAX-IP matrix is an exact two-valued affine image of the DNF pattern matrix with gap of at least $8$.
  arXiv  Detail & Related papers  (2026-07-22T17:27:20Z)
• Module Lattice Security (Part III): Structured CVP Distance on the Log-Unit Lattice [1.0152838128195467]
  We show that the $L2$ CVP distance from a random short ring element to the log-unit lattice converges to $frac2sqrt6sqrtn$ as $n=2k-1toinfty$.<n>For the $Linfty$ norm, the maximum over $n$ sub-Gaussian coordinates yields $O(sqrtlog n)$ which translates into a sub-polynomial approximation factor for the Short Generator Problem.
  arXiv  Detail & Related papers  (2026-05-17T12:00:59Z)
• Tikhonov-regularised projected gradient flow for equality-constrained bilinear quantum control [0.0]
  We study a projection-type gradient flow for equality-constrained control objective on $mathcalH=L(0,T;mathbbR)$.<n>We replace $$ with $_varepsilon:=+varepsilon2I$ and prove: (i) an exact spectral identity giving $(_varepsilon)=(_min2+varepsilon2)$; (ii) objective monotonicity $mathrmdJ/
  arXiv  Detail & Related papers  (2026-04-29T12:53:58Z)
• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  We study entrywise scalar quantization of two matrices prior to multiplication.<n>We obtain a closed-form optimal point density [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X,, and prove a correlation-driven phase transition.
  arXiv  Detail & Related papers  (2026-03-20T01:53:44Z)
• Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
  We introduce a general framework for constrained subspace approximation.<n>We show it provides new algorithms for partition-constrained subspace approximation with applications to $k$-means clustering, and projected non-negative matrix factorization.
  arXiv  Detail & Related papers  (2025-04-29T15:56:48Z)
• Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems [2.3721580767877257]
  We propose an algorithm for solving non-strongly concave minimax problems.<n>The proposed algorithm is proved to be upper-order stationary points within $tell.<n>ell.<n>$.<n>$.<n>$.<n>$.<n>$.<n>$.<n>$.<n>$.<n>$.<n>$.<n>$.<n>$.<n>$.<n>$.<n>$.<n>$.<n>$
  arXiv  Detail & Related papers  (2024-11-24T09:46:36Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  We study the problem of residual error estimation for matrix and vector norms using a linear sketch. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
  arXiv  Detail & Related papers  (2024-08-16T02:33:07Z)
• Convergence of Alternating Gradient Descent for Matrix Factorization [5.439020425819001]
  We consider alternating gradient descent (AGD) with fixed step size applied to the asymmetric matrix factorization objective. We show that, for a rank-$r$ matrix $mathbfA in mathbbRm times n$, smoothness $C$ in the complexity $T$ to be an absolute constant.
  arXiv  Detail & Related papers  (2023-05-11T16:07:47Z)
• Krylov Methods are (nearly) Optimal for Low-Rank Approximation [8.017116107657206]
  We show that any algorithm requires $Omegaleft(log(n)/varepsilon1/2right)$ matrix-vector products, exactly matching the upper bound obtained by Krylov methods. Our lower bound addresses Open Question 1WooWoo14, providing evidence for the lack of progress on algorithms for Spectral LRA.
  arXiv  Detail & Related papers  (2023-04-06T16:15:19Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  "Statistical-computational gaps" occur in many statistical inference tasks. We consider a model for random order-3 decomposition where one component is slightly larger in norm than the rest. We show that tensor entries can accurately estimate the largest component when $ll n3/2$ but fail to do so when $rgg n3/2$.
  arXiv  Detail & Related papers  (2022-11-10T00:40:37Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  We consider online statistical inference of constrained nonlinear optimization problems.<n>We apply the Sequential Quadratic Programming (StoSQP) method to solve these problems.
  arXiv  Detail & Related papers  (2022-05-27T00:34:03Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• Constant matters: Fine-grained Complexity of Differentially Private Continual Observation [10.624505781812385]
  We study fine-grained error bounds for differentially private algorithms for counting continual observation. We are the first to give concrete error bounds for various problems under continual observation.
  arXiv  Detail & Related papers  (2022-02-23T11:50:20Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
  arXiv  Detail & Related papers  (2021-09-06T14:21:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.