Chasing the Constants and Its Implication in Private Learning

on YouTube ↗31m

" summary

Claims a constructive upper bound and a matching lower bound for the factorization norm of the lower‑triangular all‑ones matrix that drives private continual prefix‑sum error, with an explicit group‑algebra factorization achieving the asymptotic log T / π term and a normalized square‑root factorization reducing the additive constant to about 0.84, leaving an additive gap ≈0.14 + o(1). Methods use Toeplitz symbol/ generating‑function factorization, Wallis and binomial coefficient estimates, and exact small‑n (n=2) optimization; implications tighten utility for private continual counting and private convex optimization.

AI-written summary · about

" chapters (10)

1. 0:00Chasing constants in private learning
2. 1:18Problem definition and model
3. 4:23Prefix sum in privacy
4. 8:14Binary tree mechanism limits
5. 13:54Matrix mechanism factorization
6. 18:10Minimize gamma-2 norm
7. 20:40Square root factorization
8. 25:00Toeplitz matrix and polynomials
9. 28:11Case analysis t=2
10. 30:18Summary and ongoing work