Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis
AuthorsXin Lyu, Kunal Talwar
AuthorsXin Lyu, Kunal Talwar
Fingerprinting codes are a crucial tool for proving lower bounds in differential privacy. They have been used to prove tight lower bounds for several fundamental questions, especially in the "low accuracy" regime. Unlike reconstruction/discrepancy approaches however, they are more suited for proving worst-case lower bounds, for query sets that arise naturally from the fingerprinting codes construction. In this work, we propose a general framework for proving fingerprinting type lower bounds, that allows us to tailor the technique to the geometry of the query set. Our approach allows us to prove several new results.
First, we show that any (sample- and population-)accurate algorithm for answering arbitrary adaptive counting queries over a universe to accuracy needs samples. This shows that the approaches based on differential privacy are optimal for this question, and improves significantly on the previously known lower bounds of and . Seconly, we show that any -DP algorithm for answering counting queries to accuracy needs samples. Our framework allows for directly proving this bound and improves by the bound proved by Bun, Ullman and Vadhan (2013) using composition. Thirdly, we characterize the sample complexity of answering a set of random 0-1 queries under approximate differential privacy. To achieve this, we give new upper and lower bounds that combined with existing bounds allow us to complete the picture.
July 11, 2025research area Methods and Algorithms, research area Privacyconference ICML
We design new differentially private algorithms for the problems of adversarial bandits and bandits with expert advice. For adversarial bandits, we give a simple and efficient conversion of any non-private bandit algorithms to private bandit algorithms. Instantiating our conversion with existing non-private bandit algorithms gives a regret upper bound of , improving upon the existing upper bound...
May 5, 2019research area Privacyconference COLT
We develop lower bounds for estimation under local privacy constraints—including differential privacy and its relaxations to approximate or Rényi differential privacy—by showing an equivalence between private estimation and communication-restricted estimation problems. Our results apply to arbitrarily interactive privacy mechanisms, and they also give sharp lower bounds for all levels of differential privacy protections, that is, privacy...