PaperlayerView exact revision on arXiv

Source-linked AI summary

Privately Releasing Conjunctions and the Statistical Query Barrier

Anupam Gupta, Moritz Hardt, Aaron Roth, Jonathan Ullman

arXiv:1011.1296v4cs.DScs.CRcs.LG

TL;DR

The paper asks whether query release under SQ-only access can beat exhaustive querying, while efficient private release of all Boolean conjunctions remains open. It links SQ release complexity to agnostic SQ learning and gives a polynomial-time differentially private release algorithm for conjunctions with 1% average error.

  • Problem

    Efficiently releasing all Boolean conjunction answers with differential privacy is a major open problem, alongside determining whether SQ access can answer a query class more efficiently than exhaustive querying.

    Source: §1 · p. 2

  • Method

    The paper combines a submodular-function approximation algorithm with a multiplicative-weights reduction linking SQ query release to agnostic SQ learning.

    Source: §1.1 · pp. 3–4

  • Results

    Up to an O(d) factor, SQ query-release complexity equals agnostic SQ-learning complexity, and a polynomial-time differentially private algorithm releases Boolean conjunctions with 1% average error.

    Source: §1 · p. 2, §1.1 · p. 3

  • Takeaways & Limitations

    SQ-based running-time lower bounds constrain most known private algorithms, making agnostic SQ-learning complexity a barrier to efficient private release.

    Source: §1 · p. 3

    The monotone-conjunction SQ lower bound does not extend when arbitrary errors on 1% of conjunctions are allowed; an inefficient poly(2^d)-time algorithm handles random conjunctions.

    Source: §5.1 · p. 21

Abstract

from arXiv · show

Suppose we would like to know all answers to a set of statistical queries C on a data set up to small error, but we can only access the data itself using statistical queries. A trivial solution is to exhaustively ask all queries in C. Can we do any better? + We show that the number of statistical queries necessary and sufficient for this task is---up to polynomial factors---equal to the agnostic learning complexity of C in Kearns' statistical query (SQ) model. This gives a complete answer to the question when running time is not a concern. + We then show that the problem can be solved efficiently (allowing arbitrary error on a small fraction of queries) whenever the answers to C can be described by a submodular function. This includes many natural concept classes, such as graph cuts and Boolean disjunctions and conjunctions. While interesting from a learning theoretic point of view, our main applications are in privacy-preserving data analysis: Here, our second result leads to the first algorithm that efficiently releases differentially private answers to of all Boolean conjunctions with 1% average error. This presents significant progress on a key open problem in privacy-preserving data analysis. Our first result on the other hand gives unconditional lower bounds on any differentially private algorithm that admits a (potentially non-privacy-preserving) implementation using only statistical queries. Not only our algorithms, but also most known private algorithms can be implemented using only statistical queries, and hence are constrained by these lower bounds. Our result therefore isolates the complexity of agnostic learning in the SQ-model as a new barrier in the design of differentially private algorithms.

1 Introduction

The introduction frames efficient private release of all Boolean conjunctions as an open problem and asks how much statistical-query access is needed to release a query class. It presents efficient approximate release for submodular-described queries and characterizes SQ release through agnostic learning, yielding a barrier for SQ-based private algorithms.

1 Introduction

  • A polynomial-time ε-differentially private mechanism releases Boolean conjunctions with 1% average error, and the theorem gives an α-error guarantee on a 1−β fraction of queries.The theorem requires |D| ≥ d^O(log(1/β)/α^2)/ε.Source: §1 · p. 2, §1.1 · p. 3

1.1 Overview of our results

  • Efficient approximation applies to low-sensitivity submodular query collections, including graph cuts and set-coverage functions.The informal theorem gives runtime d^O(log(1/β)/α^2) and approximation error α on at least a 1−β fraction of inputs.Source: §1 · p. 2, §1.1 · p. 3

1 Introduction

  • Up to an O(d) factor, the statistical-query complexity of releasing all queries in C matches agnostic SQ-learning complexity, with query bounds in both directions.A learner using q queries yields a release mechanism using O(qd/α^2) queries, while a release mechanism using q queries implies a learner using at most 2q.Source: §1 · p. 2, §1.1 · p. 3
  • Feldman’s agnostic-learning lower bound implies no polynomial-time SQ algorithm releases monotone conjunctions to subconstant error, even if its implementation need not preserve privacy.The paper states that the lower bound applies to algorithms interacting with data only through SQ queries and does not depend on output representation.Source: §1 · p. 2, §1.2 · p. 5
  • The characterization also applies to local privacy, while familiar mechanisms such as Median and Multiplicative Weights are SQ-implementable and inherit the running-time lower bounds.Those mechanisms do not preserve their privacy guarantees in the local model because they require too many queries there.Source: §1 · pp. 2–3

