An Inversion Theorem for Buffered Linear Toeplitz (BLT) Matrices and Applications to Streaming Differential Privacy
Not on the map. Why?
Abstract (arXiv)
Buffered Linear Toeplitz (BLT) matrices are a family of parameterized lower-triangular matrices that play an important role in streaming differential privacy with correlated noise. Our main result is a BLT inversion theorem: the inverse of a BLT matrix is itself a BLT matrix with different parameters. We also present an efficient and differentiable O(d3) algorithm to compute the parameters of the inverse BLT matrix, where d is the degree of the original BLT (typically d < 10). Our characterization enables direct optimization of BLT parameters for privacy mechanisms through automatic differentiation.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 10 of its 20 references that are in the map. First posted on arXiv 30 Apr 2025.
Builds on
10 of 20 references.
References · 10
- 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
- 2021Practical and Private (Deep) Learning without Sampling or Shufflingcited by 169
- 2022Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streamscited by 59
- 2023(Amplified) Banded Matrix Factorization: A unified approach to private trainingcited by 49
- 2022Constant matters: Fine-grained Complexity of Differentially Private Continual Observationcited by 23
- 2023Privacy Amplification for Matrix Mechanismscited by 17
- 2024Efficient and Near-Optimal Noise Generation for Streaming Differential Privacycited by 17
- 2024Scaling up the Banded Matrix Factorization Mechanism for Differentially Private MLcited by 12
- 2024A Hassle-free Algorithm for Private Learning in Practice: Don't Use Tree Aggregation, Use BLTscited by 9
- 2024Improved Differentially Private Continual Observation Using Group Algebracited by 7
Built on by
Citing papers per year: 2025: 3.
3 papers.