---
_id: '14462'
abstract:
- lang: eng
  text: "We study fine-grained error bounds for differentially private algorithms
    for counting under continual observation. Our main insight is that the matrix
    mechanism when using lower-triangular matrices can be used in the continual observation
    model. More specifically, we give an explicit factorization for the counting matrix
    Mcount and upper bound the error explicitly. We also give a fine-grained analysis,
    specifying the exact constant in the upper bound. Our analysis is based on upper
    and lower bounds of the completely bounded norm (cb-norm) of Mcount\r\n. Along
    the way, we improve the best-known bound of 28 years by Mathias (SIAM Journal
    on Matrix Analysis and Applications, 1993) on the cb-norm of Mcount for a large
    range of the dimension of Mcount. Furthermore, we are the first to give concrete
    error bounds for various problems under continual observation such as binary counting,
    maintaining a histogram, releasing an approximately cut-preserving synthetic graph,
    many graph-based statistics, and substring and episode counting. Finally, we note
    that our result can be used to get a fine-grained error bound for non-interactive
    local learning and the first lower bounds on the additive error for (ϵ,δ)-differentially-private
    counting under continual observation. Subsequent to this work, Henzinger et al.
    (SODA, 2023) showed that our factorization also achieves fine-grained mean-squared
    error."
acknowledgement: "This project has received funding from the European Research Council
  (ERC) under the European Union’s Horizon 2020 research and innovation programme
  (Grant agreement No.\r\n101019564 “The Design of Modern Fully Dynamic Data Structures
  (MoDynStruct)” and from the Austrian Science Fund (FWF) project Z 422-N, and project
  “Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional
  funding from the netidee SCIENCE Stiftung, 2020–2024. 2020–2024. JU’s research was
  funded by Decanal Research Grant. A part of this work was done when JU was visiting
  Indian Statistical Institute, Delhi. The authors would like to thank Rajat Bhatia,
  Aleksandar Nikolov, Shanta Laisharam, Vern Paulsen, Ryan Rogers, Abhradeep Thakurta,
  and Sarvagya Upadhyay for useful discussions."
alternative_title:
- PMLR
article_processing_charge: No
arxiv: 1
author:
- first_name: Hendrik
  full_name: Fichtenberger, Hendrik
  last_name: Fichtenberger
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Jalaj
  full_name: Upadhyay, Jalaj
  last_name: Upadhyay
citation:
  ama: 'Fichtenberger H, Henzinger M, Upadhyay J. Constant matters: Fine-grained error
    bound on differentially private continual observation. In: <i>Proceedings of the
    40th International Conference on Machine Learning</i>. Vol 202. ML Research Press;
    2023:10072-10092.'
  apa: 'Fichtenberger, H., Henzinger, M., &#38; Upadhyay, J. (2023). Constant matters:
    Fine-grained error bound on differentially private continual observation. In <i>Proceedings
    of the 40th International Conference on Machine Learning</i> (Vol. 202, pp. 10072–10092).
    Honolulu, Hawaii, HI, United States: ML Research Press.'
  chicago: 'Fichtenberger, Hendrik, Monika Henzinger, and Jalaj Upadhyay. “Constant
    Matters: Fine-Grained Error Bound on Differentially Private Continual Observation.”
    In <i>Proceedings of the 40th International Conference on Machine Learning</i>,
    202:10072–92. ML Research Press, 2023.'
  ieee: 'H. Fichtenberger, M. Henzinger, and J. Upadhyay, “Constant matters: Fine-grained
    error bound on differentially private continual observation,” in <i>Proceedings
    of the 40th International Conference on Machine Learning</i>, Honolulu, Hawaii,
    HI, United States, 2023, vol. 202, pp. 10072–10092.'
  ista: 'Fichtenberger H, Henzinger M, Upadhyay J. 2023. Constant matters: Fine-grained
    error bound on differentially private continual observation. Proceedings of the
    40th International Conference on Machine Learning. ICML: International Conference
    on Machine Learning, PMLR, vol. 202, 10072–10092.'
  mla: 'Fichtenberger, Hendrik, et al. “Constant Matters: Fine-Grained Error Bound
    on Differentially Private Continual Observation.” <i>Proceedings of the 40th International
    Conference on Machine Learning</i>, vol. 202, ML Research Press, 2023, pp. 10072–92.'
  short: H. Fichtenberger, M. Henzinger, J. Upadhyay, in:, Proceedings of the 40th
    International Conference on Machine Learning, ML Research Press, 2023, pp. 10072–10092.
conference:
  end_date: 2023-07-29
  location: Honolulu, Hawaii, HI, United States
  name: 'ICML: International Conference on Machine Learning'
  start_date: 2023-07-23
corr_author: '1'
date_created: 2023-10-29T23:01:17Z
date_published: 2023-07-30T00:00:00Z
date_updated: 2025-05-19T10:59:58Z
day: '30'
department:
- _id: MoHe
ec_funded: 1
external_id:
  arxiv:
  - '2202.11205'
intvolume: '       202'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://proceedings.mlr.press/v202/fichtenberger23a/fichtenberger23a.pdf
month: '07'
oa: 1
oa_version: Published Version
page: 10072-10092
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
  call_identifier: H2020
  grant_number: '101019564'
  name: The design and evaluation of modern fully dynamic data structures
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
  grant_number: Z00422
  name: Efficient algorithms
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
  grant_number: P33775
  name: Fast Algorithms for a Reactive Network Layer
publication: Proceedings of the 40th International Conference on Machine Learning
publication_identifier:
  eissn:
  - 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Constant matters: Fine-grained error bound on differentially private continual
  observation'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 202
year: '2023'
...