---
OA_place: repository
OA_type: green
_id: '19038'
abstract:
- lang: eng
text: Differentially private weighted prefix sum under continual observation is
a crucial component in the production-level deployment of private next-word prediction
for Gboard, which, according to Google, has over a billion users. More specifically,
Google uses a differentially private mechanism to sum weighted gradients in its
private follow-the-regularized leader algorithm. Apart from efficiency, the additive
error of the private mechanism is crucial as multiplied with the square root of
the model’s dimension d (with d ranging up to 10 trillion, for example, Switch
Transformers or M6-10T), it determines the accuracy of the learning system. So,
any improvement in leading constant matters significantly in practice. In this
paper, we show a novel connection between mechanisms for continual weighted prefix
sum and a concept in representation theory known as the group matrix introduced
in correspondence between Dedekind and Frobenius (Sitzungsber. Preuss. Akad. Wiss.
Berlin, 1897) and generalized by Schur (Journal für die reine und angewandte Mathematik,
1904). To the best of our knowledge, this is the first application of group algebra
in the analysis of differentially private algorithms. Using this connection, we
analyze a class of matrix norms known as factorization norms that give upper and
lower bounds for the additive error under general ℓp-norms of the matrix mechanism.
This allows us to give 1. the first efficient factorization that matches the best-known
non-constructive upper bound on the factorization norm by Mathias (SIAM Journal
of Matrix Analysis and Applications, 1993) for the matrix used in Google’s deployment,
and also improves on the previous best-known constructive bound of Fichtenberger,
Henzinger, and Upadhyay (ICML 2023) and Henzinger, Upadhyay, and Upadhyay (SODA
2023); thereby, partially resolving an open question in operator theory, 2. the
first upper bound on the additive error for a large class of weight functions
for weighted prefix sum problems, including the sliding window matrix (Bolot,
Fawaz, Muthukrishnan, Nikolov, and Taft (ICDT 2013). We also improve the bound
on factorizing the striped matrix used for outputting a synthetic graph that approximates
all cuts (Fichtenberger, Henzinger, and Upadhyay (ICML 2023)); 3. a general improved
upper bound on the factorization norms that depend on algebraic properties of
the weighted sum matrices and that applies to a more general class of weighting
functions than the ones considered in Henzinger, Upadhyay, and Upadhyay (SODA
2024). Using the known connection between these factorization norms and the ℓp-error
of continual weighted sum, we give an upper bound on the ℓp-error for the continual
weighted sum problem for p ≥ 2.
acknowledgement: 'Monika Henzinger: This project has received funding from the European
Research Council(ERC) under the European Union’s Horizon 2020 research and innovation
programme (Grantagreement No. 101019564) and the Austrian Science Fund (FWF) grant
DOI 10.55776/Z422,grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional
funding from the netidee SCIENCEStiftung, 2020–2024.Jalaj Upadhyay’s research was
funded by the Rutgers Decanal Grant no. 302918 and an unrestricted giftfrom Google.
This work was done in part while visiting the Institute of Science and Technology
Austria (ISTA).The authors would like to thank Sarvagya Upadhyay for the initial
discussion and feedback on the early draft of the paper. The authors would like
to thank the anonymous reviewers, Brendan McMahan and Abhradeep Thakurta for the
discussions that helped improve the presentation of the final version of the paper.'
article_processing_charge: No
arxiv: 1
author:
- 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: 'Henzinger M, Upadhyay J. Improved differentially private continual observation
using group algebra. In: Proceedings of the 2025 Annual ACM-SIAM Symposium
on Discrete Algorithms. Vol 5. Association for Computing Machinery; 2025:2951-2970.
doi:10.1137/1.9781611978322.95'
apa: 'Henzinger, M., & Upadhyay, J. (2025). Improved differentially private
continual observation using group algebra. In Proceedings of the 2025 Annual
ACM-SIAM Symposium on Discrete Algorithms (Vol. 5, pp. 2951–2970). New Orleans,
LA, United States: Association for Computing Machinery. https://doi.org/10.1137/1.9781611978322.95'
chicago: Henzinger, Monika, and Jalaj Upadhyay. “Improved Differentially Private
Continual Observation Using Group Algebra.” In Proceedings of the 2025 Annual
ACM-SIAM Symposium on Discrete Algorithms, 5:2951–70. Association for Computing
Machinery, 2025. https://doi.org/10.1137/1.9781611978322.95.
ieee: M. Henzinger and J. Upadhyay, “Improved differentially private continual observation
using group algebra,” in Proceedings of the 2025 Annual ACM-SIAM Symposium
on Discrete Algorithms, New Orleans, LA, United States, 2025, vol. 5, pp.
2951–2970.
ista: 'Henzinger M, Upadhyay J. 2025. Improved differentially private continual
observation using group algebra. Proceedings of the 2025 Annual ACM-SIAM Symposium
on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 5, 2951–2970.'
mla: Henzinger, Monika, and Jalaj Upadhyay. “Improved Differentially Private Continual
Observation Using Group Algebra.” Proceedings of the 2025 Annual ACM-SIAM Symposium
on Discrete Algorithms, vol. 5, Association for Computing Machinery, 2025,
pp. 2951–70, doi:10.1137/1.9781611978322.95.
short: M. Henzinger, J. Upadhyay, in:, Proceedings of the 2025 Annual ACM-SIAM Symposium
on Discrete Algorithms, Association for Computing Machinery, 2025, pp. 2951–2970.
conference:
end_date: 2025-01-15
location: New Orleans, LA, United States
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2025-01-12
date_created: 2025-02-17T09:31:03Z
date_published: 2025-01-20T00:00:00Z
date_updated: 2025-04-14T13:50:49Z
day: '20'
department:
- _id: MoHe
doi: 10.1137/1.9781611978322.95
ec_funded: 1
external_id:
arxiv:
- '2412.02840'
intvolume: ' 5'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2412.02840
month: '01'
oa: 1
oa_version: Preprint
page: 2951 - 2970
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: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: P33775
name: Fast Algorithms for a Reactive Network Layer
publication: Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
isbn:
- 979-833131200-8
issn:
- 1071-9040
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Improved differentially private continual observation using group algebra
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 5
year: '2025'
...