---
res:
  bibo_abstract:
  - 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.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Monika H
      foaf_name: Henzinger, Monika H
      foaf_surname: Henzinger
      foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
    orcid: 0000-0002-5008-6530
  - foaf_Person:
      foaf_givenName: Jalaj
      foaf_name: Upadhyay, Jalaj
      foaf_surname: Upadhyay
  bibo_doi: 10.1137/1.9781611978322.95
  bibo_volume: 5
  dct_date: 2025^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/1071-9040
  - http://id.crossref.org/issn/979-833131200-8
  dct_language: eng
  dct_publisher: Association for Computing Machinery@
  dct_title: Improved differentially private continual observation using group algebra@
...