Differentially Private Online-to-Batch Conversion for Stochastic Optimization

Explore a Google TechTalk presented by Ashok Cutkosky on differentially private online to batch conversion in stochastic optimization. Delve into the challenges of privacy-preserving algorithms and learn about a novel approach that bridges the gap between simple but suboptimal methods and complex but theoretically optimal techniques. Discover how this new variation on the classical online-to-batch conversion can transform any online optimization algorithm into a private stochastic optimization algorithm, potentially achieving optimal convergence rates. Throughout the 50-minute talk, examine key concepts such as DP-SGD, bespoke analysis, online linear optimization, and tree aggregation. Gain insights into the applications of this method, including adaptivity and parameter-free comparator adaptation, while considering the implications for privacy in machine learning and optimization practices.

Intro
Privacy and Learning
Privacy Preserving Learning
Stochastic Optimization
Private Stochastic Convex Optimization
Typical Strategy 1: DP-SGD
Typical Strategy 2: Bespoke Analysis
Two techniques summary
High-level result
Outline of Strategy
Key Ingredient 1: Online (Linear) Optimization/Learning
Online Linear Optimization
Key Ingredient 2: Online to Batch Conversion
Straw man algorithm: Gaussian mechanism + online-to-batch
Key Ingredient 2: Anytime Online-to-Batch Conversion
Important Property of Anytime Online-to-Batch
Anytime vs Classic Sensitivity
Gradient as sum of gradient differences
Our actual strategy
Final Ingredient: Tree Aggregation
Final Algorithm
Loose Ends
Unpacking the bound
Applications: Adaptivity
Applications: Parameter-free/Comparator Adaptive
Fine Print, Open problems