English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study fine-grained error bounds for differentially private algorithms forcounting under continual observation. Our main insight is that the matrixmechanism when using lower-triangular matrices can be used in the continualobservation model. More specifically, we give an explicit factorization for thecounting matrix $M_\mathsf{count}$ and upper bound the error explicitly. Wealso give a fine-grained analysis, specifying the exact constant in the upperbound. Our analysis is based on upper and lower bounds of the {\em completelybounded norm} (cb-norm) of $M_\mathsf{count}$. Along the way, we improve thebest-known bound of 28 years by Mathias (SIAM Journal on Matrix Analysis andApplications, 1993) on the cb-norm of $M_\mathsf{count}$ for a large range ofthe dimension of $M_\mathsf{count}$. Furthermore, we are the first to giveconcrete error bounds for various problems under continual observation such asbinary counting, maintaining a histogram, releasing an approximatelycut-preserving synthetic graph, many graph-based statistics, and substring andepisode counting. Finally, we note that our result can be used to get afine-grained error bound for non-interactive local learning {and the firstlower bounds on the additive error for$(\epsilon,\delta)$-differentially-private counting under continualobservation.} Subsequent to this work, Henzinger et al. (SODA2023) showed thatour factorization also achieves fine-grained mean-squared error.

Constant matters: Fine-grained Complexity of Differentially Private Continual Observation