1.1 Overview of our results

  • The reductions preserve query complexity but not runtime, and the equivalence extends information-theoretically to other restricted forms of database access.The paper says this also relates the privacy cost of release to the cost of optimizing over the same query class.Source: §1.1 · p. 4
  • The submodular method represents a function using a small family of strongly Lipschitz submodular functions, then uses concentration bounds to approximate most queries.The characterization method instead uses multiplicative weights, with an agnostic learner finding queries that distinguish the data from the maintained distribution.Source: §1.1 · p. 4

1.2 Related Work

  • The paper distinguishes its approach from the hardness result by outputting a data structure and allowing small average error rather than requiring a synthetic data set answering every two-literal conjunction.The cited hardness result is conditional and applies to mechanisms outputting data sets with small error on all two-literal conjunctions.Source: §1.2 · p. 5

2 Preliminaries

The preliminaries define differential privacy and the statistical-query model, then frame query release as approximation and introduce submodularity as a useful structure for query answers.

2 Preliminaries

  • Differential privacy bounds how much an output distribution can change between adjacent databases, while a counting query is a predicate whose answer changes by at most 1/n between such databases.Adding Laplacian noise of magnitude 1/(εn) makes a single counting query differentially private.Source: §2 · p. 6
  • In Kearns’ SQ model, an oracle answers predicates with estimates within tolerance τ of their expectation under a distribution.For a uniform distribution over a data set, statistical queries correspond to counting queries; a noisy oracle can make an SQ algorithm differentially private.Source: §2 · p. 6
  • An SQ algorithm using k queries can be run with a Laplacian-noise oracle that preserves differential privacy, provided the database is sufficiently large relative to k and the tolerance.The stated sample-size condition is n ≥ k(log k + log(1/β))/ετ.Source: §2 · p. 6
  • Query release requires answers to be accurate for most queries, and can be framed as approximating the function that maps each query to its data-set answer.The function-approximation definition likewise measures accuracy over most inputs drawn from a distribution.Source: §2 · pp. 6–7
  • Submodularity is characterized by diminishing marginal values as sets grow, and the preliminaries define both Lipschitz bounds on those marginals and the property itself.The section notes that query-answer functions are submodular for many concept classes of interest.Source: §2 · p. 7
  • The preliminaries state concentration results for Lipschitz submodular functions under product distributions.The lemma concerns 1-Lipschitz functions, and its corollary concerns γ-Lipschitz functions with values in [0,1].Source: §2 · p. 7

3 Approximating Submodular Functions

This section develops a decomposition of submodular functions into a small collection of Lipschitz submodular functions, preserving input-set values, and uses it to approximate expectations under product distributions. It covers bounded functions and gives a decomposition for non-monotone submodular functions.

3 Approximating Submodular Functions

  • The structural theorem decomposes a bounded submodular function into regional shifted submodular functions with marginals at most γ, while preserving the original value for every input set.For each S, the selected region satisfies F(S) ⊆ S ⊆ V(F(S)) and g_F(S)(S) = f(S).Source: §3 · p. 7, §3.1 · p. 8

3.1 Monotone Submodular Functions

  • The decomposition has at most |U|^O(1/γ) functions, and its mappings can be computed in |U|^O(1/γ) time; the maps also uniquely characterize each region.Uniqueness holds when B ⊆ S ⊆ V(B) and S ∩ T(B) = ∅.Source: §3.1 · p. 8
  • Although the structural lemma applies to non-monotone functions, its Lipschitz guarantee suffices for the release algorithm only for monotone submodular functions.The release algorithm requires a bound on the absolute marginal values.Source: §3.1 · p. 8
  • A tolerant-query version retains the decomposition guarantees using oracle queries to f with tolerance γ/12.It adjusts the marginal thresholds used to construct the regions.Source: §3.1 · pp. 10–11
  • Algorithm 5 (α, β)-approximates any submodular f:2^U→[0,1] under product D in |U|^O(α^-2 log(1/β)) time using queries of tolerance α^2/72 log(2/β).The algorithm estimates each regional function’s expectation under a product distribution restricted to its region.Source: §3.1 · p. 12

