[Seminar] High-Dimensional Private Linear Regression with Optimal Rates

Speaker

Mr. Simone Bombari, Institute of Science & Technology Austria (ISTA), Austria

Abstract

Differentially private (DP) linear regression has received significant attention in the recent theoretical literature, with several approaches proposed to improve error rates. Our work considers the popular high-dimensional regime with random data, where the number of training samples n and the input dimension d grow at a proportional rate d/n → γ, and it studies a family of one-pass DP gradient descent (DP-GD) algorithms satisfying ρ2/2 zero concentrated DP. In this setting, we establish a deterministic equivalent for the DP-GD trajectory in terms of a system of ordinary differential equations. This allows to analyze the effect of gradient clipping constants that are smaller than the typical norm of the per-sample gradients - a setup shown to improve performance in practice.
For well-conditioned data, we show that DP-GD, upon properly choosing clipping constant and learning rate, achieves the non-asymptotic risk of O(γ + γ2/ρ2), and we establish that this rate is minimax optimal. Then, we consider the ill-conditioned case where the data covariance spectrum follows a power-law distribution, and we show that the risk displays a power-like scaling law in γ, highlighting the change in the exponent as a function of the privacy parameter ρ. Overall, our analysis demonstrates the benefits of practical algorithmic design choices, including aggressive gradient clipping and decaying learning rate schedules.

Biography

Simone Bombari is a PhD student at the Institute of Science and Technology Austria, supervised by Marco Mondelli. Before joining ISTA, he obtained his Bachelor's and Master's degrees in Physics from the University of Pisa and Scuola Normale Superiore. Simone's recent research focuses on the intersection of machine learning, privacy and high-dimensional probability. During his PhD, he was an intern at AWS and G-Research, and his work has been supported by a Google PhD Fellowship. Starting this fall, he will join NYU as a Faculty Fellow and the Flatiron Institute as a Research Fellow.