Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis

Xin Lyu, Kunal Talwar · 2024

Read Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis by Xin Lyu, Kunal Talwar (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-14396.txt.

Introduction

Xin Lyu and Kunal Talwar prove new limits on how much data any privacy-respecting algorithm needs, by letting the shape of the questions dictate the proof, in this 2024 paper. Fingerprinting codes were invented to trace leaked copies of digital content. They have become the standard weapon for showing that some statistical tasks are impossible below a certain sample size.

Older fingerprinting arguments worked only for question sets that resembled the codes themselves. The authors build a general framework that bends the technique to the geometry of the actual query set. Two payoffs follow. Answering a batch of adaptive counting questions accurately provably needs a number of samples matching the best known private algorithms, settling that differential privacy is the right tool there. A second bound tightens what any private algorithm needs for counting queries in general. Lower bounds are the signposts that tell algorithm designers to stop searching.

Catalog record

CREATORXin Lyu, Kunal Talwar
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE140 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-14396

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis Xin Lyu, Kunal Talwar Abstract 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 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, including the following. • We show that any (sample- and population-)accurate algorithm for answering Q Q arbitrary adaptive counting queries over a universe 𝒳 \mathcal{X} to accuracy α \alpha needs Ω ⁡ ( log ⁡ | 𝒳 | ⋅ log ⁡ Q α 3 ) \Omega(\frac{\sqrt{\log|\mathcal{X}|}\cdot\log Q}{\alpha^{3}}) samples, matching known upper bounds. This shows that the approaches based on differential privacy are optimal for this question, and improves significantly on the previously known lower bounds of log ⁡ Q α 2 \frac{\log Q}{\alpha^{2}} and min ⁡ ( Q , log ⁡ | 𝒳 | ) / α 2 \min(\sqrt{Q},\sqrt{\log|\mathcal{X}|})/\alpha^{2} . • We show that any ( ε , δ ) (\varepsilon,\delta) -DP algorithm for answering Q Q counting queries to accuracy α \alpha needs Ω ⁡ ( log ⁡ | 𝒳 | ​ log ⁡ ( 1 / δ ) ​ log ⁡ Q ε ​ α 2 ) \Omega(\frac{\sqrt{\log|\mathcal{X}|\log(1/\delta)}\log Q}{\varepsilon\alpha^{2}}) samples, matching known upper bounds up to constants. Our framework allows for proving this bound via a direct correlation analysis and improves the prior bound of [ BUV14 ] by log ⁡ ( 1 / δ ) \sqrt{\log(1/\delta)} . • For privately releasing a set of random 0 0 - 1 1 queries, we show tight sample complexity lower bounds in the high accuracy regime. In the low accuracy regime, the picture is more complex. For random queries, we show that there is a discontinuity in the sample complexity. For d d random queries over a universe 𝒳 \mathcal{X} , the sample complexity grows as Θ ε , δ ​ ( 1 α 2 ) \Theta_{\varepsilon,\delta}(\frac{1}{\alpha^{2}}) , with no dependence on d d or | 𝒳 | |\mathcal{X}| . This new sample complexity bound, based on sparse histograms, is asymptotically better than known lower bounds for CDP. However, at α ≈ log ⁡ | 𝒳 | / d \alpha\approx\sqrt{\log|\mathcal{X}|}/\sqrt{d} , the sample complexity jumps to Θ ε , δ ​ ( d / α ) \Theta_{\varepsilon,\delta}(\sqrt{d}/\alpha) . 1 Introduction Differential Privacy [ DMNS17 ] is standard notion of privacy in statistical databases. Differentially Private (DP) algorithms have been deployed by the US Census Bureau for publishing tables [ AACM+22 ] , the Israeli Department of Health for publishing birth records [ HC24 ] , and by several companies for training machine learning models and sharing statistics (see e.g. [ App17 , DKY17 , XZA+23 , ZRX+23 ] ). While there is now a large body of literature on designing differentially private algorithms for numerous machine learning and statistical tasks, algorithms for answering statistical (SQ) queries date back to some of the earliest work on Differential Privacy. In this work, we revisit the question of answering statistical/counting queries under a differential privacy constraint. In a bit more detail, we consider a dataset of size n where each user comes from a universe \mathcal{X} . A counting query q is defined by a function p:\mathcal{X}\rightarrow[-1,1] and the desired answer to such a query on a dataset D=\{d_{1},\ldots,d_{n}\} is q(D)=\frac{1}{n}\sum_{i=1}^{n}p(d_{i}) . We would like to design an (\varepsilon,\delta) -DP algorithm that answers Q counting queries, and we will measure the error of a mechanism M on a dataset D by either the \ell_{\infty} error \max_{i\in Q}|M(D)_{i}-q_{i}(D)| or the (normalized) \ell_{2} error \sqrt{\frac{1}{Q}\sum_{i=1}^{Q}(M(D)_{i}-q_{i}(D))^{2}} . There has been a large body of work on understanding upper and lower bounds for counting queries under differential privacy (see Section 1.2 ). Lower bounds for (\varepsilon,\delta) -DP broadly fall into a few classes. Reconstruction arguments [ DN03 ] show that an algorithm that is too accurate allows for reconstructing the input dataset. This approach was generalized by Muthukrishnan and Nikolov [ MN12 ] who recognized the hereditary discrepancy of the query set as the primary object of interest. Nikolov, Talwar and Zhang [ NTZ13 ] connected this to the geometry of the so-called sensitivity polytope , and showed that for every set of queries, the lower bound from hereditary discrepancy is within polylogarithmic factors of an appropriate Gaussian noise mechanism with a carefully chosen covariance, when n is large enough. For the large dataset regime, this reconstrution/discrepancy approach yields nearly tight bounds not just in the worst case, but for any given set of queries. For small datasets, this approach is suboptimal by polylogarithmic in |\mathcal{X}| factors. Indeed, for a query set as simple as one-way marginals, the right achievable error rate was open until the seminal work of Bun, Ullman, and Vadhan [ BUV14 ] . This work showed that fingerprinting codes from cryptography can be adapted to prove tight lower bounds for certain sets of queries, including the tight bounds for one-way marginals. Further, they showed that these lower bounds can be “composed” with other lower bounds to get tight worst-case bounds. This approach has been used to prove worst-case lower bounds for several problems in differential privacy and in adaptive data analysis [ HU14 , SU15 ] . It is natural to ask if there is a geometric query-specific generalization of the fingerprinting codes technique. In this work, we make progress towards pushing this technique to a broader class of problems. We develop a new abstract framework for proving lower bounds using the underlying approach in fingerprinting codes. Our approach has two main technical ingredients. First, we use an exponential tilt to define a family of distributions over an arbitrary set of points. This yields a family of distributions over the polytope K of choice, that comes from the exponential family and is thus more amenable to the use of fingerprinting tools [ KMS22 ] . Second, we relax the need for the “parameter vector” to come from a hyper-rectangle as in most previous work, using Stokes’ theorem to control the appropriate “score”. Recent work by Portella and Harvey [ PH24 ] used Stokes’ theorem for a specific family of distributions via the Stein-Haff identity. Our work shows that this approach can be used to prove lower bounds for a large family of problems. 1.1 Our Results Adaptive data analysis over a bounded domain. Adaptive Data Analysis addresses the question of statistical validity of query answers in the face of adaptivity. While k non-adaptive counting queries can be answered to accuracy \alpha using O(\log k/\alpha^{2}) samples, these bounds break down when the queries can be adaptive. Dwork, Feldman, Hardt, Pitassi, Reingold and Roth [ DFH+15c ] first showed that O(\sqrt{k}) samples suffice to answer k queries. Using the private multiplicative weights algorithm of Hardt and Rothblum [ HR10 ] , subsequent work by Bassily, Nissim, Smith, Steinke, Stemmer and Ullman [ BNS+16 ] showed that one

Read the complete text