3.2 Non-monotone Submodular Functions

  • For any submodular f: 2^U → [0,1] and γ > 0, Algorithm 4 provides a family G whose functions have marginal absolute values at most γ only for x and S in the corresponding V(B,C).For every S ⊆ U, F(S) ⊆ S ⊆ V(F(S)) and g_F(S)(S) = f(S); |G| is at most |U|^{O(1/γ)}, and F, V, T are computable with γ/12-tolerance oracle access in time |U|^{O(1/γ)}.Source: §3.2 · p. 13
  • Algorithm 5 estimates the mean of each decomposed function over its restricted product distribution using a small number of random samples.The data structure stores these estimates and the mapping F.Source: §3.2 · p. 14
  • For α, β ∈ (0, 1], Algorithm 5 (α, β)-approximates any submodular f: 2^U → [0, 1] under product distributions in time |U|^{O(α^-2 log(1/β))}.It uses oracle queries with tolerance α^2/(72 log(1/β)).Source: §3.2 · p. 14

4 Applications to privacy-preserving query release

The section applies submodular-function approximation to privately release monotone disjunctions and conjunctions, and graph cut functions. It also identifies scope boundaries for non-monotone queries and graph data.

4 Applications to privacy-preserving query release

  • Corollary 4.2 gives ε-differentially private (α, β)-release of monotone Boolean disjunctions over any product distribution.The data structure is built by applying the submodular approximation result to FDisj, which is monotone submodular.Source: §4 · p. 15
  • Releasing disjunctions on data items negated bitwise suffices to release monotone conjunctions over the same distribution.Thus Corollary 4.2 extends directly to monotone conjunctions.Source: §4 · p. 16
  • For width w, the required concentration property still holds for monotone submodular functions, allowing the theorem to be instantiated for each width.The uniform distribution on width-w disjunctions is not a product distribution, so the direct product-distribution result does not apply.Source: §4 · p. 16
  • The presentation omits non-monotone conjunctions and disjunctions; for width w ≥ log(1/α), the constant 0 approximates FDisj on a random non-monotone conjunction.The remark says a random non-monotone conjunction of that width is false on any fixed data item with probability 2^-w.Source: §4 · p. 16

4.1 Releasing the cut function of a graph

  • A graph cut function counts edges crossing a cut, has sensitivity 1/|V|^2, and is submodular, enabling private release over any product distribution.The cut release preserves ε-differential privacy.Source: §4.1 · p. 17

5 Equivalence between agnostic learning and query release

The section establishes an information-theoretic equivalence between agnostic learning and query release in the statistical-query model. A weak agnostic SQ learner yields a release algorithm, and a release algorithm in turn yields an agnostic learner.

5 Equivalence between agnostic learning and query release

  • A weak agnostic learner need only find a sufficiently good predicate when one exists, rather than maximize agreement over the class.The reduction applies to weak agnostic learning; strong agnostic learning also supplies such a weak learner under the stated accuracy condition.Source: §5 · p. 17
  • A weak agnostic SQ learner for C yields an (α, 0)-release algorithm using at most 8 log|X|/β^2 learner calls, with success probability at least 1−Tγ.The learner must be (α/2, β, γ, τ)-weak agnostic and have τ≤β/8.Source: §5 · p. 17
  • The reduction iteratively uses an agnostic learner to find a concept distinguishing the data distribution from the current estimate, then applies multiplicative weights until no good distinguisher remains.The potential argument bounds the number of update steps before every concept in C is indistinguishable up to the target bias.Source: §5 · p. 18, §5.1 · p. 19

5.1 Proof of Theorem 5.1

  • A release algorithm making at most k statistical queries yields a strong agnostic learner using 2k queries, with accuracy 2α and success probability at least 1−2γ.The reduction simulates label-conditioned query oracles using statistical queries to the original distribution.Source: §5.1 · p. 21
  • No polynomial number of statistical queries can release monotone conjunctions to o(1) error when every conjunction must be accurate.The stated corollary applies to algorithms making k(d) queries on a database of size k(d), for any polynomial k(d).Source: §5.1 · p. 21
  • That lower bound does not rule out arbitrary errors on 1% of conjunctions: an inefficient poly(2^d)-time algorithm can release random conjunctions with small additive error.The paper notes that this algorithm is omitted from the formal description and analysis.Source: §5.1 · p. 21
  • The reductions are not specific to statistical queries: a query-release algorithm can use a small number of black-box calls to a learning algorithm without other database access.The paper also states that an ε-differentially private agnostic learner can yield release with Tε≈log|X|ε differential privacy.Source: §5.1 · p. 21
Loading 1011.1296v4…