Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.28703
curl -X POST /api/v1/records/arxiv/2607.28703/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.28703/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'