On Differential Privacy for Adaptively Solving Search Problems via Sketching

Shiyuan Feng, Ying Feng, George Li, Zhao Song, David Woodruff, Lichen Zhang

International Conference on Machine Learning 2025 · Oral

This talk, presented by Zhao Song from UC Berkeley, introduces a novel framework for achieving **differential privacy (DP)** in the context of **adaptively solving search problems** through the strategic use of **sketching**. The research is a collaborative effort with Shiyuan Feng, Ying Feng, George Li, David Woodruff, and Lichen Zhang, with the core ideas largely attributed to Lichen Zhang. The talk addresses a fundamental challenge in privacy-preserving machine learning and data systems: how to maintain strong privacy guarantees when queries are not independent but rather adaptively chosen based on the results of previous queries. This scenario is common in real-world applications such as personalized recommendations, interactive data analysis, and adaptive learning algorithms, where the traditional approaches to differential privacy often lead to significant utility loss or require excessive computational resources.

AI review

A theoretically motivated paper combining differential privacy, adaptive query composition, and sketching to achieve sqrt(T) resource improvements over naive baselines for adaptive nearest neighbor search and dynamic programming. The central idea is genuine and the setting is well-motivated, but the article's account of the work leaves too many technical details underspecified to assess whether the theorems are tight, whether the assumptions are reasonable in practice, and whether the sqrt(T) result is truly novel relative to existing adaptive data analysis literature. Solid theoretical work…