Doctoral Thesis: Differential Privacy via Randomized Sketches

Presenter: Omri Lev

Presenter’s Affiliation: LIDS

Thesis Supervisor(s): Prof. Ashia C. Wilson

Details

• Date: Thursday, June 4
• Time: 1:00 pm - 3:00 pm
• Location: Building 45 (51 Vassar St, Cambridge, MA 02139), Room 322

Additional Location Details:

Abstract: Machine learning models trained on personal data are ubiquitous, making it essential to protect individuals’ privacy. Differential privacy (DP) has emerged as the standard framework for privacy-preserving data analysis, providing a formal guarantee that the inclusion or exclusion of any individual has only a limited effect on the output distribution of a computation. At the same time, randomized sketching has become a central tool for designing computationally efficient optimization methods with strong guarantees across machine learning and data science. At a high level, sketching methods multiply a large data-dependent quantity by a lower-dimensional random projection and then solve the resulting reduced problem. Because this reduced problem is typically much cheaper to solve, the overall runtime is usually dominated by the projection step, which can often be implemented efficiently using sparse or structured matrices.

Despite their shared reliance on randomness, the connection between randomized sketching and differential privacy remains only partially understood. This thesis develops new theory and algorithms at this interface. We use modern tools from differential privacy to derive state-of-the-art privacy guarantees for sketching-based mechanisms and to design new private algorithms with guarantees suitable for practical deployment. Then, focusing on the classical problem of differentially private ordinary least squares (DP-OLS), we provide a comprehensive study of existing sketch-based methods, identifying their limitations and characterizing the regimes in which they succeed or fail. Building on this analysis, we develop new algorithms that leverage ideas from the classical sketching literature to improve over prior methods in both utility and runtime. Our approach yields computationally efficient and near-optimal private algorithms with strong theoretical guarantees and excellent empirical performance.

Zoom: https://mit.zoom.us/j/4808560731?omn=96674479432; https://mit.zoom.us/my/omrilev