Introduction
Differential privacy (DP) [30 , 32 ] has emerged as the gold standard for privacy-preserving data analysis, offering a mathematically rigorous framework that limits the risk of disclosing the data of any individual entity. Informally, a randomized algorithm is differentially private if its output distribution is nearly unchanged when any individual record is modified or removed. This ensures that adversaries learn little about any one participant, even with auxiliary information.
Despite its mathematical elegance, the practical implementation and verification of differential privacy can be challenging [14 , 3 , 44 , 7 , 5 , 9 , 69 ] . Because privacy guarantees are probabilistic and often counterintuitive, even subtle coding errors or floating-point vulnerabilities can lead to privacy leakage [54 ] . This has led the community toward primitives that avoid floating-point numbers [21 , 18 ] . More broadly, verifying that an implementation of a differentially private algorithm is correct can be challenging, and even testing or auditing for privacy requires considerable effort [8 , 43 ] .
To mitigate these risks, the field has moved toward a modular “API-centric” approach. Rather than requiring developers to implement complex mechanisms from scratch, privacy frameworks, dating from early systems like PINQ [53 ] and Airavat [59 ] to modern efforts like OpenDP and Google’s differential privacy building blocks, rely on a small set of vetted primitives. These primitives are the “building blocks” for private algorithms; by thoroughly auditing a limited number of functions, such as the Laplace mechanism or standard composition theorems, one can build complex pipelines while mathematically tracking the total privacy loss.
In federated or distributed architectures, implementing such primitives is harder, and thus this modularity is even more critical. Specifically, primitives must be implemented under a variety of operational and security constraints. The move toward these standardized, vetted interfaces has led to the adoption of large-scale DP frameworks [62 , 68 ] , which provide high-level query languages backed by reliable primitives. However, as the ecosystem of these frameworks expands, it becomes vital to understand the relative power of various primitives.
Previous work has successfully formalized specific trust models, such as the local [67 , 35 , 50 ] and shuffle [4 , 22 , 34 ] privacy models. More broadly, a privacy framework can treat simple privacy primitives as interchangeable building blocks and support a set of privacy-accounting methods. A complex algorithm can be built by combining primitives, each run on all or a subset of the data, while privacy accounting upper bounds the algorithm’s privacy cost. As an example, an aggregation system allows for algorithms that apply a function f : X → R d f : \mathcal{X} \to\mathbb{R}^{d} f : X → R d f ~ ( x 1 , … , x n ) = ∑ i clip 1 ( f ( x i ) ) + N ( 0 , σ 2 I d ) \tilde{f}(x_{1}, \ldots, x_{n}) = \sum_{i} \operatorname{clip}_{1}(f(x_{i})) + \mathcal{N}(0, \sigma^{2} I_{d}) f ~ ( x 1 , … , x n ) = ∑ i clip 1 ( f ( x i )) + N ( 0 , σ 2 I d ) σ \sigma σ clip 1 \operatorname{clip}_{1} clip 1 ℓ 2 \ell_{2} ℓ 2 [55 ] . One can then use such a system to implement differentially private gradient descent to train a machine learning model. Enhancing the primitive and accounting to allow for privacy amplification by sampling further enables DP stochastic gradient descent [16 , 1 ] . Aggregation, potentially with sampling, can support a rich class of algorithms, and such systems have been proposed under various assumptions [28 , 12 RCWH+20, FES+17, 58 , 60 TWM+24] .
In this work, we study the limits of the Aggregation API, and propose an additional primitive to help circumvent some of these limitations.
Our Contributions
Despite the wide applicability of the Aggregation API, there are important tasks that are not known to be implementable accurately using aggregation alone. Foremost among these is perhaps the selection problem, where the best-known algorithms using aggregation incur significant overhead compared to the optimal central-DP bounds: while centrally one can do selection using O ( log d / ε ) O(\log d/\varepsilon) O ( log d / ε ) Ω ( d / ε ) \Omega(\sqrt{d}/\varepsilon) Ω ( d / ε ) [26 , 22 , 24 , 20 ] , no existing lower bounds exclude a better way to do selection using an aggregation API.
Our first result is a strong lower bound ruling out this possibility. We show that any selection algorithm using an aggregation API requires sample complexity Ω ( d / ϵ ) \Omega(\sqrt{d}/\epsilon) Ω ( d / ϵ ) ( ϵ , δ ) (\epsilon,\delta) ( ϵ , δ ) 1 / 3 1/3 1/3
Theorem 2.1. [Informal] Any ( O ( 1 ) , O ( 1 / poly ( d ) ) ) (O(1),O(1/\operatorname{poly}(d))) ( O ( 1 ) , O ( 1/ poly ( d ))) d d d Ω ( d ) \Omega(\sqrt{d}) Ω ( d )
The main advantage of this lower bound over most existing lower bounds for selection in restricted models is that we allow algorithms that use queries adaptively. Adaptivity is crucial for implementing most standard ML algorithms and is known to be necessary for some learning problems [25 ] . We prove this result specifically for aggregation with Gaussian noise addition, with the privacy guarantee derived by composition of the guarantees for individual queries (Theorem 4.4 ). This implies that our lower bound applies to any API with a comparable privacy-utility trade-off, which is known to be asymptotically optimal for L 2 L2 L 2 [28 ] while satisfying weaker privacy guarantees. We then prove a lower bound for such protocols using the information-theoretic techniques from [10 , 33 ] .
To address these limitations, we propose adding a new Sparse Vector Technique (SVT) primitive. This primitive implements a special case of the sparse vector technique of [31 ] , and suffices to implement a large class of private algorithms. By integrating SVT as a fundamental primitive, our approach expands the expressive power of DP APIs, improves accuracy guarantees, and supports a wider range of applications.
Informally, the SVT primitive implements the AboveThreshold subroutine for additive queries. We first formally define the SVT primitive. This technique is designed to privately process a potentially long sequence of queries by revealing information only about those whose true values exceed a specified threshold. A key innovation of SVT is that by careful correlation of the noise, the incurred privacy cost grows with the number of initialized SVT streams, and is independent of the number of queries issued. In our proposed primitive, each query is restricted to be a sum of bounded contributions from individual users. These are often referred to as additive or counting queries in the context of SVT, and decomposable score functions in the context of selection. Given n n n x 1 , … , x n ∈ X x_1,\ldots,x_n \in\mathcal{X} x 1 , … , x n ∈ X q j : X → [ 0 , 1 ] q_j:\mathcal{X}\to[0,1] q j : X → [ 0 , 1 ] τ j \tau_j τ j ∑ i = 1 n q j ( x i ) ≥ τ j \sum_{i=1}^{n} q_j(x_i)\ge\tau_j ∑ i = 1 n q j ( x i ) ≥ τ j 1 ( q j , τ j ) (q_j,\tau_j) ( q j , τ j )
This primitive has the advantage of simplicity: each query is similar to an aggregation query with one additional threshold parameter. This simplicity allows for efficient and modular implementations of this primitive. While the precise implementation will vary with the trust model, we discuss several options in § 5 . At the same time, we show that this primitive is quite powerful. SVT by itself has several applications and one can naturally implement any algorithm that builds on SVT for additive queries in this model (e.g., Private Multiplicative Weights [46 ] ). We next argue that selection (the task solved by the exponential mechanism [56 ] ) can be implemented using the SVT API for any decomposable score function. Recall that given a dataset ( x 1 , … , x n ) ∈ X n (x_1,\ldots,x_n) \in\mathcal{X}^n ( x 1 , … , x n ) ∈ X n d d d s 1 , … , s d : X n → R s_1,\ldots,s_d:\mathcal{X}^n \to\mathbb{R} s 1 , … , s d : X n → R k ∈ [ d ] k \in[d] k ∈ [ d ] s j ( x 1 , … , x n ) = ∑ i = 1 n f j ( x i ) s_j(x_1,\ldots,x_n)=\sum_{i=1}^n f_j(x_i) s j ( x 1 , … , x n ) = ∑ i = 1 n f j ( x i ) f j : X → [ 0 , 1 ] f_j:\mathcal{X}\to[0,1] f j : X → [ 0 , 1 ] j j j α \alpha α
s j ( x 1 , … , x n ) ≥ max k ∈ [ d ] s k ( x 1 , … , x n ) − α . s_j(x_1,\ldots,x_n) \ge\max_{k\in[d]} s_k(x_1,\ldots,x_n)-\alpha. s j ( x 1 , … , x n ) ≥ k ∈ [ d ] max s k ( x 1 , … , x n ) − α . The reader may immediately notice that if one knew the target value max k ∈ [ d ] s k ( x 1 , … , x n ) \max_{k\in[d]} s_k(x_1,\ldots,x_n) max k ∈ [ d ] s k ( x 1 , … , x n ) d d d O ( log d / ε ) O(\log d/\varepsilon) O ( log d / ε ) O ( d ( n + 1 ) ) O(d(n+1)) O ( d ( n + 1 ))
It is easy to see that any algorithm must make Ω ( d ) \Omega(d) Ω ( d ) n n n d d d O ( log d / ε ) O(\log d/\varepsilon) O ( log d / ε ) n n n d d d O ( d log ∗ d ) O(d\log^* d) O ( d log ∗ d )
Theorem 2.2. Let ε ∈ ( 0 , 1 ] \varepsilon\in(0,1] ε ∈ ( 0 , 1 ] ε \varepsilon ε O ( log ( d n ) ε ) O\left(\frac{\log(dn)}{\varepsilon}\right) O ( ε l o g ( d n ) ) O ( d log ∗ n + log 3 n ) O(d\log^* n+\log^3 n) O ( d log ∗ n + log 3 n )
When the number of users n n n d d d O ( log d / ε ) O(\log d/\varepsilon) O ( log d / ε ) d d d O ( log ∗ d ) O(\log^* d) O ( log ∗ d ) Theorem 2.2 , specifically, to F p F_p F p
Our lower and upper bounds for selection extend to other natural tasks. Combined with known results for the shuffle model, our new upper bounds in the SVT model, and our lower bounds in the aggregation model emphasize the value of the SVT primitive. As we show in Figure 1 , our new API allows for accurate selection, where aggregation and shuffle models must incur large errors.
Figure 1. Comparison of the additive error achievable for the different APIs in the federated setting, up to constant factors, for n n n ℓ 2 \ell_2 ℓ 2 ℓ 2 \ell_2 ℓ 2 [ 0 , 1 ] d [0,1]^d [ 0 , 1 ] d d / ε \sqrt{d}/\varepsilon d / ε o ( n ) o(n) o ( n ) n ≥ Ω ( d / ε ) n \ge\Omega(\sqrt{d}/\varepsilon) n ≥ Ω ( d / ε ) ε \varepsilon ε Theorem 2.2 for SVT with n n n d d d Theorem 4.4 ), and for robust or single-round shuffle protocols (Theorem 3.3 and Theorem 3.4 ).
Other related work. Our lower bounds for aggregation APIs are most closely related to statistical query (SQ) lower bounds in learning theory [6 , 40 ] . An SQ oracle is an oracle that for a query q q q P P P τ \tau τ E x ∼ P [ q ( x ) ] \mathbb{E}_{x\sim P}[q(x)] E x ∼ P [ q ( x )] k k k Ω ( 2 k τ 2 ) \Omega(2^k\tau^2) Ω ( 2 k τ 2 ) τ \tau τ [37 ] ). Learning a parity function reduces to selection in dimension 2 k 2^k 2 k
SQ lower bounds are known to imply lower bounds for the local model of privacy with a pure-DP randomizer [50 ] . This reduction is also based on a simulation of a randomizer using an SQ oracle and, as a result, does not imply any lower bounds for the setting where the number of queries is comparable to d d d Ω ( d / ε 2 ) \Omega(d/\varepsilon^2) Ω ( d / ε 2 ) ε \varepsilon ε [27 ] . A similar lower bound on non-interactive local-DP protocols was given by [64 ] for sparse Boolean mean estimation. More recently, a lower bound of d / ε 2 d/\varepsilon^2 d / ε 2 ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) [33 ] .
Several recent works [24 , 20 , 11 ] provide lower bounds for private selection in variants of the multi-message shuffle model. All of these apply only to non-interactive (or one-round shuffling) settings. In fact, [11 ] show that a two-round multi-message protocol can simulate arbitrary secure multi-party protocols. The lower bound of [24 ] is the same as ours, Ω ( d / ε ) \Omega(\sqrt{d}/\varepsilon) Ω ( d / ε ) [20 , 11 ] are of the form d / m d/m d / m m m m
The question of implementing selection using simpler APIs has also been raised as an open question for low-sensitivity queries in [61 ] , and recent work [51 ] has shown nearly-optimal algorithms for that model. Arbitrary low-sensitivity queries can, however, be challenging to implement, and hence we focus on additive queries in this work.
Preliminaries
We use the notation [ n ] [n] [ n ] n > 0 n > 0 n > 0 { 1 , 2 , … , n } \{1,2,\ldots,n\} { 1 , 2 , … , n } f ( n ) f(n) f ( n ) g ( n ) g(n) g ( n ) f ( n ) ⪯ g ( n ) f(n) \preceq g(n) f ( n ) ⪯ g ( n ) f ( n ) = O ( g ( n ) ) f(n) = O(g(n)) f ( n ) = O ( g ( n )) C ≥ 0 C \ge0 C ≥ 0 f ( x ) ≤ C ⋅ g ( x ) f(x) \le C \cdot g(x) f ( x ) ≤ C ⋅ g ( x ) x ≥ n x \ge n x ≥ n n n n
Definition 3.1 (Differential privacy [30 ] ). Let M M M x ∈ X n \mathbf{x} \in\mathcal{X}^n x ∈ X n R \mathcal{R} R x , x ′ \mathbf{x},\mathbf{x}' x , x ′ x i = x i ′ x_i = x'_i x i = x i ′ n n n M M M ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) x , x ′ \mathbf{x},\mathbf{x}' x , x ′ E ⊆ R E \subseteq\mathcal{R} E ⊆ R
Pr [ M ( x ) ∈ E ] ≤ e ε ⋅ Pr [ M ( x ′ ) ∈ E ] + δ . \Pr[M(\mathbf{x}) \in E] \le e^\varepsilon\cdot\Pr[M(\mathbf{x}') \in E] + \delta. Pr [ M ( x ) ∈ E ] ≤ e ε ⋅ Pr [ M ( x ′ ) ∈ E ] + δ . When an algorithm is ( ε , 0 ) (\varepsilon,0) ( ε , 0 ) ε \varepsilon ε
Shuffle model. In the shuffle model, each individual user first randomizes their own data into one or more messages. These messages are then sent to a secure shuffler, which aggregates and randomly permutes all user messages. The shuffle model considers an attacker who only sees the collection of messages after the permutation and thus, the set of shuffled messages must satisfy differential privacy. Equivalently, an attacker can only observe the histogram of the messages. Formally, we have the following definition:
Definition 3.2 (Shuffle model of differential privacy). In the shuffle model of privacy, a protocol Π \Pi Π
A randomizer Π R : X → Y ∗ \Pi_{\mathrm{R}} : \mathcal{X} \to\mathcal{Y}^{*} Π R : X → Y ∗ 1 1 1
A shuffler Π S : Y ∗ → Y ∗ \Pi_{\mathrm{S}} : \mathcal{Y}^{*} \to\mathcal{Y}^{*} Π S : Y ∗ → Y ∗
An analyzer Π A : Y ∗ → O \Pi_{\mathrm{A}} : \mathcal{Y}^{*} \to\mathcal{O} Π A : Y ∗ → O
Since the shuffler is the same across all protocols, we use Π = ( Π R , Π A ) \Pi= (\Pi_{\mathrm{R}}, \Pi_{\mathrm{A}}) Π = ( Π R , Π A ) Π \Pi Π x ∈ X n x \in\mathcal{X}^{n} x ∈ X n Π ( x ) = Π A ( Π S ( Π R ( x 1 ) , … , Π R ( x n ) ) ) \Pi(x) = \Pi_{\mathrm{A}}(\Pi_{\mathrm{S}}(\Pi_{\mathrm{R}}(x_{1}), \ldots, \Pi_{\mathrm{R}}(x_{n}))) Π ( x ) = Π A ( Π S ( Π R ( x 1 ) , … , Π R ( x n ))) ( Π S ∘ Π R n ) ( x ) : = Π S ( Π R ( x 1 ) , … , Π R ( x n ) ) (\Pi_{\mathrm{S}} \circ\Pi_{\mathrm{R}}^{n})(x) := \Pi_{\mathrm{S}}(\Pi_{\mathrm{R}}(x_{1}), \ldots, \Pi_{\mathrm{R}}(x_{n})) ( Π S ∘ Π R n ) ( x ) := Π S ( Π R ( x 1 ) , … , Π R ( x n ))
We remark on two existing lower bounds for selection in the shuffle model of privacy. We first recall the following lower bound by [20 ] :
Theorem 3.3 (Theorem 1.9 in [20 ] ). Any ( ε , δ ) (\varepsilon, \delta) ( ε , δ ) m m m d d d 1 10 \frac{1}{10} 10 1 Ω ( d m ) \Omega\left(\frac{d}{m}\right) Ω ( m d ) ε = O ( 1 ) \varepsilon= O(1) ε = O ( 1 ) δ = o ( 1 d ) \delta= o\left(\frac{1}{d}\right) δ = o ( d 1 )
Theorem 3.4 (Theorem 7.3 in [24 ] ). Any ( ε , δ ) (\varepsilon, \delta) ( ε , δ ) 1 3 \frac{1}{3} 3 1 d d d α \alpha α 99 / 100 99/100 99/100 Ω ( d α ε ) \Omega\left(\frac{\sqrt{d}}{\alpha\varepsilon}\right) Ω ( α ε d ) δ log d δ ≪ α 2 ε 2 d \delta\log\frac{d}{\delta} \ll\frac{\alpha^{2}\varepsilon^{2}}{d} δ log δ d ≪ d α 2 ε 2
Lower Bounds for Private Selection via Noisy Aggregates
The problem of private selection and its specific instantiations have been studied in a number of distributed models of computation. In this section, we review the known lower bounds that are most relevant to our setting. We then give a new lower bound for algorithms that rely on noisy aggregation. Specifically, we study algorithms whose only access to the dataset is through the noisy aggregation oracle defined in Definition 4.1 , i.e., through noisy values of ∑ i ∈ [ n ] ϕ ( x i ) \sum_{i \in[n]} \phi(x_i) ∑ i ∈ [ n ] ϕ ( x i ) ϕ : X → R k \phi: \mathcal{X} \to\mathbb{R}^{k} ϕ : X → R k k k k
Our lower bounds apply to algorithms that receive answers perturbed by standard Gaussian noise. This is both the most commonly used method in practice and the method that achieves an asymptotically tight privacy-utility trade-off (for expected squared L 2 L_2 L 2
We start by formally defining the Gaussian Aggregation oracle. For simplicity of presentation, we assume that each query given to the oracle has L 2 L_2 L 2 B 2 k ( 1 ) = { x ∈ R k ∣ ∥ x ∥ 2 ≤ 1 } B_2^k(1)=\{x\in\mathbb{R}^k\mid\lVert x\rVert_2\le1\} B 2 k ( 1 ) = { x ∈ R k ∣ ∥ x ∥ 2 ≤ 1 }
Definition 4.1. For the input dataset S = ( x 1 , … , x n ) S=(x_1,\ldots,x_n) S = ( x 1 , … , x n ) G ( S ) \mathcal{G}(S) G ( S ) S S S ϕ : X → B 2 k ( 1 ) \phi:\mathcal{X}\to B_2^k(1) ϕ : X → B 2 k ( 1 ) σ > 0 \sigma>0 σ > 0 N ( ϕ ( S ) , σ 2 I k ) \mathcal{N}(\phi(S),\sigma^2 I_k) N ( ϕ ( S ) , σ 2 I k ) ϕ ( S ) = ∑ i ∈ [ n ] ϕ ( x i ) \phi(S)=\sum_{i\in[n]}\phi(x_i) ϕ ( S ) = ∑ i ∈ [ n ] ϕ ( x i )
The privacy properties of a single answer to such a query are well-known. Most conveniently for applications involving composition, a single answer satisfies 2 / σ 2 2/\sigma^2 2/ σ 2 [15 ] . We assume that privacy bounds for an algorithm with access to the Gaussian Aggregation oracle are derived directly from (advanced) composition of individual privacy guarantees. Following an analogous notion in [49 ] , we refer to such privacy guarantees as compositional .
Definition 4.2. Let A \mathcal{A} A G ( S ) \mathcal{G}(S) G ( S ) t t t σ 1 , … , σ t \sigma_1,\ldots,\sigma_t σ 1 , … , σ t A \mathcal{A} A ρ \rho ρ ρ 1 = 2 / σ 1 2 , … , ρ t = 2 / σ t 2 \rho_1=2/\sigma_1^2,\ldots,\rho_t=2/\sigma_t^2 ρ 1 = 2/ σ 1 2 , … , ρ t = 2/ σ t 2 ∑ i ≤ t ρ i ≤ ρ \sum_{i\le t}\rho_i\le\rho ∑ i ≤ t ρ i ≤ ρ
We remark that, for simplicity, in this definition the noise scales are chosen non-adaptively, since that is required by the standard composition results for Renyi DP [55 , 15 ] , and standard applications such as DP-SGD do not need adaptive choice of noise scales. However, using fully adaptive composition results for RDP with a Renyi filter [42 ] , we can also allow the noise scales to be chosen adaptively (with the filter ensuring the condition ∑ i ≤ t ρ i ≤ ρ \sum_{i\le t}\rho_i\le\rho ∑ i ≤ t ρ i ≤ ρ
Our lower bound for selection for d d d 1 / 2 1/2 1/2 1 1 1 i i i d d d X i X^i X i j j j j j j X j i X^i_j X j i
Problem 4.3 (Sparse Boolean distinguishing). For Z ∈ { 1 , 2 } Z\in\{1,2\} Z ∈ { 1 , 2 } V ∈ [ d ] V\in[d] V ∈ [ d ] D Z , V D_{Z,V} D Z , V { 0 , 1 } d \{0,1\}^d { 0 , 1 } d Z = 2 Z=2 Z = 2 D Z , V D_{Z,V} D Z , V { 0 , 1 } d \{0,1\}^d { 0 , 1 } d Z = 1 Z=1 Z = 1 D Z , V D_{Z,V} D Z , V { x ∈ { 0 , 1 } d : x V = 1 } \{x\in\{0,1\}^d:x_V=1\} { x ∈ { 0 , 1 } d : x V = 1 } i i i X i X^i X i D Z , V D_{Z,V} D Z , V Z Z Z Z Z Z { 1 , 2 } \{1,2\} { 1 , 2 } V V V [ d ] [d] [ d ] 2 / 3 2/3 2/3 Z ^ \widehat{Z} Z Pr [ Z ^ = Z ] ≥ 2 / 3 \Pr[\widehat{Z}=Z]\ge2/3 Pr [ Z = Z ] ≥ 2/3
We now state our main lower bound for this problem.
Theorem 4.4. Every 2 / 3 2/3 2/3 Problem 4.3 ) that is given access to G ( S ) \mathcal{G}(S) G ( S ) ρ \rho ρ n = Ω ( d / ρ ) n=\Omega(\sqrt{d/\rho}) n = Ω ( d / ρ )
The key idea of our proof is to use the fact that the Gaussian Aggregation oracle can be implemented via distributed noise addition [28 ] . The transcript of this implementation satisfies privacy guarantees that are exactly n n n σ / n \sigma/\sqrt{n} σ / n ρ \rho ρ n ρ n\rho n ρ G G G
Lemma 4.5 ([28 ] ). Let A A A G ( S ) G(S) G ( S ) ρ \rho ρ n ρ n\rho n ρ D i s t \mathit{Dist} Dist A A A A A A
Proof. We provide a short, self-contained proof. In the distributed noise addition protocol of [28 ] , to simulate the Gaussian aggregation oracle, which adds noise N ( 0 , σ 2 I k ) \mathcal{N}(0,\sigma^2 I_k) N ( 0 , σ 2 I k ) n n n N ( 0 , ( σ 2 / n ) I k ) \mathcal{N}(0,(\sigma^2/n)I_k) N ( 0 , ( σ 2 / n ) I k ) n n n N ( 0 , σ 2 / n ) \mathcal{N}(0,\sigma^2/n) N ( 0 , σ 2 / n ) N ( 0 , σ 2 I k ) \mathcal{N}(0,\sigma^2 I_k) N ( 0 , σ 2 I k ) G ( S ) G(S) G ( S ) 2 2 2 σ 2 / n \sigma^2/n σ 2 / n n ρ n\rho n ρ
Therefore it suffices to prove lower bounds for local zCDP protocols. Lower bounds for such protocols that allow adaptive queries were first established by Duchi and Rogers [33 ] , building on the framework of Braverman et al. [10 ] . In particular, they show that constant-error 1-sparse Gaussian mean estimation requires Ω ( d / ρ l o c a l ) \Omega(d/\rho_{\mathrm{local}}) Ω ( d / ρ local ) ρ l o c a l \rho_{\mathrm{local}} ρ local d d d § 9 .
We also note that ρ \rho ρ ( ρ + 2 ρ log ( 1 / δ ) , δ ) (\rho+ 2\sqrt{\rho\log(1/\delta)},\delta) ( ρ + 2 ρ log ( 1/ δ ) , δ ) δ > 0 \delta> 0 δ > 0 [15 ] . Thus, if an algorithm derives an ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) ε ≤ 1 \varepsilon\leq1 ε ≤ 1 ρ ≤ ε 2 / ( 4 log ( 1 / δ ) ) \rho\leq\varepsilon^2/(4\log(1/\delta)) ρ ≤ ε 2 / ( 4 log ( 1/ δ )) Theorem 4.4 gives n = Ω ( d log ( 1 / δ ) / ε ) n = \Omega(\sqrt{d\log(1/\delta)}/\varepsilon) n = Ω ( d log ( 1/ δ ) / ε )
The SVT Primitive
We start by defining the expected behavior of our proposed SVT primitive. Informally, it takes as input a sequence of linear queries and thresholds, and up to a small additive error, the oracle outputs YES if f ( x 1 , … , x n ) ≥ τ f(x_1,\ldots,x_n) \geq\tau f ( x 1 , … , x n ) ≥ τ § 5.1 ), and a more general version that implements the BetweenThreshold algorithm of [17 ] (§ 5.2 ).
Initialize: Takes as input a privacy parameter ε \varepsilon ε Query: Takes as input a function f : X → [ 0 , 1 ] f : \mathcal{X} \to[0,1] f : X → [ 0 , 1 ] τ \tau τ ∑ i = 1 n f ( x i ) ≥ τ \sum_{i=1}^{n} f(x_i) \ge\tau ∑ i = 1 n f ( x i ) ≥ τ
( α , β ) (\alpha,\beta) ( α , β ) α \alpha α ( f , τ ) (f,\tau) ( f , τ ) ∑ i = 1 n f ( x i ) ≥ τ + α \sum_{i=1}^{n} f(x_i) \ge\tau+\alpha ∑ i = 1 n f ( x i ) ≥ τ + α ( f , τ ) (f,\tau) ( f , τ ) ∑ i = 1 n f ( x i ) ≤ τ − α \sum_{i=1}^{n} f(x_i) \le\tau-\alpha ∑ i = 1 n f ( x i ) ≤ τ − α ( α , β ) (\alpha,\beta) ( α , β ) α \alpha α β \beta β
Using such a primitive, one can design compositionally differentially private algorithms in a natural way, where the incurred privacy cost is computed by applying a composition theorem to the privacy cost of individual API calls. In the upper bounds presented in this work, we use basic composition for pure-DP selection and advanced composition for approximate-DP applications [32 ] .
One way to implement this primitive is to use the AboveThreshold algorithm, which satisfies ε \varepsilon ε ( α , β ) (\alpha,\beta) ( α , β ) K K K α = O ( log 2 ( K + 1 ) β / ε ) \alpha= O\left(\log\frac{2(K+1)}{\beta}/\varepsilon\right) α = O ( log β 2 ( K + 1 ) / ε ) [31 ] , and the formal description below is equivalent to the version in [32 ] .
Algorithm 1 SVTInit
Input: Privacy parameter ε \varepsilon ε
Output: Create an SVT object S
S . n ← Lap ( 2 ε ) S.n \leftarrow\operatorname{Lap}\left(\frac{2}{\varepsilon}\right) S . n ← Lap ( ε 2 )
S . ε ← ε S.\varepsilon\leftarrow\varepsilon S . ε ← ε
S . D o n e ← F a l s e S.Done \leftarrow False S . D o n e ← F a l se
Incur privacy cost ε \varepsilon ε
Algorithm 2 SVTQuery
Input: Handle S, Function f : X → R f : \mathcal{X} \to\mathbb{R} f : X → R τ ∈ R \tau\in\mathbb{R} τ ∈ R
Output: Output YES or NO.
if not S . D o n e S.Done S . D o n e
Compute f ( x ) = ∑ i clip [ 0 , 1 ] ( f ( x i ) ) f(\mathbf{x}) = \sum_i \operatorname{clip}_{[0,1]}(f(x_i)) f ( x ) = ∑ i clip [ 0 , 1 ] ( f ( x i ))
Sample u u u Lap ( 4 S . ε ) \operatorname{Lap}\left(\frac{4}{S.\varepsilon}\right) Lap ( S . ε 4 )
if f ( x ) + u > τ + S . n f(\mathbf{x}) + u > \tau+ S.n f ( x ) + u > τ + S . n
S . D o n e ← T r u e S.Done \leftarrow True S . D o n e ← T r u e
Return YES
else
Return NO
else
Return ERROR.
The following proofs can be found in [32 ] .
Theorem 5.1. SVT satisfies ε \varepsilon ε
Theorem 5.2. For any sequence of functions f 1 , … , f K : X → [ 0 , 1 ] f_1,\ldots,f_K : \mathcal{X} \to[0,1] f 1 , … , f K : X → [ 0 , 1 ] τ 1 , … , τ K \tau_1,\ldots,\tau_K τ 1 , … , τ K ( α , β ) (\alpha,\beta) ( α , β ) β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) K ≥ 1 K \ge1 K ≥ 1 α = 2 ε log 2 K β \alpha= \frac{2}{\varepsilon}\log\frac{2K}{\beta} α = ε 2 log β 2 K
The clipping step in Algorithm 2 ensures that every contribution lies in [ 0 , 1 ] [0,1] [ 0 , 1 ] f f f [ 0 , 1 ] [0,1] [ 0 , 1 ]
We describe various design choices for our formalization of the SVT primitive. First, our choice of an SVT-based API over a dedicated selection primitive merits justification. Our goal is to propose a primitive that is relatively simple to implement while still capturing the power used in most commonly used DP techniques. While selection is a more common task, it is not clear that it allows for the implementation of SVT, so SVT is arguably a more general primitive. Regardless, abstracting and understanding the relative power of different natural primitives is an important goal in itself.
Second, as defined, the AboveThreshold algorithm is well-defined for arbitrary sensitivity-1 queries, and indeed the privacy and utility guarantees in Theorem 5.1 and Theorem 5.2 hold in that generality. Our choice of restricting the functions f j ( ⋅ ) f_j(\cdot) f j ( ⋅ ) ∑ i f j ( x i ) \sum_i f_j(x_i) ∑ i f j ( x i ) § 5 and § 6 .
We can also define a “batch” version of the SVT primitive, where a sequence of queries is given in advance and the index of the first Yes, if any, is returned. This may be simpler to implement, as it does not need to retain internal state between API calls. In most settings, the batch and online versions are equivalent, except that the online version may be more communication efficient. One could also imagine algorithms that run multiple such SVT primitives in parallel, potentially with different parameters, and where composition could be analyzed using the concurrent composition theorems of [65 , 52 , 66 ] .
Implementation. The implementation of an SVT primitive will be a function of the specific trust model. A few different approaches have been studied for aggregation in the federated setting and we argue that these can accommodate the SVT primitive with relative ease.
The easiest approach is perhaps to use Trusted Execution Environments (TEEs), which have been proposed as an approach to implementing private federated algorithms in [JCM⁺24, ERB⁺24]. The simplicity of the SVT primitive makes it fairly well-suited for a TEE implementation, as it may be easy to verify the correctness of an implementation. While TEEs can in principle be used to implement general selection or even run an arbitrary central DP algorithm, the value of a minimal primitive like SVT is that it only needs to be audited and analyzed once. Running arbitrary analyst code inside the enclave makes the privacy guarantees depend on unaudited code, and both side-channel vulnerabilities and privacy budget state-continuity attacks [JCM⁺24] worsen as the trusted code base grows. In contrast, SVT’s trusted state is a single scalar and its logic spans just a few lines of code, which is why we consider it a realistic and highly secure basis for solving more general problems.
A different approach to federated aggregation is to use the two-server or Prio model [19 ] . There is a large body of work on this model, and differentially private aggregation in this setup has been studied by [TWM⁺24]. In the two-party settings, noise addition requires some care: there are multiple algorithms for federative noise addition, e.g., Franzese et al. [FFG⁺25], though a simple approach is for both servers to independently add scaled noise. Existing aggregation approaches already allow the two servers to very efficiently construct secret shares of the f j ( x ) f_j(x) f j ( x ) f j ( x i ) f_j(x_i) f j ( x i ) γ \gamma γ ν j \nu_j ν j [2 ] implement these ingredients in the same model.
An alternative approach, potentially combining trust models, is to use a TEE for the comparison part. This has the advantage that the input to the TEE, namely the secret shares of f j ( x ) f_j(x) f j ( x ) n n n f j ( x ) f_j(x) f j ( x ) [13 ] ). There are many approaches to secure noise generation in the MPC model, and the comparison operation can be implemented using general MPC. In all of these approaches, we exploit the fact that the computation of f j ( x ) f_j(x) f j ( x ) n n n
Finally, we remark that SVT is significantly easier to implement securely than a general selection API. General selection requires arbitrary score functions as input, whereas each SVT query deals with a single score function at a time. This allows for much simpler cryptographic implementations; for example, if garbled circuits were used to implement selection, then Argmax would need to be securely solved over an arbitrary number of candidates. Indeed, [DKN+24] noted that “the bottleneck in the secure computation protocol is the comparisons required to compute argmax.” Each candidate set size would require a different circuit, further making verification and auditing harder. Moreover, the secure part of the computation invariably adds non-trivial “constant” overheads. Because SVT processes a single score function at a time and returns a boolean threshold comparison, it allows the analyst to perform the Argmax outside of the cryptographic boundary, resulting in significant computational savings.
A Batch Version
Here, we define a batch version of the SVT primitive, where one inputs a sequence of queries ( f , τ ) (f,\tau) ( f , τ )
Input: A sequence of functions f 1 , … , f K : X → [ 0 , 1 ] f_1,\ldots,f_K:\mathcal{X}\to[0,1] f 1 , … , f K : X → [ 0 , 1 ] τ 1 , … , τ K \tau_1,\ldots,\tau_K τ 1 , … , τ K ε \varepsilon ε
Output: An output o ∈ [ K ] ∪ { ⊥ } o\in[K]\cup\{\perp\} o ∈ [ K ] ∪ { ⊥ }
( α , β ) (\alpha,\beta) ( α , β ) Accuracy Property: For j ∈ [ K ] j\in[K] j ∈ [ K ] x ∈ X n x\in\mathcal{X}^n x ∈ X n f j ( x ) = ∑ i f j ( x i ) f_j(x)=\sum_i f_j(x_i) f j ( x ) = ∑ i f j ( x i ) o ∈ [ K ] ∪ { ⊥ } o\in[K]\cup\{\perp\} o ∈ [ K ] ∪ { ⊥ } α \alpha α x x x o = ⊥ o=\perp o =⊥ f j ( x ) ≤ τ j + α f_j(x)\leq\tau_j+\alpha f j ( x ) ≤ τ j + α j ∈ [ K ] j\in[K] j ∈ [ K ] o ∈ [ K ] o\in[K] o ∈ [ K ] f j ( x ) ≤ τ j + α f_j(x)\leq\tau_j+\alpha f j ( x ) ≤ τ j + α j < o j<o j < o f o ( x ) ≥ τ o − α f_o(x)\geq\tau_o-\alpha f o ( x ) ≥ τ o − α ( α , β ) (\alpha,\beta) ( α , β ) α \alpha α β \beta β
As in the online case, this batch version can be implemented using AboveThreshold. This batch version has the advantage of not needing to retain internal state between API calls.
A More Powerful Variant
Next we present a more general primitive that may be amenable to similar implementation techniques as our simple SVT primitive.
Our more general primitive will allow the query to specify two thresholds ( τ L , τ H ) (\tau^L,\tau^H) ( τ L , τ H ) f f f f ( x ) f(x) f ( x ) τ L \tau^L τ L τ H \tau^{H} τ H
Algorithm 3 AboveThreshold
Input: Dataset x ∈ X n \mathbf{x} \in\mathcal{X}^{n} x ∈ X n f 1 , … , f K : X → [ 0 , 1 ] f_{1},\ldots,f_{K}:\mathcal{X}\to[0,1] f 1 , … , f K : X → [ 0 , 1 ] τ 1 , … , τ K \tau_{1},\ldots,\tau_{K} τ 1 , … , τ K ε \varepsilon ε
Output: Output o ∈ [ K ] ∪ { ⊥ } o \in[K]\cup\{\bot\} o ∈ [ K ] ∪ { ⊥ }
γ ← Lap ( 2 ε ) \gamma\leftarrow\operatorname{Lap}\left(\frac{2}{\varepsilon}\right) γ ← Lap ( ε 2 )
for j = 1 , 2 , … , K j=1,2,\ldots,K j = 1 , 2 , … , K do
f j ( x ) ← ∑ i f j ( x i ) f_{j}(\mathbf{x})\leftarrow\sum_{i}f_{j}(x_{i}) f j ( x ) ← ∑ i f j ( x i )
ν j ← Lap ( 4 ε ) \nu_{j}\leftarrow\operatorname{Lap}\left(\frac{4}{\varepsilon}\right) ν j ← Lap ( ε 4 )
if f j ( x ) + ν j ≥ τ j + γ f_{j}(\mathbf{x})+\nu_{j}\geq\tau_{j}+\gamma f j ( x ) + ν j ≥ τ j + γ then
Return j j j
Return ⊥ \bot ⊥
Algorithm 4 CompareToThresholdsInit
Input: Privacy parameters ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 )
Output: Create a CompareToThresholds Object CTT
C T T . n ← Lap ( 2 ε ) \mathrm{CTT}.n\leftarrow\operatorname{Lap}\left(\frac{2}{\varepsilon}\right) CTT . n ← Lap ( ε 2 )
C T T . ε = ε \mathrm{CTT}.\varepsilon=\varepsilon CTT . ε = ε
C T T . g a p = 12 ε ( log 10 ε + log 1 δ + 1 ) \mathrm{CTT}.gap=\frac{12}{\varepsilon}\left(\log\frac{10}{\varepsilon}+\log\frac{1}{\delta}+1\right) CTT . g a p = ε 12 ( log ε 10 + log δ 1 + 1 )
C T T . D o n e ← F a l s e \mathrm{CTT}.Done\leftarrow False CTT . D o n e ← F a l se
Incur privacy cost ( ε , δ ) (\varepsilon,\delta) ( ε , δ )
Algorithm 5 CompareToThresholdsQuery
Input: Handle CTT, Function f : X → R f:\mathcal{X}\to\mathbb{R} f : X → R τ L , τ H ∈ R \tau^{L},\tau^{H}\in\mathbb{R} τ L , τ H ∈ R x \mathbf{x} x
Output: Output Low, High, or Close.
if not CTT.D o n e Done D o n e τ H − τ L ≥ C T T . g a p \tau^{H}-\tau^{L}\geq\mathrm{CTT}.gap τ H − τ L ≥ CTT . g a p then
Compute f ( x ) = ∑ i clip [ 0 , 1 ] ( f ( x i ) ) f(\mathbf{x})=\sum_{i}\operatorname{clip}_{[0,1]}(f(x_{i})) f ( x ) = ∑ i clip [ 0 , 1 ] ( f ( x i ))
Sample u u u Lap ( 6 C T T . ε ) \operatorname{Lap}\left(\frac{6}{\mathrm{CTT}.\varepsilon}\right) Lap ( CTT . ε 6 )
if f ( x ) + u > τ H − C T T . n f(\mathbf{x})+u>\tau^{H}-\mathrm{CTT}.n f ( x ) + u > τ H − CTT . n then
Return High
if f ( x ) + u < τ L + C T T . n f(\mathbf{x})+u<\tau^{L}+\mathrm{CTT}.n f ( x ) + u < τ L + CTT . n then
Return Low
C T T . D o n e ← T r u e \mathrm{CTT}.Done\leftarrow True CTT . D o n e ← T r u e
Return Close
else
Return ERROR.
This variant satisfies ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) [17 ] .
Selection in the SVT Model
In this section we give differentially private algorithms for the selection problem in the SVT model. We first describe a simple binary search over the range of the scores (Algorithm 6), which uses O ( d log n ) O(d\log n) O ( d log n ) log n \log n log n O ( d n ) O(dn) O ( d n ) log n \log n log n O ( d log n ) O(d\log n) O ( d log n ) § 6.3 we combine sampling with a filtering pass to obtain the same error using O ( d log ∗ n + log 3 n ) O(d\log^* n+\log^3 n) O ( d log ∗ n + log 3 n ) [ 0 , 1 ] [0,1] [ 0 , 1 ] [ 0 , Δ ] [0,\Delta] [ 0 , Δ ] Δ \Delta Δ Δ \Delta Δ
Algorithm 6 Private binary search
Input: Oracle O \mathcal{O} O [ ℓ , u ] = [ 0 , n ] [\ell,u]=[0,n] [ ℓ , u ] = [ 0 , n ] α ≥ 1 \alpha\geq1 α ≥ 1
Output: Index j j j s ( v j ) s(v_j) s ( v j )
m ← u + ℓ 2 m\leftarrow\frac{u+\ell}{2} m ← 2 u + ℓ
Query oracle O \mathcal{O} O 1 , 2 , … , d 1,2,\ldots,d 1 , 2 , … , d m m m
If returned index j < d j<d j < d O \mathcal{O} O j + 1 , … , d j+1,\ldots,d j + 1 , … , d m m m
if exactly one index in [ d ] [d] [ d ]
Return that index ▷Only one positive answer; its score is within 2 α 2\alpha 2 α
else if two indices returned then
ℓ ← m − α \ell\leftarrow m-\alpha ℓ ← m − α ≥ m \geq m ≥ m
else
u ← m + α u\leftarrow m+\alpha u ← m + α ≤ m \leq m ≤ m
if u − ℓ > 3 α u-\ell>3\alpha u − ℓ > 3 α
Recurse to find index for upper and lower limits [ ℓ , u ] [\ell,u] [ ℓ , u ]
else
Return the last returned index, or arbitrary index if no indices returned.
The algorithm appears in full in Algorithm 6 and can be informally interpreted as a binary search over the set of possible scores for the index with the maximum score. At a high level, we design a private selection procedure that repeatedly performs noisy threshold comparisons to narrow down the range of possible values for the maximum score, and isolate a high-scoring coordinate. Rather than explicitly evaluating all scores with independent noise, as in the naïve Laplace mechanism, the algorithm adaptively compares against a threshold using the SVT primitive. This approach allows us to limit privacy loss to the relatively small number of times the algorithm observes that a score exceeds a threshold, while ignoring the vast majority of coordinates whose scores are clearly suboptimal.
Concretely, the algorithm maintains a candidate interval for the maximum score and performs a logarithmic number of rounds. In each round, it picks the mid point of the current interval where the maximum lies and scans the coordinates in their given order using the SVT primitive. Based on whether zero, one, or multiple coordinates cross the threshold, the algorithm refines its estimate of the maximum and continues.
If the current width is W W W W / 2 + α W/2+\alpha W /2 + α [ ℓ , u ] = [ 0 , n ] [\ell,u]=[0,n] [ ℓ , u ] = [ 0 , n ] α ≥ 1 \alpha\ge1 α ≥ 1 R = ⌈ log 2 ( 2 n ) ⌉ + 1 R=\lceil\log_2(2n)\rceil+1 R = ⌈ log 2 ( 2 n )⌉ + 1 d d d ε / ( 2 R ) \varepsilon/(2R) ε / ( 2 R ) ε \varepsilon ε
Assuming that the SVT oracle is ( α , β ) (\alpha,\beta) ( α , β ) 2 R 2R 2 R α \alpha α 2 R β 2R\beta 2 R β d d d m m m m + α m+\alpha m + α m m m m − α m-\alpha m − α [ ℓ , u ] [\ell,u] [ ℓ , u ] m m m 2 α 2\alpha 2 α u − ℓ u-\ell u − ℓ 3 α 3\alpha 3 α [ ℓ , u ] [\ell,u] [ ℓ , u ] ℓ \ell ℓ O ( α ) O(\alpha) O ( α ) ( O ( log ( d / β ) ε ) , β ) (O(\frac{\log(d/\beta)}{\varepsilon}),\beta) ( O ( ε l o g ( d / β ) ) , β ) ε \varepsilon ε
Theorem 6.1. For d ≥ 2 d\ge2 d ≥ 2 n ≥ 1 n\ge1 n ≥ 1 0 < ε ≤ 1 0<\varepsilon\le1 0 < ε ≤ 1 β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) ε / ( 2 R ) \varepsilon/(2R) ε / ( 2 R ) ε \varepsilon ε O ( log ( 2 n ) log ( 2 d log ( 2 n ) / β ) / ε ) O(\log(2n)\log(2d\log(2n)/\beta)/\varepsilon) O ( log ( 2 n ) log ( 2 d log ( 2 n ) / β ) / ε ) 1 − β 1-\beta 1 − β O ( d log ( 2 n ) ) O(d\log(2n)) O ( d log ( 2 n ))
Corollary 6.2. Given an oracle O \mathbb{O} O ( α , β ) (\alpha,\beta) ( α , β ) α = O ( log d ε ) \alpha=O(\frac{\log d}{\varepsilon}) α = O ( ε l o g d ) β = 1 poly ( d ) \beta=\frac{1}{\operatorname{poly}(d)} β = poly ( d ) 1 ε \varepsilon ε
Unfortunately, the additive error of this binary search approach is O ( log d log n ε ) O(\frac{\log d\log n}{\varepsilon}) O ( ε l o g d l o g n ) O ( log d ε ) O(\frac{\log d}{\varepsilon}) O ( ε l o g d ) O ( log n ) O(\log n) O ( log n ) O ( log d ε ) O(\frac{\log d}{\varepsilon}) O ( ε l o g d )
Linear Scan
We first observe that a simple linear scan can achieve an optimal additive error. Namely, the protocol simply starts from the maximum possible score of an index and repeatedly calls the SVT API. For each query where the SVT API does not return a coordinate, the protocol decreases the guess for the maximum possible score of an index, repeating until the guess is within the typical bounds for Laplacian noise added to the score of the maximum coordinate. Since this approach will report only a single coordinate from the SVT API, it spends less privacy budget than the binary search approach. Assuming the score for each user is normalized to [ 0 , 1 ] [0,1] [ 0 , 1 ]
Theorem 6.3. For n ≥ 1 n\ge1 n ≥ 1 d ≥ 2 d\ge2 d ≥ 2 β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) [ ℓ , u ] = [ 0 , n ] [\ell,u]=[0,n] [ ℓ , u ] = [ 0 , n ] ε \varepsilon ε ε \varepsilon ε O ( 1 + log ( d ( n + 1 ) / β ) / ε ) O(1+\log(d(n+1)/\beta)/\varepsilon) O ( 1 + log ( d ( n + 1 ) / β ) / ε ) 1 − β 1-\beta 1 − β O ( d ( n + 1 ) ) O(d(n+1)) O ( d ( n + 1 ))
Proof. Privacy follows from the fact that we run exactly one SVT oracle, and stop once we get one score above the threshold. The accuracy bound follows from the fact that we use decreasing thresholds and the SVT oracle is α \alpha α [ 0 , 1 ] [0,1] [ 0 , 1 ] [ 0 , n ] [0,n] [ 0 , n ] n n n 0 0 0 d d d O ( n d ) O(nd) O ( n d )
Algorithm 7 Private linear scan
Input: Oracle O \mathcal{O} O u u u ℓ \ell ℓ
Output: Index j ∈ [ d ] j \in[d] j ∈ [ d ]
for m ← u , u − 1 , u − 2 , … , ℓ m \leftarrow u, u-1, u-2, \ldots, \ell m ← u , u − 1 , u − 2 , … , ℓ
Query the same initialized SVT stream O \mathcal{O} O m m m j ∈ [ d ] j \in[d] j ∈ [ d ]
if an index j ∈ [ d ] j \in[d] j ∈ [ d ] then
Return j j j
Return an arbitrary index in [ d ] [d] [ d ]
Improved Binary Search
The downside is that to achieve the additive error O ( 1 + log ( d ( n + 1 ) / β ) / ε ) O(1+\log(d(n+1)/\beta)/\varepsilon) O ( 1 + log ( d ( n + 1 ) / β ) / ε ) O ( n d ) O(nd) O ( n d ) O ( d log n ) O(d\log n) O ( d log n ) O ( log d log n / ε ) O(\log d\log n/\varepsilon) O ( log d log n / ε ) log n \log n log n O ( d log n ) O(d\log n) O ( d log n ) t t t γ T − t \gamma^{T-t} γ T − t γ = 3 / 4 \gamma=3/4 γ = 3/4 ( 2 γ ) − ( T − t ) (2\gamma)^{-(T-t)} ( 2 γ ) − ( T − t ) P P P u u u P P P ℓ \ell ℓ § 6.3 and in § 7 .
We next analyze Algorithm 8. Let E \mathcal{E} E T T T β T \frac{\beta}{T} T β Pr [ E ] ≥ 1 − β \Pr[\mathcal{E}] \ge1-\beta Pr [ E ] ≥ 1 − β E \mathcal{E} E
Lemma 6.4. For all t ∈ [ T + 1 ] t \in[T+1] t ∈ [ T + 1 ] s j ⋆ ( D ) ≥ ℓ t s_{j^\star}(D) \ge\ell_t s j ⋆ ( D ) ≥ ℓ t S ⋆ ≤ u t S^\star\le u_t S ⋆ ≤ u t S ⋆ = max j ∈ P s j ( D ) S^\star=\max_{j\in P}s_j(D) S ⋆ = max j ∈ P s j ( D )
Proof. We prove the claim by induction on t t t t = 1 t=1 t = 1 s j ⋆ ( D ) = s j 0 ( D ) ≥ ℓ = ℓ 1 s_{j^\star}(D)=s_{j_0}(D)\ge\ell=\ell_1 s j ⋆ ( D ) = s j 0 ( D ) ≥ ℓ = ℓ 1 S ⋆ ≤ u = u 1 S^\star\le u=u_1 S ⋆ ≤ u = u 1 t t t m t = ( ℓ t + u t ) / 2 m_t=(\ell_t+u_t)/2 m t = ( ℓ t + u t ) /2 S ⋆ ≤ m t + α t S^\star\le m_t+\alpha_t S ⋆ ≤ m t + α t
S ⋆ ≤ min { u t , m t + α t } = u t + 1 . S^\star\le\min\{u_t,m_t+\alpha_t\}=u_{t+1}. S ⋆ ≤ min { u t , m t + α t } = u t + 1 . We also have ℓ t + 1 = ℓ t \ell_{t+1}=\ell_t ℓ t + 1 = ℓ t
On the other hand, if index j j j s j ( D ) ≥ m t − α t s_j(D)\ge m_t-\alpha_t s j ( D ) ≥ m t − α t m t − α t > ℓ t m_t-\alpha_t>\ell_t m t − α t > ℓ t ℓ t + 1 = m t − α t \ell_{t+1}=m_t-\alpha_t ℓ t + 1 = m t − α t j ⋆ = j j^\star=j j ⋆ = j s j ⋆ ( D ) ≥ ℓ t + 1 s_{j^\star}(D)\ge\ell_{t+1} s j ⋆ ( D ) ≥ ℓ t + 1 ℓ t + 1 = ℓ t \ell_{t+1}=\ell_t ℓ t + 1 = ℓ t u t + 1 = u t u_{t+1}=u_t u t + 1 = u t
We next bound the size of the search space, showing that it geometrically decreases at each step t ∈ [ T ] t\in[T] t ∈ [ T ]
Lemma 6.5. Let W t = u t − ℓ t W_t=u_t-\ell_t W t = u t − ℓ t t ≤ T t\le T t ≤ T W t + 1 ≤ W t 2 + α t W_{t+1}\le\frac{W_t}{2}+\alpha_t W t + 1 ≤ 2 W t + α t
Algorithm 8 Private geometric binary search (GeometricBinarySearch)
Input: Oracle O \mathcal{O} O P ⊆ [ d ] P \subseteq[d] P ⊆ [ d ] [ ℓ , u ] [\ell,u] [ ℓ , u ] max j ∈ P s j ( D ) ≤ u \max_{j\in P}s_j(D)\leq u max j ∈ P s j ( D ) ≤ u j 0 ∈ [ d ] j_0\in[d] j 0 ∈ [ d ] ℓ ≤ s j 0 ( D ) \ell\leq s_{j_0}(D) ℓ ≤ s j 0 ( D ) T ≥ 1 T\geq1 T ≥ 1 ε > 0 \varepsilon>0 ε > 0 β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 )
Output: Index j ⋆ j^\star j ⋆ [ ℓ , u ] [\ell,u] [ ℓ , u ] s j ⋆ ( D ) ≥ ℓ s_{j^\star}(D)\geq\ell s j ⋆ ( D ) ≥ ℓ max j ∈ P s j ( D ) ≤ u \max_{j\in P}s_j(D)\leq u max j ∈ P s j ( D ) ≤ u
γ ← 3 / 4 \gamma\leftarrow3/4 γ ← 3/4 Z ← 1 − γ T 1 − γ Z\leftarrow\frac{1-\gamma^T}{1-\gamma} Z ← 1 − γ 1 − γ T j ⋆ ← j 0 j^\star\leftarrow j_0 j ⋆ ← j 0
for t = 1 , … , T t=1,\ldots,T t = 1 , … , T do
ε t ← ε Z γ T − t \varepsilon_t\leftarrow\frac{\varepsilon}{Z} \gamma^{T-t} ε t ← Z ε γ T − t
α t ← 32 ε t log ( 2 ∣ P ∣ T β ) \alpha_t\leftarrow\frac{32}{\varepsilon_t}\log\left(\frac{2|P|T}{\beta}\right) α t ← ε t 32 log ( β 2∣ P ∣ T )
m ← ℓ + u 2 m\leftarrow\frac{\ell+u}{2} m ← 2 ℓ + u
Query oracle O \mathcal{O} O P P P m m m ε t \varepsilon_t ε t β / T \beta/T β / T
if no index returned then
u ← min { u , m + α t } u\leftarrow\min\{u,m+\alpha_t\} u ← min { u , m + α t } ≲ m \lesssim m ≲ m
else (oracle returns index j j j
if m − α t > ℓ m-\alpha_t>\ell m − α t > ℓ then
ℓ ← m − α t \ell\leftarrow m-\alpha_t ℓ ← m − α t
j ⋆ ← j j^\star\leftarrow j j ⋆ ← j
Return ( j ⋆ , ℓ , u ) (j^\star,\ell,u) ( j ⋆ , ℓ , u )
Proof. Since m t = ℓ t + u t 2 m_t=\frac{\ell_t+u_t}{2} m t = 2 ℓ t + u t
m t − ℓ t = u t − m t = W t 2 . m_t-\ell_t=u_t-m_t=\frac{W_t}{2}. m t − ℓ t = u t − m t = 2 W t . Now, if no index is returned, then we have
W t + 1 = u t + 1 − ℓ t ≤ ( m t + α t ) − ℓ t = W t 2 + α t . W_{t+1}=u_{t+1}-\ell_t\leq(m_t+\alpha_t)-\ell_t=\frac{W_t}{2}+\alpha_t. W t + 1 = u t + 1 − ℓ t ≤ ( m t + α t ) − ℓ t = 2 W t + α t . Otherwise, if an index is returned, we have
W t + 1 = u t − ℓ t + 1 ≤ u t − ( m t − α t ) = W t 2 + α t . W_{t+1}=u_t-\ell_{t+1}\leq u_t-(m_t-\alpha_t)=\frac{W_t}{2}+\alpha_t. W t + 1 = u t − ℓ t + 1 ≤ u t − ( m t − α t ) = 2 W t + α t . The following theorem summarizes the guarantees of Algorithm 8.
Theorem 6.6. Algorithm 8 is ε \varepsilon ε ∣ P ∣ T |P|T ∣ P ∣ T W = u − ℓ W=u-\ell W = u − ℓ 1 − β 1-\beta 1 − β ( j ⋆ , ℓ ′ , u ′ ) (j^\star,\ell',u') ( j ⋆ , ℓ ′ , u ′ ) s j ⋆ ( D ) ≥ ℓ ′ s_{j^\star}(D)\geq\ell' s j ⋆ ( D ) ≥ ℓ ′ max j ∈ P s j ( D ) ≤ u ′ \max_{j\in P}s_j(D)\leq u' max j ∈ P s j ( D ) ≤ u ′
u ′ − ℓ ′ ≤ W 2 T + 384 ε log ( 2 ∣ P ∣ T β ) . u'-\ell'\leq\frac{W}{2^T}+\frac{384}{\varepsilon}\log\left(\frac{2|P|T}{\beta}\right). u ′ − ℓ ′ ≤ 2 T W + ε 384 log ( β 2∣ P ∣ T ) . In particular , for P = [ d ] P=[d] P = [ d ] [ ℓ , u ] = [ 0 , n ] [\ell,u]=[0,n] [ ℓ , u ] = [ 0 , n ] j 0 = 1 j_0=1 j 0 = 1 T = max { 1 , ⌈ log 2 n ⌉ } T=\max\{1,\lceil\log_2 n\rceil\} T = max { 1 , ⌈ log 2 n ⌉} 1 − β 1-\beta 1 − β
S ⋆ − s j ⋆ ( D ) ≤ 1 + 384 ε log ( 2 d ( 1 + log 2 n ) β ) . S^\star-s_{j^\star}(D)\leq1+\frac{384}{\varepsilon}\log\left(\frac{2d(1+\log_2 n)}{\beta}\right). S ⋆ − s j ⋆ ( D ) ≤ 1 + ε 384 log ( β 2 d ( 1 + log 2 n ) ) . Proof. Algorithm 8 accesses the data only through T T T t t t ε t \varepsilon_t ε t ∣ P ∣ |P| ∣ P ∣ Z Z Z ∑ t ∈ [ T ] ε t = ε \sum_{t\in[T]} \varepsilon_t=\varepsilon ∑ t ∈ [ T ] ε t = ε E \mathcal{E} E
S ⋆ − s j ⋆ ( D ) ≤ u T + 1 − ℓ T + 1 = W T + 1 . S^\star-s_{j^\star}(D)\leq u_{T+1}-\ell_{T+1}=W_{T+1}. S ⋆ − s j ⋆ ( D ) ≤ u T + 1 − ℓ T + 1 = W T + 1 . By Lemma 6.5 , we have
W T + 1 ≤ W 1 2 T + ∑ t = 1 T α t 2 T − t . W_{T+1}\leq\frac{W_1}{2^T}+\sum_{t=1}^{T}\frac{\alpha_t}{2^{T-t}}. W T + 1 ≤ 2 T W 1 + t = 1 ∑ T 2 T − t α t . Since α t = 32 ε t log ( 2 ∣ P ∣ T β ) = 32 Z ε γ − ( T − t ) log ( 2 ∣ P ∣ T β ) \alpha_t=\frac{32}{\varepsilon_t}\log\left(\frac{2|P|T}{\beta}\right)=\frac{32Z}{\varepsilon}\gamma^{-(T-t)}\log\left(\frac{2|P|T}{\beta}\right) α t = ε t 32 log ( β 2∣ P ∣ T ) = ε 32 Z γ − ( T − t ) log ( β 2∣ P ∣ T )
∑ t = 1 T α t 2 T − t = 32 Z ε log ( 2 ∣ P ∣ T β ) ∑ k = 0 T − 1 ( 2 γ ) − k ≤ 384 ε log ( 2 ∣ P ∣ T β ) , \sum_{t=1}^{T}\frac{\alpha_t}{2^{T-t}}=\frac{32Z}{\varepsilon}\log\left(\frac{2|P|T}{\beta}\right)\sum_{k=0}^{T-1}(2\gamma)^{-k}\leq\frac{384}{\varepsilon}\log\left(\frac{2|P|T}{\beta}\right), t = 1 ∑ T 2 T − t α t = ε 32 Z log ( β 2∣ P ∣ T ) k = 0 ∑ T − 1 ( 2 γ ) − k ≤ ε 384 log ( β 2∣ P ∣ T ) , where we used that Z ≤ 1 1 − γ = 4 Z\leq\frac{1}{1-\gamma}=4 Z ≤ 1 − γ 1 = 4 ∑ k ≥ 0 ( 2 γ ) − k = 3 \sum_{k\geq0}(2\gamma)^{-k}=3 ∑ k ≥ 0 ( 2 γ ) − k = 3 W 1 = n ≤ 2 T W_1=n\leq2^T W 1 = n ≤ 2 T T ≤ 1 + log 2 n T\leq1+\log_2 n T ≤ 1 + log 2 n
Corollary 6.7. If d ≥ 2 d\geq2 d ≥ 2 0 < ε ≤ 1 0<\varepsilon\leq1 0 < ε ≤ 1 β = d − c \beta=d^{-c} β = d − c c > 0 c>0 c > 0 n ≤ e poly ( d ) n\leq e^{\operatorname{poly}(d)} n ≤ e poly ( d ) P = [ d ] P=[d] P = [ d ] [ ℓ , u ] = [ 0 , n ] [\ell,u]=[0,n] [ ℓ , u ] = [ 0 , n ] j 0 = 1 j_0=1 j 0 = 1 T = max { 1 , ⌈ log 2 n ⌉ } T=\max\{1,\lceil\log_2 n\rceil\} T = max { 1 , ⌈ log 2 n ⌉} O ( d log n ) O(d\log n) O ( d log n ) 1 − β 1-\beta 1 − β j ⋆ j^\star j ⋆
S ⋆ − s j ⋆ ( D ) = O ( log d ε ) . S^\star-s_{j^\star}(D)=O\left(\frac{\log d}{\varepsilon}\right). S ⋆ − s j ⋆ ( D ) = O ( ε log d ) . Running Algorithm 8 on a single candidate gives a simple way to privately estimate a sum using the SVT API, which we use in § 7 .
Corollary 6.8. Let f : X → [ 0 , 1 ] f:\mathcal{X}\to[0,1] f : X → [ 0 , 1 ] ε > 0 \varepsilon>0 ε > 0 β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) T = max { 1 , ⌈ log 2 n ⌉ } T=\max\{1,\lceil\log_2 n\rceil\} T = max { 1 , ⌈ log 2 n ⌉} ε \varepsilon ε T T T 1 − β 1-\beta 1 − β 1 + 384 ε log 2 T β 1+\frac{384}{\varepsilon}\log\frac{2T}{\beta} 1 + ε 384 log β 2 T ∑ i ∈ [ n ] f ( x i ) \sum_{i\in[n]}f(x_i) ∑ i ∈ [ n ] f ( x i )
Proof. We run Algorithm 8 with the single candidate f f f [ 0 , n ] [0,n] [ 0 , n ] f f f T T T Theorem 6.6 , the returned interval [ ℓ ′ , u ′ ] [\ell',u'] [ ℓ ′ , u ′ ] ∑ i ∈ [ n ] f ( x i ) \sum_{i\in[n]}f(x_i) ∑ i ∈ [ n ] f ( x i ) n / 2 T + 384 ε log 2 T β n/2^T+\frac{384}{\varepsilon}\log\frac{2T}{\beta} n / 2 T + ε 384 log β 2 T
Near-Linear Algorithm
We now describe an algorithm that achieves the error of Algorithm 8 using only O ( d log ∗ n + log 3 n ) O(d\log^\ast n+\log^3 n) O ( d log ∗ n + log 3 n ) s j s_j s j s j ( D ) s_j(D) s j ( D ) S ⋆ = max j ∈ [ d ] s j S^\star=\max_{j\in[d]}s_j S ⋆ = max j ∈ [ d ] s j
Like Algorithm 8, our algorithm maintains an interval [ ℓ , u ] [\ell,u] [ ℓ , u ] S ⋆ S^\star S ⋆ j w j_w j w ℓ \ell ℓ d d d phases , each of which reduces the length of the interval from x α x^\alpha x α O ( α log 3 x ) O(\alpha\log^3 x) O ( α log 3 x ) O ( d + log 3 x ) O(d+\log^3 x) O ( d + log 3 x ) α \alpha α O ( log ∗ n ) O(\log^\ast n) O ( log ∗ n ) O ( α ) O(\alpha) O ( α )
The main step of a phase is a filtering pass in which we query every candidate once against a fixed threshold τ \tau τ τ \tau τ Y Y Y Y Y Y ∣ Y ∣ |Y| ∣ Y ∣ P P P 1 / t 1/t 1/ t t = ⌈ log 2 x ⌉ t=\lceil\log_2 x\rceil t = ⌈ log 2 x ⌉ P P P P P P t t t ∣ P ∣ t |P|t ∣ P ∣ t d d d τ \tau τ P P P t t t t 2 t^2 t 2 e − t e^{-t} e − t ∣ Y ∣ < t 2 |Y|<t^2 ∣ Y ∣ < t 2 Y Y Y t t t t 3 t^3 t 3
We use privacy budget ε / t 3 \varepsilon/t^3 ε / t 3 O ( α t 3 ) = O ( α log 3 x ) O(\alpha t^3)=O(\alpha\log^3 x) O ( α t 3 ) = O ( α log 3 x ) t 2 t^2 t 2 O ( ε / t ) O(\varepsilon/t) O ( ε / t ) t 2 t^2 t 2 d d d Y Y Y d t dt d t e − t e^{-t} e − t ( P , [ ℓ , u ] , j , T , ε , β ) (P,[\ell,u],j,T,\varepsilon,\beta) ( P , [ ℓ , u ] , j , T , ε , β ) P P P [ ℓ , u ] [\ell,u] [ ℓ , u ] j j j T T T ε \varepsilon ε β \beta β
We now analyze Algorithm 9. Let k k k i < k i<k i < k x i x_i x i t i = ⌈ log 2 x i ⌉ t_i=\lceil\log_2 x_i\rceil t i = ⌈ log 2 x i ⌉ x x x t t t i i i i = 0 i=0 i = 0 x k x_k x k x x x n n n d d d ε \varepsilon ε β \beta β x i + 1 = 64 t i 3 x_{i+1}=64t_i^3 x i + 1 = 64 t i 3 t i ≥ 64 t_i\ge64 t i ≥ 64 i < k i<k i < k t i + 1 ≤ 7 + 3 log 2 t i ≤ t i / 2 t_{i+1}\le7+3\log_2 t_i\le t_i/2 t i + 1 ≤ 7 + 3 log 2 t i ≤ t i /2
∑ i < k 1 t i ≤ 2 t k − 1 ≤ 1 32 . (1) \sum_{i<k}\frac{1}{t_i}\le\frac{2}{t_{k-1}}\le\frac{1}{32}. \tag*{(1)} i < k ∑ t i 1 ≤ t k − 1 2 ≤ 32 1 . (1) Further, it is easy to see that two consecutive phases reduce any sufficiently large value of x x x log 2 x \log_2 x log 2 x k = O ( log ∗ n ) k=O(\log^* n) k = O ( log ∗ n )
We first show that the algorithm is private, which follows from basic composition since the budgets of all phases are fixed in advance.
Lemma 6.9. Algorithm 9 is ε \varepsilon ε
Proof. The algorithm accesses the data only through SVT streams, either in a filtering pass or in a run of Algorithm 8. In phase i i i ε / t i 3 \varepsilon/t_i^3 ε / t i 3 t i 2 t_i^2 t i 2 ε / t i 3 \varepsilon/t_i^3 ε / t i 3 i i i ( t i 2 + 2 ) ε / t i 3 ≤ 2 ε / t i (t_i^2+2)\varepsilon/t_i^3\le2\varepsilon/t_i ( t i 2 + 2 ) ε / t i 3 ≤ 2 ε / t i (1) , all phases together use budget at most ε / 16 \varepsilon/16 ε /16 ε / 2 \varepsilon/2 ε /2
Algorithm 9 Private selection by sampling and filtering
Input: Oracle O \mathcal{O} O [ d ] [d] [ d ] [ 0 , n ] [0,n] [ 0 , n ] ε ∈ ( 0 , 1 ] \varepsilon\in(0,1] ε ∈ ( 0 , 1 ] β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 )
Output: Index j ⋆ j^\star j ⋆
1: N ← 3 log 2 ( 2 n ) N \leftarrow3\log_2(2n) N ← 3 log 2 ( 2 n ) β ′ ← β / N \beta' \leftarrow\beta/N β ′ ← β / N α ← 8 ε log 384 d log 3 ( 2 n ) β \alpha\leftarrow\frac{8}{\varepsilon}\log\frac{384d\log^3(2n)}{\beta} α ← ε 8 log β 384 d l o g 3 ( 2 n ) ℓ ← 0 \ell\leftarrow0 ℓ ← 0 u ← n u \leftarrow n u ← n j w ← 1 j_w \leftarrow1 j w ← 1 x ← n / α x \leftarrow n/\alpha x ← n / α while x ≥ 2 64 x \ge2^{64} x ≥ 2 64 do ▷one phase 4: \quad t ← ⌈ log 2 x ⌉ t \leftarrow\lceil\log_2 x\rceil t ← ⌈ log 2 x ⌉ ε ′ ← ε / t 3 \varepsilon' \leftarrow\varepsilon/t^3 ε ′ ← ε / t 3 a ← t 3 α a \leftarrow t^3\alpha a ← t 3 α P ′ ⊆ [ d ] P' \subseteq[d] P ′ ⊆ [ d ] 1 / t 1/t 1/ t P ← P ′ ∪ { j w } P \leftarrow P' \cup\{j_w\} P ← P ′ ∪ { j w } ( j P , ℓ P , ⋅ ) ← GeometricBinarySearch ( P , [ ℓ , u ] , j w , t , ε ′ , β ′ ) (j_P,\ell_P,\cdot) \leftarrow\operatorname{GeometricBinarySearch}(P,[\ell,u],j_w,t,\varepsilon',\beta') ( j P , ℓ P , ⋅ ) ← GeometricBinarySearch ( P , [ ℓ , u ] , j w , t , ε ′ , β ′ ) τ ← ℓ P + 50 a \tau\leftarrow\ell_P+50a τ ← ℓ P + 50 a Y ← ∅ Y \leftarrow\varnothing Y ← ∅ ε ′ \varepsilon' ε ′ for j = 1 , … , d j=1,\ldots,d j = 1 , … , d do 9: \qquad if the query ( f j , τ ) (f_j,\tau) ( f j , τ ) Yes then 10: \qquad\quad Y ← Y ∪ { j } Y \leftarrow Y \cup\{j\} Y ← Y ∪ { j } if ∣ Y ∣ = t |Y|=t ∣ Y ∣ = t then break, else initialize a new SVT stream with budget ε ′ \varepsilon' ε ′ C ← [ d ] C \leftarrow[d] C ← [ d ] if ∣ Y ∣ = t |Y|=t ∣ Y ∣ = t and C ← Y ∪ { j P } C \leftarrow Y \cup\{j_P\} C ← Y ∪ { j P } ( j w , ℓ , u ′ ) ← GeometricBinarySearch ( C , [ ℓ P , u ] , j P , t , ε ′ , β ′ ) (j_w,\ell,u') \leftarrow\operatorname{GeometricBinarySearch}(C,[\ell_P,u],j_P,t,\varepsilon',\beta') ( j w , ℓ , u ′ ) ← GeometricBinarySearch ( C , [ ℓ P , u ] , j P , t , ε ′ , β ′ ) u ← min { u , max { u ′ , τ + a } } u \leftarrow\min\{u,\max\{u',\tau+a\}\} u ← min { u , max { u ′ , τ + a }} x ← 64 t 3 x \leftarrow64t^3 x ← 64 t 3 ( j ⋆ , ⋅ , ⋅ ) ← GeometricBinarySearch ( [ d ] , [ ℓ , u ] , j w , 64 , ε / 2 , β ′ ) (j^\star,\cdot,\cdot) \leftarrow\operatorname{GeometricBinarySearch}([d],[\ell,u],j_w,64,\varepsilon/2,\beta') ( j ⋆ , ⋅ , ⋅ ) ← GeometricBinarySearch ([ d ] , [ ℓ , u ] , j w , 64 , ε /2 , β ′ ) return j ⋆ j^\star j ⋆
Next we analyze the accuracy of the algorithm. Every run of Algorithm 8 is made with failure probability β ′ = β / N \beta'=\beta/N β ′ = β / N d d d 8 ε ′ log 2 d N β \frac{8}{\varepsilon'}\log\frac{2dN}{\beta} ε ′ 8 log β 2 d N β / N \beta/N β / N 1 + ∑ i < k ( t i 2 + 2 ) ≤ N 1+\sum_{i<k}(t_i^2+2)\le N 1 + ∑ i < k ( t i 2 + 2 ) ≤ N t i + 1 ≤ t i / 2 t_{i+1}\le t_i/2 t i + 1 ≤ t i /2 t 0 ≤ log 2 ( 2 n ) t_0\le\log_2(2n) t 0 ≤ log 2 ( 2 n ) α ≥ 1 \alpha\ge1 α ≥ 1 E \mathcal{E} E Theorem 6.6 and every stream of a filtering pass is accurate as above. By a union bound, Pr [ E ] ≥ 1 − β \Pr[\mathcal{E}]\ge1-\beta Pr [ E ] ≥ 1 − β α \alpha α E \mathcal{E} E i i i t i 3 α t_i^3\alpha t i 3 α i i i [ ℓ ′ , u ′ ] [\ell',u'] [ ℓ ′ , u ′ ] ( u ′ − ℓ ′ ) / 2 t i + 48 t i 3 α (u'-\ell')/2^{t_i}+48t_i^3\alpha ( u ′ − ℓ ′ ) / 2 t i + 48 t i 3 α ( u − ℓ ) / 2 64 + 96 α (u-\ell)/2^{64}+96\alpha ( u − ℓ ) / 2 64 + 96 α
We now show that on the event E \mathcal{E} E P P P τ + a \tau+a τ + a C C C
Lemma 6.10. On the event E \mathcal{E} E i ≤ k i\le k i ≤ k i i i i = k i=k i = k S ⋆ ≤ u S^\star\le u S ⋆ ≤ u s j w ≥ ℓ s_{j_w}\ge\ell s j w ≥ ℓ u − ℓ ≤ x i α u-\ell\le x_i\alpha u − ℓ ≤ x i α i < k i<k i < k t i 2 t_i^2 t i 2 t i 2 t_i^2 t i 2 max j ∈ P s j \max_{j\in P}s_j max j ∈ P s j
Proof. We prove the claim by induction on i i i i = 0 i=0 i = 0 [ 0 , n ] [0,n] [ 0 , n ] x 0 = n / α x_0=n/\alpha x 0 = n / α i < k i<k i < k t = t i t=t_i t = t i a = t 3 α a=t^3\alpha a = t 3 α P P P ℓ P ≥ ℓ \ell_P \ge\ell ℓ P ≥ ℓ s j P ≥ ℓ P s_{j_P} \ge\ell_P s j P ≥ ℓ P S P ⋆ = max j ∈ P s j ≤ ℓ P + ( u − ℓ ) / 2 t + 48 a ≤ ℓ P + 49 a S_P^\star= \max_{j\in P} s_j \le\ell_P + (u-\ell)/2^t + 48a \le\ell_P + 49a S P ⋆ = max j ∈ P s j ≤ ℓ P + ( u − ℓ ) / 2 t + 48 a ≤ ℓ P + 49 a j j j s j ≤ S P ⋆ s_j \le S_P^\star s j ≤ S P ⋆ s j ≤ τ − a s_j \le\tau-a s j ≤ τ − a j ∉ Y j\notin Y j ∈ / Y s j ≤ τ + a s_j \le\tau+a s j ≤ τ + a
Let ( j ′ , ℓ ′ , u ′ ) (j^\prime,\ell^\prime,u^\prime) ( j ′ , ℓ ′ , u ′ ) C C C j w = j ′ j_w=j^\prime j w = j ′ ℓ = ℓ ′ \ell=\ell^\prime ℓ = ℓ ′ u = min { u , max { u ′ , τ + a } } u=\min\{u,\max\{u^\prime,\tau+a\}\} u = min { u , max { u ′ , τ + a }} [ ℓ P , u ] [\ell_P,u] [ ℓ P , u ] j P j_P j P s j ′ ≥ ℓ ′ s_{j^\prime}\ge\ell^\prime s j ′ ≥ ℓ ′ S C ⋆ = max j ∈ C s j ≤ u ′ S_C^\star=\max_{j\in C}s_j\le u^\prime S C ⋆ = max j ∈ C s j ≤ u ′ u ′ − ℓ ′ ≤ 49 a u^\prime-\ell^\prime\le49a u ′ − ℓ ′ ≤ 49 a C C C S ⋆ ≤ max { u ′ , τ + a } S^\star\le\max\{u^\prime,\tau+a\} S ⋆ ≤ max { u ′ , τ + a } C = [ d ] C=[d] C = [ d ] S ⋆ = S C ⋆ ≤ u ′ S^\star=S_C^\star\le u^\prime S ⋆ = S C ⋆ ≤ u ′ u u u S ⋆ S^\star S ⋆ max { u ′ − ℓ ′ , τ + a − ℓ ′ } \max\{u^\prime-\ell^\prime,\tau+a-\ell^\prime\} max { u ′ − ℓ ′ , τ + a − ℓ ′ } Y ≠ ∅ Y\ne\emptyset Y = ∅ C C C S C ⋆ ≥ τ − a S_C^\star\ge\tau-a S C ⋆ ≥ τ − a ℓ ′ ≥ S C ⋆ − 49 a ≥ τ − 50 a \ell^\prime\ge S_C^\star-49a\ge\tau-50a ℓ ′ ≥ S C ⋆ − 49 a ≥ τ − 50 a Y = ∅ Y=\emptyset Y = ∅ ℓ ′ ≥ ℓ P = τ − 50 a \ell^\prime\ge\ell_P=\tau-50a ℓ ′ ≥ ℓ P = τ − 50 a 51 a ≤ x i + 1 α 51a\le x_{i+1}\alpha 51 a ≤ x i + 1 α
Finally, we bound the expected number of queries. The run of Algorithm 8 on P P P d d d d d d C C C t 3 t^3 t 3 Lemma 6.10 , on the event E \mathcal{E} E t 2 t^2 t 2 e − t e^{-t} e − t
Lemma 6.11. If β ≤ 1 / d \beta\le1/d β ≤ 1/ d 3 d k + 2 log 2 3 ( 2 n ) + 64 d = O ( d log ∗ n + log 3 n ) 3dk+2\log_2^3(2n)+64d=O(d\log^\ast n+\log^3 n) 3 d k + 2 log 2 3 ( 2 n ) + 64 d = O ( d log ∗ n + log 3 n )
Proof. Consider phase i < k i<k i < k t = t i t=t_i t = t i P P P ∣ P ∣ t |P|t ∣ P ∣ t E [ ∣ P ∣ ] ≤ 1 + d / t \mathbb{E}[|P|]\le1+d/t E [ ∣ P ∣ ] ≤ 1 + d / t d d d C C C t 3 t^3 t 3 d t dt d t j 1 , … , j d j_1,\ldots,j_d j 1 , … , j d P ′ P^\prime P ′ j 1 , … , j t 2 j_1,\ldots,j_{t^2} j 1 , … , j t 2 t 2 t^2 t 2 max j ∈ P s j \max_{j\in P}s_j max j ∈ P s j Lemma 6.10 , this implies that the filtering pass stops early only if E \mathcal{E} E P ′ P^\prime P ′ j 1 , … , j t 2 j_1,\ldots,j_{t^2} j 1 , … , j t 2 β + ( 1 − 1 / t ) t 2 ≤ β + e − t \beta+(1-1/t)^{t^2}\le\beta+e^{-t} β + ( 1 − 1/ t ) t 2 ≤ β + e − t i i i
( 1 + d / t ) t + d + t 3 + ( β + e − t ) d t ≤ 3 d + t 3 + 2 t , (1+d/t)t+d+t^3+(\beta+e^{-t})dt\le3d+t^3+2t, ( 1 + d / t ) t + d + t 3 + ( β + e − t ) d t ≤ 3 d + t 3 + 2 t , where we used that β d ≤ 1 \beta d\le1 β d ≤ 1 t e − t ≤ 1 te^{-t}\le1 t e − t ≤ 1 t i + 1 ≤ t i / 2 t_{i+1}\le t_i/2 t i + 1 ≤ t i /2 t 0 ≤ log 2 ( 2 n ) t_0\le\log_2(2n) t 0 ≤ log 2 ( 2 n ) 3 d k + 2 log 2 3 ( 2 n ) 3dk+2\log_2^3(2n) 3 d k + 2 log 2 3 ( 2 n ) 64 d 64d 64 d
By Lemma 6.10 , on the event E \mathcal{E} E u − ℓ ≤ x k α < 2 64 α u-\ell\le x_k\alpha<2^{64}\alpha u − ℓ ≤ x k α < 2 64 α S ⋆ S^\star S ⋆ ℓ \ell ℓ j ⋆ j^\star j ⋆ S ⋆ − s j ⋆ ≤ α + 96 α = 97 α S^\star-s_{j^\star}\le\alpha+96\alpha=97\alpha S ⋆ − s j ⋆ ≤ α + 96 α = 97 α Theorem 2.2 .
Theorem 6.12. Let n ≥ 2 n\ge2 n ≥ 2 d ≥ 1 d\ge1 d ≥ 1 ε ∈ ( 0 , 1 ] \varepsilon\in(0,1] ε ∈ ( 0 , 1 ] β ∈ ( 0 , 1 / d ] \beta\in(0,1/d] β ∈ ( 0 , 1/ d ] ε \varepsilon ε 1 − β 1-\beta 1 − β j ⋆ j^\star j ⋆
max j ∈ [ d ] s j ( D ) − s j ⋆ ( D ) ≤ 776 ε log 384 d log 2 3 ( 2 n ) β = O ( 1 ε log d log n β ) . \max_{j\in[d]}s_j(D)-s_{j^\star}(D)\le\frac{776}{\varepsilon}\log\frac{384d\log_2^3(2n)}{\beta}=O\left(\frac{1}{\varepsilon}\log\frac{d\log n}{\beta}\right). j ∈ [ d ] max s j ( D ) − s j ⋆ ( D ) ≤ ε 776 log β 384 d log 2 3 ( 2 n ) = O ( ε 1 log β d log n ) . The expected number of SVT queries made by the algorithm is O ( d log ∗ n + log 3 n ) O(d\log^* n+\log^3 n) O ( d log ∗ n + log 3 n ) β = 1 / ( d n ) \beta=1/(dn) β = 1/ ( d n ) O ( log ( d n ) ϵ ) O\left(\frac{\log(dn)}{\epsilon}\right) O ( ϵ l o g ( d n ) ) d ≥ log 3 n d\ge\log^3 n d ≥ log 3 n O ( d log ∗ d ) O(d\log^* d) O ( d log ∗ d )
Applications in the SVT Model
Because private selection appears in many settings, Theorem 2.2 has a wide range of applications. In this section, we present several examples demonstrating how the SVT primitive substantially improves upon existing models.
F p F_p F p i ∈ [ d ] i\in[d] i ∈ [ d ] F p F_p F p L p L_p L p p ≥ 1 p\ge1 p ≥ 1 s ( i ) = ∑ j ∈ [ n ] ∣ v i ( j ) ∣ p s(i)=\sum_{j\in[n]}|v_i^{(j)}|^p s ( i ) = ∑ j ∈ [ n ] ∣ v i ( j ) ∣ p s ( i ) = ( ∑ j ∈ [ n ] ∣ v i ( j ) ∣ p ) 1 / p s(i)=\left(\sum_{j\in[n]}|v_i^{(j)}|^p\right)^{1/p} s ( i ) = ( ∑ j ∈ [ n ] ∣ v i ( j ) ∣ p ) 1/ p j ∈ [ n ] j\in[n] j ∈ [ n ] w ( j ) w^{(j)} w ( j ) w i ( j ) = ∣ v i ( j ) ∣ p w_i^{(j)}=|v_i^{(j)}|^p w i ( j ) = ∣ v i ( j ) ∣ p i ∈ [ d ] i\in[d] i ∈ [ d ] F p F_p F p s ( i ) = ∑ j ∈ [ n ] w i ( j ) s(i)=\sum_{j\in[n]}w_i^{(j)} s ( i ) = ∑ j ∈ [ n ] w i ( j ) ∣ v i ( j ) ∣ ≤ b |v_i^{(j)}|\le b ∣ v i ( j ) ∣ ≤ b w i ( j ) w_i^{(j)} w i ( j ) [ 0 , b p ] [0,b^p] [ 0 , b p ] w ( 1 ) / b p , … , w ( n ) / b p w^{(1)}/b^p,\ldots,w^{(n)}/b^p w ( 1 ) / b p , … , w ( n ) / b p O ( b p log d ϵ ) O\left(\frac{b^p\log d}{\epsilon}\right) O ( ϵ b p l o g d ) F p F_p F p n n n d d d ( y − a ) 1 / p ≥ y 1 / p − a 1 / p (y-a)^{1/p}\ge y^{1/p}-a^{1/p} ( y − a ) 1/ p ≥ y 1/ p − a 1/ p 0 ≤ a ≤ y 0\le a\le y 0 ≤ a ≤ y a a a F p F_p F p a 1 / p a^{1/p} a 1/ p L p L_p L p
Squared Euclidean loss, i.e., F 2 F_2 F 2 If v i ( j ) v_i^{(j)} v i ( j ) s ( i ) = ∑ j ∈ [ n ] ( v i ( j ) ) 2 s(i)=\sum_{j\in[n]}(v_i^{(j)})^2 s ( i ) = ∑ j ∈ [ n ] ( v i ( j ) ) 2 i i i ℓ 2 \ell_2 ℓ 2 ( v i ( 1 ) , … , v i ( n ) ) (v_i^{(1)},\ldots,v_i^{(n)}) ( v i ( 1 ) , … , v i ( n ) ) s ( i ) s(i) s ( i )
Absolute deviation, i.e., F 1 F_1 F 1 L 1 L_1 L 1 Taking p = 1 p=1 p = 1 s ( i ) = ∑ j ∈ [ n ] ∣ v i ( j ) ∣ s(i)=\sum_{j\in[n]}|v_i^{(j)}| s ( i ) = ∑ j ∈ [ n ] ∣ v i ( j ) ∣ L 1 L_1 L 1
Higher-order moments, i.e., F p F_p F p p > 2 p>2 p > 2 For larger p p p s ( i ) = ∑ j ∈ [ n ] ∣ v i ( j ) ∣ p s(i)=\sum_{j\in[n]}|v_i^{(j)}|^p s ( i ) = ∑ j ∈ [ n ] ∣ v i ( j ) ∣ p L p L_p L p s ( i ) = ( ∑ j ∈ [ n ] ∣ v i ( j ) ∣ p ) 1 / p s(i)=\left(\sum_{j\in[n]}|v_i^{(j)}|^p\right)^{1/p} s ( i ) = ( ∑ j ∈ [ n ] ∣ v i ( j ) ∣ p ) 1/ p ℓ ∞ \ell_\infty ℓ ∞ s ∞ ( i ) = max j ∈ [ n ] ∣ v i ( j ) ∣ s_\infty(i)=\max_{j\in[n]}|v_i^{(j)}| s ∞ ( i ) = max j ∈ [ n ] ∣ v i ( j ) ∣ p p p F p F_p F p L p L_p L p
Heavy-hitters with categories. In many real-world datasets, items are associated with multiple categories, forming sparse binary vectors where each item is represented by a vector indicating its presence across various categories. The goal is to identify the top k k k
Formally, suppose there are n n n r r r d d d n n n r r r v ( 1 ) , … , v ( n ) ∈ { 0 , 1 } d v^{(1)}, \ldots, v^{(n)} \in\{0,1\}^{d} v ( 1 ) , … , v ( n ) ∈ { 0 , 1 } d ∥ v ( i ) ∥ 0 ≤ r \lVert v^{(i)} \rVert_{0} \le r ∥ v ( i ) ∥ 0 ≤ r i ∈ [ n ] i \in[n] i ∈ [ n ] k k k k k k v = ∑ i ∈ [ n ] v ( i ) ∈ R d v = \sum_{i \in[n]} v^{(i)} \in\mathbb{R}^{d} v = ∑ i ∈ [ n ] v ( i ) ∈ R d
We first observe that because each item can be in up to r r r L 1 L_{1} L 1 v v v 2 r 2r 2 r d d d 2 r / ε 2r/\varepsilon 2 r / ε Θ ( r log d / ε ) \Theta(r \log d/\varepsilon) Θ ( r log d / ε ) 1 1 1 f j ( v ( i ) ) = v j ( i ) f_j(v^{(i)}) = v_j^{(i)} f j ( v ( i ) ) = v j ( i ) r r r Theorem 6.12 k k k ε / k \varepsilon/k ε / k 1 / d 1/d 1/ d
Theorem 7.1. Let ε ∈ ( 0 , 1 ] \varepsilon\in(0,1] ε ∈ ( 0 , 1 ] n ≥ 2 n \ge2 n ≥ 2 k ≤ d k \le d k ≤ d ε \varepsilon ε j 1 , … , j k j_1,\ldots,j_k j 1 , … , j k 1 − k / d 1-k/d 1 − k / d t ∈ [ k ] t \in[k] t ∈ [ k ] v j t v_{j_t} v j t t t t O ( k log ( d log n ) ε ) O\left(\frac{k\log(d\log n)}{\varepsilon}\right) O ( ε k l o g ( d l o g n ) ) O ( k ( d log ∗ n + log 3 n ) ) O(k(d\log^{*} n+\log^{3} n)) O ( k ( d log ∗ n + log 3 n ))
Proof. In round t t t t − 1 t-1 t − 1 t t t Theorem 6.12 with budget ε / k \varepsilon/k ε / k 1 / d 1/d 1/ d 1 − 1 / d 1-1/d 1 − 1/ d O ( k log ( d log n ) / ε ) O(k\log(d\log n)/\varepsilon) O ( k log ( d log n ) / ε ) k k k
Sparse mean estimation. Let X 1 , … , X n ∈ R d X_1,\ldots,X_n \in\mathbb{R}^{d} X 1 , … , X n ∈ R d N ( μ , I d ) \mathcal{N}(\mu,I_d) N ( μ , I d ) μ \mu μ k k k ∥ μ ∥ 0 ≤ k \lVert\mu\rVert_{0} \le k ∥ μ ∥ 0 ≤ k k ≪ d k \ll d k ≪ d ∥ μ ∥ ∞ ≤ 1 \lVert\mu\rVert_{\infty} \le1 ∥ μ ∥ ∞ ≤ 1 μ \mu μ k k k ℓ 2 \ell_{2} ℓ 2 O ( k log ( d ) / n ) O(\sqrt{k\log(d)/n}) O ( k log ( d ) / n ) μ \mu μ μ \mu μ
Our estimator follows the non-private one. We first privately select k k k
Both steps use only sums of bounded functions of the samples, which we obtain by clipping every entry to the interval [ − B , B ] [-B,B] [ − B , B ] B = 1 + 2 log ( 8 n d / β ) B=1+\sqrt{2\log(8nd/\beta)} B = 1 + 2 log ( 8 n d / β ) β \beta β X ~ 1 , … , X ~ n \widetilde{X}_1,\ldots,\widetilde{X}_n X 1 , … , X n
To select coordinates we use the 2 d 2d 2 d f j , σ ( X ~ i ) = B + σ X ~ i j 2 B ∈ [ 0 , 1 ] f_{j,\sigma}(\widetilde{X}_i)=\frac{B+\sigma\widetilde{X}_{ij}}{2B}\in[0,1] f j , σ ( X i ) = 2 B B + σ X ij ∈ [ 0 , 1 ] j ∈ [ d ] j\in[d] j ∈ [ d ] σ ∈ { − 1 , + 1 } \sigma\in\{-1,+1\} σ ∈ { − 1 , + 1 } max σ ∑ i f j , σ ( X ~ i ) = n 2 + 1 2 B ∣ ∑ i X ~ i j ∣ \max_{\sigma}\sum_i f_{j,\sigma}(\widetilde{X}_i)=\frac{n}{2}+\frac{1}{2B}\left|\sum_i\widetilde{X}_{ij}\right| max σ ∑ i f j , σ ( X i ) = 2 n + 2 B 1 ∑ i X ij k k k k k k ε / ( 2 k ) \varepsilon/(2k) ε / ( 2 k ) min { β / ( 4 k ) , 1 / ( 2 d ) } \min\{\beta/(4k),1/(2d)\} min { β / ( 4 k ) , 1/ ( 2 d )} S ^ \widehat{S} S j ∈ S ^ j\in\widehat{S} j ∈ S ∑ i X ~ i j \sum_i\widetilde{X}_{ij} ∑ i X ij g j ( X ~ i ) = B + X ~ i j 2 B g_j(\widetilde{X}_i)=\frac{B+\widetilde{X}_{ij}}{2B} g j ( X i ) = 2 B B + X ij ε / ( 2 k ) \varepsilon/(2k) ε / ( 2 k ) β / ( 4 k ) \beta/(4k) β / ( 4 k ) g ^ j \widehat{g}_j g j μ ^ j = B ( 2 g ^ j − n ) n \widehat{\mu}_j=\frac{B(2\widehat{g}_j-n)}{n} μ j = n B ( 2 g j − n ) j ∉ S ^ j\notin\widehat{S} j ∈ / S μ ^ j = 0 \widehat{\mu}_j=0 μ j = 0 ε \varepsilon ε
Theorem 7.2. Let ε ∈ ( 0 , 1 ] \varepsilon\in(0,1] ε ∈ ( 0 , 1 ] β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) n ≥ 2 n\ge2 n ≥ 2 k ≤ d k\le d k ≤ d ε \varepsilon ε O ( k ( d log ∗ n + log 3 n ) ) O(k(d\log^* n+\log^3 n)) O ( k ( d log ∗ n + log 3 n )) 1 − β 1-\beta 1 − β
∥ μ ^ − μ ∥ ∞ = O ( log ( d / β ) n + k log ( n d / β ) log d log n β n ε ) , ∥ μ ^ − μ ∥ 2 ≤ 2 k ∥ μ ^ − μ ∥ ∞ . \lVert\widehat{\mu}-\mu\rVert_\infty=O\left(\sqrt{\frac{\log(d/\beta)}{n}}+\frac{k\sqrt{\log(nd/\beta)}\log\frac{d\log n}{\beta}}{n\varepsilon}\right),\qquad\lVert\widehat{\mu}-\mu\rVert_2\le\sqrt{2k}\lVert\widehat{\mu}-\mu\rVert_\infty. ∥ μ − μ ∥ ∞ = O ( n log ( d / β ) + n ε k log ( n d / β ) log β d l o g n ) , ∥ μ − μ ∥ 2 ≤ 2 k ∥ μ − μ ∥ ∞ . For δ ∈ ( 0 , 1 / 2 ] \delta\in(0,1/2] δ ∈ ( 0 , 1/2 ] k k k O ( k log ( 1 / δ ) ) O(\sqrt{k\log(1/\delta)}) O ( k log ( 1/ δ ) ) ( ε , δ ) (\varepsilon,\delta) ( ε , δ )
The analysis follows the non-private one. With high probability no entry is clipped and all the empirical sums are within A = 2 n log ( 8 d / β ) A=\sqrt{2n\log(8d/\beta)} A = 2 n log ( 8 d / β ) O ( A ) O(A) O ( A ) μ \mu μ A A A
Proof. Let S j = ∑ i ∈ [ n ] X i j S_j=\sum_{i\in[n]}X_{ij} S j = ∑ i ∈ [ n ] X ij S j − n μ j ∼ N ( 0 , n ) S_j-n\mu_j\sim\mathcal{N}(0,n) S j − n μ j ∼ N ( 0 , n ) X i j − μ j ∼ N ( 0 , 1 ) X_{ij}-\mu_j\sim\mathcal{N}(0,1) X ij − μ j ∼ N ( 0 , 1 ) 1 − β / 2 1-\beta/2 1 − β /2 ∣ S j − n μ j ∣ ≤ A |S_j-n\mu_j|\le A ∣ S j − n μ j ∣ ≤ A j ∈ [ d ] j\in[d] j ∈ [ d ] X ~ i = X i \widetilde{X}_i=X_i X i = X i i ∈ [ n ] i\in[n] i ∈ [ n ] Theorem 6.12 and a union bound over the k k k 1 − β / 4 1-\beta/4 1 − β /4 j t j_t j t t t t ∣ S j t ∣ ≥ ∣ S j ∣ − E 1 |S_{j_t}|\ge|S_j|-E_1 ∣ S j t ∣ ≥ ∣ S j ∣ − E 1 j j j t t t E 1 = O ( k B ε log d log n β ) E_1=O\left(\frac{kB}{\varepsilon}\log\frac{d\log n}{\beta}\right) E 1 = O ( ε k B log β d l o g n ) 2 B 2B 2 B Theorem 6.12 . By Corollary 6.8, with probability at least 1 − β / 4 1-\beta/4 1 − β /4 ∣ n μ ^ j − S j ∣ ≤ E 2 |n\widehat{\mu}_j-S_j|\le E_2 ∣ n μ j − S j ∣ ≤ E 2 j ∈ S ^ j\in\widehat{S} j ∈ S E 2 = O ( k B ε log k log n β ) E_2=O\left(\frac{kB}{\varepsilon}\log\frac{k\log n}{\beta}\right) E 2 = O ( ε k B log β k l o g n ) 1 − β 1-\beta 1 − β
For j ∈ S ^ j\in\widehat{S} j ∈ S ∣ μ ^ j − μ j ∣ ≤ ( ∣ n μ ^ j − S j ∣ + ∣ S j − n μ j ∣ ) / n ≤ ( E 2 + A ) / n |\widehat{\mu}_j-\mu_j|\le(|n\widehat{\mu}_j-S_j|+|S_j-n\mu_j|)/n\le(E_2+A)/n ∣ μ j − μ j ∣ ≤ ( ∣ n μ j − S j ∣ + ∣ S j − n μ j ∣ ) / n ≤ ( E 2 + A ) / n j ∗ j^* j ∗ μ \mu μ S ^ \widehat{S} S ∣ S ^ ∣ = k ≥ ∥ μ ∥ 0 |\widehat{S}|=k\ge\lVert\mu\rVert_0 ∣ S ∣ = k ≥ ∥ μ ∥ 0 j ′ j' j ′ μ \mu μ j ∗ j^* j ∗ j ′ j' j ′
A ≥ ∣ S j ′ ∣ ≥ ∣ S j ∗ ∣ − E 1 ≥ n ∣ μ j ∗ ∣ − A − E 1 , A\ge|S_{j'}|\ge|S_{j^*}|-E_1\ge n|\mu_{j^*}|-A-E_1, A ≥ ∣ S j ′ ∣ ≥ ∣ S j ∗ ∣ − E 1 ≥ n ∣ μ j ∗ ∣ − A − E 1 , that is, ∣ μ ^ j ∗ − μ j ∗ ∣ = ∣ μ j ∗ ∣ ≤ ( 2 A + E 1 ) / n |\widehat{\mu}_{j^*}-\mu_{j^*}|=|\mu_{j^*}|\le(2A+E_1)/n ∣ μ j ∗ − μ j ∗ ∣ = ∣ μ j ∗ ∣ ≤ ( 2 A + E 1 ) / n μ ^ j = μ j = 0 \widehat{\mu}_j=\mu_j=0 μ j = μ j = 0 ∥ μ ^ − μ ∥ ∞ \lVert\widehat{\mu}-\mu\rVert_\infty ∥ μ − μ ∥ ∞ B = O ( log ( n d / β ) ) B=O(\sqrt{\log(nd/\beta)}) B = O ( log ( n d / β ) ) ∥ μ ^ − μ ∥ 2 \lVert\widehat{\mu}-\mu\rVert_2 ∥ μ − μ ∥ 2 μ ^ − μ \widehat{\mu}-\mu μ − μ 2 k 2k 2 k Theorem 6.12 and Corollary 6.8. ∎
Multiplicative weights and exponential mechanism (MWEM). We next consider MWEM, a framework introduced by [45 ] based on multiplicative weights and the exponential mechanism, for privately producing synthetic datasets that accurately answer any set of queries on a protected dataset. In particular, we assume there exists a set Q Q Q q q q q : D → [ − 1 , + 1 ] q : D \to[-1,+1] q : D → [ − 1 , + 1 ] D D D [ − 1 , + 1 ] [-1,+1] [ − 1 , + 1 ] A A A
q ( A ) = ∑ x ∈ D q ( x ) ⋅ A ( x ) . q(A) = \sum_{x \in D} q(x) \cdot A(x). q ( A ) = x ∈ D ∑ q ( x ) ⋅ A ( x ) . The goal is to produce a synthetic dataset B B B q ( B ) ≈ q ( A ) q(B) \approx q(A) q ( B ) ≈ q ( A ) q ∈ Q q \in Q q ∈ Q
We first recall a standard approach toward achieving this goal in the central model of differential privacy, as depicted in Algorithm 10. The algorithm, known as MWEM, maintains a synthetic dataset that is initialized uniformly over the domain D D D T T T A A A Q Q Q
Algorithm 10 MWEM Algorithm [45 ]
Input: Private dataset B B B n n n d d d Q Q Q T T T ε > 0 \varepsilon> 0 ε > 0
Output: Synthetic histogram A A A n n n D D D
Initialize A 0 A_0 A 0 D D D n n n
for t = 1 t = 1 t = 1 T T T do
Use exponential mechanism to privately select the query q t ∈ Q q_t \in Q q t ∈ Q ∣ q ( B ) − q ( A t − 1 ) ∣ \lvert q(B) - q(A_{t-1}) \rvert ∣ q ( B ) − q ( A t − 1 )∣ ε 2 T \frac{\varepsilon}{2T} 2 T ε
m t ← q t ( B ) + Lap ( 4 T ε ) m_t \leftarrow q_t(B) + \operatorname{Lap}\left(\frac{4T}{\varepsilon}\right) m t ← q t ( B ) + Lap ( ε 4 T )
Let A t A_t A t n n n
A t ( x ) ∝ A t − 1 ( x ) × exp ( q t ( x ) × m t − q t ( A t − 1 ) 2 n ) A_t(x) \propto A_{t-1}(x) \times\exp\left(q_t(x) \times\frac{m_t - q_t(A_{t-1})}{2n}\right) A t ( x ) ∝ A t − 1 ( x ) × exp ( q t ( x ) × 2 n m t − q t ( A t − 1 ) ) Return A = 1 T ∑ t ∈ [ T ] A t A = \frac{1}{T}\sum_{t \in[T]} A_t A = T 1 ∑ t ∈ [ T ] A t T T T
Observe that the key challenge to implementing Algorithm 10 in distributed models is implementing the exponential mechanism to privately select the query q t ∈ Q q_t \in Q q t ∈ Q ∣ q ( B ) − q ( A t − 1 ) ∣ \lvert q(B) - q(A_{t-1}) \rvert ∣ q ( B ) − q ( A t − 1 )∣ f : R d → R d ′ f : \mathbb{R}^{d} \to\mathbb{R}^{d'} f : R d → R d ′ q ∈ Q q \in Q q ∈ Q k ∈ [ d ′ ] k \in[d'] k ∈ [ d ′ ] q q q q ( B ) = ∑ i ∈ [ n ] ( f ( v i ) ) k q(B) = \sum_{i \in[n]}(f(v_i))_k q ( B ) = ∑ i ∈ [ n ] ( f ( v i ) ) k ∣ q ( B ) − q ( A t − 1 ) ∣ \lvert q(B) - q(A_{t-1}) \rvert ∣ q ( B ) − q ( A t − 1 )∣ q ( A t − 1 ) q(A_{t-1}) q ( A t − 1 ) d ′ d' d ′ w ∈ R d ′ w \in\mathbb{R}^{d'} w ∈ R d ′ q q q k ∈ [ d ′ ] k \in[d'] k ∈ [ d ′ ]
q ( B ) − q ( A t − 1 ) = w k + ∑ i ∈ [ n ] ( f ( v i ) ) k . q(B) - q(A_{t-1}) = w_k + \sum_{i \in[n]}(f(v_i))_k. q ( B ) − q ( A t − 1 ) = w k + i ∈ [ n ] ∑ ( f ( v i ) ) k . For example, consider the class of two-way marginal queries, defined as follows. A two-way marginal query q ( a , b ) q_{(a,b)} q ( a , b ) a , b ∈ [ d ] a,b \in[d] a , b ∈ [ d ] a a a b b b q ( a , b ) ( B ) = ∑ i ∈ [ n ] 1 [ v i ( a ) = v i ( b ) = 1 ] q_{(a,b)}(B) = \sum_{i\in[n]} \mathbf{1}[v_i(a) = v_i(b) = 1] q ( a , b ) ( B ) = ∑ i ∈ [ n ] 1 [ v i ( a ) = v i ( b ) = 1 ] v i ∈ { 0 , 1 } d v_i \in\{0,1\}^{d} v i ∈ { 0 , 1 } d d ′ d' d ′ ( a , b ) (a,b) ( a , b ) d ′ = O ( d 2 ) d' = O(d^2) d ′ = O ( d 2 ) f ( v i ) ∈ R d ′ f(v_i) \in\mathbb{R}^{d'} f ( v i ) ∈ R d ′
( f ( v i ) ) ( a , b ) = 1 [ v i ( a ) = v i ( b ) = 1 ] . \left(f(v_i)\right)_{(a,b)} = \mathbf{1}[v_i(a) = v_i(b) = 1]. ( f ( v i ) ) ( a , b ) = 1 [ v i ( a ) = v i ( b ) = 1 ] . Then for any two-way marginal query q ( a , b ) q_{(a,b)} q ( a , b )
q ( a , b ) ( B ) = ∑ i ∈ [ n ] ( f ( v i ) ) ( a , b ) . q_{(a,b)}(B) = \sum_{i\in[n]} \left(f(v_i)\right)_{(a,b)}. q ( a , b ) ( B ) = i ∈ [ n ] ∑ ( f ( v i ) ) ( a , b ) . Moreover, since A t − 1 A_{t-1} A t − 1 t t t w ∈ R d ′ w \in\mathbb{R}^{d'} w ∈ R d ′ w ( a , b ) = − q ( a , b ) ( A t − 1 ) w_{(a,b)} = -q_{(a,b)}(A_{t-1}) w ( a , b ) = − q ( a , b ) ( A t − 1 )
q ( a , b ) ( B ) − q ( a , b ) ( A t − 1 ) = w ( a , b ) + ∑ i ∈ [ n ] ( f ( v i ) ) ( a , b ) . q_{(a,b)}(B) - q_{(a,b)}(A_{t-1}) = w_{(a,b)} + \sum_{i\in[n]} \left(f(v_i)\right)_{(a,b)}. q ( a , b ) ( B ) − q ( a , b ) ( A t − 1 ) = w ( a , b ) + i ∈ [ n ] ∑ ( f ( v i ) ) ( a , b ) . Thus, for two-way marginal queries, the signed MWEM discrepancy can be realized as a coordinate of an aggregated embedded vector plus a public offset. After analyzing Algorithm 10, we show how this representation allows us to implement the selection step in the SVT model, using approximate selection in place of the exponential mechanism.
We define Δ t = max q ∈ Q ∣ q ( A t − 1 ) − q ( B ) ∣ \Delta_t = \max_{q\in Q} |q(A_{t-1}) - q(B)| Δ t = max q ∈ Q ∣ q ( A t − 1 ) − q ( B ) ∣ β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) η = 8 T ε ln 2 T ∣ Q ∣ β \eta= \frac{8T}{\varepsilon}\ln\frac{2T|Q|}{\beta} η = ε 8 T ln β 2 T ∣ Q ∣
Lemma 7.3. With probability at least 1 − β 1-\beta 1 − β t ∈ [ T ] t \in[T] t ∈ [ T ]
∣ q t ( A t − 1 ) − q t ( B ) ∣ ≥ Δ t − η , ∣ m t − q t ( B ) ∣ ≤ η . |q_t(A_{t-1}) - q_t(B)| \ge\Delta_t - \eta,\qquad|m_t-q_t(B)| \le\eta. ∣ q t ( A t − 1 ) − q t ( B ) ∣ ≥ Δ t − η , ∣ m t − q t ( B ) ∣ ≤ η . Proof. Since q ( x ) ∈ [ − 1 , + 1 ] q(x) \in[-1,+1] q ( x ) ∈ [ − 1 , + 1 ] q ( B ) q(B) q ( B ) ∣ q ( B ) − q ( A t − 1 ) ∣ |q(B)-q(A_{t-1})| ∣ q ( B ) − q ( A t − 1 ) ∣ A t − 1 A_{t-1} A t − 1 [56 , 32 ] , with privacy parameter ε 2 T \frac{\varepsilon}{2T} 2 T ε q t q_t q t ∣ q t ( A t − 1 ) − q t ( B ) ∣ ≥ Δ t − 8 T ε ( ln ∣ Q ∣ + ln 2 T β ) = Δ t − η |q_t(A_{t-1})-q_t(B)| \ge\Delta_t-\frac{8T}{\varepsilon}\left(\ln|Q|+\ln\frac{2T}{\beta}\right)=\Delta_t-\eta ∣ q t ( A t − 1 ) − q t ( B ) ∣ ≥ Δ t − ε 8 T ( ln ∣ Q ∣ + ln β 2 T ) = Δ t − η 1 − β 2 T 1-\frac{\beta}{2T} 1 − 2 T β m t − q t ( B ) ∼ Lap ( 4 T ε ) m_t-q_t(B)\sim\operatorname{Lap}\left(\frac{4T}{\varepsilon}\right) m t − q t ( B ) ∼ Lap ( ε 4 T ) ∣ m t − q t ( B ) ∣ ≤ 4 T ε ln 2 T β ≤ η |m_t-q_t(B)|\le\frac{4T}{\varepsilon}\ln\frac{2T}{\beta}\le\eta ∣ m t − q t ( B ) ∣ ≤ ε 4 T ln β 2 T ≤ η 1 − β 2 T 1-\frac{\beta}{2T} 1 − 2 T β 2 T 2T 2 T
Following the standard analysis of MWEM [45 ] , we show in Section B that on the accuracy event of Lemma 7.3 the averaged synthetic dataset is accurate.
Lemma 7.4. For an integer T ≥ 1 T \ge1 T ≥ 1 ∣ D ∣ ≥ 2 |\mathcal{D}| \ge2 ∣ D ∣ ≥ 2
max q ∈ Q ∣ q ( A ) − q ( B ) ∣ ≤ n ⋅ log ∣ D ∣ T + η . \max_{q\in Q}|q(A)-q(B)| \le n\cdot\sqrt{\frac{\log|\mathcal{D}|}{T}}+\eta. q ∈ Q max ∣ q ( A ) − q ( B ) ∣ ≤ n ⋅ T log ∣ D ∣ + η . For 0 < ε ≤ 1 0 < \varepsilon\le1 0 < ε ≤ 1 L = ln 2 n ∣ Q ∣ β L = \ln\frac{2n|Q|}{\beta} L = ln β 2 n ∣ Q ∣ T = min { n , ⌈ ( n ε ) 2 / 3 ( log ∣ D ∣ ) 1 / 3 L − 2 / 3 ⌉ } T = \min\left\{n,\left\lceil(n\varepsilon)^{2/3}(\log|\mathcal{D}|)^{1/3}L^{-2/3}\right\rceil\right\} T = min { n , ⌈ ( n ε ) 2/3 ( log ∣ D ∣ ) 1/3 L − 2/3 ⌉ } log ∣ D ∣ > n \log|\mathcal{D}| > n log ∣ D ∣ > n n n n T T T T ≤ n T \le n T ≤ n η ≤ 8 T ε L \eta\le\frac{8T}{\varepsilon}L η ≤ ε 8 T L
Corollary 7.5. For 0 < ε ≤ 1 0 < \varepsilon\le1 0 < ε ≤ 1 1 − β 1-\beta 1 − β
max q ∈ Q ∣ q ( A ) − q ( B ) ∣ ≤ n 2 / 3 ⋅ ( log ∣ D ∣ ln ( 2 n ∣ Q ∣ / β ) ε ) 1 / 3 . \max_{q\in\mathcal{Q}} |q(A)-q(B)| \le n^{2/3}\cdot\left(\frac{\log|\mathcal{D}|\ln(2n|\mathcal{Q}|/\beta)}{\varepsilon}\right)^{1/3}. q ∈ Q max ∣ q ( A ) − q ( B ) ∣ ≤ n 2/3 ⋅ ( ε log ∣ D ∣ ln ( 2 n ∣ Q ∣/ β ) ) 1/3 . Finally, we show that Algorithm 10 is differentially private.
Lemma 7.6. Algorithm 10 is ε \varepsilon ε
Proof. The algorithm makes T T T ε 2 T \frac{\varepsilon}{2T} 2 T ε T T T ε 2 T \frac{\varepsilon}{2T} 2 T ε ε \varepsilon ε
We now describe how to implement Algorithm 10 in the SVT model. The algorithm accesses the private dataset only to select the query q t q_t q t m t m_t m t q ( A t − 1 ) q(A_{t-1}) q ( A t − 1 ) t t t
Specifically, for the selection step we use 2 ∣ Q ∣ 2|\mathcal{Q}| 2∣ Q ∣ q ∈ Q q\in\mathcal{Q} q ∈ Q σ ∈ { − 1 , + 1 } \sigma\in\{-1,+1\} σ ∈ { − 1 , + 1 } f q , σ ( x ) = 1 + σ q ( x ) 2 ∈ [ 0 , 1 ] f_{q,\sigma}(x)=\frac{1+\sigma q(x)}{2}\in[0,1] f q , σ ( x ) = 2 1 + σ q ( x ) ∈ [ 0 , 1 ] w q , σ = n − σ q ( A t − 1 ) 2 ∈ [ 0 , n ] w_{q,\sigma}=\frac{n-\sigma q(A_{t-1})}{2}\in[0,n] w q , σ = 2 n − σ q ( A t − 1 ) ∈ [ 0 , n ] ( q , σ ) (q,\sigma) ( q , σ )
∑ i ∈ [ n ] f q , σ ( x i ) + w q , σ = n + σ ( q ( B ) − q ( A t − 1 ) ) 2 ∈ [ 0 , 2 n ] , \sum_{i\in[n]} f_{q,\sigma}(x_i)+w_{q,\sigma}=n+\frac{\sigma\left(q(B)-q(A_{t-1})\right)}{2}\in[0,2n], i ∈ [ n ] ∑ f q , σ ( x i ) + w q , σ = n + 2 σ ( q ( B ) − q ( A t − 1 ) ) ∈ [ 0 , 2 n ] , and the maximum of the shifted scores over all candidates is n + Δ t / 2 n+\Delta_t/2 n + Δ t /2 ( q , σ ) (q,\sigma) ( q , σ ) τ \tau τ ( f q , σ , τ − w q , σ ) (f_{q,\sigma},\tau-w_{q,\sigma}) ( f q , σ , τ − w q , σ ) [ 0 , n ] [0,n] [ 0 , n ] [ 0 , 2 n ] [0,2n] [ 0 , 2 n ] 2 ∣ Q ∣ 2|\mathcal{Q}| 2∣ Q ∣ ε 2 T \frac{\varepsilon}{2T} 2 T ε β 2 T \frac{\beta}{2T} 2 T β ⌈ log 2 ( 2 n ) ⌉ \lceil\log_2(2n)\rceil ⌈ log 2 ( 2 n )⌉ 1 − β 2 T 1-\frac{\beta}{2T} 1 − 2 T β ∣ q t ( A t − 1 ) − q t ( B ) ∣ ≥ Δ t − η ′ |q_t(A_{t-1})-q_t(B)|\ge\Delta_t-\eta' ∣ q t ( A t − 1 ) − q t ( B ) ∣ ≥ Δ t − η ′
η ′ = O ( T ε log T ∣ Q ∣ log n β ) . \eta'=O\left(\frac{T}{\varepsilon}\log\frac{T|\mathcal{Q}|\log n}{\beta}\right). η ′ = O ( ε T log β T ∣ Q ∣ log n ) . For the measurement step we apply Corollary 6.8 to the function 1 + q t ( x ) 2 \frac{1+q_t(x)}{2} 2 1 + q t ( x ) ε 2 T \frac{\varepsilon}{2T} 2 T ε β 2 T \frac{\beta}{2T} 2 T β m t = 2 g ^ − n m_t=2\hat{g}-n m t = 2 g ^ − n g ^ \hat{g} g ^ ∣ m t − q t ( B ) ∣ ≤ η ′ |m_t-q_t(B)|\le\eta' ∣ m t − q t ( B ) ∣ ≤ η ′ 1 − β 2 T 1-\frac{\beta}{2T} 1 − 2 T β η ′ \eta' η ′ η ′ \eta' η ′ η \eta η η ′ \eta' η ′ η \eta η T ≤ n T\le n T ≤ n η ′ = O ( T ε log n ∣ Q ∣ β ) \eta'=O\left(\frac{T}{\varepsilon}\log\frac{n|\mathcal{Q}|}{\beta}\right) η ′ = O ( ε T log β n ∣ Q ∣ ) ε \varepsilon ε 2 T 2T 2 T β 2 T ≤ 1 2 ∣ Q ∣ \frac{\beta}{2T}\le\frac{1}{2|\mathcal{Q}|} 2 T β ≤ 2∣ Q ∣ 1 2 n 2n 2 n n n n η ′ \eta' η ′ O ( ∣ Q ∣ log ∗ n + log 3 n ) O(|\mathcal{Q}|\log^* n+\log^3 n) O ( ∣ Q ∣ log ∗ n + log 3 n )
Putting these statements together, we have the following:
Theorem 7.7. For any private dataset B B B n n n Q Q Q ε ∈ ( 0 , 1 ] \varepsilon\in(0,1] ε ∈ ( 0 , 1 ] β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) ε \varepsilon ε A A A 1 − β 1-\beta 1 − β
max q ∈ Q ∣ q ( A ) − q ( B ) ∣ ≤ n 2 / 3 ⋅ ( log ∣ D ∣ ⋅ log ( n ∣ Q ∣ / β ) ε ) 1 / 3 \max_{q\in Q} \lvert q(A)-q(B)\rvert\leq n^{2/3}\cdot\left(\frac{\log\lvert\mathcal{D}\rvert\cdot\log(n\lvert Q\rvert/\beta)}{\varepsilon}\right)^{1/3} q ∈ Q max ∣ q ( A ) − q ( B )∣ ≤ n 2/3 ⋅ ( ε log ∣ D ∣ ⋅ log ( n ∣ Q ∣ / β ) ) 1/3 In fact, we can achieve better utility bounds if we permit ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) 0 < ε ≤ 1 0 < \varepsilon\leq1 0 < ε ≤ 1 δ ∈ ( 0 , 1 / 2 ] \delta\in(0,1/2] δ ∈ ( 0 , 1/2 ] 2 T 2T 2 T Θ ( ε / T log ( 1 / δ ) ) \Theta\left(\varepsilon/\sqrt{T\log(1/\delta)}\right) Θ ( ε / T log ( 1/ δ ) ) T T T η ′ \eta' η ′ O ( T log ( 1 / δ ) ) O\left(\sqrt{T\log(1/\delta)}\right) O ( T log ( 1/ δ ) ) T ≍ n ε log ∣ D ∣ / log ( 1 / δ ) / log ( n ∣ Q ∣ / β ) T \asymp n\varepsilon\sqrt{\log\lvert\mathcal{D}\rvert/\log(1/\delta)}/\log(n\lvert Q\rvert/\beta) T ≍ n ε log ∣ D ∣ / log ( 1/ δ ) / log ( n ∣ Q ∣ / β )
Theorem 7.8. For any private dataset B B B n n n Q Q Q 0 < ε ≤ 1 0 < \varepsilon\leq1 0 < ε ≤ 1 δ ∈ ( 0 , 1 / 2 ] \delta\in(0,1/2] δ ∈ ( 0 , 1/2 ] β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) A A A 1 − β 1-\beta 1 − β
max q ∈ Q ∣ q ( A ) − q ( B ) ∣ ≤ n ε ⋅ polylog ( ∣ D ∣ , ∣ Q ∣ , n , 1 δ , 1 β ) . \max_{q\in Q}\lvert q(A)-q(B)\rvert\leq\sqrt{\frac{n}{\varepsilon}}\cdot\operatorname{polylog}\left(\lvert\mathcal{D}\rvert,\lvert Q\rvert,n,\frac{1}{\delta},\frac{1}{\beta}\right). q ∈ Q max ∣ q ( A ) − q ( B )∣ ≤ ε n ⋅ polylog ( ∣ D ∣ , ∣ Q ∣ , n , δ 1 , β 1 ) . Acknowledgments
AI tools were used to assist in improving the clarity and presentation of some proofs. All mathematical arguments were reviewed and verified by the authors.
Proof of the Lower Bound for Selection with Gaussian Aggregation
Our lower bound relies on a lower bound for solving the problem in the standard setting of distributed multi-party protocols. Specifically, we use the standard number-in-hand blackboard communication model. Each user initially knows only its own input and its private randomness. The users communicate by writing messages to a common transcript, where each message may depend on the sender’s input, the sender’s private randomness, public randomness, and the previous transcript. The full transcript is denoted by M M M M M M Z ^ \hat{Z} Z ^ M M M B ( 2 ) B(2) B ( 2 ) { 1 , 2 } \{1,2\} { 1 , 2 }
Theorem A.1. For every 2 / 3 2/3 2/3 Problem 4.3 , its transcript M M M
I ( M ; X ≤ n ∣ V , Z ) = Ω ( d ) . I\left(M;X^{\leq n}\mid V,Z\right)=\Omega(d). I ( M ; X ≤ n ∣ V , Z ) = Ω ( d ) . Our proof follows the approach in [10 ] , which established a lower bound for the sparse Gaussian mean estimation problem (see also [33 ] ). The key lemma in their result is Jayram’s Hellinger cut-and-paste inequality that we state below, where h h h h 2 ( P , Q ) = 1 2 ∫ ( p − q ) 2 h^2(P,Q)=\frac{1}{2}\int(\sqrt{p}-\sqrt{q})^2 h 2 ( P , Q ) = 2 1 ∫ ( p − q ) 2 R = ( P + Q ) / 2 R=(P+Q)/2 R = ( P + Q ) /2 KL ( P ∥ R ) ≥ 2 h 2 ( P , R ) \operatorname{KL}(P\mathbin\Vert R)\geq2h^2(P,R) KL ( P ∥ R ) ≥ 2 h 2 ( P , R ) 1 2 KL ( P ∥ R ) + 1 2 KL ( Q ∥ R ) ≥ h 2 ( P , R ) + h 2 ( Q , R ) ≥ 1 2 ( h ( P , R ) + h ( Q , R ) ) 2 ≥ 1 2 h 2 ( P , Q ) \frac{1}{2}\operatorname{KL}(P\mathbin\Vert R)+\frac{1}{2}\operatorname{KL}(Q\mathbin\Vert R)\geq h^2(P,R)+h^2(Q,R)\geq\frac{1}{2}(h(P,R)+h(Q,R))^2\geq\frac{1}{2}h^2(P,Q) 2 1 KL ( P ∥ R ) + 2 1 KL ( Q ∥ R ) ≥ h 2 ( P , R ) + h 2 ( Q , R ) ≥ 2 1 ( h ( P , R ) + h ( Q , R ) ) 2 ≥ 2 1 h 2 ( P , Q ) h h h
Lemma A.2 (Jayram’s cut-and-paste inequality [47 Theorem 7] ; see also [10 Theorem A.1] ). There is an absolute constant C > 0 C>0 C > 0 n n n i i i ν i 1 , ν i 2 \nu_i^1,\nu_i^2 ν i 1 , ν i 2 r ∈ { 1 , 2 } n r\in\{1,2\}^n r ∈ { 1 , 2 } n P r P_r P r X i ∼ ν r i i X^i\sim\nu_{r_i}^i X i ∼ ν r i i a , b ∈ { 1 , 2 } n a,b\in\{1,2\}^n a , b ∈ { 1 , 2 } n
∑ i = 1 n h 2 ( P a ← b i , P a ) ≥ C ⋅ h 2 ( P b , P a ) . \sum_{i=1}^{n}h^2(P_{a\leftarrow b_i},P_a)\geq C\cdot h^2(P_b,P_a). i = 1 ∑ n h 2 ( P a ← b i , P a ) ≥ C ⋅ h 2 ( P b , P a ) . Proof of Theorem A.1. Let X j ≤ n = ( X j 1 , … , X j n ) X_j^{\leq n}=(X_j^1,\ldots,X_j^n) X j ≤ n = ( X j 1 , … , X j n ) Z = 2 Z=2 Z = 2
I ( M ; X V ≤ n ∣ V , Z = 2 ) = 1 d ∑ j = 1 d I ( M ; X j ≤ n ∣ V = j , Z = 2 ) = 1 d ∑ j = 1 d I ( M ; X j ≤ n ∣ Z = 2 ) ≤ 1 d I ( M ; X ≤ n ∣ Z = 2 ) . (2) \begin{aligned}
I\left(M;X_V^{\leq n}\mid V,Z=2\right)=\frac{1}{d}\sum_{j=1}^{d}I\left(M;X_j^{\leq n}\mid V=j,Z=2\right) \\
&=\frac{1}{d}\sum_{j=1}^{d}I\left(M;X_j^{\leq n}\mid Z=2\right) \\
&\leq\frac{1}{d}I\left(M;X^{\leq n}\mid Z=2\right). \tag*{(2)}
\end{aligned} I ( M ; X V ≤ n ∣ V , Z = 2 ) = d 1 j = 1 ∑ d I ( M ; X j ≤ n ∣ V = j , Z = 2 ) = d 1 j = 1 ∑ d I ( M ; X j ≤ n ∣ Z = 2 ) ≤ d 1 I ( M ; X ≤ n ∣ Z = 2 ) . (2) The second equality follows from the fact that when Z = 2 Z=2 Z = 2 V V V [23 Section 2.5] : if Y 1 , … , Y m Y_1,\ldots,Y_m Y 1 , … , Y m W W W I ( Y 1 , … , Y m ; M ∣ W ) I(Y_1,\ldots,Y_m;M\mid W) I ( Y 1 , … , Y m ; M ∣ W ) X 1 ≤ n , … , X d ≤ n X_1^{\le n},\ldots,X_d^{\le n} X 1 ≤ n , … , X d ≤ n Z = 2 Z=2 Z = 2
Applying the same property to the independent user coordinates X V 1 , … , X V n X_V^1,\ldots,X_V^n X V 1 , … , X V n ( V , Z = 2 ) (V,Z=2) ( V , Z = 2 )
I ( M ; X V ≤ n ∣ V , Z = 2 ) ≥ ∑ i = 1 n I ( M ; X V i ∣ V , Z = 2 ) . (3) I\left(M;X_V^{\le n}\mid V,Z=2\right)\ge\sum_{i=1}^{n}I\left(M;X_V^i\mid V,Z=2\right). \tag*{(3)} I ( M ; X V ≤ n ∣ V , Z = 2 ) ≥ i = 1 ∑ n I ( M ; X V i ∣ V , Z = 2 ) . (3) Next fix a user i ∈ { 1 , … , n } i\in\{1,\ldots,n\} i ∈ { 1 , … , n } V = j V=j V = j I ( M ; X j i ∣ V = j , Z = 2 ) I\left(M;X_j^i\mid V=j,Z=2\right) I ( M ; X j i ∣ V = j , Z = 2 ) b b b { 1 , 2 } n \{1,2\}^n { 1 , 2 } n M b M_b M b M M M k k k X j k X_j^k X j k b k b_k b k b k = 1 b_k=1 b k = 1 X j k = 1 X_j^k=1 X j k = 1 b k = 2 b_k=2 b k = 2 X j k X_j^k X j k { 0 , 1 } \{0,1\} { 0 , 1 } { 0 , 1 } \{0,1\} { 0 , 1 } D b D_b D b X ≤ n X^{\le n} X ≤ n
First consider the setting where Z i ∼ B ( 2 ) Z_i\sim B(2) Z i ∼ B ( 2 ) i i i X j i X_j^i X j i Z i Z_i Z i n − 1 n-1 n − 1 Z = 2 Z=2 Z = 2 Z i Z_i Z i Z i → X j i → M Z_i\to X_j^i\to M Z i → X j i → M
I Z i ∼ B ( 2 ) , X ≤ n ∼ D 2 ˉ ← Z i ( M ; X j i ∣ V = j ) ≥ I Z i ∼ B ( 2 ) , X ≤ n ∼ D 2 ˉ ← Z i ( M ; Z i ∣ V = j ) = E z ∼ B ( 2 ) [ KL ( M 2 ˉ ← z ∥ E Z i M 2 ˉ ← Z i ) ] = 1 2 KL ( M 2 ˉ ← 1 ∥ 1 2 M 2 ˉ ← 1 + 1 2 M 2 ˉ ) + 1 2 KL ( M 2 ˉ ∥ 1 2 M 2 ˉ ← 1 + 1 2 M 2 ˉ ) ≥ 1 2 h 2 ( M 2 ˉ ← 1 , M 2 ˉ ) . (4) \begin{aligned}
I_{Z_i\sim B(2),X^{\le n}\sim D_{\bar{2}\leftarrow Z_i}}\left(M;X_j^i\mid V=j\right)
&\ge I_{Z_i\sim B(2),X^{\le n}\sim D_{\bar{2}\leftarrow Z_i}}\left(M;Z_i\mid V=j\right)\\
&=\mathop{\mathbb{E}}_{z\sim B(2)}\left[\operatorname{KL}\left(M_{\bar{2}\leftarrow z}\,\middle\|\,\mathop{\mathbb{E}}_{Z_i}M_{\bar{2}\leftarrow Z_i}\right)\right]\\
&=\frac{1}{2}\operatorname{KL}\left(M_{\bar{2}\leftarrow1}\,\middle\|\,\frac{1}{2}M_{\bar{2}\leftarrow1}+\frac{1}{2}M_{\bar{2}}\right)
+\frac{1}{2}\operatorname{KL}\left(M_{\bar{2}}\,\middle\|\,\frac{1}{2}M_{\bar{2}\leftarrow1}+\frac{1}{2}M_{\bar{2}}\right)\\
&\ge\frac{1}{2}h^2(M_{\bar{2}\leftarrow1},M_{\bar{2}}). \tag*{(4)}
\end{aligned} I Z i ∼ B ( 2 ) , X ≤ n ∼ D 2 ˉ ← Z i ( M ; X j i ∣ V = j ) ≥ I Z i ∼ B ( 2 ) , X ≤ n ∼ D 2 ˉ ← Z i ( M ; Z i ∣ V = j ) = E z ∼ B ( 2 ) [ KL ( M 2 ˉ ← z ∥ E Z i M 2 ˉ ← Z i ) ] = 2 1 KL ( M 2 ˉ ← 1 2 1 M 2 ˉ ← 1 + 2 1 M 2 ˉ ) + 2 1 KL ( M 2 ˉ 2 1 M 2 ˉ ← 1 + 2 1 M 2 ˉ ) ≥ 2 1 h 2 ( M 2 ˉ ← 1 , M 2 ˉ ) . (4) Observe that, in the experiment with Z i ∼ B ( 2 ) Z_i\sim B(2) Z i ∼ B ( 2 ) Pr [ X j i = x ∣ Z i = 2 ] ≥ 2 3 Pr [ X j i = x ] \Pr[X_j^i=x\mid Z_i=2]\ge\frac{2}{3}\Pr[X_j^i=x] Pr [ X j i = x ∣ Z i = 2 ] ≥ 3 2 Pr [ X j i = x ] x ∈ { 0 , 1 } x\in\{0,1\} x ∈ { 0 , 1 }
Lemma A.3 ([10 Lemma 5] ). Suppose two distributions μ , μ ′ \mu,\mu' μ , μ ′ μ ≥ c ⋅ μ ′ \mu\ge c\cdot\mu' μ ≥ c ⋅ μ ′ Π ( X ) \Pi(X) Π ( X ) X X X X ∼ μ X\sim\mu X ∼ μ X ′ ∼ μ ′ X'\sim\mu' X ′ ∼ μ ′
I ( X ; Π ( X ) ) ≥ c ⋅ I ( X ′ ; Π ( X ′ ) ) . I(X;\Pi(X))\ge c\cdot I(X';\Pi(X')). I ( X ; Π ( X )) ≥ c ⋅ I ( X ′ ; Π ( X ′ )) . Applying this lemma gives
I X ≤ n ∼ D 2 ˉ ( M ; X j i ∣ V = j , Z = 2 ) ≥ 2 3 I Z i ∼ B ( 2 ) , X ≤ n ∼ D 2 ˉ ← Z i ( M ; X j i ∣ V = j ) . (5) I_{X^{\le n}\sim D_{\bar{2}}}\left(M;X_j^i\mid V=j,Z=2\right)\ge\frac{2}{3}I_{Z_i\sim B(2),X^{\le n}\sim D_{\bar{2}\leftarrow Z_i}}\left(M;X_j^i\mid V=j\right). \tag*{(5)} I X ≤ n ∼ D 2 ˉ ( M ; X j i ∣ V = j , Z = 2 ) ≥ 3 2 I Z i ∼ B ( 2 ) , X ≤ n ∼ D 2 ˉ ← Z i ( M ; X j i ∣ V = j ) . (5) We next use Lemma A.2 to pass from changing one user to changing all users. For the fixed coordinate j j j Lemma A.2 with a = 2 ˉ a=\bar{2} a = 2 ˉ b = 1 ˉ b=\bar{1} b = 1 ˉ M b M_b M b
∑ i = 1 n h 2 ( M 2 ˉ ← 1 , M 2 ˉ ) ≥ C ⋅ h 2 ( M 1 ˉ , M 2 ˉ ) . (6) \sum_{i=1}^{n}h^2(M_{\bar{2}\leftarrow1},M_{\bar{2}})\ge C\cdot h^2(M_{\bar{1}},M_{\bar{2}}). \tag*{(6)} i = 1 ∑ n h 2 ( M 2 ˉ ← 1 , M 2 ˉ ) ≥ C ⋅ h 2 ( M 1 ˉ , M 2 ˉ ) . (6) Taking expectation over random V = j V=j V = j
E V [ C ⋅ h 2 ( M ˉ 1 , M ˉ 2 ) ] ≤ E V [ ∑ i = 1 n h 2 ( M 2 i ⃗ ← 1 , M ˉ 2 ) ] ≤ 2 E V [ ∑ i = 1 n I Z i ∼ B ( 2 ) , X ≤ n ∼ D 2 i ⃗ ← Z i ( M ; X V i ∣ V ) ] ≤ 3 ∑ i = 1 n I ( M ; X V i ∣ V , Z = 2 ) ≤ 3 d I ( M ; X ≤ n ∣ Z = 2 ) . (7) \begin{aligned}
\mathbb{E}_{V}\left[C\cdot h^{2}(\bar{M}_{1},\bar{M}_{2})\right]
&\le\mathbb{E}_{V}\left[\sum_{i=1}^{n}h^{2}(M_{2\vec{i}\leftarrow1},\bar{M}_{2})\right]\\
&\le2\mathbb{E}_{V}\left[\sum_{i=1}^{n}I_{Z_i\sim B(2),X^{\le n}\sim D_{2\vec{i}\leftarrow Z_i}}\left(M;X_{V}^{i}\mid V\right)\right]\\
&\le3\sum_{i=1}^{n}I\left(M;X_{V}^{i}\mid V,Z=2\right)\\
&\le\frac{3}{d}I\left(M;X^{\le n}\mid Z=2\right). \tag*{(7)}
\end{aligned} E V [ C ⋅ h 2 ( M ˉ 1 , M ˉ 2 ) ] ≤ E V [ i = 1 ∑ n h 2 ( M 2 i ← 1 , M ˉ 2 ) ] ≤ 2 E V [ i = 1 ∑ n I Z i ∼ B ( 2 ) , X ≤ n ∼ D 2 i ← Z i ( M ; X V i ∣ V ) ] ≤ 3 i = 1 ∑ n I ( M ; X V i ∣ V , Z = 2 ) ≤ d 3 I ( M ; X ≤ n ∣ Z = 2 ) . (7) The first inequality in Equation (7) is Equation (6) , averaged over the random coordinate V V V (4) to each user i i i V V V Lemma A.3 as in Equation (5) : since X V i X_{V}^{i} X V i Z = 2 Z=2 Z = 2 Z i ∼ B ( 2 ) Z_i\sim B(2) Z i ∼ B ( 2 ) 2 / 3 2/3 2/3 2 3 \frac{2}{3} 3 2 Z = 2 Z=2 Z = 2 (3) and Equation (2) .
It remains to use the 2 / 3 2/3 2/3 j j j P j P_j P j M M M V = j V=j V = j Z = 1 Z=1 Z = 1 Q Q Q M M M Z = 2 Z=2 Z = 2 Z = 2 Z=2 Z = 2 V V V Q Q Q M ˉ 2 \bar{M}_2 M ˉ 2 j j j P j P_j P j M ˉ r ˉ \bar{M}_{\bar{r}} M ˉ r ˉ j j j P ˉ = E V P V \bar{P}=\mathbb{E}_{V}P_V P ˉ = E V P V Z = 1 Z=1 Z = 1 A = { m : Z ^ ( m ) = 1 } A=\{m:\hat{Z}(m)=1\} A = { m : Z ^ ( m ) = 1 } 2 / 3 2/3 2/3
P ˉ ( A ) − Q ( A ) ≥ 1 3 , \bar{P}(A)-Q(A)\ge\frac{1}{3}, P ˉ ( A ) − Q ( A ) ≥ 3 1 , and hence TV ( P ˉ , Q ) ≥ 1 / 3 \operatorname{TV}(\bar{P},Q)\ge1/3 TV ( P ˉ , Q ) ≥ 1/3
1 3 ≤ TV ( P ˉ , Q ) ≤ E V [ TV ( P V , Q ) ] ≤ 2 E V [ h ( P V , Q ) ] , \frac{1}{3}\le\operatorname{TV}(\bar{P},Q)\le\mathbb{E}_{V}\left[\operatorname{TV}(P_V,Q)\right]\le\sqrt{2}\mathbb{E}_{V}\left[h(P_V,Q)\right], 3 1 ≤ TV ( P ˉ , Q ) ≤ E V [ TV ( P V , Q ) ] ≤ 2 E V [ h ( P V , Q ) ] , By Jensen’s inequality this implies that
E V [ h 2 ( M ˉ 1 , M ˉ 2 ) ] = Ω ( 1 ) . (8) \mathbb{E}_{V}\left[h^{2}(\bar{M}_{1},\bar{M}_{2})\right]=\Omega(1). \tag*{(8)} E V [ h 2 ( M ˉ 1 , M ˉ 2 ) ] = Ω ( 1 ) . (8) Combining Equation (7) and Equation (8) gives
I ( M ; X ≤ n ∣ Z = 2 ) = Ω ( d ) . I\left(M;X^{\le n}\mid Z=2\right)=\Omega(d). I ( M ; X ≤ n ∣ Z = 2 ) = Ω ( d ) . Finally, conditioned on Z = 2 Z=2 Z = 2 M M M X ≤ n X^{\le n} X ≤ n V V V
I ( M ; X ≤ n ∣ V , Z = 2 ) = I ( M ; X ≤ n ∣ Z = 2 ) . I\left(M;X^{\le n}\mid V,Z=2\right)=I\left(M;X^{\le n}\mid Z=2\right). I ( M ; X ≤ n ∣ V , Z = 2 ) = I ( M ; X ≤ n ∣ Z = 2 ) . Since Z ∼ B ( 2 ) Z\sim B(2) Z ∼ B ( 2 )
I ( M ; X ≤ n ∣ V , Z ) ≥ 1 2 I ( M ; X ≤ n ∣ V , Z = 2 ) = Ω ( d ) , I\left(M;X^{\le n}\mid V,Z\right)\ge\frac{1}{2}I\left(M;X^{\le n}\mid V,Z=2\right)=\Omega(d), I ( M ; X ≤ n ∣ V , Z ) ≥ 2 1 I ( M ; X ≤ n ∣ V , Z = 2 ) = Ω ( d ) , as claimed.
To relate the lower bound in Theorem A.1 to private aggregation we recall that differential privacy limits mutual information.
For this purpose we will need only privacy with respect to KL divergence (or Renyi DP of order 1). We say that an algorithm A : X n → Y \mathcal{A}:\mathcal{X}^{n}\to\mathcal{Y} A : X n → Y ρ \rho ρ S , S ′ S,S' S , S ′ KL ( A ( S ) ∥ A ( S ′ ) ) ≤ ρ \operatorname{KL}(\mathcal{A}(S)\Vert\mathcal{A}(S'))\leq\rho KL ( A ( S ) ∥ A ( S ′ )) ≤ ρ
Lemma A.4 ([41 ] ). Assume that the transcript of a communication protocol viewed as the output of an algorithm acting on the users’ inputs is ρ \rho ρ D D D X \mathcal{X} X X ≤ n X^{\leq n} X ≤ n D D D
I ( M ; X ≤ n ) ≤ ρ n . I\left(M;X^{\leq n}\right)\leq\rho n. I ( M ; X ≤ n ) ≤ ρ n . We can now complete the proof of Theorem 4.4 using Lemma 4.5 .
Proof of Theorem 4.4. Let A \mathcal{A} A Problem 4.3 that has access to G ( S ) \mathcal{G}(S) G ( S ) ρ \rho ρ Lemma 4.5 , there is a local n ρ n\rho n ρ A \mathcal{A} A A \mathcal{A} A X ≤ n X^{\leq n} X ≤ n Problem 4.3 , Dist-A \mathcal{A} A M M M
By Theorem A.1 ,
I ( M ; X ≤ n ∣ V , Z ) = Ω ( d ) . I\left(M;X^{\leq n}\mid V,Z\right)=\Omega(d). I ( M ; X ≤ n ∣ V , Z ) = Ω ( d ) . On the other hand, the local n ρ n\rho n ρ n ρ n\rho n ρ v ∈ [ d ] v\in[d] v ∈ [ d ] z ∈ { 1 , 2 } z\in\{1,2\} z ∈ { 1 , 2 } ( V , Z ) = ( v , z ) (V,Z)=(v,z) ( V , Z ) = ( v , z ) D z , v D_{z,v} D z , v
I ( M ; X ≤ n ∣ V = v , Z = z ) ≤ n 2 ρ . I\left(M;X^{\leq n}\mid V=v,Z=z\right)\leq n^{2}\rho. I ( M ; X ≤ n ∣ V = v , Z = z ) ≤ n 2 ρ . Averaging over V V V Z Z Z
I ( M ; X ≤ n ∣ V , Z ) ≤ n 2 ρ . I\left(M;X^{\leq n}\mid V,Z\right)\leq n^{2}\rho. I ( M ; X ≤ n ∣ V , Z ) ≤ n 2 ρ . Combining the two inequalities gives n 2 ρ = Ω ( d ) n^{2}\rho=\Omega(d) n 2 ρ = Ω ( d )
n = Ω ( d ρ ) . n=\Omega\left(\sqrt{\frac{d}{\rho}}\right). n = Ω ( ρ d ) . as claimed.
Analysis of MWEM in the Central Model
We prove Lemma 7.4 using the standard potential argument for MWEM [45 ] , with Δ t \Delta_t Δ t η \eta η
Φ t = ∑ x ∈ D B ( x ) n ⋅ log B ( x ) A t ( x ) . \Phi_t=\sum_{x\in D}\frac{B(x)}{n}\cdot\log\frac{B(x)}{A_t(x)}. Φ t = x ∈ D ∑ n B ( x ) ⋅ log A t ( x ) B ( x ) . We utilize the following two standard properties of relative entropy:
Fact B.1 (Non-negativity of relative entropy). [45 ] Φ t ≥ 0 \Phi_t \ge0 Φ t ≥ 0 t ∈ [ T ] t \in[T] t ∈ [ T ]
Fact B.2 (Jensen’s inequality for relative entropy). [45 ] Φ 0 ≤ log ∣ D ∣ \Phi_0 \le\log|\mathcal{D}| Φ 0 ≤ log ∣ D ∣
We also have the following well-known fact for the exponential function:
Fact B.3. [45 ] For all x ∈ [ − 1 , 1 ] x \in[-1,1] x ∈ [ − 1 , 1 ] exp ( x ) ≤ 1 + x + x 2 \exp(x) \le1 + x + x^2 exp ( x ) ≤ 1 + x + x 2
To bound the error ∣ q t ( A ) − q t ( B ) ∣ |q_t(A)-q_t(B)| ∣ q t ( A ) − q t ( B ) ∣
Lemma B.4. For each t ∈ [ T ] t \in[T] t ∈ [ T ]
Φ t − 1 − Φ t ≥ ( q t ( A t − 1 ) − q t ( B ) 2 n ) 2 − ( m t − q t ( B ) 2 n ) 2 . \Phi_{t-1} - \Phi_t \ge\left(\frac{q_t(A_{t-1}) - q_t(B)}{2n}\right)^2 - \left(\frac{m_t - q_t(B)}{2n}\right)^2. Φ t − 1 − Φ t ≥ ( 2 n q t ( A t − 1 ) − q t ( B ) ) 2 − ( 2 n m t − q t ( B ) ) 2 . Proof. By definition, we have
Φ t − 1 − Φ t = ∑ x ∈ D B ( x ) n log A t ( x ) A t − 1 ( x ) . \Phi_{t-1} - \Phi_t = \sum_{x \in\mathcal{D}} \frac{B(x)}{n} \log\frac{A_t(x)}{A_{t-1}(x)}. Φ t − 1 − Φ t = x ∈ D ∑ n B ( x ) log A t − 1 ( x ) A t ( x ) . Let α t : = m t − q t ( A t − 1 ) 2 n \alpha_t := \frac{m_t-q_t(A_{t-1})}{2n} α t := 2 n m t − q t ( A t − 1 ) β t \beta_t β t t t t
A t ( x ) A t − 1 ( x ) = 1 β t ⋅ exp ( q t ( x ) ⋅ α t ) \frac{A_t(x)}{A_{t-1}(x)} = \frac{1}{\beta_t} \cdot\exp(q_t(x) \cdot\alpha_t) A t − 1 ( x ) A t ( x ) = β t 1 ⋅ exp ( q t ( x ) ⋅ α t ) so that
Φ t − 1 − Φ t = α t ⋅ q t ( B ) n − log β t . \Phi_{t-1} - \Phi_t = \frac{\alpha_t \cdot q_t(B)}{n} - \log\beta_t. Φ t − 1 − Φ t = n α t ⋅ q t ( B ) − log β t . Since we have the normalization factor
β t = ∑ x ∈ D A t − 1 ( x ) n ⋅ exp ( q t ( x ) ⋅ α t ) , \beta_t = \sum_{x \in\mathcal{D}} \frac{A_{t-1}(x)}{n} \cdot\exp(q_t(x) \cdot\alpha_t), β t = x ∈ D ∑ n A t − 1 ( x ) ⋅ exp ( q t ( x ) ⋅ α t ) , Note that A t − 1 / n A_{t-1}/n A t − 1 / n D \mathcal{D} D ∑ x A t − 1 ( x ) = n \sum_x A_{t-1}(x) = n ∑ x A t − 1 ( x ) = n q t ( X ) ∈ [ − 1 , 1 ] q_t(X) \in[-1,1] q t ( X ) ∈ [ − 1 , 1 ] X ∼ A t − 1 / n X \sim A_{t-1}/n X ∼ A t − 1 / n α t \alpha_t α t
log β t ≤ α t q t ( A t − 1 ) n + α t 2 2 ≤ α t q t ( A t − 1 ) n + α t 2 . \log\beta_t \le\frac{\alpha_t q_t(A_{t-1})}{n} + \frac{\alpha_t^2}{2} \le\frac{\alpha_t q_t(A_{t-1})}{n} + \alpha_t^2. log β t ≤ n α t q t ( A t − 1 ) + 2 α t 2 ≤ n α t q t ( A t − 1 ) + α t 2 . Therefore,
Φ t − 1 − Φ t ≥ α t n ⋅ ( q t ( B ) − q t ( A t − 1 ) ) − α t 2 . \Phi_{t-1} - \Phi_t \ge\frac{\alpha_t}{n} \cdot(q_t(B) - q_t(A_{t-1})) - \alpha_t^2. Φ t − 1 − Φ t ≥ n α t ⋅ ( q t ( B ) − q t ( A t − 1 )) − α t 2 . The desired claim then holds from the definition of α t \alpha_t α t
:::
Lemma 7.4. For an integer T ≥ 1 T \ge1 T ≥ 1 ∣ D ∣ ≥ 2 |\mathcal{D}| \ge2 ∣ D ∣ ≥ 2
max q ∈ Q ∣ q ( A ) − q ( B ) ∣ ≲ n ⋅ log ∣ D ∣ T + η . \max_{q \in\mathcal{Q}} |q(A) - q(B)| \lesssim n \cdot\sqrt{\frac{\log|\mathcal{D}|}{T}} + \eta. q ∈ Q max ∣ q ( A ) − q ( B ) ∣ ≲ n ⋅ T log ∣ D ∣ + η . Proof. Firstly, observe that since Δ t = max q ∈ Q ∣ q ( A t − 1 ) − q ( B ) ∣ \Delta_t = \max_{q \in\mathcal{Q}} |q(A_{t-1}) - q(B)| Δ t = max q ∈ Q ∣ q ( A t − 1 ) − q ( B ) ∣
max q ∈ Q ∣ q ( A ) − q ( B ) ∣ ≤ 1 T ∑ t = 1 T Δ t + 1 T max q ∈ Q ∣ q ( A T ) − q ( A 0 ) ∣ \max_{q \in\mathcal{Q}} |q(A) - q(B)| \le\frac{1}{T} \sum_{t=1}^{T} \Delta_t + \frac{1}{T} \max_{q \in\mathcal{Q}} |q(A_T) - q(A_0)| q ∈ Q max ∣ q ( A ) − q ( B ) ∣ ≤ T 1 t = 1 ∑ T Δ t + T 1 q ∈ Q max ∣ q ( A T ) − q ( A 0 ) ∣ @page 38/39 starts_mid=0 ends_mid=1
Fact B.1 (Non-negativity of relative entropy). [45 ] Φ t ≥ 0 \Phi_t \ge0 Φ t ≥ 0 t ∈ [ T ] t \in[T] t ∈ [ T ]
Fact B.2 (Jensen’s inequality for relative entropy). [45 ] Φ 0 ≤ log ∣ D ∣ \Phi_0 \le\log|\mathcal{D}| Φ 0 ≤ log ∣ D ∣
We also have the following well-known fact for the exponential function:
Fact B.3. [45 ] For all x ∈ [ − 1 , 1 ] x \in[-1,1] x ∈ [ − 1 , 1 ] exp ( x ) ≤ 1 + x + x 2 \exp(x) \le1 + x + x^2 exp ( x ) ≤ 1 + x + x 2
To bound the error ∣ q t ( A ) − q t ( B ) ∣ |q_t(A) - q_t(B)| ∣ q t ( A ) − q t ( B ) ∣
Lemma B.4. For each t ∈ [ T ] t \in[T] t ∈ [ T ]
Φ t − 1 − Φ t ≥ ( q t ( A t − 1 ) − q t ( B ) 2 n ) 2 − ( m t − q t ( B ) 2 n ) 2 . \Phi_{t-1} - \Phi_t \ge\left(\frac{q_t(A_{t-1}) - q_t(B)}{2n}\right)^2 - \left(\frac{m_t - q_t(B)}{2n}\right)^2. Φ t − 1 − Φ t ≥ ( 2 n q t ( A t − 1 ) − q t ( B ) ) 2 − ( 2 n m t − q t ( B ) ) 2 . Proof. By definition, we have
Φ t − 1 − Φ t = ∑ x ∈ D B ( x ) n log A t ( x ) A t − 1 ( x ) . \Phi_{t-1} - \Phi_t = \sum_{x \in\mathcal{D}} \frac{B(x)}{n} \log\frac{A_t(x)}{A_{t-1}(x)}. Φ t − 1 − Φ t = x ∈ D ∑ n B ( x ) log A t − 1 ( x ) A t ( x ) . Let α t : = m t − q t ( A t − 1 ) 2 n \alpha_t := \frac{m_t-q_t(A_{t-1})}{2n} α t := 2 n m t − q t ( A t − 1 ) β t \beta_t β t t t t
A t ( x ) A t − 1 ( x ) = 1 β t ⋅ exp ( q t ( x ) ⋅ α t ) \frac{A_t(x)}{A_{t-1}(x)} = \frac{1}{\beta_t} \cdot\exp(q_t(x) \cdot\alpha_t) A t − 1 ( x ) A t ( x ) = β t 1 ⋅ exp ( q t ( x ) ⋅ α t ) so that
Φ t − 1 − Φ t = α t ⋅ q t ( B ) n − log β t . \Phi_{t-1} - \Phi_t = \frac{\alpha_t \cdot q_t(B)}{n} - \log\beta_t. Φ t − 1 − Φ t = n α t ⋅ q t ( B ) − log β t . Since we have the normalization factor
β t = ∑ x ∈ D A t − 1 ( x ) n ⋅ exp ( q t ( x ) ⋅ α t ) , \beta_t = \sum_{x \in\mathcal{D}} \frac{A_{t-1}(x)}{n} \cdot\exp(q_t(x) \cdot\alpha_t), β t = x ∈ D ∑ n A t − 1 ( x ) ⋅ exp ( q t ( x ) ⋅ α t ) , Note that A t − 1 / n A_{t-1}/n A t − 1 / n D \mathcal{D} D ∑ x A t − 1 ( x ) = n \sum_x A_{t-1}(x) = n ∑ x A t − 1 ( x ) = n q t ( X ) ∈ [ − 1 , 1 ] q_t(X) \in[-1,1] q t ( X ) ∈ [ − 1 , 1 ] X ∼ A t − 1 / n X \sim A_{t-1}/n X ∼ A t − 1 / n α t \alpha_t α t
log β t ≤ α t q t ( A t − 1 ) n + α t 2 2 ≤ α t q t ( A t − 1 ) n + α t 2 . \log\beta_t \le\frac{\alpha_t q_t(A_{t-1})}{n} + \frac{\alpha_t^2}{2} \le\frac{\alpha_t q_t(A_{t-1})}{n} + \alpha_t^2. log β t ≤ n α t q t ( A t − 1 ) + 2 α t 2 ≤ n α t q t ( A t − 1 ) + α t 2 . Therefore,
Φ t − 1 − Φ t ≥ α t n ⋅ ( q t ( B ) − q t ( A t − 1 ) ) − α t 2 . \Phi_{t-1} - \Phi_t \ge\frac{\alpha_t}{n} \cdot(q_t(B) - q_t(A_{t-1})) - \alpha_t^2. Φ t − 1 − Φ t ≥ n α t ⋅ ( q t ( B ) − q t ( A t − 1 )) − α t 2 . The desired claim then holds from the definition of α t \alpha_t α t
Lemma 7.4. For an integer T ≥ 1 T \ge1 T ≥ 1 ∣ D ∣ ≥ 2 |\mathcal{D}| \ge2 ∣ D ∣ ≥ 2
max q ∈ Q ∣ q ( A ) − q ( B ) ∣ ≲ n ⋅ log ∣ D ∣ T + η . \max_{q \in\mathcal{Q}} |q(A) - q(B)| \lesssim n \cdot\sqrt{\frac{\log|\mathcal{D}|}{T}} + \eta. q ∈ Q max ∣ q ( A ) − q ( B ) ∣ ≲ n ⋅ T log ∣ D ∣ + η . Proof. Firstly, observe that since Δ t = max q ∈ Q ∣ q ( A t − 1 ) − q ( B ) ∣ \Delta_t = \max_{q \in\mathcal{Q}} |q(A_{t-1}) - q(B)| Δ t = max q ∈ Q ∣ q ( A t − 1 ) − q ( B ) ∣
max q ∈ Q ∣ q ( A ) − q ( B ) ∣ ≤ 1 T ∑ t = 1 T Δ t + 1 T max q ∈ Q ∣ q ( A T ) − q ( A 0 ) ∣ \max_{q \in\mathcal{Q}} |q(A) - q(B)| \le\frac{1}{T} \sum_{t=1}^{T} \Delta_t + \frac{1}{T} \max_{q \in\mathcal{Q}} |q(A_T) - q(A_0)| q ∈ Q max ∣ q ( A ) − q ( B ) ∣ ≤ T 1 t = 1 ∑ T Δ t + T 1 q ∈ Q max ∣ q ( A T ) − q ( A 0 ) ∣ @page 38/39 starts_mid=0 ends_mid=1
Fact B.1 (Non-negativity of relative entropy). [45 ] Φ t ≥ 0 \Phi_t \ge0 Φ t ≥ 0 t ∈ [ T ] t \in[T] t ∈ [ T ]
Fact B.2 (Jensen’s inequality for relative entropy). [45 ] Φ 0 ≤ log ∣ D ∣ \Phi_0 \le\log|\mathcal{D}| Φ 0 ≤ log ∣ D ∣
We also have the following well-known fact for the exponential function:
Fact B.3. [45 ] For all x ∈ [ − 1 , 1 ] x \in[-1,1] x ∈ [ − 1 , 1 ] exp ( x ) ≤ 1 + x + x 2 \exp(x) \le1 + x + x^2 exp ( x ) ≤ 1 + x + x 2
To bound the error ∣ q t ( A ) − q t ( B ) ∣ |q_t(A) - q_t(B)| ∣ q t ( A ) − q t ( B ) ∣
Lemma B.4. For each t ∈ [ T ] t \in[T] t ∈ [ T ]
Φ t − 1 − Φ t ≥ ( q t ( A t − 1 ) − q t ( B ) 2 n ) 2 − ( m t − q t ( B ) 2 n ) 2 . \Phi_{t-1} - \Phi_t \ge\left(\frac{q_t(A_{t-1}) - q_t(B)}{2n}\right)^2 - \left(\frac{m_t - q_t(B)}{2n}\right)^2. Φ t − 1 − Φ t ≥ ( 2 n q t ( A t − 1 ) − q t ( B ) ) 2 − ( 2 n m t − q t ( B ) ) 2 . Proof. By definition, we have
Φ t − 1 − Φ t = ∑ x ∈ D B ( x ) n log A t ( x ) A t − 1 ( x ) . \Phi_{t-1} - \Phi_t = \sum_{x \in\mathcal{D}} \frac{B(x)}{n} \log\frac{A_t(x)}{A_{t-1}(x)}. Φ t − 1 − Φ t = x ∈ D ∑ n B ( x ) log A t − 1 ( x ) A t ( x ) . Let α t : = m t − q t ( A t − 1 ) 2 n \alpha_t := \frac{m_t-q_t(A_{t-1})}{2n} α t := 2 n m t − q t ( A t − 1 ) β t \beta_t β t t t t
A t ( x ) A t − 1 ( x ) = 1 β t ⋅ exp ( q t ( x ) ⋅ α t ) \frac{A_t(x)}{A_{t-1}(x)} = \frac{1}{\beta_t} \cdot\exp(q_t(x) \cdot\alpha_t) A t − 1 ( x ) A t ( x ) = β t 1 ⋅ exp ( q t ( x ) ⋅ α t ) so that
Φ t − 1 − Φ t = α t ⋅ q t ( B ) n − log β t . \Phi_{t-1} - \Phi_t = \frac{\alpha_t \cdot q_t(B)}{n} - \log\beta_t. Φ t − 1 − Φ t = n α t ⋅ q t ( B ) − log β t . Since we have the normalization factor
β t = ∑ x ∈ D A t − 1 ( x ) n ⋅ exp ( q t ( x ) ⋅ α t ) , \beta_t = \sum_{x \in\mathcal{D}} \frac{A_{t-1}(x)}{n} \cdot\exp(q_t(x) \cdot\alpha_t), β t = x ∈ D ∑ n A t − 1 ( x ) ⋅ exp ( q t ( x ) ⋅ α t ) , Note that A t − 1 / n A_{t-1}/n A t − 1 / n D \mathcal{D} D ∑ x A t − 1 ( x ) = n \sum_x A_{t-1}(x) = n ∑ x A t − 1 ( x ) = n q t ( X ) ∈ [ − 1 , 1 ] q_t(X) \in[-1,1] q t ( X ) ∈ [ − 1 , 1 ] X ∼ A t − 1 / n X \sim A_{t-1}/n X ∼ A t − 1 / n α t \alpha_t α t
log β t ≤ α t q t ( A t − 1 ) n + α t 2 2 ≤ α t q t ( A t − 1 ) n + α t 2 . \log\beta_t \le\frac{\alpha_t q_t(A_{t-1})}{n} + \frac{\alpha_t^2}{2} \le\frac{\alpha_t q_t(A_{t-1})}{n} + \alpha_t^2. log β t ≤ n α t q t ( A t − 1 ) + 2 α t 2 ≤ n α t q t ( A t − 1 ) + α t 2 . Therefore,
Φ t − 1 − Φ t ≥ α t n ⋅ ( q t ( B ) − q t ( A t − 1 ) ) − α t 2 . \Phi_{t-1} - \Phi_t \ge\frac{\alpha_t}{n} \cdot(q_t(B) - q_t(A_{t-1})) - \alpha_t^2. Φ t − 1 − Φ t ≥ n α t ⋅ ( q t ( B ) − q t ( A t − 1 )) − α t 2 . The desired claim then holds from the definition of α t \alpha_t α t
Lemma 7.4. For an integer T ≥ 1 T \ge1 T ≥ 1 ∣ D ∣ ≥ 2 |\mathcal{D}| \ge2 ∣ D ∣ ≥ 2
max q ∈ Q ∣ q ( A ) − q ( B ) ∣ ≲ n ⋅ log ∣ D ∣ T + η . \max_{q \in\mathcal{Q}} |q(A) - q(B)| \lesssim n \cdot\sqrt{\frac{\log|\mathcal{D}|}{T}} + \eta. q ∈ Q max ∣ q ( A ) − q ( B ) ∣ ≲ n ⋅ T log ∣ D ∣ + η . Proof. Firstly, observe that since Δ t = max q ∈ Q ∣ q ( A t − 1 ) − q ( B ) ∣ \Delta_t = \max_{q \in\mathcal{Q}} |q(A_{t-1}) - q(B)| Δ t = max q ∈ Q ∣ q ( A t − 1 ) − q ( B ) ∣
max q ∈ Q ∣ q ( A ) − q ( B ) ∣ ≤ 1 T ∑ t = 1 T Δ t + 1 T max q ∈ Q ∣ q ( A T ) − q ( A 0 ) ∣ \max_{q \in\mathcal{Q}} |q(A) - q(B)| \le\frac{1}{T} \sum_{t=1}^{T} \Delta_t + \frac{1}{T} \max_{q \in\mathcal{Q}} |q(A_T) - q(A_0)| q ∈ Q max ∣ q ( A ) − q ( B ) ∣ ≤ T 1 t = 1 ∑ T Δ t + T 1 q ∈ Q max ∣ q ( A T ) − q ( A 0 ) ∣ @page 38/39 starts_mid=0 ends_mid=1
Fact B.1 (Non-negativity of relative entropy). [45 ] Φ t ≥ 0 \Phi_t \ge0 Φ t ≥ 0 t ∈ [ T ] t \in[T] t ∈ [ T ]
Fact B.2 (Jensen’s inequality for relative entropy). [45 ] Φ 0 ≤ log ∣ D ∣ \Phi_0 \le\log|\mathcal{D}| Φ 0 ≤ log ∣ D ∣
We also have the following well-known fact for the exponential function:
Fact B.3. [45 ] For all x ∈ [ − 1 , 1 ] x \in[-1,1] x ∈ [ − 1 , 1 ] exp ( x ) ≤ 1 + x + x 2 \exp(x) \le1 + x + x^2 exp ( x ) ≤ 1 + x + x 2
To bound the error ∣ q t ( A ) − q t ( B ) ∣ |q_t(A) - q_t(B)| ∣ q t ( A ) − q t ( B ) ∣
Lemma B.4. For each t ∈ [ T ] t \in[T] t ∈ [ T ]
Φ t − 1 − Φ t ≥ ( q t ( A t − 1 ) − q t ( B ) 2 n ) 2 − ( m t − q t ( B ) 2 n ) 2 . \Phi_{t-1} - \Phi_t \ge\left(\frac{q_t(A_{t-1}) - q_t(B)}{2n}\right)^2 - \left(\frac{m_t - q_t(B)}{2n}\right)^2. Φ t − 1 − Φ t ≥ ( 2 n q t ( A t − 1 ) − q t ( B ) ) 2 − ( 2 n m t − q t ( B ) ) 2 . Proof. By definition, we have
Φ t − 1 − Φ t = ∑ x ∈ D B ( x ) n log A t ( x ) A t − 1 ( x ) . \Phi_{t-1} - \Phi_t = \sum_{x \in\mathcal{D}} \frac{B(x)}{n} \log\frac{A_t(x)}{A_{t-1}(x)}. Φ t − 1 − Φ t = x ∈ D ∑ n B ( x ) log A t − 1 ( x ) A t ( x ) . Let α t : = m t − q t ( A t − 1 ) 2 n \alpha_t := \frac{m_t-q_t(A_{t-1})}{2n} α t := 2 n m t − q t ( A t − 1 ) β t \beta_t β t t t t
A t ( x ) A t − 1 ( x ) = 1 β t ⋅ exp ( q t ( x ) ⋅ α t ) \frac{A_t(x)}{A_{t-1}(x)} = \frac{1}{\beta_t} \cdot\exp(q_t(x) \cdot\alpha_t) A t − 1 ( x ) A t ( x ) = β t 1 ⋅ exp ( q t ( x ) ⋅ α t ) so that
Φ t − 1 − Φ t = α t ⋅ q t ( B ) n − log β t . \Phi_{t-1} - \Phi_t = \frac{\alpha_t \cdot q_t(B)}{n} - \log\beta_t. Φ t − 1 − Φ t = n α t ⋅ q t ( B ) − log β t . Since we have the normalization factor
β t = ∑ x ∈ D A t − 1 ( x ) n ⋅ exp ( q t ( x ) ⋅ α t ) , \beta_t = \sum_{x \in\mathcal{D}} \frac{A_{t-1}(x)}{n} \cdot\exp(q_t(x) \cdot\alpha_t), β t = x ∈ D ∑ n A t − 1 ( x ) ⋅ exp ( q t ( x ) ⋅ α t ) , Note that A t − 1 / n A_{t-1}/n A t − 1 / n D \mathcal{D} D ∑ x A t − 1 ( x ) = n \sum_x A_{t-1}(x) = n ∑ x A t − 1 ( x ) = n q t ( X ) ∈ [ − 1 , 1 ] q_t(X) \in[-1,1] q t ( X ) ∈ [ − 1 , 1 ] X ∼ A t − 1 / n X \sim A_{t-1}/n X ∼ A t − 1 / n α t \alpha_t α t
log β t ≤ α t q t ( A t − 1 ) n + α t 2 2 ≤ α t q t ( A t − 1 ) n + α t 2 . \log\beta_t \le\frac{\alpha_t q_t(A_{t-1})}{n} + \frac{\alpha_t^2}{2} \le\frac{\alpha_t q_t(A_{t-1})}{n} + \alpha_t^2. log β t ≤ n α t q t ( A t − 1 ) + 2 α t 2 ≤ n α t q t ( A t − 1 ) + α t 2 . Therefore,
Φ t − 1 − Φ t ≥ α t n ⋅ ( q t ( B ) − q t ( A t − 1 ) ) − α t 2 . \Phi_{t-1} - \Phi_t \ge\frac{\alpha_t}{n} \cdot(q_t(B) - q_t(A_{t-1})) - \alpha_t^2. Φ t − 1 − Φ t ≥ n α t ⋅ ( q t ( B ) − q t ( A t − 1 )) − α t 2 . The desired claim then holds from the definition of α t \alpha_t α t
Lemma 7.4. For an integer T ≥ 1 T \ge1 T ≥ 1 ∣ D ∣ ≥ 2 |\mathcal{D}| \ge2 ∣ D ∣ ≥ 2
max q ∈ Q ∣ q ( A ) − q ( B ) ∣ ≲ n ⋅ log ∣ D ∣ T + η . \max_{q \in\mathcal{Q}} |q(A) - q(B)| \lesssim n \cdot\sqrt{\frac{\log|\mathcal{D}|}{T}} + \eta. q ∈ Q max ∣ q ( A ) − q ( B ) ∣ ≲ n ⋅ T log ∣ D ∣ + η . Proof. Firstly, observe that since Δ t = max q ∈ Q ∣ q ( A t − 1 ) − q ( B ) ∣ \Delta_t = \max_{q \in\mathcal{Q}} |q(A_{t-1}) - q(B)| Δ t = max q ∈ Q ∣ q ( A t − 1 ) − q ( B ) ∣
max q ∈ Q ∣ q ( A ) − q ( B ) ∣ ≤ 1 T ∑ t = 1 T Δ t + 1 T max q ∈ Q ∣ q ( A T ) − q ( A 0 ) ∣ \max_{q \in\mathcal{Q}} |q(A) - q(B)| \le\frac{1}{T} \sum_{t=1}^{T} \Delta_t + \frac{1}{T} \max_{q \in\mathcal{Q}} |q(A_T) - q(A_0)| q ∈ Q max ∣ q ( A ) − q ( B ) ∣ ≤ T 1 t = 1 ∑ T Δ t + T 1 q ∈ Q max ∣ q ( A T ) − q ( A 0 ) ∣ @page 38/39 starts_mid=0 ends_mid=1
Fact B.1 (Non-negativity of relative entropy). [45 ] Φ t ≥ 0 \Phi_t \ge0 Φ t ≥ 0 t ∈ [ T ] t \in[T] t ∈ [ T ]
Fact B.2 (Jensen’s inequality for relative entropy). [45 ] Φ 0 ≤ log ∣ D ∣ \Phi_0 \le\log|\mathcal{D}| Φ 0 ≤ log ∣ D ∣
We also have the following well-known fact for the exponential function:
Fact B.3. [45 ] For all x ∈ [ − 1 , 1 ] x \in[-1,1] x ∈ [ − 1 , 1 ] exp ( x ) ≤ 1 + x + x 2 \exp(x) \le1 + x + x^2 exp ( x ) ≤ 1 + x + x 2
To bound the error ∣ q t ( A ) − q t ( B ) ∣ |q_t(A) - q_t(B)| ∣ q t ( A ) − q t ( B ) ∣
Lemma B.4. For each t ∈ [ T ] t \in[T] t ∈ [ T ]
Φ t − 1 − Φ t ≥ ( q t ( A t − 1 ) − q t ( B ) 2 n ) 2 − ( m t − q t ( B ) 2 n ) 2 . \Phi_{t-1} - \Phi_t \ge\left(\frac{q_t(A_{t-1}) - q_t(B)}{2n}\right)^2 - \left(\frac{m_t - q_t(B)}{2n}\right)^2. Φ t − 1 − Φ t ≥ ( 2 n q t ( A t − 1 ) − q t ( B ) ) 2 − ( 2 n m t − q t ( B ) ) 2 . Proof. By definition, we have
Φ t − 1 − Φ t = ∑ x ∈ D B ( x ) n log A t ( x ) A t − 1 ( x ) . \Phi_{t-1} - \Phi_t = \sum_{x \in\mathcal{D}} \frac{B(x)}{n} \log\frac{A_t(x)}{A_{t-1}(x)}. Φ t − 1 − Φ t = x ∈ D ∑ n B ( x ) log A t − 1 ( x ) A t ( x ) . Let α t : = m t − q t ( A t − 1 ) 2 n \alpha_t := \frac{m_t-q_t(A_{t-1})}{2n} α t := 2 n m t − q t ( A t − 1 ) β t \beta_t β t t t t
A t ( x ) A t − 1 ( x ) = 1 β t ⋅ exp ( q t ( x ) ⋅ α t ) \frac{A_t(x)}{A_{t-1}(x)} = \frac{1}{\beta_t} \cdot\exp(q_t(x) \cdot\alpha_t) A t − 1 ( x ) A t ( x ) = β t 1 ⋅ exp ( q t ( x ) ⋅ α t ) so that
Φ t − 1 − Φ t = α t ⋅ q t ( B ) n − log β t . \Phi_{t-1} - \Phi_t = \frac{\alpha_t \cdot q_t(B)}{n} - \log\beta_t. Φ t − 1 − Φ t = n α t ⋅ q t ( B ) − log β t . Since we have the normalization factor
β t = ∑ x ∈ D A t − 1 ( x ) n ⋅ exp ( q t ( x ) ⋅ α t ) , \beta_t = \sum_{x \in\mathcal{D}} \frac{A_{t-1}(x)}{n} \cdot\exp(q_t(x) \cdot\alpha_t), β t = x ∈ D ∑ n A t − 1 ( x ) ⋅ exp ( q t ( x ) ⋅ α t ) , Note that A t − 1 / n A_{t-1}/n A t − 1 / n D \mathcal{D} D ∑ x A t − 1 ( x ) = n \sum_x A_{t-1}(x) = n ∑ x A t − 1 ( x ) = n q t ( X ) ∈ [ − 1 , 1 ] q_t(X) \in[-1,1] q t ( X ) ∈ [ − 1 , 1 ] X ∼ A t − 1 / n X \sim A_{t-1}/n X ∼ A t − 1 / n α t \alpha_t α t
log β t ≤ α t q t ( A t − 1 ) n + α t 2 2 ≤ α t q t ( A t − 1 ) n + α t 2 . \log\beta_t \le\frac{\alpha_t q_t(A_{t-1})}{n} + \frac{\alpha_t^2}{2} \le\frac{\alpha_t q_t(A_{t-1})}{n} + \alpha_t^2. log β t ≤ n α t q t ( A t − 1 ) + 2 α t 2 ≤ n α t q t ( A t − 1 ) + α t 2 . Therefore,
Φ t − 1 − Φ t ≥ α t n ⋅ ( q t ( B ) − q t ( A t − 1 ) ) − α t 2 . \Phi_{t-1} - \Phi_t \ge\frac{\alpha_t}{n} \cdot(q_t(B) - q_t(A_{t-1})) - \alpha_t^2. Φ t − 1 − Φ t ≥ n α t ⋅ ( q t ( B ) − q t ( A t − 1 )) − α t 2 . The desired claim then holds from the definition of α t \alpha_t α t
Lemma 7.4. For an integer T ≥ 1 T \ge1 T ≥ 1 ∣ D ∣ ≥ 2 |\mathcal{D}| \ge2 ∣ D ∣ ≥ 2
max q ∈ Q ∣ q ( A ) − q ( B ) ∣ ≲ n ⋅ log ∣ D ∣ T + η . \max_{q \in\mathcal{Q}} |q(A) - q(B)| \lesssim n \cdot\sqrt{\frac{\log|\mathcal{D}|}{T}} + \eta. q ∈ Q max ∣ q ( A ) − q ( B ) ∣ ≲ n ⋅ T log ∣ D ∣ + η . Proof. Firstly, observe that since Δ t = max q ∈ Q ∣ q ( A t − 1 ) − q ( B ) ∣ \Delta_t = \max_{q \in\mathcal{Q}} |q(A_{t-1}) - q(B)| Δ t = max q ∈ Q ∣ q ( A t − 1 ) − q ( B ) ∣
max q ∈ Q ∣ q ( A ) − q ( B ) ∣ ≤ 1 T ∑ t = 1 T Δ t + 1 T max q ∈ Q ∣ q ( A T ) − q ( A 0 ) ∣ \max_{q \in\mathcal{Q}} |q(A) - q(B)| \le\frac{1}{T} \sum_{t=1}^{T} \Delta_t + \frac{1}{T} \max_{q \in\mathcal{Q}} |q(A_T) - q(A_0)| q ∈ Q max ∣ q ( A ) − q ( B ) ∣ ≤ T 1 t = 1 ∑ T Δ t + T 1 q ∈ Q max ∣ q ( A T ) − q ( A 0 ) ∣ @page 38/39 starts_mid=0 ends_mid=1
Fact B.1 (Non-negativity of relative entropy). [45 ] Φ t ≥ 0 \Phi_t \ge0 Φ t ≥ 0 t ∈ [ T ] t \in[T] t ∈ [ T ]
Fact B.2 (Jensen’s inequality for relative entropy). [45 ] Φ 0 ≤ log ∣ D ∣ \Phi_0 \le\log|\mathcal{D}| Φ 0 ≤ log ∣ D ∣
We also have the following well-known fact for the exponential function:
Fact B.3. [45 ] For all x ∈ [ − 1 , 1 ] x \in[-1,1] x ∈ [ − 1 , 1 ] exp ( x ) ≤ 1 + x + x 2 \exp(x) \le1 + x + x^2 exp ( x ) ≤ 1 + x + x 2
To bound the error ∣ q t ( A ) − q t ( B ) ∣ |q_t(A) - q_t(B)| ∣ q t ( A ) − q t ( B ) ∣
Lemma B.4. For each t ∈ [ T ] t \in[T] t ∈ [ T ]
Φ t − 1 − Φ t ≥ ( q t ( A t − 1 ) − q t ( B ) 2 n ) 2 − ( m t − q t ( B ) 2 n ) 2 . \Phi_{t-1} - \Phi_t \ge\left(\frac{q_t(A_{t-1}) - q_t(B)}{2n}\right)^2 - \left(\frac{m_t - q_t(B)}{2n}\right)^2. Φ t − 1 − Φ t ≥ ( 2 n q t ( A t − 1 ) − q t ( B ) ) 2 − ( 2 n m t − q t ( B ) ) 2 . Proof. By definition, we have
Φ t − 1 − Φ t = ∑ x ∈ D B ( x ) n log A t ( x ) A t − 1 ( x ) . \Phi_{t-1} - \Phi_t = \sum_{x \in\mathcal{D}} \frac{B(x)}{n} \log\frac{A_t(x)}{A_{t-1}(x)}. Φ t − 1 − Φ t = x ∈ D ∑ n B ( x ) log A t − 1 ( x ) A t ( x ) . Let α t : = m t − q t ( A t − 1 ) 2 n \alpha_t := \frac{m_t-q_t(A_{t-1})}{2n} α t := 2 n m t − q t ( A t − 1 ) β t \beta_t β t t t t
A t ( x ) A t − 1 ( x ) = 1 β t ⋅ exp ( q t ( x ) ⋅ α t ) \frac{A_t(x)}{A_{t-1}(x)} = \frac{1}{\beta_t} \cdot\exp(q_t(x) \cdot\alpha_t) A t − 1 ( x ) A t ( x ) = β t 1 ⋅ exp ( q t ( x ) ⋅ α t ) so that
Φ t − 1 − Φ t = α t ⋅ q t ( B ) n − log β t . \Phi_{t-1} - \Phi_t = \frac{\alpha_t \cdot q_t(B)}{n} - \log\beta_t. Φ t − 1 − Φ t = n α t ⋅ q t ( B ) − log β t . Since we have the normalization factor
β t = ∑ x ∈ D A t − 1 ( x ) n ⋅ exp ( q t ( x ) ⋅ α t ) , \beta_t = \sum_{x \in\mathcal{D}} \frac{A_{t-1}(x)}{n} \cdot\exp(q_t(x) \cdot\alpha_t), β t = x ∈ D ∑ n A t − 1 ( x ) ⋅ exp ( q t ( x ) ⋅ α t ) , Note that A t − 1 / n A_{t-1}/n A t − 1 / n D \mathcal{D} D ∑ x A t − 1 ( x ) = n \sum_x A_{t-1}(x) = n ∑ x A t − 1 ( x ) = n q t ( X ) ∈ [ − 1 , 1 ] q_t(X) \in[-1,1] q t ( X ) ∈ [ − 1 , 1 ] X ∼ A t − 1 / n X \sim A_{t-1}/n X ∼ A t − 1 / n α t \alpha_t α t
log β t ≤ α t q t ( A t − 1 ) n + α t 2 2 ≤ α t q t ( A t − 1 ) n + α t 2 . \log\beta_t \le\frac{\alpha_t q_t(A_{t-1})}{n} + \frac{\alpha_t^2}{2} \le\frac{\alpha_t q_t(A_{t-1})}{n} + \alpha_t^2. log β t ≤ n α t q t ( A t − 1 ) + 2 α t 2 ≤ n α t q t ( A t − 1 ) + α t 2 . Therefore,
Φ t − 1 − Φ t ≥ α t n ⋅ ( q t ( B ) − q t ( A t − 1 ) ) − α t 2 . \Phi_{t-1} - \Phi_t \ge\frac{\alpha_t}{n} \cdot(q_t(B) - q_t(A_{t-1})) - \alpha_t^2. Φ t − 1 − Φ t ≥ n α t ⋅ ( q t ( B ) − q t ( A t − 1 )) − α t 2 . The desired claim then holds from the definition of α t \alpha_t α t
Lemma 7.4. For an integer T ≥ 1 T \ge1 T ≥ 1 ∣ D ∣ ≥ 2 |\mathcal{D}| \ge2 ∣ D ∣ ≥ 2
max q ∈ Q ∣ q ( A ) − q ( B ) ∣ ≲ n ⋅ log ∣ D ∣ T + η . \max_{q \in\mathcal{Q}} |q(A) - q(B)| \lesssim n \cdot\sqrt{\frac{\log|\mathcal{D}|}{T}} + \eta. q ∈ Q max ∣ q ( A ) − q ( B ) ∣ ≲ n ⋅ T log ∣ D ∣ + η . Proof. Firstly, observe that since Δ t = max q ∈ Q ∣ q ( A t − 1 ) − q ( B ) ∣ \Delta_t = \max_{q \in\mathcal{Q}} |q(A_{t-1}) - q(B)| Δ t = max q ∈ Q ∣ q ( A t − 1 ) − q ( B ) ∣
max q ∈ Q ∣ q ( A ) − q ( B ) ∣ ≤ 1 T ∑ t = 1 T Δ t + 1 T max q ∈ Q ∣ q ( A T ) − q ( A 0 ) ∣ \max_{q \in\mathcal{Q}} |q(A) - q(B)| \le\frac{1}{T} \sum_{t=1}^{T} \Delta_t + \frac{1}{T} \max_{q \in\mathcal{Q}} |q(A_T) - q(A_0)| q ∈ Q max ∣ q ( A ) − q ( B ) ∣ ≤ T 1 t = 1 ∑ T Δ t + T 1 q ∈ Q max ∣ q ( A T ) − q ( A 0 ) ∣ @page 38/39 starts_mid=0 ends_mid=1
Fact B.1 (Non-negativity of relative entropy). [45 ] Φ t ≥ 0 \Phi_t \ge0 Φ t ≥ 0 t ∈ [ T ] t \in[T] t ∈ [ T ]
Fact B.2 (Jensen’s inequality for relative entropy). [45 ] Φ 0 ≤ log ∣ D ∣ \Phi_0 \le\log|\mathcal{D}| Φ 0 ≤ log ∣ D ∣
We also have the following well-known fact for the exponential function:
Fact B.3. [45 ] For all x ∈ [ − 1 , 1 ] x \in[-1,1] x ∈ [ − 1 , 1 ] exp ( x ) ≤ 1 + x + x 2 \exp(x) \le1 + x + x^2 exp ( x ) ≤ 1 + x + x 2
To bound the error ∣ q t ( A ) − q t ( B ) ∣ |q_t(A) - q_t(B)| ∣ q t ( A ) − q t ( B ) ∣
Lemma B.4. For each t ∈ [ T ] t \in[T] t ∈ [ T ]
Φ t − 1 − Φ t ≥ ( q t ( A t − 1 ) − q t ( B ) 2 n ) 2 − ( m t − q t ( B ) 2 n ) 2 . \Phi_{t-1} - \Phi_t \ge\left(\frac{q_t(A_{t-1}) - q_t(B)}{2n}\right)^2 - \left(\frac{m_t - q_t(B)}{2n}\right)^2. Φ t − 1 − Φ t ≥ ( 2 n q t ( A t − 1 ) − q t ( B ) ) 2 − ( 2 n m t − q t ( B ) ) 2 . Proof. By definition, we have
Φ t − 1 − Φ t = ∑ x ∈ D B ( x ) n log A t ( x ) A t − 1 ( x ) . \Phi_{t-1} - \Phi_t = \sum_{x \in\mathcal{D}} \frac{B(x)}{n} \log\frac{A_t(x)}{A_{t-1}(x)}. Φ t − 1 − Φ t = x ∈ D ∑ n B ( x ) log A t − 1 ( x ) A t ( x ) . Let α t : = m t − q t ( A t − 1 ) 2 n \alpha_t := \frac{m_t-q_t(A_{t-1})}{2n} α t := 2 n m t − q t ( A t − 1 ) β t \beta_t β t t t t
A t ( x ) A t − 1 ( x ) = 1 β t ⋅ exp ( q t ( x ) ⋅ α t ) \frac{A_t(x)}{A_{t-1}(x)} = \frac{1}{\beta_t} \cdot\exp(q_t(x) \cdot\alpha_t) A t − 1 ( x ) A t ( x ) = β t 1 ⋅ exp ( q t ( x ) ⋅ α t ) so that
Φ t − 1 − Φ t = α t ⋅ q t ( B ) n − log β t . \Phi_{t-1} - \Phi_t = \frac{\alpha_t \cdot q_t(B)}{n} - \log\beta_t. Φ t − 1 − Φ t = n α t ⋅ q t ( B ) − log β t . Since we have the normalization factor
β t = ∑ x ∈ D A t − 1 ( x ) n ⋅ exp ( q t ( x ) ⋅ α t ) , \beta_t = \sum_{x \in\mathcal{D}} \frac{A_{t-1}(x)}{n} \cdot\exp(q_t(x) \cdot\alpha_t), β t = x ∈ D ∑ n A t − 1 ( x ) ⋅ exp ( q t ( x ) ⋅ α t ) , Note that A t − 1 / n A_{t-1}/n A t − 1 / n D \mathcal{D} D ∑ x A t − 1 ( x ) = n \sum_x A_{t-1}(x) = n ∑ x A t − 1 ( x ) = n q t ( X ) ∈ [ − 1 , 1 ] q_t(X) \in[-1,1] q t ( X ) ∈ [ − 1 , 1 ] X ∼ A t − 1 / n X \sim A_{t-1}/n X ∼ A t − 1 / n α t \alpha_t α t
log β t ≤ α t q t ( A t − 1 ) n + α t 2 2 ≤ α t q t ( A t − 1 ) n + α t 2 . \log\beta_t \le\frac{\alpha_t q_t(A_{t-1})}{n} + \frac{\alpha_t^2}{2} \le\frac{\alpha_t q_t(A_{t-1})}{n} + \alpha_t^2. log β t ≤ n α t q t ( A t − 1 ) + 2 α t 2 ≤ n α t q t ( A t − 1 ) + α t 2 . Therefore,
Φ t − 1 − Φ t ≥ α t n ⋅ ( q t ( B ) − q t ( A t − 1 ) ) − α t 2 . \Phi_{t-1} - \Phi_t \ge\frac{\alpha_t}{n} \cdot(q_t(B) - q_t(A_{t-1})) - \alpha_t^2. Φ t − 1 − Φ t ≥ n α t ⋅ ( q t ( B ) − q t ( A t − 1 )) − α t 2 . The desired claim then holds from the definition of α t \alpha_t α t
Lemma 7.4. For an integer T ≥ 1 T \ge1 T ≥ 1 ∣ D ∣ ≥ 2 |\mathcal{D}| \ge2 ∣ D ∣ ≥ 2
max q ∈ Q ∣ q ( A ) − q ( B ) ∣ ≲ n ⋅ log ∣ D ∣ T + η . \max_{q \in\mathcal{Q}} |q(A) - q(B)| \lesssim n \cdot\sqrt{\frac{\log|\mathcal{D}|}{T}} + \eta. q ∈ Q max ∣ q ( A ) − q ( B ) ∣ ≲ n ⋅ T log ∣ D ∣ + η . Proof. Firstly, observe that since Δ t = max q ∈ Q ∣ q ( A t − 1 ) − q ( B ) ∣ \Delta_t = \max_{q \in\mathcal{Q}} |q(A_{t-1}) - q(B)| Δ t = max q ∈ Q ∣ q ( A t − 1 ) − q ( B ) ∣
max q ∈ Q ∣ q ( A ) − q ( B ) ∣ ≤ 1 T ∑ t = 1 T Δ t + 1 T max q ∈ Q ∣ q ( A T ) − q ( A 0 ) ∣ \max_{q \in\mathcal{Q}} |q(A) - q(B)| \le\frac{1}{T} \sum_{t=1}^{T} \Delta_t + \frac{1}{T} \max_{q \in\mathcal{Q}} |q(A_T) - q(A_0)| q ∈ Q max ∣ q ( A ) − q ( B ) ∣ ≤ T 1 t = 1 ∑ T Δ t + T 1 q ∈ Q max ∣ q ( A T ) − q ( A 0 ) ∣ ≤ 1 T ∑ t = 1 T Δ t + 2 n T \le\frac{1}{T}\sum_{t=1}^{T}\Delta_t+\frac{2n}{T} ≤ T 1 t = 1 ∑ T Δ t + T 2 n On the accuracy event of Lemma 7.3 we have that Δ t ≤ ∣ q t ( A t − 1 ) − q t ( B ) ∣ + η \Delta_t \leq\lvert q_t(A_{t-1})-q_t(B)\rvert+\eta Δ t ≤ ∣ q t ( A t − 1 ) − q t ( B )∣ + η ∣ m t − q t ( B ) ∣ ≤ η \lvert m_t-q_t(B)\rvert\leq\eta ∣ m t − q t ( B )∣ ≤ η t ∈ [ T ] t\in[T] t ∈ [ T ]
1 T ∑ t ∈ [ T ] Δ t ≤ ( n 2 T ⋅ ∑ t ∈ [ T ] ( Φ t − 1 − Φ t ) + η 2 ) 1 / 2 + η . \frac{1}{T}\sum_{t\in[T]}\Delta_t\leq\left(\frac{n^2}{T}\cdot\sum_{t\in[T]}(\Phi_{t-1}-\Phi_t)+\eta^2\right)^{1/2}+\eta. T 1 t ∈ [ T ] ∑ Δ t ≤ T n 2 ⋅ t ∈ [ T ] ∑ ( Φ t − 1 − Φ t ) + η 2 1/2 + η . By a telescoping argument, observe that ∑ t ∈ [ T ] ( Φ t − 1 − Φ t ) = Φ 0 − Φ T \sum_{t\in[T]}(\Phi_{t-1}-\Phi_t)=\Phi_0-\Phi_T ∑ t ∈ [ T ] ( Φ t − 1 − Φ t ) = Φ 0 − Φ T
1 T ∑ t ∈ [ T ] Δ t ≤ ( n 2 ⋅ log ( ∣ D ∣ ) T + η 2 ) 1 / 2 + η . \frac{1}{T}\sum_{t\in[T]}\Delta_t\leq\left(\frac{n^2\cdot\log(\lvert\mathcal{D}\rvert)}{T}+\eta^2\right)^{1/2}+\eta. T 1 t ∈ [ T ] ∑ Δ t ≤ ( T n 2 ⋅ log (∣ D ∣) + η 2 ) 1/2 + η . Since x + y ≤ x + y \sqrt{x+y}\leq\sqrt{x}+\sqrt{y} x + y ≤ x + y 2 n / T = O ( n log ∣ D ∣ / T ) 2n/T=O(n\sqrt{\log\lvert\mathcal{D}\rvert/T}) 2 n / T = O ( n log ∣ D ∣ / T ) ∣ D ∣ ≥ 2 \lvert\mathcal{D}\rvert\geq2 ∣ D ∣ ≥ 2 T ≥ 1 T\geq1 T ≥ 1
max q ∈ Q ∣ q ( A ) − q ( B ) ∣ ≲ n ⋅ log ∣ D ∣ T + η . \max_{q\in\mathcal{Q}}\lvert q(A)-q(B)\rvert\lesssim n\cdot\sqrt{\frac{\log\lvert\mathcal{D}\rvert}{T}}+\eta. q ∈ Q max ∣ q ( A ) − q ( B )∣ ≲ n ⋅ T log ∣ D ∣ + η . 
