Research map / Learning theory and algorithms / Sample complexity
Constant Matters: Fine-grained Error Bound on Differentially Private Continual Observation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Explicit lower-triangular factorization of M_count (Algorithm 1) instead of binary mechanism | continual binary counting · continual counting, T up to 244 | cb-norm upper bound: ≈0.35 improvement over Mathias bound for 50≤T≤244 | Helped |
| Use lower-triangular factorization so matrix mechanism works in continual release (output at t uses only first t rows) | matrix mechanism for continual counting · continual counting | validity of continual release | Helped |
| Replace binary mechanism with the factorization mechanism | binary counting l_inf error · continual counting | l_inf additive error: binary mechanism suboptimal by factor π log2(e) | Helped |
| Smooth, monotone error (factorization) vs non-smooth binary mechanism error | continual counting output error · continual counting | smoothness of additive error over time | Helped |
Closest papers by meaning
- Private Continual Counting of Unbounded Streams (NeurIPS 2025 · similarity 0.91)
- Continual Counting with Gradual Privacy Expiration (NeurIPS 2024 · similarity 0.85)
- Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model (ICML 2025 · similarity 0.84)
- Differentially Private Quantiles with Smaller Error (NeurIPS 2025 · similarity 0.83)
- MaxSketch: Robust Distinct Counting in Streams via Random Projections (NeurIPS 2026 · similarity 0.83)
- A Statistical Theory of Regularization-Based Continual Learning (ICML 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.