Introduction
Differential privacy provides a mathematical framework for analyzing/processing sensitive data while limiting what the released output reveals about any one individual [9 , 10 ] . It requires that changing an individual’s data have only a limited effect on the output distribution of the data processing algorithm. A basic task within this framework is private function evaluation : given a sensitive dataset S S S U n \mathcal{U}^{n} U n f f f f ( S ) f(S) f ( S ) f ( S ) f(S) f ( S )
A standard way to privately evaluate f f f global sensitivity [9 ] . Consider a real-valued function f : U ∗ → R f: U^* \to\mathbb{R} f : U ∗ → R U ∗ U^* U ∗ U \mathcal{U} U f f f Δ f = sup S ∼ S ′ ∣ f ( S ) − f ( S ′ ) ∣ \Delta_f = \sup_{S \sim S'} \lvert f(S) - f(S') \rvert Δ f = sup S ∼ S ′ ∣ f ( S ) − f ( S ′ )∣
First, a valid sensitivity bound may be unavailable or untrustworthy. A curator may have only black-box access to a function submitted by an untrusted analyst, and privacy cannot rely on the correctness of the analyst’s claimed sensitivity bound. Even when the implementation is available, establishing a valid bound can be difficult for complex computations. This challenge concerns how to guarantee privacy without trusted sensitivity information, regardless of whether the function’s actual global sensitivity is small or large.
Second, global sensitivity can be too large to yield useful accuracy, even on datasets where the function is stable. This motivates data-dependent notions of sensitivity. The local sensitivity of f f f S S S LS f ( S ) = sup S ′ ∼ S ∣ f ( S ) − f ( S ′ ) ∣ \operatorname{LS}_f(S) = \sup_{S' \sim S} \lvert f(S) - f(S') \rvert LS f ( S ) = sup S ′ ∼ S ∣ f ( S ) − f ( S ′ )∣ [23 ] addresses this problem through smoothly varying upper bounds on local sensitivity that support private noise calibration. However, both local and smooth sensitivity account for arbitrary insertions as well as deletions. Consequently, both quantities can be large or infinite even when f f f
The two challenges are also connected computationally. With only black-box access to an arbitrary function, evaluating its behavior on all insertion neighbors requires exploring the input universe, which may be prohibitively large or infinite. Restricting attention to subsets of the observed dataset avoids this universe-dependent search and captures stability under deletions.
These considerations motivate a data-dependent measure of stability that considers only deletions [12 , 17 ] . Following Linder et al. [21 ] , the down sensitivity of a real-valued function f f f S S S λ ≥ 0 \lambda\ge0 λ ≥ 0
DS λ f ( S ) = max S ′ ∈ N λ ↓ ( S ) ∣ f ( S ) − f ( S ′ ) ∣ \operatorname{DS}_{\lambda}^{f}(S) = \max_{S' \in\mathcal{N}_{\lambda}^{\downarrow}(S)} \lvert f(S) - f(S') \rvert DS λ f ( S ) = S ′ ∈ N λ ↓ ( S ) max ∣ f ( S ) − f ( S ′ )∣ where N λ ↓ ( S ) = { S ′ ⊆ S : ∣ S ∖ S ′ ∣ ≤ λ } \mathcal{N}_{\lambda}^{\downarrow}(S) = \{S' \subseteq S : \lvert S \setminus S' \rvert\le\lambda\} N λ ↓ ( S ) = { S ′ ⊆ S : ∣ S ∖ S ′ ∣ ≤ λ } λ \lambda λ S S S f f f S S S f f f f f f λ < ∣ S ∣ \lambda< \lvert S \rvert λ < ∣ S ∣ DS λ f ( S ) ≤ λ ∣ S ∣ − λ ( max S − min S ) \operatorname{DS}_{\lambda}^{f}(S) \le\frac{\lambda}{\lvert S \rvert-\lambda}(\max S - \min S) DS λ f ( S ) ≤ ∣ S ∣ − λ λ ( max S − min S )
The above observations motivate the notion of a private black-box evaluator [21 ] that aims to approximate f ( S ) f(S) f ( S ) S S S f f f f f f S S S S S S f f f [21 ] construct such an evaluator whose output lies between the minimum and maximum values of f f f N λ ↓ ( S ) N_{\lambda}^{\downarrow}(S) N λ ↓ ( S ) ∣ y ^ − f ( S ) ∣ ≤ D λ S f ( S ) |\hat{y} - f(S)| \le D_{\lambda}^{S}f(S) ∣ y ^ − f ( S ) ∣ ≤ D λ S f ( S )
The depth λ \lambda λ 1
Our goal is to address private black-box evaluation for high-dimensional vector-valued functions. A simple baseline for achieving this is to apply the one-dimensional evaluator of Linder et al. [21 ] to each coordinate separately, allocating the privacy budget through composition. The output of the resulting approach would be guaranteed to be in an axis-aligned box—whose side-lengths correspond to coordinate-wise down sensitivities—around the true value of the function.
Such a box can lose the relationships between coordinates. For example, the function’s outputs may vary substantially along a diagonal (that is, not axis-aligned) direction while remaining constant in a perpendicular direction. Bounds on the individual coordinates do not capture this directional stability:
Example 1. The Tukey depth [28 ] of x ∈ R d x \in\mathbb{R}^{d} x ∈ R d S S S x x x S S S ( 0 , 0 ) (0, 0) ( 0 , 0 ) ( 1 , 1 ) (1, 1) ( 1 , 1 ) f f f [ 0 , 1 ] × [ 0 , 1 ] [0, 1] \times[0, 1] [ 0 , 1 ] × [ 0 , 1 ] ( 0 , 1 ) (0, 1) ( 0 , 1 ) ( 0 , 0 ) (0, 0) ( 0 , 0 ) ( 1 , 1 ) (1, 1) ( 1 , 1 ) n / 2 n/2 n /2
Examples like this motivate an accuracy guarantee based on the convex hull of the output vectors. Specifically, we consider the following problem:
Design a private black-box evaluator that given dataset S S S f f f R d \mathbb{R}^{d} R d
y ^ ∈ CH ( { f ( S ′ ) : S ′ ∈ N λ ↓ ( S ) } ) . \hat{y} \in\operatorname{CH}\left(\left\{f(S') : S' \in N_{\lambda}^{\downarrow}(S)\right\}\right). y ^ ∈ CH ( { f ( S ′ ) : S ′ ∈ N λ ↓ ( S ) } ) . where CH denotes the convex hull of a set. The goal is to achieve a small deletion depth λ \lambda λ d d d ε , δ \varepsilon, \delta ε , δ ∣ Y ∣ |\mathcal{Y}| ∣ Y ∣
The convex-hull based guarantee respects variation in every direction, including directions that do not align with the coordinates.
This geometric property makes the evaluator useful for the optimization applications developed in this paper. In one dimension, the convex hull is an interval, recovering the one-dimensional notion of accuracy of Linder et al. [21 ] .
Our contributions and techniques
We construct evaluators for arbitrary vector-valued functions with a finite output domain Y ⊆ R d \mathcal{Y} \subseteq\mathbb{R}^{d} Y ⊆ R d f f f CH ( { f ( S ′ ) : S ′ ∈ N λ ↓ ( S ) } ) \operatorname{CH}(\{f(S') : S' \in\mathcal{N}_{\lambda}^{\downarrow}(S)\}) CH ({ f ( S ′ ) : S ′ ∈ N λ ↓ ( S )}) f ( T ) f(T) f ( T ) T ∈ N λ ↓ ( S ) T \in\mathcal{N}_{\lambda}^{\downarrow}(S) T ∈ N λ ↓ ( S )
Theorem 1.1 (Informal version of 2.6 and 2.7). Let Y ⊆ R d \mathcal{Y} \subseteq\mathbb{R}^{d} Y ⊆ R d
A ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) λ = O ~ ( d 2.58 log ∗ ∣ Y ∣ log ( 1 / δ ) ε ) \lambda= \widetilde{O}\left(d^{2.58\log^{*}|\mathcal{Y}|}\frac{\log(1/\delta)}{\varepsilon}\right) λ = O ( d 2.58 l o g ∗ ∣ Y ∣ ε l o g ( 1/ δ ) )
A ( ε , 0 ) (\varepsilon,0) ( ε , 0 ) λ = O ( d 3 log ∣ Y ∣ ε ) \lambda= O\left(\frac{d^{3}\log|\mathcal{Y}|}{\varepsilon}\right) λ = O ( ε d 3 l o g ∣ Y ∣ )
For real-valued functions, this recovers the one-dimensional evaluation guarantees of Linder et al. [21 ] , based on down sensitivity.2
Theorem 1.2 (Informal version of 4.9 and 4.10). Private evaluation of arbitrary black-box functions can be reduced to private quasi-concave optimization (QCO).
In private QCO [5 , 8 ] , we are given a dataset S S S V ⊆ R d \mathcal{V} \subseteq\mathbb{R}^{d} V ⊆ R d q q q y ∈ V y \in\mathcal{V} y ∈ V q ( S , y ) q(S,y) q ( S , y ) S S S CH ( V ) \operatorname{CH}(\mathcal{V}) CH ( V )
For every fixed y y y q ( ⋅ , y ) q(\cdot,y) q ( ⋅ , y )
For every dataset S S S q ( S , ⋅ ) q(S,\cdot) q ( S , ⋅ )
Now, given an arbitrary black-box function f f f q ( S , y ) q(S,y) q ( S , y ) y ∈ R d y \in\mathbb{R}^{d} y ∈ R d y ∈ CH ( { f ( S ′ ) : S ′ ∈ N λ ↓ ( S ) } ) y \in\operatorname{CH}(\{f(S') : S' \in\mathcal{N}_{\lambda}^{\downarrow}(S)\}) y ∈ CH ({ f ( S ′ ) : S ′ ∈ N λ ↓ ( S )}) q ( S , y ) q(S,y) q ( S , y )
Our reduction constructs a depth function (Definition 4.1) that measures how deeply a candidate vector lies within the convex hull CH ( { f ( S ′ ) : S ′ ∈ N λ ↓ ( S ) } ) \operatorname{CH}(\{f(S') : S' \in\mathcal{N}_{\lambda}^{\downarrow}(S)\}) CH ({ f ( S ′ ) : S ′ ∈ N λ ↓ ( S )}) f f f § 4 , we show how to overcome these challenges to obtain a reduction from private black-box evaluation to private QCO.
Conversely, we can treat a non-private quasi-concave optimizer as the black-box function, and evaluate it using our private black-box evaluator. Combined with the previous theorem, this gives:
Theorem 1.3 (Informal version of 5.3). Up to a factor of dimension d d d
In particular, this means that the hardest instances of black-box evaluation in this sense already arise from non-private optimizers of quasi-concave quality functions: solving private QCO suffices for universal evaluation, and a universal evaluator must also be able to solve private QCO.
Finally, we develop a generic high-dimensional QCO solver in Theorem 3.2 . The one-dimensional solver of Beimel et al. [5 ] takes a lower bound on the optimal quality as input and guarantees a multiplicative approximation to that bound. We develop a one-dimensional solver that follows the same core recursive approach and provides an agnostic additive-error guarantee: it approximates the actual optimum without requiring its value or a lower bound as input. We then extend this solver to d d d [4 , 18 , 24 ] . The resulting generic high-dimensional QCO solver may be of independent interest.
Our black-box evaluation framework provides a general tool for privately solving a broad range of optimization problems. We illustrate this with the following applications:
Private center points. We recover the result of Beimel et al. [4 ] for privately finding center points with an explicit additive approximation to the dataset’s maximum Tukey depth in Corollary 6.4 .
User-level private optimization. In § 6.3 , we obtain user-level private algorithms for quasi-concave and convex optimization using only black-box access to non-private optimizers. Our evaluator requires no supplied sensitivity or Lipschitz bound and no uniform bound on users’ contribution sizes. Utility depends on the worst non-private solution after removing a small number of users, evaluated on the original dataset. Our evaluator incurs an additive overhead in the required number of users, whereas the sample-and-aggregate baseline incurs a multiplicative overhead [23 ] .
Related work
Almost immediately after the introduction of the global sensitivity framework [9 ] , a line of work began that aims to get accuracy guarantees tailored to a particular input (e.g., [23 , 22 ] ). The thread closest to our setting, launched by [16 ] , considers a setting in which the analyst supplies additional parameters describing a tentative (not promised) upper bound on the sensitivity of f f f
Following Linder et al. [21 ] , we call this the claimed sensitivity bound setting . The private evaluators in this setting guarantee differential privacy even when the supplied sensitivity bound is incorrect; however, their stated accuracy guarantees apply only when the bound is valid.
On the other hand, when no claimed sensitivity bound is available, Fang et al. [12 ] developed a private evaluator for monotone functions with a public finite output domain.3 [21 ] extended this approach to arbitrary real-valued functions, providing a private evaluator that requires no sensitivity bound and guarantees privacy without assuming monotonicity.
More recently, Steinke and Steinke [27 ] studied tradeoffs between the amount of data needed for statistical estimation and the number of black-box evaluations, while Brown et al. [3 ] obtained improved tradeoffs for monotone statistics. These two works concern scalar outputs, and give accuracy guarantees primarily based on distributional assumptions on the input.
Rubinstein et al. [26 ] also address vector-valued estimators through an efficient subsample-test-aggregate reduction from down sensitivity to privacy, with an application to high-dimensional linear regression. Their reduction requires a test that certifies bounded deletion sensitivity and whose acceptance probability cannot decrease too sharply when a record is removed. Our evaluator requires only black-box access to f f f f f f
Paper organization. § 2 defines private black-box evaluation in high dimensions and states the main results. § 3 develops our private quasi-concave optimization algorithm in high dimensions. § 4 reduces private black-box evaluation to private quasi-concave optimization. § 5 establishes reductions in both directions between the two problems, relating their sample complexities. Finally, § 6 presents applications to private center points and user-level quasi-concave and convex optimization, and compares the framework with the sample-and-aggregate baseline.
Private black-box evaluation in high dimensions
In this section, we formulate private black-box evaluation in high dimensions and present our main results. Our goal is to privately evaluate an arbitrary function using only black-box access, without assuming a bound on its sensitivity. We express utility through a convex-hull guarantee on the function’s outputs over nearby subdatasets. This connects the utility of the private evaluator to the behavior of the underlying function under deletions, allowing us to derive private algorithms from non-private solvers.
The set of natural numbers smaller or equal to k k k [ k ] [k] [ k ] U \mathcal{U} U U ∗ \mathcal{U}^{*} U ∗ U \mathcal{U} U
Definition 2.1 (Down-neighborhood). The k k k S ∈ U ∗ S \in\mathcal{U}^{*} S ∈ U ∗
N k ↓ ( S ) = { S ′ ⊆ S such that ∣ S ′ ∣ ≥ ∣ S ∣ − k } . N_k^{\downarrow}(S)=\{S' \subseteq S\text{ such that } |S'| \geq|S|-k\}. N k ↓ ( S ) = { S ′ ⊆ S such that ∣ S ′ ∣ ≥ ∣ S ∣ − k } . The h h h
M h ↓ ( S ) = { S ′ ⊆ S such that ∣ S ′ ∣ ≥ h } . M_h^{\downarrow}(S)=\{S' \subseteq S\text{ such that } |S'| \geq h\}. M h ↓ ( S ) = { S ′ ⊆ S such that ∣ S ′ ∣ ≥ h } . Two data sets S , S ′ ∈ U ∗ S,S' \in\mathcal{U}^{*} S , S ′ ∈ U ∗ S ′ ∈ N 1 ↓ ( S ) S' \in N_1^{\downarrow}(S) S ′ ∈ N 1 ↓ ( S ) S ∈ N 1 ↓ ( S ′ ) S \in N_1^{\downarrow}(S') S ∈ N 1 ↓ ( S ′ )
Definition 2.2 (Differential privacy). Let U , Y \mathcal{U},\mathcal{Y} U , Y ε > 0 \varepsilon> 0 ε > 0 δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) A : U ∗ → Y \mathcal{A}:\mathcal{U}^{*}\to\mathcal{Y} A : U ∗ → Y ( ε , δ ) (\varepsilon,\delta) ( ε , δ )
two neighboring data sets S , S ′ ∈ U ∗ S,S' \in\mathcal{U}^* S , S ′ ∈ U ∗ A ⊆ R d A \subseteq\mathbb{R}^d A ⊆ R d Pr ( A ( S ) ∈ A ) ≤ e ε Pr ( A ( S ′ ) ∈ A ) + δ \Pr(\mathcal{A}(S) \in A) \leq e^\varepsilon\Pr(\mathcal{A}(S') \in A) + \delta Pr ( A ( S ) ∈ A ) ≤ e ε Pr ( A ( S ′ ) ∈ A ) + δ
The sensitivity of a univariate function f : U ∗ → R f:\mathcal{U}^* \to\mathbb{R} f : U ∗ → R Δ f = sup ∣ f ( S ) − f ( S ′ ) ∣ \Delta_f = \sup|f(S)-f(S')| Δ f = sup ∣ f ( S ) − f ( S ′ ) ∣ S , S ′ ∈ U ∗ S,S' \in\mathcal{U}^* S , S ′ ∈ U ∗
We express the utility of a private black-box evaluator by requiring its output to lie in the convex hull of the function’s values on nearby subdatasets. As we will see in our applications, this geometric guarantee allows us to transfer utility guarantees from non-private solvers to their private evaluations. In one dimension, this notion reduces to the interval guarantee of the Sens-o-Matic wrapper of Linder et al. [21 ] .
The convex hull of a set of points S ⊆ R d S \subseteq\mathbb{R}^d S ⊆ R d S S S
CH ( S ) = { ∑ i = 1 k w i x i | k ∈ N , x i ∈ S , w i > 0 , ∑ i = 1 k w i = 1 } \operatorname{CH}(S) = \left\{ \sum_{i=1}^{k} w_i x_i \mathrel{}\middle|\mathrel{} k \in\mathbb{N}, x_i \in S, w_i > 0, \sum_{i=1}^{k} w_i = 1 \right\} CH ( S ) = { i = 1 ∑ k w i x i k ∈ N , x i ∈ S , w i > 0 , i = 1 ∑ k w i = 1 } Definition 2.3 (Convex Down-neighborhood Image (CDI)). For any set S ∈ U ∗ S \in\mathcal{U}^* S ∈ U ∗ a function f : U ∗ → R d f:\mathcal{U}^* \to\mathbb{R}^d f : U ∗ → R d and h ∈ N h \in\mathbb{N} h ∈ N we define CDI h f ( S ) \operatorname{CDI}_h^f(S) CDI h f ( S ) as the convex hull of the image of M h ↓ ( S ) \mathcal{M}_h^\downarrow(S) M h ↓ ( S ) under mapping f f f In other words, CDI h f ( S ) = CH ( f ( M h ↓ ( S ) ) ) \operatorname{CDI}_h^f(S) = \operatorname{CH}\left(f\left(\mathcal{M}_h^\downarrow(S)\right)\right) CDI h f ( S ) = CH ( f ( M h ↓ ( S ) ) ) 4
The CDI is convex by construction. For fixed h h h
Claim 2.4. For every f : U ∗ → R d f:\mathcal{U}^* \to\mathbb{R}^d f : U ∗ → R d and h ∈ N h \in\mathbb{N} h ∈ N the function CDI h f ( . ) \operatorname{CDI}_h^f(.) CDI h f ( . ) is monotone in the sense that for every S 1 , S 2 ∈ U ∗ S_1,S_2 \in\mathcal{U}^* S 1 , S 2 ∈ U ∗ such that S 1 ⊆ S 2 S_1 \subseteq S_2 S 1 ⊆ S 2 we have CDI h f ( S 1 ) ⊆ CDI h f ( S 2 ) \operatorname{CDI}_h^f(S_1) \subseteq\operatorname{CDI}_h^f(S_2) CDI h f ( S 1 ) ⊆ CDI h f ( S 2 )
We now combine privacy, local oracle access, and convex-hull utility in a single definition. Let f : U ∗ → R d f:\mathcal{U}^* \to\mathbb{R}^d f : U ∗ → R d R d \mathbb{R}^d R d A \mathcal{A} A S ∈ U ∗ S \in\mathcal{U}^* S ∈ U ∗ f f f f ( S ) f(S) f ( S ) A \mathcal{A} A S S S A \mathcal{A} A f f f
Definition 2.5 (Differentially Private Black-box Evaluator). Let Y ⊆ R d \mathcal{Y} \subseteq\mathbb{R}^d Y ⊆ R d be a public finite domain, ε > 0 \varepsilon> 0 ε > 0 δ ∈ [ 0 , 1 ) \delta\in[0,1) δ ∈ [ 0 , 1 ) β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) and λ ∈ N \lambda\in\mathbb{N} λ ∈ N An ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) differentially private ( λ , β ) (\lambda,\beta) ( λ , β ) black-box evaluator is a probabilistic algorithm A \mathcal{A} A that receives a data set S ∈ U ∗ S \in\mathcal{U}^* S ∈ U ∗ and has black-box query access to an arbitrary function f : U ∗ → Y f:\mathcal{U}^* \to\mathcal{Y} f : U ∗ → Y and outputs a y ∈ R d y \in\mathbb{R}^d y ∈ R d and has the following properties:
A \mathcal{A} A ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) S S S
A \mathcal{A} A f f f f ( S ′ ) f(S') f ( S ′ ) S ′ ∈ N λ ↓ ( S ) S' \in\mathcal{N}_\lambda^\downarrow(S) S ′ ∈ N λ ↓ ( S )
A ( S ) ∈ CH ( f ( N λ ↓ ( S ) ) ) \mathcal{A}(S) \in\operatorname{CH}(f(\mathcal{N}_\lambda^\downarrow(S))) A ( S ) ∈ CH ( f ( N λ ↓ ( S ))) 1 − β 1-\beta 1 − β
The following theorems give universal privacy wrappers for arbitrary black-box functions. It requires neither a sensitivity bound nor access to the function’s implementation, yet guarantees that the private output lies in the convex hull of its values on nearby subdatasets.
Theorem 2.6 (Approximate-DP black-box evaluator). Let β , ε , δ ∈ ( 0 , 1 ) \beta,\varepsilon,\delta\in(0,1) β , ε , δ ∈ ( 0 , 1 ) Y ⊆ R d \mathcal{Y} \subseteq\mathbb{R}^{d} Y ⊆ R d ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) ( λ , β ) (\lambda,\beta) ( λ , β )
λ = O ~ ( d 2.5 log ∗ ∣ Y ∣ log ( 1 / β δ ) ε ) . \lambda= \widetilde{O}\left(\frac{d^{2.5}\log^{*}|\mathcal{Y}|\log(1/\beta\delta)}{\varepsilon}\right). λ = O ( ε d 2.5 log ∗ ∣ Y ∣ log ( 1/ β δ ) ) . Theorem 2.7 (Pure-DP black-box evaluator). Let β , ε ∈ ( 0 , 1 ) \beta,\varepsilon\in(0,1) β , ε ∈ ( 0 , 1 ) Y ⊆ R d \mathcal{Y} \subseteq\mathbb{R}^{d} Y ⊆ R d ( ε , 0 ) (\varepsilon,0) ( ε , 0 ) ( λ , β ) (\lambda,\beta) ( λ , β )
λ = O ( d 3 log ( ∣ Y ∣ / β ) ε ) . \lambda= O\left(\frac{d^{3}\log(|\mathcal{Y}|/\beta)}{\varepsilon}\right). λ = O ( ε d 3 log ( ∣ Y ∣/ β ) ) . Private quasi-concave optimization (QCO)
In this section, we introduce our private quasi-concave optimization algorithm, a key primitive for solving black-box evaluation. We begin by defining quasiconcavity 5
Definition 3.1 (Quasi-concave function). Let Y ⊆ R d \mathcal{Y} \subseteq\mathbb{R}^{d} Y ⊆ R d f : Y → R f : \mathcal{Y} \to\mathbb{R} f : Y → R A ⊆ Y A \subseteq\mathcal{Y} A ⊆ Y y ∈ CH ( A ) ∩ Y y \in\operatorname{CH}(A) \cap\mathcal{Y} y ∈ CH ( A ) ∩ Y
f ( y ) ≥ min z ∈ A f ( z ) . f(y) \geq\min_{z\in A} f(z). f ( y ) ≥ z ∈ A min f ( z ) . When Y \mathcal{Y} Y f f f f f f
In the context of private quasi-concave optimization, let q : U ∗ × R d → R q : \mathcal{U}^{*} \times\mathbb{R}^{d} \to\mathbb{R} q : U ∗ × R d → R Δ q \Delta_q Δ q Y ⊆ R d \mathcal{Y} \subseteq\mathbb{R}^{d} Y ⊆ R d S ∈ U ∗ S \in\mathcal{U}^{*} S ∈ U ∗ y ^ ∈ CH ( Y ) \hat{y} \in\operatorname{CH}(\mathcal{Y}) y ^ ∈ CH ( Y ) max y ∈ Y q ( S , y ) \max_{y\in\mathcal{Y}} q(S,y) max y ∈ Y q ( S , y ) Δ q > 0 \Delta_q > 0 Δ q > 0
We develop a 1-dimensional solver with an agnostic utility guarantee: it approximates the actual maximum up to additive error, without requiring its value or a lower bound on it as input. This differs from the multiplicative guarantee relative to a supplied quality promise in RecConcave [5 ] . This is useful when no informative lower bound on the optimal quality is known in advance. The guarantee remains relative to the actual optimum, and, for a fixed sensitivity bound, the additive error is independent of its magnitude.
At a very high-level, our algorithm follows the same recursive idea of [5 ] : it identifies the scale of an interval on which the quality is close to optimal by expressing scale selection as another QCO problem on a domain of size O ( log ∣ Y ∣ ) O(\log|\mathcal{Y}|) O ( log ∣ Y ∣ )
We then extend the solver to high dimensions by optimizing one coordinate at a time. At each iteration, the quality of a candidate coordinate is the maximum quality attainable by completing the remaining coordinates. This approach raises a subtle technical point, which is that we must extend the domain Y \mathcal{Y} Y Y ~ \widetilde{\mathcal{Y}} Y Definition 4.5 and the ensuing results. The errors accumulate over the d d d d d d d \sqrt{d} d [4 , 18 , 24 ] .
We remark that Cohen et al. [8 ] also provide agnostic additive-error guarantees for one-dimensional QCO, with sharper domain-size dependence, through a reduction to a cumulatively private interior-point solver. Our coordinate-wise analysis requires explicit dependence on accumulated error, privacy and failure parameters, while their stated QCO guarantee does not fully expose these parameter dependencies. We therefore give a direct recursive construction following Beimel et al. [5 ] , with a self-contained, fully parameterized guarantee in Theorem G.2 .
The following theorem formalizes the guarantee of our algorithm. We provide the full construction and proof of the 1-dimensional solver, together with its extension to high dimensions, in Section G.
Theorem 3.2. Let β , ϵ , δ ∈ ( 0 , 1 / 2 ) \beta,\epsilon,\delta\in(0,1/2) β , ϵ , δ ∈ ( 0 , 1/2 ) C > 0 C > 0 C > 0 Y ⊆ R d \mathcal{Y} \subseteq\mathbb{R}^{d} Y ⊆ R d ∣ Y ∣ ≥ 2 |\mathcal{Y}| \geq2 ∣ Y ∣ ≥ 2 Q : U ∗ × Y → R Q:\mathcal{U}^{*} \times\mathcal{Y} \to\mathbb{R} Q : U ∗ × Y → R 1 1 1 ( ϵ , δ ) (\epsilon,\delta) ( ϵ , δ )
Δ ≥ C d 1.5 8 log ∗ ∣ Y ∣ log ∗ ∣ Y ∣ log ( 1 / δ ) ϵ log ( d log ∗ ∣ Y ∣ β δ ) , \Delta\geq C d^{1.5} \frac{8^{\log^{*}|\mathcal{Y}|}\log^{*}|\mathcal{Y}|\sqrt{\log(1/\delta)}}{\epsilon} \log\left(\frac{d\log^{*}|\mathcal{Y}|}{\beta\delta}\right), Δ ≥ C d 1.5 ϵ 8 l o g ∗ ∣ Y ∣ log ∗ ∣ Y ∣ log ( 1/ δ ) log ( β δ d log ∗ ∣ Y ∣ ) , and every dataset S ∈ U ∗ S \in\mathcal{U}^{*} S ∈ U ∗ y ^ ∈ CH ( Y ) \hat{y} \in\operatorname{CH}(\mathcal{Y}) y ^ ∈ CH ( Y )
Q ( S , y ^ ) ≥ max y ∈ Y Q ( S , y ) − Δ Q(S,\hat{y}) \geq\max_{y \in\mathcal{Y}} Q(S,y) - \Delta Q ( S , y ^ ) ≥ y ∈ Y max Q ( S , y ) − Δ with probability at least $1-\beta.
Black-box evaluation using QCO
In this section, we reduce private black-box evaluation to private quasi-concave optimization. The key is to associate every black-box function f f f 1 1 1 f f f
The following function is defined in the spirit of Tukey depth, but on the convex down-neighborhood image of a function.
Definition 4.1 (CDI Depth). Let U \mathcal{U} U Y ⊆ R d \mathcal{Y} \subseteq\mathbb{R}^{d} Y ⊆ R d S ∈ U ∗ S \in\mathcal{U}^{*} S ∈ U ∗ y ∈ Y y \in\mathcal{Y} y ∈ Y f : U ∗ → Y f:\mathcal{U}^{*} \to\mathcal{Y} f : U ∗ → Y h ∈ N h \in\mathbb{N} h ∈ N depth h f : U ∗ × Y → R \operatorname{depth}_{h}^{f}:\mathcal{U}^{*} \times\mathcal{Y} \to\mathbb{R} depth h f : U ∗ × Y → R
depth h f ( S , y ) = min { ∣ S ′ ∣ : S ′ ⊆ S , y ∉ CDI h f ( S ∖ S ′ ) } \operatorname{depth}_{h}^{f}(S,y)=\min\left\{|S'|:S' \subseteq S,\ y \notin\operatorname{CDI}_{h}^{f}(S\setminus S')\right\} depth h f ( S , y ) = min { ∣ S ′ ∣ : S ′ ⊆ S , y ∈ / CDI h f ( S ∖ S ′ ) } Claim 4.2. For every f : U ∗ → R d f:\mathcal{U}^{*}\to\mathbb{R}^{d} f : U ∗ → R d S ∈ U ∗ S\in\mathcal{U}^{*} S ∈ U ∗ y ∈ R d y\in\mathbb{R}^{d} y ∈ R d depth h f ( S , y ) \operatorname{depth}_{h}^{f}(S,y) depth h f ( S , y ) h h h h , h ′ ∈ N h,h'\in\mathbb{N} h , h ′ ∈ N h ≤ h ′ h\le h' h ≤ h ′ depth h ′ f ( S , y ) ≤ depth h f ( S , y ) \operatorname{depth}_{h'}^{f}(S,y)\le\operatorname{depth}_{h}^{f}(S,y) depth h ′ f ( S , y ) ≤ depth h f ( S , y )
Claim 4.3. For every f : U ∗ → R d f:\mathcal{U}^{*}\to\mathbb{R}^{d} f : U ∗ → R d h ∈ N h\in\mathbb{N} h ∈ N S ∈ U ∗ S\in\mathcal{U}^{*} S ∈ U ∗ depth h f ( S , ⋅ ) \operatorname{depth}_{h}^{f}(S,\cdot) depth h f ( S , ⋅ )
Claim 4.4. For every f : U ∗ → R d f:\mathcal{U}^{*}\to\mathbb{R}^{d} f : U ∗ → R d h ∈ N h\in\mathbb{N} h ∈ N y ∈ R d y\in\mathbb{R}^{d} y ∈ R d depth h f ( ⋅ , y ) \operatorname{depth}_{h}^{f}(\cdot,y) depth h f ( ⋅ , y ) S , S ′ ⊆ R d S,S'\subseteq\mathbb{R}^{d} S , S ′ ⊆ R d ∣ depth h f ( S , y ) − depth h f ( S ′ , y ) ∣ ≤ ∣ S ∖ S ′ ∣ + ∣ S ′ ∖ S ∣ \left|\operatorname{depth}_{h}^{f}(S,y)-\operatorname{depth}_{h}^{f}(S',y)\right|\le|S\setminus S'|+|S'\setminus S| depth h f ( S , y ) − depth h f ( S ′ , y ) ≤ ∣ S ∖ S ′ ∣ + ∣ S ′ ∖ S ∣
The two preceding claims show that for any choice of f f f h h h depth h f ( S , y ) \operatorname{depth}_{h}^{f}(S,y) depth h f ( S , y ) y y y
The utility guarantee of private quasi-concave optimization is relative to the best score over its finite candidate domain. We must therefore ensure that this domain contains a point with sufficiently large CDI depth. Such a point need not belong to the original output domain Y \mathcal{Y} Y Y \mathcal{Y} Y Y ~ \widetilde{\mathcal{Y}} Y
Definition 4.5 (CH-closed domain extension). Let Y ⊆ R d \mathcal{Y}\subseteq\mathbb{R}^{d} Y ⊆ R d Y ~ ⊆ CH ( Y ) \widetilde{\mathcal{Y}}\subseteq\operatorname{CH}(\mathcal{Y}) Y ⊆ CH ( Y ) Y \mathcal{Y} Y I ⊆ 2 Y \mathcal{I}\subseteq2^{\mathcal{Y}} I ⊆ 2 Y A I = ⋂ S i ∈ I CH ( S i ) ≠ ∅ A_{\mathcal{I}}=\bigcap_{S_i\in\mathcal{I}}\operatorname{CH}(S_i)\ne\varnothing A I = ⋂ S i ∈ I CH ( S i ) = ∅ A I ∩ Y ~ ≠ ∅ A_{\mathcal{I}}\cap\widetilde{\mathcal{Y}}\ne\varnothing A I ∩ Y = ∅
The following lemma shows that the extended domain contains a point with sufficiently large CDI depth. Unlike RecConcave [5 ] , which takes a lower bound on the optimal quality as input, our algorithm does not require such a bound in advance. The bound follows from Helly’s theorem and is used only in the utility analysis of the evaluator and its applications. See C.6 for the proof.
Lemma 4.6. Let Y ⊆ R d \mathcal{Y}\subseteq\mathbb{R}^{d} Y ⊆ R d Y ~ \widetilde{\mathcal{Y}} Y Y \mathcal{Y} Y f : U ∗ → Y f:\mathcal{U}^{*}\to\mathcal{Y} f : U ∗ → Y h ∈ N h\in\mathbb{N} h ∈ N S ∈ U ∗ S\in\mathcal{U}^{*} S ∈ U ∗ y ∗ ∈ Y ~ y^{*}\in\widetilde{\mathcal{Y}} y ∗ ∈ Y depth h f ( S , y ∗ ) ≥ ∣ S ∣ − h d + 1 \operatorname{depth}_{h}^{f}(S,y^{*})\ge\frac{|S|-h}{d+1} depth h f ( S , y ∗ ) ≥ d + 1 ∣ S ∣ − h
The following two lemmas construct finite extensions of any nonempty finite domain Y \mathcal{Y} Y
Lemma 4.7. For every finite set Y ⊆ R d \mathcal{Y}\subseteq\mathbb{R}^{d} Y ⊆ R d Y ~ ⊆ R d \widetilde{\mathcal{Y}}\subseteq\mathbb{R}^{d} Y ⊆ R d 2 2 ∣ Y ∣ 2^{2^{|\mathcal{Y}|}} 2 2 ∣ Y ∣
Lemma 4.8. For every finite set Y ⊆ R d \mathcal{Y}\subseteq\mathbb{R}^{d} Y ⊆ R d Y ~ ⊆ R d \widetilde{\mathcal{Y}}\subseteq\mathbb{R}^{d} Y ⊆ R d ∣ Y ∣ d 2 |\mathcal{Y}|^{d^{2}} ∣ Y ∣ d 2
Putting these ingredients together, we obtain our main algorithms for privately optimizing the CDI depth function.
Theorem 4.9 (Main, Approximate-DP). Let β , ϵ , δ ∈ ( 0 , 1 / 2 ) \beta,\epsilon,\delta\in(0,1/2) β , ϵ , δ ∈ ( 0 , 1/2 ) C > 0 C>0 C > 0 U \mathcal{U} U Y ⊆ R d \mathcal{Y}\subseteq\mathbb{R}^{d} Y ⊆ R d ∣ Y ∣ ≥ 2 |\mathcal{Y}|\ge2 ∣ Y ∣ ≥ 2 Y ~ \widetilde{\mathcal{Y}} Y
be a finite extension of Y \mathcal{Y} Y f : U ∗ → Y f:\mathcal{U}^{*}\to\mathcal{Y} f : U ∗ → Y h ∈ N h\in\mathbb{N} h ∈ N depth h f \operatorname{depth}_{h}^{f} depth h f ( ε , δ ) (\varepsilon,\delta) ( ε , δ )
Δ ≥ C d 1.5 8 log ∗ ∣ Y ~ ∣ log ∗ ∣ Y ~ ∣ log ( 2 / δ ) ε log ( d log ∗ ∣ Y ~ ∣ β δ ) \Delta\geq C d^{1.5}\frac{8^{\log^{*}|\widetilde{\mathcal{Y}}|}\log^{*}|\widetilde{\mathcal{Y}}|\sqrt{\log(2/\delta)}}{\varepsilon}\log\left(\frac{d\log^{*}|\widetilde{\mathcal{Y}}|}{\beta\delta}\right) Δ ≥ C d 1.5 ε 8 l o g ∗ ∣ Y ∣ log ∗ ∣ Y ∣ log ( 2/ δ ) log ( β δ d log ∗ ∣ Y ∣ ) and every dataset S ∈ U ∗ S\in\mathcal{U}^{*} S ∈ U ∗ y ^ ∈ CH ( Y ~ ) \widehat{y}\in\operatorname{CH}(\widetilde{\mathcal{Y}}) y ∈ CH ( Y )
depth h f ( S , y ^ ) ≥ max y ∈ Y ~ depth h f ( S , y ) − Δ ≥ ∣ S ∣ − h d + 1 − Δ \operatorname{depth}_{h}^{f}(S,\widehat{y})\geq\max_{y\in\widetilde{\mathcal{Y}}}\operatorname{depth}_{h}^{f}(S,y)-\Delta\geq\frac{|S|-h}{d+1}-\Delta depth h f ( S , y ) ≥ y ∈ Y max depth h f ( S , y ) − Δ ≥ d + 1 ∣ S ∣ − h − Δ with probability at least 1 − β 1-\beta 1 − β
Proof. Note that the function depth h f \operatorname{depth}_{h}^{f} depth h f S ∈ U ∗ S\in\mathcal{U}^{*} S ∈ U ∗ Y ~ \widetilde{\mathcal{Y}} Y Y \mathcal{Y} Y max y ∈ Y ~ depth h f ( S , y ) ≥ ∣ S ∣ − h d + 1 \max_{y\in\widetilde{\mathcal{Y}}}\operatorname{depth}_{h}^{f}(S,y)\geq\frac{|S|-h}{d+1} max y ∈ Y depth h f ( S , y ) ≥ d + 1 ∣ S ∣ − h Theorem 3.2 concludes the result.
Figure 1.
Figure 2.
We are now ready to introduce our approximate-DP black-box evaluator in Algorithm 2, which satisfies the privacy and utility guarantees of Theorem 2.6 . A private estimate of the dataset size determines whether to optimize the CDI depth or return f ( ∅ ) f(\varnothing) f ( ∅ ) § 10 .7 for the formal proof.
Algorithm 3 Pure-DP CDI Depth Optimizer
Input: Parameters β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) ε > 0 \varepsilon> 0 ε > 0 h ∈ N h \in\mathbb{N} h ∈ N U \mathcal{U} U Y ⊆ R d \mathcal{Y} \subseteq\mathbb{R}^{d} Y ⊆ R d Y ~ \widetilde{\mathcal{Y}} Y Y \mathcal{Y} Y S ∈ U ∗ S \in\mathcal{U}^{*} S ∈ U ∗ f : U ∗ → Y f : \mathcal{U}^{*} \to\mathcal{Y} f : U ∗ → Y
Let depth h f : U ∗ × Y ~ → R \operatorname{depth}_{h}^{f} : \mathcal{U}^{*} \times\widetilde{\mathcal{Y}} \to\mathbb{R} depth h f : U ∗ × Y → R
Run the Exponential Mechanism A.2 with quality function depth h f \operatorname{depth}_{h}^{f} depth h f β , ε \beta, \varepsilon β , ε S S S U \mathcal{U} U Y ~ \widetilde{\mathcal{Y}} Y y ^ \hat{y} y ^
return y ^ \hat{y} y ^
Theorem 4.10 (Main, Pure-DP). Let β ∈ ( 0 , 1 ) , ε > 0 \beta\in(0,1), \varepsilon> 0 β ∈ ( 0 , 1 ) , ε > 0 U \mathcal{U} U Y ⊆ R d \mathcal{Y} \subseteq\mathbb{R}^{d} Y ⊆ R d Y ~ \widetilde{\mathcal{Y}} Y Y \mathcal{Y} Y f : U ∗ → Y f : \mathcal{U}^{*} \to\mathcal{Y} f : U ∗ → Y h ∈ N h \in\mathbb{N} h ∈ N depth h f : U ∗ × Y ~ → R \operatorname{depth}_{h}^{f} : \mathcal{U}^{*} \times\widetilde{\mathcal{Y}} \to\mathbb{R} depth h f : U ∗ × Y → R ( ε , 0 ) (\varepsilon,0) ( ε , 0 )
Δ ≥ 2 log ( ∣ Y ~ ∣ / β ) ε , \Delta\ge\frac{2\log\left(|\widetilde{\mathcal{Y}}|/\beta\right)}{\varepsilon}, Δ ≥ ε 2 log ( ∣ Y ∣/ β ) , and every dataset S ∈ U ∗ S \in\mathcal{U}^{*} S ∈ U ∗ y ^ ∈ Y ~ \hat{y} \in\widetilde{\mathcal{Y}} y ^ ∈ Y
depth h f ( S , y ^ ) ≥ max y ∈ Y ~ depth h f ( S , y ) − Δ ≥ ∣ S ∣ − h d + 1 − Δ \operatorname{depth}_{h}^{f}(S,\hat{y}) \ge\max_{y\in\widetilde{\mathcal{Y}}}\operatorname{depth}_{h}^{f}(S,y)-\Delta\ge\frac{|S|-h}{d+1}-\Delta depth h f ( S , y ^ ) ≥ y ∈ Y max depth h f ( S , y ) − Δ ≥ d + 1 ∣ S ∣ − h − Δ with probability at least $1-\beta.
Proof. Note that the function depth h f \operatorname{depth}_{h}^{f} depth h f Claim 4.4 ). Also, using Theorem 4.6, we know that for every S ∈ U ∗ S \in\mathcal{U}^{*} S ∈ U ∗ Y ~ \widetilde{\mathcal{Y}} Y Y \mathcal{Y} Y max y ∈ Y ~ depth h f ( S , y ) ≥ ∣ S ∣ − h d + 1 \max_{y\in\widetilde{\mathcal{Y}}}\operatorname{depth}_{h}^{f}(S,y) \ge\frac{|S|-h}{d+1} max y ∈ Y depth h f ( S , y ) ≥ d + 1 ∣ S ∣ − h Theorem A.2 ) concludes the result.
Algorithm 4 presents our pure-DP black-box evaluator, which satisfies the privacy and utility guarantees of Theorem 2.7 . As before, a private estimate of the dataset size determines whether to optimize the CDI depth or return f ( ∅ ) f(\varnothing) f ( ∅ ) § 10 .8 for the formal proof.
Equivalency of Private Black-box Evaluation and QCO
In this section, we show that, up to an O ( d ) O(d) O ( d ) f : U ∗ → Y f : \mathcal{U}^{*} \to\mathcal{Y} f : U ∗ → Y
Algorithm 4 Pure-DP Black-Box Evaluator
Input: Parameters β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) ε > 0 \varepsilon> 0 ε > 0 Y ⊆ R d \mathcal{Y} \subseteq\mathbb{R}^{d} Y ⊆ R d ∣ Y ∣ ≥ 2 |\mathcal{Y}| \ge2 ∣ Y ∣ ≥ 2 S ∈ U ∗ S \in\mathcal{U}^{*} S ∈ U ∗ f : U ∗ → Y f:\mathcal{U}^{*} \to\mathcal{Y} f : U ∗ → Y
Choose an extension Y ~ \widetilde{\mathcal{Y}} Y Lemma 4.8 , and let M = ∣ Y ~ ∣ M = |\widetilde{\mathcal{Y}}| M = ∣ Y ∣
Set η = β / 2 \eta= \beta/2 η = β /2 β 0 = β / 2 \beta_{0} = \beta/2 β 0 = β /2 ε 0 = ε / 2 \varepsilon_{0} = \varepsilon/2 ε 0 = ε /2 δ 0 = min { 1 / 4 , η ( e ε 0 − 1 ) / M } \delta_{0} = \min\{1/4,\eta(e^{\varepsilon_{0}}-1)/M\} δ 0 = min { 1/4 , η ( e ε 0 − 1 ) / M }
Set Δ = 2 log ( M / β 0 ) ε 0 \Delta= \frac{2\log(M/\beta_{0})}{\varepsilon_{0}} Δ = ε 0 2 l o g ( M / β 0 ) K = ⌈ ( d + 1 ) ( Δ + 1 ) ⌉ K = \lceil(d+1)(\Delta+1)\rceil K = ⌈( d + 1 ) ( Δ + 1 )⌉ R = 1 ε 0 log ( 1 + e ε 0 − 1 2 δ 0 ) R = \frac{1}{\varepsilon_{0}}\log\left(1+\frac{e^{\varepsilon_{0}}-1}{2\delta_{0}}\right) R = ε 0 1 log ( 1 + 2 δ 0 e ε 0 − 1 )
Sample B ∼ Bernoulli ( η ) B \sim\operatorname{Bernoulli}(\eta) B ∼ Bernoulli ( η )
if B = 1 B = 1 B = 1
return a uniformly random point of Y ~ \widetilde{\mathcal{Y}} Y
end if
Sample Z ∼ TLap ( 1 , ε 0 , δ 0 ) Z \sim\operatorname{TLap}(1,\varepsilon_{0},\delta_{0}) Z ∼ TLap ( 1 , ε 0 , δ 0 ) n ~ = ∣ S ∣ + Z \widetilde{n} = |S| + Z n = ∣ S ∣ + Z
Set h = ⌊ n ~ − R − K ⌋ h = \lfloor\widetilde{n} - R - K\rfloor h = ⌊ n − R − K ⌋
if h ≤ 0 h \le0 h ≤ 0
return f ( ∅ ) f(\varnothing) f ( ∅ )
end if
Run the Pure-DP CDI Depth Optimizer (Algorithm 3) with cutoff h h h β 0 , ε 0 \beta_{0},\varepsilon_{0} β 0 , ε 0 S S S f f f Y ~ \widetilde{\mathcal{Y}} Y
return its output.
also solve private QCO. In this sense, the hardest instances of private black-box evaluation already arise from optimizers of quasi-concave quality functions. We first introduce notation for the sample complexity of private QCO and private black-box evaluation.
Definition 5.1 (Sample complexity of private QCO). Let α , β , δ , ε ∈ ( 0 , 1 ) \alpha,\beta,\delta,\varepsilon\in(0,1) α , β , δ , ε ∈ ( 0 , 1 ) d , L ≥ 1 d,L \ge1 d , L ≥ 1 n Q C O ( α , β , ε , δ , d , L ) n_{\mathrm{QCO}}(\alpha,\beta,\varepsilon,\delta,d,L) n QCO ( α , β , ε , δ , d , L ) N ≥ 1 N \ge1 N ≥ 1 U \mathcal{U} U Y ⊆ R d \mathcal{Y} \subseteq\mathbb{R}^{d} Y ⊆ R d log ∗ ∣ Y ∣ ≤ L \log^{*}|\mathcal{Y}| \le L log ∗ ∣ Y ∣ ≤ L A \mathcal{A} A
For every discrete quasi-concave quality function Q : U ∗ × Y → R Q:\mathcal{U}^{*} \times\mathcal{Y} \to\mathbb{R} Q : U ∗ × Y → R
The algorithm A ( Q , ⋅ ) \mathcal{A}(Q,\cdot) A ( Q , ⋅ ) ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) U ∗ \mathcal{U}^{*} U ∗
On every dataset S ∈ U ∗ S \in\mathcal{U}^{*} S ∈ U ∗ CH ( Y ) \operatorname{CH}(\mathcal{Y}) CH ( Y ) Q Q Q Q ( T , y ) Q(T,y) Q ( T , y ) T ⊆ S T \subseteq S T ⊆ S y ∈ Y y \in\mathcal{Y} y ∈ Y
For every dataset S ∈ U ∗ S \in\mathcal{U}^{*} S ∈ U ∗ ∣ S ∣ ≥ N |S| \ge N ∣ S ∣ ≥ N y ^ \hat{y} y ^
Q ( S , y ^ ) ≥ max y ∈ Y Q ( S , y ) − α N Q(S,\hat{y}) \ge\max_{y \in\mathcal{Y}} Q(S,y) - \alpha N Q ( S , y ^ ) ≥ y ∈ Y max Q ( S , y ) − α N with probability at least 1 − β 1-\beta 1 − β
Definition 5.2 (Sample complexity of private black-box evaluation). Let α , β , δ , ε ∈ ( 0 , 1 ) \alpha,\beta,\delta,\varepsilon\in(0,1) α , β , δ , ε ∈ ( 0 , 1 ) d , L ≥ 1 d,L \ge1 d , L ≥ 1 n b l a c k - b o x ( α , β , ε , δ , d , L ) n_{\mathrm{black\text{-}box}}(\alpha,\beta,\varepsilon,\delta,d,L) n black - box ( α , β , ε , δ , d , L ) N ≥ 1 N \ge1 N ≥ 1 U \mathcal{U} U Y ⊆ R d \mathcal{Y} \subseteq\mathbb{R}^{d} Y ⊆ R d log ∗ ∣ Y ∣ ≤ L \log^{*}|\mathcal{Y}| \le L log ∗ ∣ Y ∣ ≤ L A \mathcal{A} A
For every fixed function f : U ∗ → Y f:\mathcal{U}^{*} \to\mathcal{Y} f : U ∗ → Y
The algorithm A ( f , ⋅ ) \mathcal{A}(f,\cdot) A ( f , ⋅ ) ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) U ∗ \mathcal{U}^* U ∗
On every dataset S ∈ U ∗ S\in\mathcal{U}^* S ∈ U ∗ f f f f ( T ) f(T) f ( T ) T ∈ N ⌊ α N ⌋ ↓ ( S ) T\in N^{\downarrow}_{\lfloor\alpha N\rfloor}(S) T ∈ N ⌊ α N ⌋ ↓ ( S )
For every dataset S ∈ U ∗ S\in\mathcal{U}^* S ∈ U ∗ ∣ S ∣ ≥ N |S|\ge N ∣ S ∣ ≥ N y ^ \hat{y} y ^
y ^ ∈ CH ( f ( N ⌊ α N ⌋ ↓ ( S ) ) ) \hat{y}\in\operatorname{CH}\left(f\left(N^{\downarrow}_{\lfloor\alpha N\rfloor}(S)\right)\right) y ^ ∈ CH ( f ( N ⌊ α N ⌋ ↓ ( S ) ) ) with probability at least 1 − β 1-\beta 1 − β
The following theorem formalizes the equivalence discussed above. See D.1 for the proof.
Theorem 5.3 (From QCO to black-box evaluation and back). There exists a universal constant C > 0 C>0 C > 0 β , ε ∈ ( 0 , 1 ) \beta,\varepsilon\in(0,1) β , ε ∈ ( 0 , 1 ) δ , α ∈ ( 0 , 1 / 2 ) \delta,\alpha\in(0,1/2) δ , α ∈ ( 0 , 1/2 ) d , L ≥ 1 d,L\ge1 d , L ≥ 1
n Q C O ( 2 α , β , ε , δ , d , L ) ≤ n b l a c k − b o x ( α , β , ε , δ , d , L ) n_{\mathrm{QCO}}(2\alpha,\beta,\varepsilon,\delta,d,L)\le n_{\mathrm{black-box}}(\alpha,\beta,\varepsilon,\delta,d,L) n QCO ( 2 α , β , ε , δ , d , L ) ≤ n black − box ( α , β , ε , δ , d , L ) ≤ max { n Q C O ( α 2 ( d + 1 ) , β , ε 2 , δ 2 , d , L + 2 ) , ⌈ C α ( d + log ( 1 / δ ) ε ) ⌉ } . \le\max\left\{n_{\mathrm{QCO}}\left(\frac{\alpha}{2(d+1)},\beta,\frac{\varepsilon}{2},\frac{\delta}{2},d,L+2\right),\left\lceil\frac{C}{\alpha}\left(d+\frac{\log(1/\delta)}{\varepsilon}\right)\right\rceil\right\}. ≤ max { n QCO ( 2 ( d + 1 ) α , β , 2 ε , 2 δ , d , L + 2 ) , ⌈ α C ( d + ε log ( 1/ δ ) ) ⌉ } . Instantiations
In this section, we instantiate our main black-box evaluator with non-private solvers to obtain private algorithms for center points and user-level quasi-concave and convex optimization. These applications illustrate how our guarantees translate into utility bounds using only black-box access to the underlying solvers.
Recovering 1-dimensional black-box of linder2025privately
For d = 1 d=1 d = 1 [21 ] , with our stated locality and failure parameters. Consequently, the same application reductions apply to our evaluator, including private mean estimation with error that adapts to the scale of the data and user-level convex optimization in one dimension. In these applications, utility follows by bounding how much the non-private statistic changes when a small number of records or users are removed.
Theorem 6.1 (Sens-o-Matic Privacy Wrapper, Linder et al. [21 ] ). Let ε , δ , β ∈ ( 0 , 1 ) \varepsilon,\delta,\beta\in(0,1) ε , δ , β ∈ ( 0 , 1 ) λ ∈ N \lambda\in\mathbb{N} λ ∈ N Y ⊆ R \mathcal{Y}\subseteq\mathbb{R} Y ⊆ R
There exists a 1-dimensional ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) ( λ , β ) (\lambda,\beta) ( λ , β ) λ = 2 O ( log ∗ ∣ Y ∣ ) log ( 1 / β δ ) ε \lambda=2^{O(\log^*|\mathcal{Y}|)}\frac{\log(1/\beta\delta)}{\varepsilon} λ = 2 O ( l o g ∗ ∣ Y ∣ ) ε l o g ( 1/ β δ )
There exists a 1-dimensional ( ε , 0 ) (\varepsilon,0) ( ε , 0 ) ( λ , β ) (\lambda,\beta) ( λ , β ) λ = O ( log ( ∣ Y ∣ / β ) ε ) \lambda=O\left(\frac{\log(|\mathcal{Y}|/\beta)}{\varepsilon}\right) λ = O ( ε l o g ( ∣ Y ∣/ β ) )
Private center point
A natural geometric application of our black-box evaluator is private center point computation. Center points generalize the median to higher dimensions: every closed halfspace containing a center point of S S S ∣ S ∣ / ( d + 1 ) |S|/(d+1) ∣ S ∣/ ( d + 1 )
Definition 6.2 (Tukey depth). For a dataset S ∈ ( R d ) ∗ S \in(\mathbb{R}^{d})^* S ∈ ( R d ) ∗ y ∈ R d y \in\mathbb{R}^{d} y ∈ R d y y y S S S
TD ( S , y ) = min { ∣ S ∩ H ∣ : H ⊆ R d is a closed halfspace containing y } . \operatorname{TD}(S,y)=\min\left\{|S\cap H|: H\subseteq\mathbb{R}^{d}\text{ is a closed halfspace containing }y\right\}. TD ( S , y ) = min { ∣ S ∩ H ∣ : H ⊆ R d is a closed halfspace containing y } . where points are counted with multiplicity.
Beim et al. [4 ] give an ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) ∣ S ∣ / ( 2 ( d + 1 ) ) |S|/(2(d+1)) ∣ S ∣/ ( 2 ( d + 1 )) O ~ ( d 2.52 O ( log ∗ ∣ Y ∣ ) / ε ) \widetilde{O}(d^{2.52}O(\log^*|\mathcal{Y}|)/\varepsilon) O ( d 2.52 O ( log ∗ ∣ Y ∣ ) / ε )
A useful observation is that Tukey depth coincides with a special case of CDI depth for internal functions, whose outputs lie in the convex hull of their inputs. The following lemma formalizes this connection and is particularly useful for analyzing black-box evaluation of such functions.
A function f : ( R d ) ∗ → R d f:(\mathbb{R}^{d})^*\to\mathbb{R}^{d} f : ( R d ) ∗ → R d internal if f ( S ) ∈ CH ( S ) f(S)\in\operatorname{CH}(S) f ( S ) ∈ CH ( S ) S ∈ ( R d ) ∗ S\in(\mathbb{R}^{d})^* S ∈ ( R d ) ∗
Lemma 6.3. Let U ⊆ R d \mathcal{U}\subseteq\mathbb{R}^{d} U ⊆ R d S ∈ U ∗ S\in\mathcal{U}^* S ∈ U ∗ f : U → R d f:\mathcal{U}\to\mathbb{R}^{d} f : U → R d h ∈ N h\in\mathbb{N} h ∈ N y ∈ R d y\in\mathbb{R}^{d} y ∈ R d depth h f ( S , y ) ≤ TD ( S , y ) = depth 1 f ( S , y ) \operatorname{depth}_{h}^{f}(S,y)\leq\operatorname{TD}(S,y)=\operatorname{depth}_{1}^{f}(S,y) depth h f ( S , y ) ≤ TD ( S , y ) = depth 1 f ( S , y )
See E.1 for the proof.
Let Y ⊆ R d \mathcal{Y}\subseteq\mathbb{R}^{d} Y ⊆ R d f c e n t e r : Y ∗ → Y f_{\mathrm{center}}:\mathcal{Y}^*\to\mathcal{Y} f center : Y ∗ → Y
f c e n t e r ( S ) ∈ arg max y ∈ Y TD ( S , y ) f_{\mathrm{center}}(S)\in\underset{y\in\mathcal{Y}}{\arg\max}\ \operatorname{TD}(S,y) f center ( S ) ∈ y ∈ Y arg max TD ( S , y ) for every S ∈ Y ∗ S\in\mathcal{Y}^* S ∈ Y ∗ f c e n t e r f_{\mathrm{center}} f center depth h f c e n t e r \operatorname{depth}_{h}^{f_{\mathrm{center}}} depth h f center
Corollary 6.4 (Center point). Let Y ⊆ R d \mathcal{Y}\subseteq\mathbb{R}^{d} Y ⊆ R d Y ~ \widetilde{\mathcal{Y}} Y Lemma 4.7 . β , ε , δ ∈ ( 0 , 1 ) \beta,\varepsilon,\delta\in(0,1) β , ε , δ ∈ ( 0 , 1 ) f c e n t e r f_{\mathrm{center}} f center A \mathcal{A} A ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) S ∈ Y ∗ S\in\mathcal{Y}^* S ∈ Y ∗ y ^ : = A ( f c e n t e r , S , β , ε , δ , Y , Y ~ ) ∈ R d \hat{y}:=\mathcal{A}(f_{\mathrm{center}},S,\beta,\varepsilon,\delta,\mathcal{Y},\widetilde{\mathcal{Y}})\in\mathbb{R}^{d} y ^ := A ( f center , S , β , ε , δ , Y , Y ) ∈ R d
TD ( S , y ^ ) ≥ max y ∈ R d TD ( S , y ) − Δ ≥ ∣ S ∣ d + 1 − Δ \operatorname{TD}(S,\hat{y})\geq\max_{y\in\mathbb{R}^{d}}\operatorname{TD}(S,y)-\Delta\geq\frac{|S|}{d+1}-\Delta TD ( S , y ^ ) ≥ y ∈ R d max TD ( S , y ) − Δ ≥ d + 1 ∣ S ∣ − Δ with probability at least 1 − β 1-\beta 1 − β Δ = O ~ ( d 1.5 8 log ∗ ∣ Y ∣ ε log ( 1 β δ ) ) \Delta=\widetilde{O}\left(d^{1.5}\frac{8^{\log^*|\mathcal{Y}|}}{\varepsilon}\log\left(\frac{1}{\beta\delta}\right)\right) Δ = O ( d 1.5 ε 8 l o g ∗ ∣ Y ∣ log ( β δ 1 ) )
See E.2 for the proof.
From convex-hull guarantees to optimization
A useful observation is that the convex-hull guarantee of a black-box evaluator translates directly into optimization guarantees. For quasi-concave quality functions and convex losses, the private output is at least as good as the worst black-box output over nearby subdatasets, with all outputs evaluated on the original dataset S S S
Claim 6.5. Let U \mathcal{U} U Y ⊆ R d \mathcal{Y} \subseteq\mathbb{R}^{d} Y ⊆ R d A \mathcal{A} A ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) ( λ , β ) (\lambda,\beta) ( λ , β ) f : U ∗ → Y f:\mathcal{U}^{*} \to\mathcal{Y} f : U ∗ → Y S ∈ U ∗ S \in\mathcal{U}^{*} S ∈ U ∗ 1 − β 1-\beta 1 − β y ^ = A ( f , S ) \hat{y}=\mathcal{A}(f,S) y ^ = A ( f , S )
(1) Q ( S , y ^ ) ≥ min S ′ ∈ N λ ( S ) Q ( S , f ( S ′ ) ) \mathcal{Q}(S,\hat{y}) \ge\min_{S'\in\mathcal{N}^{\lambda}(S)} \mathcal{Q}(S,f(S')) Q ( S , y ^ ) ≥ min S ′ ∈ N λ ( S ) Q ( S , f ( S ′ )) Q : U ∗ × R d → R \mathcal{Q}:\mathcal{U}^{*}\times\mathbb{R}^{d}\to\mathbb{R} Q : U ∗ × R d → R
(2) L ( S , y ^ ) ≤ max S ′ ∈ N λ ( S ) L ( S , f ( S ′ ) ) \mathcal{L}(S,\hat{y}) \le\max_{S'\in\mathcal{N}^{\lambda}(S)} \mathcal{L}(S,f(S')) L ( S , y ^ ) ≤ max S ′ ∈ N λ ( S ) L ( S , f ( S ′ )) L : U ∗ × R d → R \mathcal{L}:\mathcal{U}^{*}\times\mathbb{R}^{d}\to\mathbb{R} L : U ∗ × R d → R
These guarantees require no sensitivity bound on Q \mathcal{Q} Q L \mathcal{L} L f f f f ( S ′ ) f(S') f ( S ′ ) S S S λ \lambda λ
In the next two subsections, we directly instantiate this claim for user-level quasi-concave and convex optimization, treating each user’s dataset as a single element of the input domain.
User-Level Private Quasi-Concave Optimization
A useful application of our black-box evaluator is quasi-concave optimization when no finite bound on the sensitivity of the quality function is available. Standard sensitivity-based private QCO algorithms require such a bound to rescale the objective to have sensitivity at most 1. Without this bound, the same approach cannot be applied directly. Our black-box evaluator avoids this requirement: it only accesses a non-private optimizer, and requires no bound on the range or sensitivity of the quality function.
This setting arises naturally in user-level privacy, where each user may hold an arbitrary number of data points. Even when each individual data point has a bounded effect on the objective, adding or removing one user’s entire dataset may change its value by an arbitrarily large amount. By treating each user’s dataset as a single element of the input domain, our evaluator provides user-level privacy without imposing a uniform bound on the users’ contribution sizes. Its utility guarantee compares the quality of the private output with that of non-private solutions obtained after removing at most λ \lambda λ
We start by recalling user-level differential privacy.
Definition 6.6 (User-Level Privacy). Let ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 ) A \mathcal{A} A ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) S , S ′ ∈ ( ( R d ) ∗ ) ∗ S,S' \in((\mathbb{R}^{d})^{*})^{*} S , S ′ ∈ (( R d ) ∗ ) ∗
We now formally define the user-level quasi-concave optimization setting and state the resulting guarantee.
Let X \mathcal{X} X Y ⊆ R d \mathcal{Y} \subseteq\mathbb{R}^{d} Y ⊆ R d Q : ( X ∗ ) ∗ × R d → R Q : (\mathcal{X}^{*})^{*} \times\mathbb{R}^{d} \to\mathbb{R} Q : ( X ∗ ) ∗ × R d → R Q ( T , ⋅ ) Q(T,\cdot) Q ( T , ⋅ ) T ∈ ( X ∗ ) ∗ T \in(\mathcal{X}^{*})^{*} T ∈ ( X ∗ ) ∗ f Q : ( X ∗ ) ∗ → Y f_{Q} : (\mathcal{X}^{*})^{*} \to\mathcal{Y} f Q : ( X ∗ ) ∗ → Y f Q ( T ) ∈ arg max y ∈ Y Q ( T , y ) f_{Q}(T) \in\arg\max_{y \in\mathcal{Y}} Q(T,y) f Q ( T ) ∈ arg max y ∈ Y Q ( T , y )
Corollary 6.7 (User-level quasi-concave optimization). Let β , ε , δ ∈ ( 0 , 1 ) \beta,\varepsilon,\delta\in(0,1) β , ε , δ ∈ ( 0 , 1 ) Q Q Q f Q f_{Q} f Q ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) S = ( S 1 , S 2 , ⋯ , S n ) ∈ ( X ∗ ) ∗ S = (S_{1},S_{2},\cdots,S_{n}) \in(\mathcal{X}^{*})^{*} S = ( S 1 , S 2 , ⋯ , S n ) ∈ ( X ∗ ) ∗ n ≥ λ = O ~ ( d 2.5 8 log ∗ ∣ Y ∣ ε log ( 1 β δ ) ) n \geq\lambda= \widetilde{O}\left(d^{2.5}\frac{8\log^{*}|\mathcal{Y}|}{\varepsilon}\log\left(\frac{1}{\beta\delta}\right)\right) n ≥ λ = O ( d 2.5 ε 8 l o g ∗ ∣ Y ∣ log ( β δ 1 ) ) y ^ = A ( f Q , S ) \hat{y} = \mathcal{A}(f_{Q},S) y ^ = A ( f Q , S )
Q ( S , y ^ ) ≥ min S ′ ∈ N λ + ( S ) Q ( S , f Q ( S ′ ) ) Q(S,\hat{y}) \geq\min_{S' \in\mathcal{N}^{+}_{\lambda}(S)} Q(S,f_{Q}(S')) Q ( S , y ^ ) ≥ S ′ ∈ N λ + ( S ) min Q ( S , f Q ( S ′ )) with probability at least 1 − β 1-\beta 1 − β
This is a direct consequence of Claim 6.5 and Theorem 2.6, treating each user’s dataset S i ∈ X ∗ S_{i} \in\mathcal{X}^{*} S i ∈ X ∗ λ \lambda λ S S S S S S Q Q Q
A useful baseline is the sample-and-aggregate framework, which runs the non-private optimizer on disjoint blocks of users and privately aggregates the resulting solutions. We compare this baseline with our black-box evaluator in subsection 6.6.
We next instantiate this guarantee for the user-level center point problem.
Let Y ⊆ R d \mathcal{Y} \subseteq\mathbb{R}^{d} Y ⊆ R d Y ~ \widetilde{\mathcal{Y}} Y Y \mathcal{Y} Y S = ( S 1 , S 2 , ⋯ , S n ) ∈ ( Y ∗ ) ∗ S = (S_{1},S_{2},\cdots,S_{n}) \in(\mathcal{Y}^{*})^{*} S = ( S 1 , S 2 , ⋯ , S n ) ∈ ( Y ∗ ) ∗ flat ( S ) : = ⨄ i ∈ [ n ] S i \operatorname{flat}(S) := \mathbin{\mathop{\biguplus}_{i \in[n]}} S_{i} flat ( S ) := ⨄ i ∈ [ n ] S i f c e n t e r : ( Y ∗ ) ∗ → Y ~ f_{\mathrm{center}} : (\mathcal{Y}^{*})^{*} \to\widetilde{\mathcal{Y}} f center : ( Y ∗ ) ∗ → Y
f c e n t e r ( S ) ∈ arg max y ∈ Y ~ TD ( flat ( S ) , y ) , f_{\mathrm{center}}(S) \in\arg\max_{y \in\widetilde{\mathcal{Y}}} \operatorname{TD}(\operatorname{flat}(S),y), f center ( S ) ∈ arg y ∈ Y max TD ( flat ( S ) , y ) , where ties are broken deterministically.
Corollary 6.8 (User-level center point). Let β , ε , δ ∈ ( 0 , 1 ) \beta,\varepsilon,\delta\in(0,1) β , ε , δ ∈ ( 0 , 1 ) Y ⊆ R d \mathcal{Y} \subseteq\mathbb{R}^{d} Y ⊆ R d Y ~ \widetilde{\mathcal{Y}} Y Y \mathcal{Y} Y Lemma 4.7 . Let f c e n t e r f_{\mathrm{center}} f center A \mathcal{A} A ( ε , δ ) (\varepsilon,\delta) ( ε , δ )
Furthermore, let S = ( S 1 , S 2 , ⋯ , S n ) S = (S_{1},S_{2},\cdots,S_{n}) S = ( S 1 , S 2 , ⋯ , S n ) S i ∈ Y m i S_{i} \in\mathcal{Y}^{m_{i}} S i ∈ Y m i i ∈ [ n ] i \in[n] i ∈ [ n ] M = ∑ i ∈ [ n ] m i M = \sum_{i \in[n]}m_{i} M = ∑ i ∈ [ n ] m i m i 1 ≥ m i 2 ≥ ⋯ ≥ m i n m_{i_{1}} \geq m_{i_{2}} \geq\cdots\geq m_{i_{n}} m i 1 ≥ m i 2 ≥ ⋯ ≥ m i n n ≥ λ = O ~ ( d 2.5 8 log ∗ ∣ Y ∣ ε log ( 1 β δ ) ) n \geq\lambda= \widetilde{O}\left(d^{2.5}\frac{8\log^{*}|\mathcal{Y}|}{\varepsilon}\log\left(\frac{1}{\beta\delta}\right)\right) n ≥ λ = O ( d 2.5 ε 8 l o g ∗ ∣ Y ∣ log ( β δ 1 ) ) y ^ = A ( f c e n t e r , S ) \hat{y} = \mathcal{A}(f_{\mathrm{center}},S) y ^ = A ( f center , S )
TD ( flat ( S ) , y ^ ) ≥ max { max y ∈ R d TD ( flat ( S ) , y ) − ∑ j ∈ [ λ ] m i j , M − ∑ j ∈ [ λ ] m i j d + 1 } \operatorname{TD}(\operatorname{flat}(S),\hat{y}) \geq\max\left\{\max_{y \in\mathbb{R}^{d}} \operatorname{TD}(\operatorname{flat}(S),y)-\sum_{j \in[\lambda]}m_{i_{j}},\frac{M-\sum_{j \in[\lambda]}m_{i_{j}}}{d+1}\right\} TD ( flat ( S ) , y ^ ) ≥ max ⎩ ⎨ ⎧ y ∈ R d max TD ( flat ( S ) , y ) − j ∈ [ λ ] ∑ m i j , d + 1 M − ∑ j ∈ [ λ ] m i j ⎭ ⎬ ⎫ with probability at least 1 − β 1-\beta 1 − β m i = m > 0 m_i=m>0 m i = m > 0 i ∈ [ n ] i\in[n] i ∈ [ n ]
TD ( flat ( S ) , y ^ ) ≥ ( n − λ ) m d + 1 . \operatorname{TD}(\operatorname{flat}(\mathcal{S}),\hat{y})\ge\frac{(n-\lambda)m}{d+1}. TD ( flat ( S ) , y ^ ) ≥ d + 1 ( n − λ ) m . See E.3 for the proof.
The two terms in the bound provide complementary guarantees. The first compares the output with the maximum Tukey depth over Y \mathcal{Y} Y ∑ j ∈ [ λ ] m i j \sum_{j\in[\lambda]}m_{i_j} ∑ j ∈ [ λ ] m i j λ \lambda λ 1 / ( d + 1 ) 1/(d+1) 1/ ( d + 1 )
For comparison, the ordinary center point guarantee from Corollary 6.4, applied to the flattened dataset of size M M M M / ( d + 1 ) − Δ M/(d+1)-\Delta M / ( d + 1 ) − Δ M d + 1 − ∑ j ∈ [ λ ] m i j d + 1 \frac{M}{d+1}-\frac{\sum_{j\in[\lambda]}m_{i_j}}{d+1} d + 1 M − d + 1 ∑ j ∈ [ λ ] m i j
Thus, the loss relative to the usual center point benchmark is controlled explicitly by the largest users’ contributions, without requiring a uniform upper bound on their sizes.
In particular, when m i = m > 0 m_i=m>0 m i = m > 0 i ∈ [ n ] i\in[n] i ∈ [ n ] TD ( flat ( S ) , y ^ ) ≥ ( n − λ ) m d + 1 \operatorname{TD}(\operatorname{flat}(\mathcal{S}),\hat{y})\ge\frac{(n-\lambda)m}{d+1} TD ( flat ( S ) , y ^ ) ≥ d + 1 ( n − λ ) m
For fixed dimension, output domain, and privacy and failure parameters, λ \lambda λ m m m n > λ n>\lambda n > λ m m m
User-Level Private Convex Optimization
Our black-box evaluator also provides a generic approach to user-level private convex optimization. It applies to arbitrary convex user loss functions and convex regularizers, without requiring a uniform bound on the users’ contribution sizes or on the sensitivity of the objective. This includes objectives formed from bounded per-example loss terms when each user may contribute arbitrarily many examples.
The evaluator A \mathcal{A} A Y \mathcal{Y} Y L \mathcal{L} L
For comparison, representative prior results on user-level private convex optimization [14 , 19 ] analyze Lipschitz losses with a fixed number of examples per user; their stochastic optimization guarantees also assume i.i.d. sampling. These works already accommodate nonsmooth losses. Our corollary provides a dataset-wise empirical-loss guarantee for arbitrary user datasets, with the excess loss controlled by the loss variation associated with at most λ \lambda λ
Another useful baseline is the sample-and-aggregate framework, which runs the non-private optimizer on disjoint blocks of users and privately aggregates the resulting solutions. We compare this baseline with our black-box evaluator in subsection 6.6.
We now formally define the user-level convex optimization setting and state the resulting guarantee.
Let X \mathcal{X} X Y ⊆ R d \mathcal{Y} \subseteq\mathbb{R}^{d} Y ⊆ R d ϕ i : X ∗ × R d → R \phi_i : \mathcal{X}^{*} \times\mathbb{R}^{d} \to\mathbb{R} ϕ i : X ∗ × R d → R r : R d → R r : \mathbb{R}^{d} \to\mathbb{R} r : R d → R S = ( S 1 , S 2 , … , S n ) ∈ ( X ∗ ) ∗ S = (S_1, S_2, \ldots, S_n) \in(\mathcal{X}^{*})^{*} S = ( S 1 , S 2 , … , S n ) ∈ ( X ∗ ) ∗ L : ( X ∗ ) ∗ × R d → R \mathcal{L} : (\mathcal{X}^{*})^{*} \times\mathbb{R}^{d} \to\mathbb{R} L : ( X ∗ ) ∗ × R d → R f L : ( X ∗ ) ∗ → Y f_{\mathcal{L}} : (\mathcal{X}^{*})^{*} \to\mathcal{Y} f L : ( X ∗ ) ∗ → Y
L ( S , y ) = ∑ i ∈ [ n ] ϕ i ( S i , y ) + r ( y ) , f L ( S ) ∈ arg min y ∈ Y L ( S , y ) , \mathcal{L}(S,y) = \sum_{i \in[n]} \phi_i(S_i,y) + r(y), \qquad f_{\mathcal{L}}(S) \in\arg\min_{y \in\mathcal{Y}} \mathcal{L}(S,y), L ( S , y ) = i ∈ [ n ] ∑ ϕ i ( S i , y ) + r ( y ) , f L ( S ) ∈ arg y ∈ Y min L ( S , y ) , where ties are broken deterministically. For a subdataset S ′ ⊆ S S' \subseteq S S ′ ⊆ S L ( S ′ , y ) = ∑ S i ∈ S ′ ϕ i ( S i , y ) + r ( y ) \mathcal{L}(S',y) = \sum_{S_i \in S'} \phi_i(S_i,y) + r(y) L ( S ′ , y ) = ∑ S i ∈ S ′ ϕ i ( S i , y ) + r ( y )
Corollary 6.9. Let β , ε , δ ∈ ( 0 , 1 ) \beta, \varepsilon, \delta\in(0,1) β , ε , δ ∈ ( 0 , 1 ) L \mathcal{L} L f L f_{\mathcal{L}} f L Theorem 2.6 is ( ε , δ ) (\varepsilon,\delta) ( ε , δ )
Furthermore, let S = ( S 1 , S 2 , … , S n ) S = (S_1,S_2,\ldots,S_n) S = ( S 1 , S 2 , … , S n ) S i ∈ X m i S_i \in\mathcal{X}^{m_i} S i ∈ X m i i ∈ [ n ] i \in[n] i ∈ [ n ] n ≥ λ = O ~ ( d 2.5 log ∗ ∣ Y ∣ ε log ( 1 β δ ) ) n \ge\lambda= \widetilde{O}\left(d^{2.5}\frac{\log^{*}|\mathcal{Y}|}{\varepsilon}\log\left(\frac{1}{\beta\delta}\right)\right) n ≥ λ = O ( d 2.5 ε l o g ∗ ∣ Y ∣ log ( β δ 1 ) ) y ^ = A ( f L , S ) \hat{y} = A(f_{\mathcal{L}},S) y ^ = A ( f L , S )
L ( S , y ^ ) ≤ max S ′ ∈ N λ ↑ ( S ) L ( S , f L ( S ′ ) ) \mathcal{L}(S,\hat{y}) \le\max_{S' \in N_{\lambda}^{\uparrow}(S)} \mathcal{L}(S,f_{\mathcal{L}}(S')) L ( S , y ^ ) ≤ S ′ ∈ N λ ↑ ( S ) max L ( S , f L ( S ′ )) ≤ min y ∈ Y L ( S , y ) + max S ′ ∈ N λ ↑ ( S ) ∑ S i ∈ S ∖ S ′ [ ϕ i ( S i , f L ( S ′ ) ) − ϕ i ( S i , f L ( S ) ) ] \le\min_{y \in\mathcal{Y}} \mathcal{L}(S,y) + \max_{S' \in N_{\lambda}^{\uparrow}(S)} \sum_{S_i \in S \setminus S'} \left[\phi_i(S_i,f_{\mathcal{L}}(S'))-\phi_i(S_i,f_{\mathcal{L}}(S))\right] ≤ y ∈ Y min L ( S , y ) + S ′ ∈ N λ ↑ ( S ) max S i ∈ S ∖ S ′ ∑ [ ϕ i ( S i , f L ( S ′ )) − ϕ i ( S i , f L ( S )) ] with probability at least 1 − β 1-\beta 1 − β
This is essentially due to Claim 6.5 and Theorem 2.6 . See E.4 for the formal proof.
Comparison with the sample-and-aggregate baseline
A natural baseline for private black-box evaluation is the sample-and-aggregate framework of Nissim et al. [23 ] . This framework applies a non-private procedure to smaller blocks of data and privately aggregates the resulting outputs. For quasi-concave quality functions and convex loss functions, a private center point algorithm is a natural choice of aggregator. The convex-hull guarantee of the aggregator preserves any lower bound on quality, or upper bound on loss, satisfied by all block outputs.
Let S ∈ U ∗ S \in\mathcal{U}^{*} S ∈ U ∗ n n n f : U ∗ → Y f : \mathcal{U}^{*} \to\mathcal{Y} f : U ∗ → Y
The sample-and-aggregate baseline randomly partitions S S S λ = O ~ ( d 2.5 log ∗ ∣ Y ∣ log ( 1 / β δ ) ε ) \lambda= \widetilde{O}\left(d^{2.5}\frac{\log^{*}|\mathcal{Y}|\log(1/\beta\delta)}{\varepsilon}\right) λ = O ( d 2.5 ε l o g ∗ ∣ Y ∣ l o g ( 1/ β δ ) ) T 1 , … , T λ T_1,\ldots,T_\lambda T 1 , … , T λ f f f Corollary 6.4 ). With probability at least 1 − β 1-\beta 1 − β
y ^ S A ∈ CH ( { f ( T 1 ) , … , f ( T λ ) } ) . \hat{y}_{\mathrm{SA}} \in\operatorname{CH}\left(\{f(T_1),\ldots,f(T_\lambda)\}\right). y ^ SA ∈ CH ( { f ( T 1 ) , … , f ( T λ )} ) . Consequently, for any quasi-concave quality function Q \mathcal{Q} Q L \mathcal{L} L
Q ( S , y ^ S A ) ≥ min i ∈ [ λ ] Q ( S , f ( T i ) ) , \mathcal{Q}(S,\hat{y}_{\mathrm{SA}}) \ge\min_{i \in[\lambda]} \mathcal{Q}(S,f(T_i)), Q ( S , y ^ SA ) ≥ i ∈ [ λ ] min Q ( S , f ( T i )) , L ( S , y ^ S A ) ≤ max i ∈ [ λ ] L ( S , f ( T i ) ) . \mathcal{L}(S,\hat{y}_{\mathrm{SA}}) \le\max_{i \in[\lambda]} \mathcal{L}(S,f(T_i)). L ( S , y ^ SA ) ≤ i ∈ [ λ ] max L ( S , f ( T i )) . On the other hand, let y ^ B B = A ( f , S ) \hat{y}_{\mathrm{BB}}=\mathcal{A}(f,S) y ^ BB = A ( f , S ) ( λ , β ) (\lambda,\beta) ( λ , β ) Theorem 2.6 ). By Claim 6.5, with probability at least 1 − β 1-\beta 1 − β
Q ( S , y ^ B B ) ≥ min S ′ ∈ N λ ↗ ( S ) Q ( S , f ( S ′ ) ) , \mathcal{Q}(S,\hat{y}_{\mathrm{BB}}) \ge\min_{S' \in\mathcal{N}_{\lambda}^{\nearrow}(S)} \mathcal{Q}(S,f(S')), Q ( S , y ^ BB ) ≥ S ′ ∈ N λ ↗ ( S ) min Q ( S , f ( S ′ )) , L ( S , y ^ B B ) ≤ max S ′ ∈ N λ ↗ ( S ) L ( S , f ( S ′ ) ) . \mathcal{L}(S,\hat{y}_{\mathrm{BB}}) \le\max_{S' \in\mathcal{N}_{\lambda}^{\nearrow}(S)} \mathcal{L}(S,f(S')). L ( S , y ^ BB ) ≤ S ′ ∈ N λ ↗ ( S ) max L ( S , f ( S ′ )) . For balanced blocks, the baseline therefore relies on solutions computed on approximately n / λ n/\lambda n / λ n − λ n-\lambda n − λ f ( T ) f(T) f ( T ) S S S T ⊆ S T \subseteq S T ⊆ S ∣ T ∣ ≥ h |T| \ge h ∣ T ∣ ≥ h
n S A = λ h , n B B = h + λ . n_{\mathrm{SA}}=\lambda h,\qquad n_{\mathrm{BB}}=h+\lambda. n SA = λh , n BB = h + λ . Thus, under this uniform-subset guarantee, the baseline incurs a multiplicative overhead, while our evaluator incurs an additive overhead. This comparison applies to both item-level and user-level privacy, by taking U = X U=\mathcal{X} U = X U = X ∗ U=\mathcal{X}^* U = X ∗
AI Disclosure
The authors proved all theorems and wrote all proofs in this work. AI (GPT-Sol 5.6) was used to check the proofs and identified some edge cases in the algorithms and theorems, which the authors subsequently addressed. AI was also used to refine the language and grammar.
Preliminaries
This section collects the differential privacy tools and geometric facts used in our constructions and analyses.
Theorem A.1 (Advanced composition, Dwork et al. [11 ] ). Let ε , δ > 0 \varepsilon,\delta> 0 ε , δ > 0 M 1 , … , M t : U ∗ → Y M_1,\ldots,M_t:\mathcal{U}^* \to\mathcal{Y} M 1 , … , M t : U ∗ → Y ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) S ∈ X n S \in\mathcal{X}^n S ∈ X n ( M 1 ( S ) , … , M t ( S ) ) (M_1(S),\ldots,M_t(S)) ( M 1 ( S ) , … , M t ( S )) ( ε ′ , t δ + δ ′ ) (\varepsilon',t\delta+\delta') ( ε ′ , t δ + δ ′ ) ε ′ = ε 2 t log ( 1 / δ ′ ) + t ε ( e ε − 1 ) \varepsilon'=\varepsilon\sqrt{2t\log(1/\delta')}+t\varepsilon(e^\varepsilon-1) ε ′ = ε 2 t log ( 1/ δ ′ ) + tε ( e ε − 1 ) δ ′ > 0 \delta'>0 δ ′ > 0
Theorem A.2 (Exponential Mechanism [22 ] ). Let ε , Δ > 0 \varepsilon,\Delta>0 ε , Δ > 0 β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) U \mathcal{U} U Y \mathcal{Y} Y S ∈ U ∗ S\in\mathcal{U}^* S ∈ U ∗ Q : U ∗ × Y → R Q:\mathcal{U}^*\times\mathcal{Y}\to\mathbb{R} Q : U ∗ × Y → R Δ \Delta Δ ( ε , 0 ) (\varepsilon,0) ( ε , 0 ) S ∈ U ∗ S\in\mathcal{U}^* S ∈ U ∗ y ^ ∈ Y \hat{y}\in\mathcal{Y} y ^ ∈ Y
Q ( S , y ^ ) ≥ max y ∈ Y Q ( S , y ) − 2 Δ log ( ∣ Y ∣ / β ) ε Q(S,\hat{y})\ge\max_{y\in\mathcal{Y}} Q(S,y)-\frac{2\Delta\log(|\mathcal{Y}|/\beta)}{\varepsilon} Q ( S , y ^ ) ≥ y ∈ Y max Q ( S , y ) − ε 2Δ log ( ∣ Y ∣/ β ) with probability at least 1 − β 1-\beta 1 − β
Definition A.3 (Truncated Laplace distribution). Let s , ε > 0 s,\varepsilon>0 s , ε > 0 δ ∈ ( 0 , 1 / 2 ) \delta\in(0,1/2) δ ∈ ( 0 , 1/2 ) R = s ε log ( 1 + e ε 2 δ ) R=\frac{s}{\varepsilon}\log\left(1+\frac{e^\varepsilon}{2\delta}\right) R = ε s log ( 1 + 2 δ e ε ) TLap ( s , ε , δ ) \operatorname{TLap}(s,\varepsilon,\delta) TLap ( s , ε , δ )
p ( z ) = { ε 2 s ( 1 − e − ε R / s ) e − ε ∣ z ∣ / s , ∣ z ∣ ≤ R , 0 , otherwise . p(z)=
\begin{cases}
\frac{\varepsilon}{2s(1-e^{-\varepsilon R/s})}e^{-\varepsilon|z|/s}, & |z|\le R,\\
0, & \text{otherwise}.
\end{cases} p ( z ) = { 2 s ( 1 − e − εR / s ) ε e − ε ∣ z ∣/ s , 0 , ∣ z ∣ ≤ R , otherwise . Lemma A.4 (Truncated Laplace mechanism, Theorem 1 of Geng et al. [13 ] ). Let δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) ε > 0 \varepsilon>0 ε > 0 q : U ∗ → R q:\mathcal{U}^*\to\mathbb{R} q : U ∗ → R s s s Z ∼ TLap ( s , ε , δ ) Z\sim\operatorname{TLap}(s,\varepsilon,\delta) Z ∼ TLap ( s , ε , δ ) q ( S ) + Z q(S)+Z q ( S ) + Z ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) ∣ Z ∣ ≤ R |Z|\le R ∣ Z ∣ ≤ R
Theorem A.5 (GAP-MAX, additive-error form of Theorem IV.6. of [2 ] ). Let ε > 0 \varepsilon>0 ε > 0 β , δ ∈ ( 0 , 1 ) \beta,\delta\in(0,1) β , δ ∈ ( 0 , 1 ) t ≥ 1 t\ge1 t ≥ 1 U \mathcal{U} U Y \mathcal{Y} Y score : U ∗ × Y → R \operatorname{score}:\mathcal{U}^*\times\mathcal{Y}\to\mathbb{R} score : U ∗ × Y → R ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) S ∈ U ∗ S\in\mathcal{U}^* S ∈ U ∗ Δ > 0 \Delta>0 Δ > 0
∣ { y ∈ Y : score ( S , y ) ≥ sup y ∈ Y score ( S , y ) − 5 Δ } ∣ ≤ t \left|\left\{y\in\mathcal{Y}:\operatorname{score}(S,y)\ge\sup_{y\in\mathcal{Y}}\operatorname{score}(S,y)-5\Delta\right\}\right|\le t { y ∈ Y : score ( S , y ) ≥ y ∈ Y sup score ( S , y ) − 5Δ } ≤ t then the output of the algorithm y ^ = GAP-MAX ( Y , S , score , Δ , β , ε , δ , t ) \hat{y}=\operatorname{GAP-MAX}(\mathcal{Y},S,\operatorname{score},\Delta,\beta,\varepsilon,\delta,t) y ^ = GAP-MAX ( Y , S , score , Δ , β , ε , δ , t )
P [ score ( S , y ^ ) ≥ sup y ∈ Y score ( S , y ) − Δ ] ≥ 1 − β \mathbb{P}\left[\operatorname{score}(S,\hat{y})\ge\sup_{y\in\mathcal{Y}}\operatorname{score}(S,y)-\Delta\right]\ge1-\beta P [ score ( S , y ^ ) ≥ y ∈ Y sup score ( S , y ) − Δ ] ≥ 1 − β provided Δ = Ω ( 1 + min { log ∣ Y ∣ , log ( 1 / δ ) } + log ( t / β ) ε ) \Delta=\Omega\left(1+\frac{\min\{\log|\mathcal{Y}|,\log(1/\delta)\}+\log(t/\beta)}{\varepsilon}\right) Δ = Ω ( 1 + ε m i n { l o g ∣ Y ∣ , l o g ( 1/ δ )} + l o g ( t / β ) )
Convex analysis
Theorem A.6 (Helly’s theorem [15 ] ). Let { S i } i ∈ I ⊆ R d \{S_i\}_{i\in\mathcal{I}}\subseteq\mathbb{R}^d { S i } i ∈ I ⊆ R d J ⊆ I \mathcal{J}\subseteq\mathcal{I} J ⊆ I ∣ J ∣ ≤ d + 1 |\mathcal{J}|\le d+1 ∣ J ∣ ≤ d + 1 ⋂ j ∈ J S j ≠ ∅ \bigcap_{j\in\mathcal{J}}S_j\ne\varnothing ⋂ j ∈ J S j = ∅ ⋂ i ∈ I S i ≠ ∅ \bigcap_{i\in\mathcal{I}}S_i\ne\varnothing ⋂ i ∈ I S i = ∅
Theorem A.7 (Center Point Theorem [25 ] ). Let S ∈ ( R d ) ∗ S \in(\mathbb{R}^{d})^{*} S ∈ ( R d ) ∗ y ∈ C H ( S ) y \in\mathrm{CH}(S) y ∈ CH ( S )
T D ( S , y ) ≥ ∣ S ∣ d + 1 . \mathrm{TD}(S,y) \ge\frac{|S|}{d+1}. TD ( S , y ) ≥ d + 1 ∣ S ∣ . Equivalently, every closed halfspace containing y y y ∣ S ∣ / ( d + 1 ) |S|/(d+1) ∣ S ∣/ ( d + 1 ) S S S
Omitted proofs from section 2
Claim B.1. Proof of Claim 2.4.
Proof. Note that, if S 1 ⊆ S 2 S_1 \subseteq S_2 S 1 ⊆ S 2 h ∈ [ ∣ S ∣ ] h \in[|S|] h ∈ [ ∣ S ∣ ] M h ↓ ( S 1 ) ⊆ M h ↓ ( S 2 ) M_h^{\downarrow}(S_1) \subseteq M_h^{\downarrow}(S_2) M h ↓ ( S 1 ) ⊆ M h ↓ ( S 2 )
⋃ S ′ ∈ M h ↓ ( S 1 ) f ( S ′ ) ⊆ ⋃ S ′ ∈ M h ↓ ( S 2 ) f ( S ′ ) . \bigcup_{S' \in M_h^{\downarrow}(S_1)} f(S') \subseteq\bigcup_{S' \in M_h^{\downarrow}(S_2)} f(S'). S ′ ∈ M h ↓ ( S 1 ) ⋃ f ( S ′ ) ⊆ S ′ ∈ M h ↓ ( S 2 ) ⋃ f ( S ′ ) . Therefore, the convex hull of the left-hand side is contained in the convex hull of the right-hand side.
Claim B.2. Proof of Claim 6.5.
Proof. By the definition of a ( λ , β ) (\lambda,\beta) ( λ , β ) 1 − β 1-\beta 1 − β
y ^ : = A ( f , S ) ∈ C H ( f ( N λ ↓ ( S ) ) ) . \hat{y} := A(f,S) \in\mathrm{CH}\left(f\left(N_{\lambda}^{\downarrow}(S)\right)\right). y ^ := A ( f , S ) ∈ CH ( f ( N λ ↓ ( S ) ) ) . By the definition of the convex hull, there exist S 1 , … , S k ∈ N λ ↓ ( S ) S_1,\ldots,S_k \in N_{\lambda}^{\downarrow}(S) S 1 , … , S k ∈ N λ ↓ ( S ) λ 1 , … , λ k ≥ 0 \lambda_1,\ldots,\lambda_k \ge0 λ 1 , … , λ k ≥ 0 ∑ i ∈ [ k ] λ i = 1 \sum_{i \in[k]} \lambda_i = 1 ∑ i ∈ [ k ] λ i = 1 y ^ = ∑ i ∈ [ k ] λ i f ( S i ) \hat{y} = \sum_{i \in[k]} \lambda_i f(S_i) y ^ = ∑ i ∈ [ k ] λ i f ( S i ) Q ( S , ⋅ ) Q(S,\cdot) Q ( S , ⋅ )
Q ( S , y ^ ) = Q ( S , ∑ i ∈ [ k ] λ i f ( S i ) ) ≥ min i ∈ [ k ] Q ( S , f ( S i ) ) ≥ min S ′ ∈ N λ ↓ ( S ) Q ( S , f ( S ′ ) ) . \begin{aligned}
Q(S,\hat{y}) &= Q\left(S,\sum_{i \in[k]} \lambda_i f(S_i)\right) \\
&\ge\min_{i \in[k]} Q(S,f(S_i)) \\
&\ge\min_{S' \in N_{\lambda}^{\downarrow}(S)} Q(S,f(S')).
\end{aligned} Q ( S , y ^ ) = Q S , i ∈ [ k ] ∑ λ i f ( S i ) ≥ i ∈ [ k ] min Q ( S , f ( S i )) ≥ S ′ ∈ N λ ↓ ( S ) min Q ( S , f ( S ′ )) . Similarly, since L ( S , ⋅ ) L(S,\cdot) L ( S , ⋅ )
L ( S , y ^ ) = L ( S , ∑ i ∈ [ k ] λ i f ( S i ) ) ≤ ∑ i ∈ [ k ] λ i L ( S , f ( S i ) ) ≤ max i ∈ [ k ] L ( S , f ( S i ) ) ≤ max S ′ ∈ N λ ↓ ( S ) L ( S , f ( S ′ ) ) . \begin{aligned}
L(S,\hat{y}) &= L\left(S,\sum_{i \in[k]} \lambda_i f(S_i)\right) \\
&\le\sum_{i \in[k]} \lambda_i L(S,f(S_i)) \\
&\le\max_{i \in[k]} L(S,f(S_i)) \\
&\le\max_{S' \in N_{\lambda}^{\downarrow}(S)} L(S,f(S')).
\end{aligned} L ( S , y ^ ) = L S , i ∈ [ k ] ∑ λ i f ( S i ) ≤ i ∈ [ k ] ∑ λ i L ( S , f ( S i )) ≤ i ∈ [ k ] max L ( S , f ( S i )) ≤ S ′ ∈ N λ ↓ ( S ) max L ( S , f ( S ′ )) . Omitted proofs from section 4
Claim C.1. Proof of Claim 4.2.
Proof. For every dataset T ∈ U ∗ T \in U^* T ∈ U ∗ M h ′ ↓ ( T ) ⊆ M h ↓ ( T ) M_{h'}^{\downarrow}(T) \subseteq M_h^{\downarrow}(T) M h ′ ↓ ( T ) ⊆ M h ↓ ( T ) C D I h ′ f ( T ) ⊆ C D I h f ( T ) \mathrm{CDI}_{h'}^f(T) \subseteq\mathrm{CDI}_h^f(T) CDI h ′ f ( T ) ⊆ CDI h f ( T ) S ′ ⊆ S S' \subseteq S S ′ ⊆ S y ∉ C D I h f ( S ∖ S ′ ) y \notin\mathrm{CDI}_{h}^f(S \setminus S') y ∈ / CDI h f ( S ∖ S ′ ) y ∉ C D I h ′ f ( S ∖ S ′ ) y \notin\mathrm{CDI}_{h'}^f(S \setminus S') y ∈ / CDI h ′ f ( S ∖ S ′ ) ∣ S ′ ∣ |S'| ∣ S ′ ∣ depth h ′ f ( S , y ) ≤ depth h f ( S , y ) \operatorname{depth}_{h'}^f(S,y) \leq\operatorname{depth}_{h}^f(S,y) depth h ′ f ( S , y ) ≤ depth h f ( S , y )
Claim C.2. Proof of Claim 4.3.
Proof. Let’s assume by contradiction that there are y 1 , y 2 ∈ R d y_1,y_2 \in\mathbb{R}^d y 1 , y 2 ∈ R d λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] t ∗ = depth h f ( S , λ y 1 + ( 1 − λ ) y 2 ) < min { depth h f ( S , y 1 ) , depth h f ( S , y 2 ) } t^* = \operatorname{depth}_h^f(S,\lambda y_1+(1-\lambda)y_2) < \min\left\{\operatorname{depth}_h^f(S,y_1),\operatorname{depth}_h^f(S,y_2)\right\} t ∗ = depth h f ( S , λ y 1 + ( 1 − λ ) y 2 ) < min { depth h f ( S , y 1 ) , depth h f ( S , y 2 ) } S ′ ⊆ S S' \subseteq S S ′ ⊆ S ∣ S ′ ∣ = t ∗ |S'|=t^* ∣ S ′ ∣ = t ∗ λ y 1 + ( 1 − λ ) y 2 \lambda y_1+(1-\lambda)y_2 λ y 1 + ( 1 − λ ) y 2 C D I h f ( S ∖ S ′ ) \mathrm{CDI}_h^f(S\setminus S') CDI h f ( S ∖ S ′ ) t ∗ < min { depth h f ( S , y 1 ) , depth h f ( S , y 2 ) } t^* < \min\left\{\operatorname{depth}_h^f(S,y_1),\operatorname{depth}_h^f(S,y_2)\right\} t ∗ < min { depth h f ( S , y 1 ) , depth h f ( S , y 2 ) } y 1 , y 2 ∈ C D I h f ( S ∖ S ′ ) y_1,y_2 \in\mathrm{CDI}_h^f(S\setminus S') y 1 , y 2 ∈ CDI h f ( S ∖ S ′ ) C D I h f ( S ∖ S ′ ) \mathrm{CDI}_h^f(S\setminus S') CDI h f ( S ∖ S ′ ) y 1 y_1 y 1 y 2 y_2 y 2
Claim C.3. Proof of Claim 4.4.
Proof. We first show that for every y ∈ R d y \in\mathbb{R}^d y ∈ R d S 1 , S 2 ⊆ R d S_1,S_2 \subseteq\mathbb{R}^d S 1 , S 2 ⊆ R d S 1 ⊆ S 2 S_1 \subseteq S_2 S 1 ⊆ S 2
I. depth h f ( S 1 , y ) ≤ depth h f ( S 2 , y ) \operatorname{depth}_h^f(S_1,y) \leq\operatorname{depth}_h^f(S_2,y) depth h f ( S 1 , y ) ≤ depth h f ( S 2 , y )
II. depth h f ( S 2 , y ) ≤ depth h f ( S 1 , y ) + ∣ S 2 ∖ S 1 ∣ \operatorname{depth}_h^f(S_2,y) \leq\operatorname{depth}_h^f(S_1,y)+|S_2\setminus S_1| depth h f ( S 2 , y ) ≤ depth h f ( S 1 , y ) + ∣ S 2 ∖ S 1 ∣
To prove (I), let S ˉ \bar{S} S ˉ depth h f ( S 2 , y ) \operatorname{depth}_h^f(S_2,y) depth h f ( S 2 , y ) y ∉ C D I h f ( S 2 ∖ S ˉ ) y \notin\mathrm{CDI}_h^f(S_2\setminus\bar{S}) y ∈ / CDI h f ( S 2 ∖ S ˉ ) ( S 1 ∖ S ˉ ) ⊆ ( S 2 ∖ S ˉ ) (S_1\setminus\bar{S}) \subseteq(S_2\setminus\bar{S}) ( S 1 ∖ S ˉ ) ⊆ ( S 2 ∖ S ˉ ) C D I h f \mathrm{CDI}_h^f CDI h f Claim 2.4 ), we can say C D I h f ( S 1 ∖ S ˉ ) ⊆ C D I h f ( S 2 ∖ S ˉ ) \mathrm{CDI}_h^f(S_1\setminus\bar{S}) \subseteq\mathrm{CDI}_h^f(S_2\setminus\bar{S}) CDI h f ( S 1 ∖ S ˉ ) ⊆ CDI h f ( S 2 ∖ S ˉ ) y y y C D I h f ( S 1 ∖ S ˉ ) \mathrm{CDI}_h^f(S_1\setminus\bar{S}) CDI h f ( S 1 ∖ S ˉ ) depth h f ( S 1 , y ) ≤ ∣ S ˉ ∣ = depth h f ( S 2 , y ) \operatorname{depth}_h^f(S_1,y) \leq|\bar{S}| = \operatorname{depth}_h^f(S_2,y) depth h f ( S 1 , y ) ≤ ∣ S ˉ ∣ = depth h f ( S 2 , y )
To prove (II), let S ~ \widetilde{S} S depth h f ( S 1 , y ) \operatorname{depth}_h^f(S_1,y) depth h f ( S 1 , y ) y ∉ C D I h f ( S 1 ∖ S ~ ) y \notin\mathrm{CDI}_h^f(S_1\setminus\widetilde{S}) y ∈ / CDI h f ( S 1 ∖ S ) S 1 ∖ S ~ = S 2 ∖ ( ( S 2 ∖ S 1 ) ∪ S ~ ) S_1\setminus\widetilde{S}=S_2\setminus\left((S_2\setminus S_1)\cup\widetilde{S}\right) S 1 ∖ S = S 2 ∖ ( ( S 2 ∖ S 1 ) ∪ S ) y ∉ C D I h f ( S 2 ∖ ( ( S 2 ∖ S 1 ) ∪ S ~ ) ) y \notin\mathrm{CDI}_h^f\left(S_2\setminus\left((S_2\setminus S_1)\cup\widetilde{S}\right)\right) y ∈ / CDI h f ( S 2 ∖ ( ( S 2 ∖ S 1 ) ∪ S ) ) depth h f ( S 2 , y ) ≤ ∣ ( S 2 ∖ S 1 ) ∪ S ~ ∣ = ∣ S 2 ∖ S 1 ∣ + ∣ S ~ ∣ = ∣ S 2 ∖ S 1 ∣ + depth h f ( S 1 , y ) \operatorname{depth}_h^f(S_2,y) \leq|(S_2\setminus S_1)\cup\widetilde{S}|=|S_2\setminus S_1|+|\widetilde{S}|=|S_2\setminus S_1|+\operatorname{depth}_h^f(S_1,y) depth h f ( S 2 , y ) ≤ ∣ ( S 2 ∖ S 1 ) ∪ S ∣ = ∣ S 2 ∖ S 1 ∣ + ∣ S ∣ = ∣ S 2 ∖ S 1 ∣ + depth h f ( S 1 , y )
Putting (I) and (II) together gives depth h f ( S 1 , y ) ≤ depth h f ( S 2 , y ) ≤ depth h f ( S 1 , y ) + ∣ S 2 ∖ S 1 ∣ \operatorname{depth}_h^f(S_1,y) \leq\operatorname{depth}_h^f(S_2,y) \leq\operatorname{depth}_h^f(S_1,y)+|S_2\setminus S_1| depth h f ( S 1 , y ) ≤ depth h f ( S 2 , y ) ≤ depth h f ( S 1 , y ) + ∣ S 2 ∖ S 1 ∣ S 1 ⊆ S 2 S_1 \subseteq S_2 S 1 ⊆ S 2 S , S ′ ⊆ R d S,S' \subseteq\mathbb{R}^d S , S ′ ⊆ R d ( S ∩ S ′ ) ⊆ S (S\cap S') \subseteq S ( S ∩ S ′ ) ⊆ S depth h f ( S ∩ S ′ , y ) ≤ depth h f ( S , y ) ≤ depth h f ( S ∩ S ′ , y ) + ∣ S ∖ ( S ∩ S ′ ) ∣ = depth h f ( S ∩ S ′ , y ) + ∣ S ′ ∖ S ∣ \operatorname{depth}_h^f(S\cap S',y) \leq\operatorname{depth}_h^f(S,y) \leq\operatorname{depth}_h^f(S\cap S',y)+|S\setminus(S\cap S')|=\operatorname{depth}_h^f(S\cap S',y)+|S'\setminus S| depth h f ( S ∩ S ′ , y ) ≤ depth h f ( S , y ) ≤ depth h f ( S ∩ S ′ , y ) + ∣ S ∖ ( S ∩ S ′ ) ∣ = depth h f ( S ∩ S ′ , y ) + ∣ S ′ ∖ S ∣ depth h f ( S ∩ S ′ , y ) ≤ depth h f ( S ′ , y ) ≤ depth h f ( S ∩ S ′ , y ) + ∣ S ′ ∖ ( S ∩ S ′ ) ∣ = depth h f ( S ∩ S ′ , y ) + ∣ S ′ ∖ S ∣ \operatorname{depth}_h^f(S\cap S',y) \leq\operatorname{depth}_h^f(S',y) \leq\operatorname{depth}_h^f(S\cap S',y)+|S'\setminus(S\cap S')|=\operatorname{depth}_h^f(S\cap S',y)+|S'\setminus S| depth h f ( S ∩ S ′ , y ) ≤ depth h f ( S ′ , y ) ≤ depth h f ( S ∩ S ′ , y ) + ∣ S ′ ∖ ( S ∩ S ′ ) ∣ = depth h f ( S ∩ S ′ , y ) + ∣ S ′ ∖ S ∣
Lemma C.4. Proof of Lemma 4.7.
Proof. We construct Y ~ \widetilde{Y} Y I ⊆ 2 Y \mathcal{I} \subseteq2^Y I ⊆ 2 Y A I ≠ ∅ A_{\mathcal{I}} \neq\varnothing A I = ∅ A I A_{\mathcal{I}} A I Y ~ \widetilde{Y} Y C H ( Y ) \mathrm{CH}(Y) CH ( Y ) A I ≠ ∅ A_{\mathcal{I}} \neq\varnothing A I = ∅ A I ∩ Y ~ ≠ ∅ A_{\mathcal{I}} \cap\widetilde{Y} \neq\varnothing A I ∩ Y = ∅ I = { { y } } \mathcal{I}=\{\{y\}\} I = {{ y }} y ∈ Y y \in Y y ∈ Y Y ⊆ Y ~ Y \subseteq\widetilde{Y} Y ⊆ Y Y ~ \widetilde{Y} Y I = ∅ \mathcal{I}=\varnothing I = ∅ 2 2 ∣ Y ∣ 2^{2^{|Y|}} 2 2 ∣ Y ∣
Proof. For a nonempty finite set T ⊆ R d T \subseteq\mathbb{R}^d T ⊆ R d aff ( T ) = { ∑ y ∈ T α y y : α y ∈ R , ∑ y ∈ T α y = 1 } \operatorname{aff}(T) = \left\{ \sum_{y\in T} \alpha_y y : \alpha_y \in\mathbb{R},\ \sum_{y\in T} \alpha_y = 1 \right\} aff ( T ) = { ∑ y ∈ T α y y : α y ∈ R , ∑ y ∈ T α y = 1 }
Let n = ∣ Y ∣ n = |\mathcal{Y}| n = ∣ Y ∣ L = { aff ( { y 1 , … , y d } ) : ( y 1 , … , y d ) ∈ Y d } \mathcal{L} = \left\{ \operatorname{aff}(\{y_1,\ldots,y_d\}) : (y_1,\ldots,y_d) \in\mathcal{Y}^d \right\} L = { aff ({ y 1 , … , y d }) : ( y 1 , … , y d ) ∈ Y d }
Y ~ = { x ∈ CH ( Y ) : { x } = ⋂ j = 1 d L j for some L 1 , … , L d ∈ L } . \widetilde{\mathcal{Y}} = \left\{ x \in\operatorname{CH}(\mathcal{Y}) : \{x\} = \bigcap_{j=1}^{d} L_j \text{ for some } L_1,\ldots,L_d \in\mathcal{L} \right\}. Y = { x ∈ CH ( Y ) : { x } = j = 1 ⋂ d L j for some L 1 , … , L d ∈ L } . Each ordered d d d L \mathcal{L} L ∣ Y ~ ∣ ≤ ∣ L ∣ d ≤ ( n d ) d = n d 2 |\widetilde{\mathcal{Y}}| \leq|\mathcal{L}|^d \leq(n^d)^d = n^{d^2} ∣ Y ∣ ≤ ∣ L ∣ d ≤ ( n d ) d = n d 2
Now, we show the extension property. Since aff ( { y , … , y } ) = { y } \operatorname{aff}(\{y,\ldots,y\}) = \{y\} aff ({ y , … , y }) = { y } Y ⊆ Y ~ \mathcal{Y} \subseteq\widetilde{\mathcal{Y}} Y ⊆ Y I ⊆ 2 Y \mathcal{I} \subseteq2^{\mathcal{Y}} I ⊆ 2 Y A I ≠ ∅ \mathcal{A}_{\mathcal{I}} \neq\emptyset A I = ∅ CH ( S i ) \operatorname{CH}(S_i) CH ( S i ) A I \mathcal{A}_{\mathcal{I}} A I x ∗ ∈ arg max x ∈ A I ∥ x ∥ 2 x^* \in\operatorname*{arg\,max}_{x\in\mathcal{A}_{\mathcal{I}}} \lVert x\rVert^2 x ∗ ∈ arg max x ∈ A I ∥ x ∥ 2
For each S i ∈ I S_i \in\mathcal{I} S i ∈ I x ∗ x^* x ∗
x ∗ = ∑ y ∈ T i λ i , y y , T i ⊆ S i , λ i , y > 0 , ∑ y ∈ T i λ i , y = 1. x^* = \sum_{y\in T_i} \lambda_{i,y}y,\qquad T_i \subseteq S_i,\qquad\lambda_{i,y} > 0,\qquad\sum_{y\in T_i} \lambda_{i,y} = 1. x ∗ = y ∈ T i ∑ λ i , y y , T i ⊆ S i , λ i , y > 0 , y ∈ T i ∑ λ i , y = 1. Let M i = aff ( T i ) M_i = \operatorname{aff}(T_i) M i = aff ( T i ) ⋂ S i ∈ I M i = { x ∗ } \bigcap_{S_i\in\mathcal{I}} M_i = \{x^*\} ⋂ S i ∈ I M i = { x ∗ } x ∗ ∈ ⋂ S i ∈ I M i x^* \in\bigcap_{S_i\in\mathcal{I}} M_i x ∗ ∈ ⋂ S i ∈ I M i x ∗ x^* x ∗ v v v x ∗ + v x^* + v x ∗ + v M i M_i M i α i , y \alpha_{i,y} α i , y x ∗ + v = ∑ y ∈ T i α i , y y x^* + v = \sum_{y\in T_i} \alpha_{i,y}y x ∗ + v = ∑ y ∈ T i α i , y y ∑ y ∈ T i α i , y = 1 \sum_{y\in T_i} \alpha_{i,y} = 1 ∑ y ∈ T i α i , y = 1
Now, let μ i , y = α i , y − λ i , y \mu_{i,y} = \alpha_{i,y} - \lambda_{i,y} μ i , y = α i , y − λ i , y v = ∑ y ∈ T i μ i , y y v = \sum_{y\in T_i} \mu_{i,y}y v = ∑ y ∈ T i μ i , y y ∑ y ∈ T i μ i , y = 0 \sum_{y\in T_i} \mu_{i,y} = 0 ∑ y ∈ T i μ i , y = 0
All λ i , y \lambda_{i,y} λ i , y ε > 0 \varepsilon> 0 ε > 0 λ i , y ± ε μ i , y ≥ 0 \lambda_{i,y} \pm\varepsilon\mu_{i,y} \geq0 λ i , y ± ε μ i , y ≥ 0 i , y i,y i , y i i i
x ∗ ± ε v = ∑ y ∈ T i ( λ i , y ± ε μ i , y ) y ∈ CH ( T i ) ⊆ CH ( S i ) x^* \pm\varepsilon v = \sum_{y\in T_i}(\lambda_{i,y} \pm\varepsilon\mu_{i,y})y \in\operatorname{CH}(T_i) \subseteq\operatorname{CH}(S_i) x ∗ ± ε v = y ∈ T i ∑ ( λ i , y ± ε μ i , y ) y ∈ CH ( T i ) ⊆ CH ( S i ) Therefore, both x ∗ ± ε v x^* \pm\varepsilon v x ∗ ± ε v A I \mathcal{A}_{\mathcal{I}} A I x ∗ ∈ arg max x ∈ A I ∥ x ∥ 2 x^* \in\operatorname*{arg\,max}_{x\in\mathcal{A}_{\mathcal{I}}} \lVert x\rVert^2 x ∗ ∈ arg max x ∈ A I ∥ x ∥ 2
∥ x ∗ + ε v ∥ 2 + ∥ x ∗ − ε v ∥ 2 2 = ∥ x ∗ ∥ 2 + ε 2 ∥ v ∥ 2 > ∥ x ∗ ∥ 2 . \frac{\lVert x^* + \varepsilon v\rVert^2 + \lVert x^* - \varepsilon v\rVert^2}{2} = \lVert x^*\rVert^2 + \varepsilon^2\lVert v\rVert^2 > \lVert x^*\rVert^2. 2 ∥ x ∗ + ε v ∥ 2 + ∥ x ∗ − ε v ∥ 2 = ∥ x ∗ ∥ 2 + ε 2 ∥ v ∥ 2 > ∥ x ∗ ∥ 2 . Thus, we showed that ⋂ S i ∈ I M i = { x ∗ } \bigcap_{S_i\in\mathcal{I}} M_i = \{x^*\} ⋂ S i ∈ I M i = { x ∗ } x ∗ ∈ Y ~ x^* \in\widetilde{\mathcal{Y}} x ∗ ∈ Y { x ∗ } \{x^*\} { x ∗ } d d d L \mathcal{L} L
First, we show that there exists a subset of the M i M_i M i d d d { x ∗ } \{x^*\} { x ∗ } V 0 = R d V_0 = \mathbb{R}^d V 0 = R d V j ≠ { x ∗ } V_j \neq\{x^*\} V j = { x ∗ } z ∈ V j ∖ { x ∗ } z \in V_j \setminus\{x^*\} z ∈ V j ∖ { x ∗ } ⋂ S i ∈ I M i = { x ∗ } \bigcap_{S_i\in\mathcal{I}} M_i = \{x^*\} ⋂ S i ∈ I M i = { x ∗ } M i M_i M i z z z V j + 1 = V j ∩ M i V_{j+1} = V_j \cap M_i V j + 1 = V j ∩ M i
This intersection contains x ∗ x^* x ∗ z z z V j V_j V j dim ( V j + 1 ) < dim ( V j ) \dim(V_{j+1}) < \dim(V_j) dim ( V j + 1 ) < dim ( V j ) d d d d d d { x ∗ } \{x^*\} { x ∗ } M i 1 , … , M i k M_{i_1},\ldots,M_{i_k} M i 1 , … , M i k 1 ≤ k ≤ d 1 \leq k \leq d 1 ≤ k ≤ d { x ∗ } = ⋂ j = 1 k M i j \{x^*\} = \bigcap_{j=1}^{k} M_{i_j} { x ∗ } = ⋂ j = 1 k M i j L \mathcal{L} L M i = aff ( T i ) M_i = \operatorname{aff}(T_i) M i = aff ( T i ) R d \mathbb{R}^d R d r = dim ( M i ) ≤ d − 1 r = \dim(M_i) \le d - 1 r = dim ( M i ) ≤ d − 1 y 0 ∈ T i y_0 \in T_i y 0 ∈ T i { y − y 0 : y ∈ T i } \{y-y_0:y\in T_i\} { y − y 0 : y ∈ T i } M i M_i M i y 1 , … , y r ∈ T i y_1,\ldots,y_r \in T_i y 1 , … , y r ∈ T i y 1 − y 0 , … , y r − y 0 y_1-y_0,\ldots,y_r-y_0 y 1 − y 0 , … , y r − y 0 M i = aff ( { y 0 , … , y r } ) M_i=\operatorname{aff}(\{y_0,\ldots,y_r\}) M i = aff ({ y 0 , … , y r }) r + 1 ≤ d r+1\le d r + 1 ≤ d Y Y Y d d d M i ∈ L M_i\in\mathcal{L} M i ∈ L
We have expressed { x ∗ } \{x^*\} { x ∗ } k ≤ d k\le d k ≤ d L \mathcal{L} L k < d k<d k < d d d d x ∗ ∈ A I ⊆ CH ( Y ) x^*\in A_{\mathcal{I}}\subseteq\operatorname{CH}(Y) x ∗ ∈ A I ⊆ CH ( Y ) { x ∗ } \{x^*\} { x ∗ } d d d L \mathcal{L} L x ∗ ∈ Y ~ x^*\in\widetilde{Y} x ∗ ∈ Y A I ∩ Y ~ ≠ ∅ A_{\mathcal{I}}\cap\widetilde{Y}\ne\varnothing A I ∩ Y = ∅
Lemma C.6. Proof of Lemma 4.6.
Proof. Let λ = ∣ S ∣ − h d + 1 \lambda=\frac{|S|-h}{d+1} λ = d + 1 ∣ S ∣ − h y ∗ ∈ Y ~ y^*\in\widetilde{Y} y ∗ ∈ Y S ′ ⊆ S S'\subseteq S S ′ ⊆ S ∣ S ′ ∣ ≥ ∣ S ∣ − λ |S'|\ge|S|-\lambda ∣ S ′ ∣ ≥ ∣ S ∣ − λ y ∗ ∈ CDI h f ( S ′ ) y^*\in\operatorname{CDI}^{f}_{h}(S') y ∗ ∈ CDI h f ( S ′ )
[ ⋂ S ′ ∈ N λ ↓ ( S ) CDI h f ( S ′ ) ] ∩ Y ~ ≠ ∅ . \left[\bigcap_{S'\in N_{\lambda}^{\downarrow}(S)}\operatorname{CDI}^{f}_{h}(S')\right]\cap\widetilde{Y}\ne\varnothing. S ′ ∈ N λ ↓ ( S ) ⋂ CDI h f ( S ′ ) ∩ Y = ∅ . Let S 1 , … , S d + 1 ∈ N λ ↓ ( S ) S_1,\ldots,S_{d+1}\in N_{\lambda}^{\downarrow}(S) S 1 , … , S d + 1 ∈ N λ ↓ ( S ) d + 1 d+1 d + 1 ∣ S ∣ − λ |S|-\lambda ∣ S ∣ − λ S 0 = ⋂ i ∈ [ d + 1 ] S i S_0=\bigcap_{i\in[d+1]}S_i S 0 = ⋂ i ∈ [ d + 1 ] S i ∣ S 0 ∣ ≥ ∣ S ∣ − ∑ i ∈ [ d + 1 ] ∣ S ∖ S i ∣ = ∣ S ∣ − ( d + 1 ) λ = h |S_0|\ge|S|-\sum_{i\in[d+1]}|S\setminus S_i|=|S|-(d+1)\lambda=h ∣ S 0 ∣ ≥ ∣ S ∣ − ∑ i ∈ [ d + 1 ] ∣ S ∖ S i ∣ = ∣ S ∣ − ( d + 1 ) λ = h S 0 ∈ M h ↓ ( S 0 ) ≠ ∅ S_0\in M_h^{\downarrow}(S_0)\ne\varnothing S 0 ∈ M h ↓ ( S 0 ) = ∅ CDI h f ( S 0 ) ≠ ∅ \operatorname{CDI}^{f}_{h}(S_0)\ne\varnothing CDI h f ( S 0 ) = ∅ CDI h f ( . ) \operatorname{CDI}^{f}_{h}(.) CDI h f ( . ) CDI h f ( S 0 ) ⊆ CDI h f ( S i ) \operatorname{CDI}^{f}_{h}(S_0)\subseteq\operatorname{CDI}^{f}_{h}(S_i) CDI h f ( S 0 ) ⊆ CDI h f ( S i ) i ∈ [ d + 1 ] i\in[d+1] i ∈ [ d + 1 ] ∅ ≠ CDI h f ( S 0 ) ⊆ ⋂ i ∈ [ d + 1 ] CDI h f ( S i ) \varnothing\ne\operatorname{CDI}^{f}_{h}(S_0)\subseteq\bigcap_{i\in[d+1]}\operatorname{CDI}^{f}_{h}(S_i) ∅ = CDI h f ( S 0 ) ⊆ ⋂ i ∈ [ d + 1 ] CDI h f ( S i )
⋂ S ′ ∈ N λ ↓ ( S ) CDI h f ( S ′ ) ≠ ∅ . \bigcap_{S'\in N_{\lambda}^{\downarrow}(S)}\operatorname{CDI}^{f}_{h}(S')\ne\varnothing. S ′ ∈ N λ ↓ ( S ) ⋂ CDI h f ( S ′ ) = ∅ . Furthermore, we can write:
⋂ S ′ ∈ N λ ↓ ( S ) CDI h f ( S ′ ) = ⋂ S ′ ∈ N λ ↓ ( S ) CH ( f ( M h ↓ ( S ′ ) ) ) = ⋂ S ′ ⊆ S s.t. ∣ S ′ ∣ = ∣ S ∣ − λ CH ( f ( M h ↓ ( S ′ ) ) ) . \begin{aligned}
\bigcap_{S'\in N_{\lambda}^{\downarrow}(S)}\operatorname{CDI}^{f}_{h}(S')
=
\bigcap_{S'\in N_{\lambda}^{\downarrow}(S)}\operatorname{CH}\left(f\left(M_h^{\downarrow}(S')\right)\right) \\
&=
\bigcap_{\substack{S'\subseteq S\\\text{s.t. }|S'|=|S|-\lambda}}\operatorname{CH}\left(f\left(M_h^{\downarrow}(S')\right)\right).
\end{aligned} S ′ ∈ N λ ↓ ( S ) ⋂ CDI h f ( S ′ ) = S ′ ∈ N λ ↓ ( S ) ⋂ CH ( f ( M h ↓ ( S ′ ) ) ) = S ′ ⊆ S s.t. ∣ S ′ ∣ = ∣ S ∣ − λ ⋂ CH ( f ( M h ↓ ( S ′ ) ) ) . Now, we use the definition 4.5, and set I = { f ( M h ↓ ( S ′ ) ) : S ′ ∈ N λ ↓ ( S ) } ⊆ 2 Y \mathcal{I}=\left\{f\left(M_h^{\downarrow}(S')\right):S'\in N_{\lambda}^{\downarrow}(S)\right\}\subseteq2^{\mathcal{Y}} I = { f ( M h ↓ ( S ′ ) ) : S ′ ∈ N λ ↓ ( S ) } ⊆ 2 Y A I = ⋂ T ∈ I CH ( T ) A_{\mathcal{I}}=\bigcap_{T\in\mathcal{I}}\operatorname{CH}(T) A I = ⋂ T ∈ I CH ( T ) A I = ⋂ S ′ ∈ N λ ↓ ( S ) CDI h f ( S ′ ) ≠ ∅ A_{\mathcal{I}}=\bigcap_{S'\in N_{\lambda}^{\downarrow}(S)}\operatorname{CDI}^{f}_{h}(S')\ne\varnothing A I = ⋂ S ′ ∈ N λ ↓ ( S ) CDI h f ( S ′ ) = ∅
[ ⋂ S ′ ∈ N λ ↓ ( S ) CDI h f ( S ′ ) ] ∩ Y ~ ≠ ∅ . \left[\bigcap_{S'\in N_{\lambda}^{\downarrow}(S)}\operatorname{CDI}^{f}_{h}(S')\right]\cap\widetilde{Y}\ne\varnothing. S ′ ∈ N λ ↓ ( S ) ⋂ CDI h f ( S ′ ) ∩ Y = ∅ . Theorem C.7. Proof of Theorem 2.6.
Proof. For ∣ Y ∣ = 1 |\mathcal{Y}|=1 ∣ Y ∣ = 1 1 1 1 n ~ \widetilde{n} n ( ε 0 , δ 0 ) (\varepsilon_0,\delta_0) ( ε 0 , δ 0 ) n ~ \widetilde{n} n h h h h ≤ 0 h\le0 h ≤ 0 f ( ∅ ) f(\varnothing) f ( ∅ ) S S S h ≥ 1 h\ge1 h ≥ 1 Theorem 4.9 gives ( ε 0 , δ 0 ) (\varepsilon_0,\delta_0) ( ε 0 , δ 0 ) ( 2 ε 0 , 2 δ 0 ) = ( ε , δ ) (2\varepsilon_0,2\delta_0)=(\varepsilon,\delta) ( 2 ε 0 , 2 δ 0 ) = ( ε , δ )
We next prove the utility. Let n = ∣ S ∣ n=|S| n = ∣ S ∣ λ = ⌈ K + 2 R + 1 ⌉ \lambda=\lceil K+2R+1\rceil λ = ⌈ K + 2 R + 1 ⌉ ∣ Z ∣ ≤ R |Z|\le R ∣ Z ∣ ≤ R h ≥ 1 h\ge1 h ≥ 1 K ≤ n − h < K + 2 R + 1 ≤ λ K\le n-h<K+2R+1\le\lambda K ≤ n − h < K + 2 R + 1 ≤ λ depth h f ( T , y ) \operatorname{depth}^{f}_{h}(T,y) depth h f ( T , y ) T ⊆ S T \subseteq S T ⊆ S f f f U ⊆ T U \subseteq T U ⊆ T ∣ U ∣ ≥ h |U| \ge h ∣ U ∣ ≥ h ∣ S ∖ U ∣ ≤ n − h ≤ λ |S \setminus U| \le n-h \le\lambda ∣ S ∖ U ∣ ≤ n − h ≤ λ ∣ T ∣ < h |T| < h ∣ T ∣ < h
If h ≤ 0 h \le0 h ≤ 0 n < K + R − Z + 1 ≤ K + 2 R + 1 ≤ λ n < K+R-Z+1 \le K+2R+1 \le\lambda n < K + R − Z + 1 ≤ K + 2 R + 1 ≤ λ ∅ ∈ N λ ⋆ ( S ) \varnothing\in N_{\lambda}^{\star}(S) ∅ ∈ N λ ⋆ ( S )
Finally, suppose h ≥ 1 h \ge1 h ≥ 1 Theorem 4.9 gives:
depth h f ( S , y ^ ) ≥ n − h d + 1 − Δ ≥ K d + 1 − Δ ≥ 1 , \operatorname{depth}_{h}^{f}(S,\hat{y}) \ge\frac{n-h}{d+1}-\Delta\ge\frac{K}{d+1}-\Delta\ge1, depth h f ( S , y ^ ) ≥ d + 1 n − h − Δ ≥ d + 1 K − Δ ≥ 1 , with probability at least 1 − β 0 1-\beta_0 1 − β 0 y ^ ∈ CDI h f ( S ) ⊆ CH ( f ( N λ ⋆ ( S ) ) ) \hat{y} \in\operatorname{CDI}_{h}^{f}(S) \subseteq\operatorname{CH}(f(N_{\lambda}^{\star}(S))) y ^ ∈ CDI h f ( S ) ⊆ CH ( f ( N λ ⋆ ( S )))
The inclusion follows from n − h ≤ λ n-h \le\lambda n − h ≤ λ h ≤ 0 h \le0 h ≤ 0 f ( ∅ ) f(\varnothing) f ( ∅ ) β 0 ≤ β \beta_0 \le\beta β 0 ≤ β
Lemma 4.7 bounds the extension size ∣ Y ~ ∣ |\widetilde{Y}| ∣ Y ∣ λ = O ( ( d + 1 ) ( Δ + 1 ) + R ) \lambda= O((d+1)(\Delta+1)+R) λ = O (( d + 1 ) ( Δ + 1 ) + R ) R = O ( log ( 1 / δ ) ε ) R = O\left(\frac{\log(1/\delta)}{\varepsilon}\right) R = O ( ε l o g ( 1/ δ ) )
Theorem C.8. Proof of Theorem 2.7 .
Proof. For ∣ Y ∣ = 1 |Y|=1 ∣ Y ∣ = 1
We first show the privacy guarantee. Let B \mathcal{B} B 1 1 1 n ~ \widetilde{n} n ( ε 0 , δ 0 ) (\varepsilon_0,\delta_0) ( ε 0 , δ 0 ) n ~ \widetilde{n} n h h h h ≤ 0 h \le0 h ≤ 0 f ( ∅ ) f(\varnothing) f ( ∅ ) S S S h ≥ 1 h \ge1 h ≥ 1 Theorem 4.10 gives ( ε 0 , 0 ) (\varepsilon_0,0) ( ε 0 , 0 ) B \mathcal{B} B ( 2 ε 0 , δ 0 ) = ( ε , δ 0 ) (2\varepsilon_0,\delta_0)=(\varepsilon,\delta_0) ( 2 ε 0 , δ 0 ) = ( ε , δ 0 )
The output of B \mathcal{B} B Y ~ \widetilde{Y} Y Y ~ \widetilde{Y} Y Y ⊆ Y ~ Y \subseteq\widetilde{Y} Y ⊆ Y f ( ∅ ) ∈ Y ~ f(\varnothing) \in\widetilde{Y} f ( ∅ ) ∈ Y S , S ′ S,S' S , S ′ y ∈ Y ~ y \in\widetilde{Y} y ∈ Y p S ( y ) = Pr [ B ( S ) = y ] p_S(y)=\Pr[\mathcal{B}(S)=y] p S ( y ) = Pr [ B ( S ) = y ] p S ( y ) ≤ e ε p S ′ ( y ) + δ 0 p_S(y) \le e^{\varepsilon}p_{S'}(y)+\delta_0 p S ( y ) ≤ e ε p S ′ ( y ) + δ 0
Let A \mathcal{A} A Pr [ A ( S ) = y ] = ( 1 − η ) p S ( y ) + η M \Pr[\mathcal{A}(S)=y]=(1-\eta)p_S(y)+\frac{\eta}{M} Pr [ A ( S ) = y ] = ( 1 − η ) p S ( y ) + M η
Pr [ A ( S ) = y ] − e ε Pr [ A ( S ′ ) = y ] = ( 1 − η ) ( p S ( y ) − e ε p S ′ ( y ) ) − η ( e ε − 1 ) M ≤ ( 1 − η ) δ 0 − η ( e ε − 1 ) M ≤ 0. \begin{aligned}
\Pr[\mathcal{A}(S)=y]-e^{\varepsilon}\Pr[\mathcal{A}(S')=y]
=(1-\eta)\left(p_S(y)-e^{\varepsilon}p_{S'}(y)\right)-\frac{\eta(e^{\varepsilon}-1)}{M} \\
&\le(1-\eta)\delta_0-\frac{\eta(e^{\varepsilon}-1)}{M}\le0.
\end{aligned} Pr [ A ( S ) = y ] − e ε Pr [ A ( S ′ ) = y ] = ( 1 − η ) ( p S ( y ) − e ε p S ′ ( y ) ) − M η ( e ε − 1 ) ≤ ( 1 − η ) δ 0 − M η ( e ε − 1 ) ≤ 0. The last inequality follows from δ 0 ≤ η ( e ε 0 − 1 ) / M \delta_0 \le\eta(e^{\varepsilon_0}-1)/M δ 0 ≤ η ( e ε 0 − 1 ) / M ε 0 ≤ ε \varepsilon_0 \le\varepsilon ε 0 ≤ ε
We next verify the oracle-query restriction. Let n = ∣ S ∣ n=|S| n = ∣ S ∣ λ = ⌈ K + 2 R + 1 ⌉ \lambda=\lceil K+2R+1\rceil λ = ⌈ K + 2 R + 1 ⌉ ∣ Z ∣ ≤ R |Z| \le R ∣ Z ∣ ≤ R h ≥ 1 h \ge1 h ≥ 1 K ≤ n − h < K + 2 R + 1 ≤ λ K \le n-h < K+2R+1 \le\lambda K ≤ n − h < K + 2 R + 1 ≤ λ depth h f ( T , y ) \operatorname{depth}_{h}^{f}(T,y) depth h f ( T , y ) T ⊆ S T \subseteq S T ⊆ S f f f U ⊆ T U \subseteq T U ⊆ T ∣ U ∣ ≥ h |U| \ge h ∣ U ∣ ≥ h ∣ S ∖ U ∣ ≤ n − h ≤ λ |S \setminus U| \le n-h \le\lambda ∣ S ∖ U ∣ ≤ n − h ≤ λ ∣ T ∣ < h |T| < h ∣ T ∣ < h
If h ≤ 0 h \le0 h ≤ 0 n < K + R − Z + 1 ≤ K + 2 R + 1 ≤ λ n < K+R-Z+1 \le K+2R+1 \le\lambda n < K + R − Z + 1 ≤ K + 2 R + 1 ≤ λ ∅ ∈ N λ ⋆ ( S ) \varnothing\in N_{\lambda}^{\star}(S) ∅ ∈ N λ ⋆ ( S ) h ≤ 0 h \le0 h ≤ 0 f ( ∅ ) f(\varnothing) f ( ∅ ) h ≥ 1 h \ge1 h ≥ 1 Theorem 4.10 gives
depth h f ( S , y ^ ) ≥ n − h d + 1 − Δ ≥ K d + 1 − Δ ≥ 1 \operatorname{depth}_{h}^{f}(S,\widehat{y}) \ge\frac{n-h}{d+1}-\Delta\ge\frac{K}{d+1}-\Delta\ge1 depth h f ( S , y ) ≥ d + 1 n − h − Δ ≥ d + 1 K − Δ ≥ 1 with probability at least 1 − β 0 1-\beta_0 1 − β 0 y ^ ∈ CDI h f ( S ) ⊆ CH ( f ( N λ ↓ ( S ) ) ) \widehat{y} \in\operatorname{CDI}_{h}^{f}(S) \subseteq\operatorname{CH}\left(f(N_{\lambda}^{\downarrow}(S))\right) y ∈ CDI h f ( S ) ⊆ CH ( f ( N λ ↓ ( S )) ) n − h ≤ λ n-h \le\lambda n − h ≤ λ η + ( 1 − η ) β 0 ≤ β \eta+(1-\eta)\beta_0 \le\beta η + ( 1 − η ) β 0 ≤ β
It remains to bound λ \lambda λ δ 0 = η ( e ε 0 − 1 ) / M \delta_0=\eta(e^{\varepsilon_0}-1)/M δ 0 = η ( e ε 0 − 1 ) / M
R = 1 ε 0 log ( 1 + M 2 n ) = 2 ε log ( 1 + M β ) . R=\frac{1}{\varepsilon_0}\log\left(1+\frac{M}{2n}\right)=\frac{2}{\varepsilon}\log\left(1+\frac{M}{\beta}\right). R = ε 0 1 log ( 1 + 2 n M ) = ε 2 log ( 1 + β M ) . Otherwise, δ 0 = 1 / 4 \delta_0=1/4 δ 0 = 1/4
R = 1 ε 0 log ( 2 e ε 0 − 1 ) ≤ 1 + log 2 ε 0 . R=\frac{1}{\varepsilon_0}\log(2e^{\varepsilon_0}-1)\le1+\frac{\log2}{\varepsilon_0}. R = ε 0 1 log ( 2 e ε 0 − 1 ) ≤ 1 + ε 0 log 2 . Consequently, R = O ( 1 + log ( M / β ) ε ) R=O\left(1+\frac{\log(M/\beta)}{\varepsilon}\right) R = O ( 1 + ε l o g ( M / β ) ) Δ \Delta Δ K K K λ = O ( d + d log ( M / β ) ε ) \lambda=O\left(d+\frac{d\log(M/\beta)}{\varepsilon}\right) λ = O ( d + ε d l o g ( M / β ) ) Lemma 4.8 gives M ≤ ∣ Y ∣ d 2 M\le|\mathcal{Y}|^{d^2} M ≤ ∣ Y ∣ d 2 λ = O ( d + d 3 log ( ∣ Y ∣ / β ) ε ) \lambda=O\left(d+\frac{d^3\log(|\mathcal{Y}|/\beta)}{\varepsilon}\right) λ = O ( d + ε d 3 l o g ( ∣ Y ∣/ β ) ) 0 < ε ≤ 1 0<\varepsilon\le1 0 < ε ≤ 1 d d d
Omitted proofs from section 5
Proof. Fix an input domain U \mathcal{U} U Y ⊆ R d \mathcal{Y}\subseteq\mathbb{R}^{d} Y ⊆ R d log ∗ ∣ Y ∣ ≤ L \log^*|\mathcal{Y}|\le L log ∗ ∣ Y ∣ ≤ L
We first prove the lower bound. Let N = n b l a c k - b o x ( α , β , ε , δ , d , L ) N=n_{\mathrm{black\text{-}box}}(\alpha,\beta,\varepsilon,\delta,d,L) N = n black - box ( α , β , ε , δ , d , L ) N = ∞ N=\infty N = ∞ A \mathcal{A} A Y \mathcal{Y} Y λ = ⌊ α N ⌋ \lambda=\lfloor\alpha N\rfloor λ = ⌊ α N ⌋
Given a discrete quasi-concave quality function Q : U ∗ × Y → R Q:\mathcal{U}^*\times\mathcal{Y}\to\mathbb{R} Q : U ∗ × Y → R 1 1 1
f Q ( T ) ∈ arg max y ∈ Y Q ( T , y ) , f_Q(T)\in\underset{y\in\mathcal{Y}}{\arg\max}\ Q(T,y), f Q ( T ) ∈ y ∈ Y arg max Q ( T , y ) , breaking ties according to a fixed public ordering of Y \mathcal{Y} Y A ( f Q , S ) \mathcal{A}(f_Q,S) A ( f Q , S ) CH ( Y ) \operatorname{CH}(\mathcal{Y}) CH ( Y ) Y \mathcal{Y} Y
For every fixed Q Q Q f Q f_Q f Q A \mathcal{A} A f Q ( T ) f_Q(T) f Q ( T ) Q ( T , y ) Q(T,y) Q ( T , y ) y ∈ Y y\in\mathcal{Y} y ∈ Y T T T N λ ↓ ( S ) N_{\lambda}^{\downarrow}(S) N λ ↓ ( S )
Suppose ∣ S ∣ ≥ N |S|\ge N ∣ S ∣ ≥ N T ∈ N λ ↓ ( S ) T\in N_{\lambda}^{\downarrow}(S) T ∈ N λ ↓ ( S )
Q ( S , f Q ( T ) ) ≥ Q ( T , f Q ( T ) ) − λ = max y ∈ Y Q ( T , y ) − λ ≥ max y ∈ Y Q ( S , y ) − 2 λ . \begin{aligned}
Q(S,f_Q(T)) &\ge Q(T,f_Q(T))-\lambda\\
&=\max_{y\in\mathcal{Y}} Q(T,y)-\lambda\\
&\ge\max_{y\in\mathcal{Y}} Q(S,y)-2\lambda.
\end{aligned} Q ( S , f Q ( T )) ≥ Q ( T , f Q ( T )) − λ = y ∈ Y max Q ( T , y ) − λ ≥ y ∈ Y max Q ( S , y ) − 2 λ . With probability at least 1 − β 1-\beta 1 − β y ^ ∈ CH ( f Q ( N λ X ( S ) ) ) \hat{y} \in\operatorname{CH}\left(f_Q\left(N_{\lambda}^{\mathcal{X}}(S)\right)\right) y ^ ∈ CH ( f Q ( N λ X ( S ) ) ) Remark G.1 ) gives
Q ( S , y ^ ) ≥ min T ∈ N λ X ( S ) Q ( S , f Q ( T ) ) ≥ max y ∈ Y Q ( S , y ) − 2 λ ≥ max y ∈ Y Q ( S , y ) − 2 α N . \begin{aligned}
\mathcal{Q}(S,\hat{y}) \ge\min_{T \in N_{\lambda}^{\mathcal{X}}(S)} \mathcal{Q}(S,f_Q(T)) \\
&\ge\max_{y \in\mathcal{Y}} \mathcal{Q}(S,y)-2\lambda\\
&\ge\max_{y \in\mathcal{Y}} \mathcal{Q}(S,y)-2\alpha N.
\end{aligned} Q ( S , y ^ ) ≥ T ∈ N λ X ( S ) min Q ( S , f Q ( T )) ≥ y ∈ Y max Q ( S , y ) − 2 λ ≥ y ∈ Y max Q ( S , y ) − 2 α N . Thus, one algorithm satisfies the QCO guarantee with accuracy parameter 2 α 2\alpha 2 α N N N
For the upper bound, let N = max { n Q C O ( α 2 ( d + 1 ) , β , ε / 2 , δ / 2 , d , L + 2 ) , ⌈ C α ( d + log ( 1 / δ ) ) ⌉ } N=\max\left\{n_{\mathrm{QCO}}\left(\frac{\alpha}{2(d+1)},\beta,\varepsilon/2,\delta/2,d,L+2\right),\left\lceil\frac{C}{\alpha}\left(d+\frac{\log(1/\delta)}{}\right)\right\rceil\right\} N = max { n QCO ( 2 ( d + 1 ) α , β , ε /2 , δ /2 , d , L + 2 ) , ⌈ α C ( d + l o g ( 1/ δ ) ) ⌉ } N = ∞ N=\infty N = ∞ n Q C O ( α 2 ( d + 1 ) , β , ε / 2 , δ / 2 , d , L + 2 ) n_{\mathrm{QCO}}\left(\frac{\alpha}{2(d+1)},\beta,\varepsilon/2,\delta/2,d,L+2\right) n QCO ( 2 ( d + 1 ) α , β , ε /2 , δ /2 , d , L + 2 ) depth h f \operatorname{depth}_{h}^{f} depth h f h h h Δ = α N / ( 2 ( d + 1 ) ) \Delta=\alpha N/(2(d+1)) Δ = α N / ( 2 ( d + 1 )) β \beta β C C C ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) ⌊ α N ⌋ \lfloor\alpha N\rfloor ⌊ α N ⌋ N N N
Omitted proofs from section 6
Lemma E.1. Proof of Lemma 6.3.
Proof. Using the definition, we can write:
depth h f ( S , y ) = min { ∣ S ′ ∣ : S ′ ⊆ S , y ∉ CDI h f ( S ∖ S ′ ) } = min { ∣ S ′ ∣ : S ′ ⊆ S , y ∉ CH ( ⋃ S ′ ′ ⊆ ( S ∖ S ′ ) ∣ S ′ ′ ∣ ≥ h f ( S ′ ′ ) ) } \begin{aligned}
\operatorname{depth}_{h}^{f}(S,y)=\min\left\{|S'|:S'\subseteq S,y\notin\operatorname{CDI}_{h}^{f}(S\setminus S')\right\} \\
&=\min\left\{|S'|:S'\subseteq S,y\notin\operatorname{CH}\left(\bigcup_{\substack{S''\subseteq(S\setminus S')\\ |S''|\geq h}}f(S'')\right)\right\}
\end{aligned} depth h f ( S , y ) = min { ∣ S ′ ∣ : S ′ ⊆ S , y ∈ / CDI h f ( S ∖ S ′ ) } = min ⎩ ⎨ ⎧ ∣ S ′ ∣ : S ′ ⊆ S , y ∈ / CH S ′′ ⊆ ( S ∖ S ′ ) ∣ S ′′ ∣ ≥ h ⋃ f ( S ′′ ) ⎭ ⎬ ⎫ In the last term, for any S ′ ′ ⊆ ( S ∖ S ′ ) S''\subseteq(S\setminus S') S ′′ ⊆ ( S ∖ S ′ ) CH ( S ′ ′ ) ⊆ CH ( S ∖ S ′ ) \operatorname{CH}(S'')\subseteq\operatorname{CH}(S\setminus S') CH ( S ′′ ) ⊆ CH ( S ∖ S ′ ) f f f f ( S ′ ′ ) ⊆ CH ( S ′ ′ ) f(S'')\subseteq\operatorname{CH}(S'') f ( S ′′ ) ⊆ CH ( S ′′ ) S ′ ′ S'' S ′′
⋃ S ′ ′ ⊆ ( S ∖ S ′ ) ∣ S ′ ′ ∣ ≥ h f ( S ′ ′ ) ⊆ CH ( S ∖ S ′ ) \bigcup_{\substack{S''\subseteq(S\setminus S')\\ |S''|\geq h}}f(S'')\subseteq\operatorname{CH}(S\setminus S') S ′′ ⊆ ( S ∖ S ′ ) ∣ S ′′ ∣ ≥ h ⋃ f ( S ′′ ) ⊆ CH ( S ∖ S ′ ) This also implies CH ( ⋃ S ′ ′ ⊆ ( S ∖ S ′ ) ∣ S ′ ′ ∣ ≥ h f ( S ′ ′ ) ) ⊆ CH ( S ∖ S ′ ) \operatorname{CH}\left(\bigcup_{\substack{S''\subseteq(S\setminus S')\\ |S''|\geq h}}f(S'')\right)\subseteq\operatorname{CH}(S\setminus S') CH ( ⋃ S ′′ ⊆ ( S ∖ S ′ ) ∣ S ′′ ∣ ≥ h f ( S ′′ ) ) ⊆ CH ( S ∖ S ′ )
depth h f ( S , y ) = min { ∣ S ′ ∣ : S ′ ⊆ S , y ∉ CH ( ⋃ S ′ ′ ⊆ ( S ∖ S ′ ) ∣ S ′ ′ ∣ ≥ h f ( S ′ ′ ) ) } ≤ min { ∣ S ′ ∣ : S ′ ⊆ S , y ∉ CH ( S ∖ S ′ ) } = T D ( S , y ) \begin{aligned}
\operatorname{depth}_{h}^{f}(S,y)=\min\left\{|S'|:S'\subseteq S,y\notin\operatorname{CH}\left(\bigcup_{\substack{S''\subseteq(S\setminus S')\\ |S''|\geq h}}f(S'')\right)\right\} \\
&\leq\min\left\{|S'|:S'\subseteq S,y\notin\operatorname{CH}(S\setminus S')\right\}=TD(S,y)
\end{aligned} depth h f ( S , y ) = min ⎩ ⎨ ⎧ ∣ S ′ ∣ : S ′ ⊆ S , y ∈ / CH S ′′ ⊆ ( S ∖ S ′ ) ∣ S ′′ ∣ ≥ h ⋃ f ( S ′′ ) ⎭ ⎬ ⎫ ≤ min { ∣ S ′ ∣ : S ′ ⊆ S , y ∈ / CH ( S ∖ S ′ ) } = T D ( S , y ) For the case where h = 1 h = 1 h = 1
CH ( ⋃ S ′ ′ ⊆ ( S ∖ S ′ ) ∣ S ′ ′ ∣ ≥ 1 f ( S ′ ′ ) ) ⊇ CH ( ⋃ S ′ ′ ∈ ( S ∖ S ′ ) f ( S ′ ′ ) ) = CH ( ⋃ S ′ ′ ∈ ( S ∖ S ′ ) S ′ ′ ) = CH ( S ∖ S ′ ) \operatorname{CH}\left(\bigcup_{\substack{S^{\prime\prime}\subseteq(S\setminus S^{\prime})\\ |S^{\prime\prime}|\ge1}} f(S^{\prime\prime})\right) \supseteq\operatorname{CH}\left(\bigcup_{S^{\prime\prime}\in(S\setminus S^{\prime})} f(S^{\prime\prime})\right)
\\
= \operatorname{CH}\left(\bigcup_{S^{\prime\prime}\in(S\setminus S^{\prime})} S^{\prime\prime}\right)
\\
= \operatorname{CH}(S\setminus S^{\prime}) CH S ′′ ⊆ ( S ∖ S ′ ) ∣ S ′′ ∣ ≥ 1 ⋃ f ( S ′′ ) ⊇ CH S ′′ ∈ ( S ∖ S ′ ) ⋃ f ( S ′′ ) = CH S ′′ ∈ ( S ∖ S ′ ) ⋃ S ′′ = CH ( S ∖ S ′ ) where the first inequality used the fact that the output of an “internal” function on a single element is that element itself.
Lemma E.2. Proof of Corollary 6.4.
Proof. Run Algorithm 1 with h = 1 h = 1 h = 1 Y \mathcal{Y} Y Y ~ \widetilde{\mathcal{Y}} Y Lemma 4.7 . The privacy guarantee follows from Theorem 4.9 . Since log ∗ ∣ Y ~ ∣ ≤ log ∗ ∣ Y ∣ + 2 \log^*|\widetilde{\mathcal{Y}}| \le\log^*|\mathcal{Y}| + 2 log ∗ ∣ Y ∣ ≤ log ∗ ∣ Y ∣ + 2
Furthermore, f c e n t e r f_{\mathrm{center}} f center Lemma 6.3 gives depth 1 f c e n t e r ( S , y ) = TD ( S , y ) \operatorname{depth}^{f_{\mathrm{center}}}_1(S,y) = \operatorname{TD}(S,y) depth 1 f center ( S , y ) = TD ( S , y ) 1 − β 1-\beta 1 − β
TD ( S , y ^ ) = depth 1 f c e n t e r ( S , y ^ ) ≥ max y ∈ Y ~ depth 1 f c e n t e r ( S , y ) − Δ = max y ∈ Y ~ TD ( S , y ) − Δ . \operatorname{TD}(S,\hat{y}) = \operatorname{depth}^{f_{\mathrm{center}}}_1(S,\hat{y})
\ge\max_{y\in\widetilde{\mathcal{Y}}}\operatorname{depth}^{f_{\mathrm{center}}}_1(S,y)-\Delta
= \max_{y\in\widetilde{\mathcal{Y}}}\operatorname{TD}(S,y)-\Delta. TD ( S , y ^ ) = depth 1 f center ( S , y ^ ) ≥ y ∈ Y max depth 1 f center ( S , y ) − Δ = y ∈ Y max TD ( S , y ) − Δ. It remains to show that the maximum Tukey depth over R d \mathbb{R}^d R d Y ~ \widetilde{\mathcal{Y}} Y t ≥ 1 t\ge1 t ≥ 1
{ y ∈ R d : TD ( S , y ) ≥ t } = ⋂ D ⊆ S ∣ D ∣ < t CH ( S ∖ D ) . \left\{y\in\mathbb{R}^d:\operatorname{TD}(S,y)\ge t\right\}
=
\bigcap_{\substack{D\subseteq S\\ |D|<t}}\operatorname{CH}(S\setminus D). { y ∈ R d : TD ( S , y ) ≥ t } = D ⊆ S ∣ D ∣ < t ⋂ CH ( S ∖ D ) . Each set in this intersection is the convex hull of a subset of Y \mathcal{Y} Y Y ~ \widetilde{\mathcal{Y}} Y { 0 , 1 , … , ∣ S ∣ } \{0,1,\ldots,|S|\} { 0 , 1 , … , ∣ S ∣ }
max y ∈ Y ~ TD ( S , y ) = max y ∈ R d TD ( S , y ) . \max_{y\in\widetilde{\mathcal{Y}}}\operatorname{TD}(S,y)
=
\max_{y\in\mathbb{R}^d}\operatorname{TD}(S,y). y ∈ Y max TD ( S , y ) = y ∈ R d max TD ( S , y ) . Finally, the center point theorem gives max y ∈ R d TD ( S , y ) ≥ ∣ S ∣ / ( d + 1 ) \max_{y\in\mathbb{R}^d}\operatorname{TD}(S,y)\ge|S|/(d+1) max y ∈ R d TD ( S , y ) ≥ ∣ S ∣/ ( d + 1 )
Corollary E.3. Proof of Corollary 6.8.
Proof. We treat each user’s dataset as a single element of the input domain Y ∗ \mathcal{Y}^* Y ∗ Theorem 2.6 . Moreover, Lemma 4.7 gives log ∗ ∣ Y ~ ∣ ≤ log ∗ ∣ Y ∣ + 2 \log^*|\widetilde{\mathcal{Y}}| \le\log^*|\mathcal{Y}| + 2 log ∗ ∣ Y ∣ ≤ log ∗ ∣ Y ∣ + 2 λ \lambda λ
We first verify that f c e n t e r f_{\mathrm{center}} f center T T T P = flat ( T ) P=\operatorname{flat}(T) P = flat ( T ) t t t
{ y ∈ R d : TD ( P , y ) ≥ t } = ⋂ D ⊆ P ∣ D ∣ < t CH ( P ∖ D ) . \{y\in\mathbb{R}^{d}:\operatorname{TD}(P,y)\ge t\}=\bigcap_{\substack{D\subseteq P\\ |D|<t}}\operatorname{CH}(P\setminus D). { y ∈ R d : TD ( P , y ) ≥ t } = D ⊆ P ∣ D ∣ < t ⋂ CH ( P ∖ D ) . Each convex hull on the right is the convex hull of a subset of Y \mathcal{Y} Y Y ~ \widetilde{\mathcal{Y}} Y P P P y ∗ ∈ Y ~ y^{*}\in\widetilde{\mathcal{Y}} y ∗ ∈ Y TD ( P , y ∗ ) = max y ∈ R d TD ( P , y ) \operatorname{TD}(P,y^{*})=\max_{y\in\mathbb{R}^{d}}\operatorname{TD}(P,y) TD ( P , y ∗ ) = max y ∈ R d TD ( P , y ) f c e n t e r f_{\mathrm{center}} f center
TD ( P , f c e n t e r ( T ) ) = max y ∈ Y ~ TD ( P , y ) = max y ∈ R d TD ( P , y ) ≥ ∣ P ∣ d + 1 . \operatorname{TD}(P,f_{\mathrm{center}}(T))=\max_{y\in\widetilde{\mathcal{Y}}}\operatorname{TD}(P,y)=\max_{y\in\mathbb{R}^{d}}\operatorname{TD}(P,y)\ge\frac{|P|}{d+1}. TD ( P , f center ( T )) = y ∈ Y max TD ( P , y ) = y ∈ R d max TD ( P , y ) ≥ d + 1 ∣ P ∣ . For P = ∅ P=\varnothing P = ∅
Assume now that n ≥ λ n\ge\lambda n ≥ λ Q ( S , y ) = TD ( flat ( S ) , y ) Q(S,y)=\operatorname{TD}(\operatorname{flat}(S),y) Q ( S , y ) = TD ( flat ( S ) , y ) Corollary 6.7 , applied with output domain Y ~ \widetilde{\mathcal{Y}} Y
TD ( flat ( S ) , y ^ ) ≥ min S ′ ∈ N λ † ( S ) TD ( flat ( S ) , f c e n t e r ( S ′ ) ) \operatorname{TD}(\operatorname{flat}(S),\hat{y})\ge\min_{S'\in\mathcal{N}_{\lambda}^{\dagger}(S)}\operatorname{TD}(\operatorname{flat}(S),f_{\mathrm{center}}(S')) TD ( flat ( S ) , y ^ ) ≥ S ′ ∈ N λ † ( S ) min TD ( flat ( S ) , f center ( S ′ )) with probability at least 1 − β 1-\beta 1 − β
Fix any S ′ ∈ N λ † ( S ) S'\in\mathcal{N}_{\lambda}^{\dagger}(S) S ′ ∈ N λ † ( S ) M ( S ∖ S ′ ) : = ∑ S i ∈ S ∖ S ′ m i M(S\setminus S'):=\sum_{S_i\in S\setminus S'}m_i M ( S ∖ S ′ ) := ∑ S i ∈ S ∖ S ′ m i S ′ S' S ′ λ \lambda λ M ( S ∖ S ′ ) ≤ ∑ j ∈ [ λ ] m i j M(S\setminus S')\le\sum_{j\in[\lambda]}m_{i_j} M ( S ∖ S ′ ) ≤ ∑ j ∈ [ λ ] m i j
Adding points cannot decrease the Tukey depth of a fixed point, and deleting M ( S ∖ S ′ ) M(S\setminus S') M ( S ∖ S ′ ) M ( S ∖ S ′ ) M(S\setminus S') M ( S ∖ S ′ )
TD ( flat ( S ) , f c e n t e r ( S ′ ) ) ≥ TD ( flat ( S ′ ) , f c e n t e r ( S ′ ) ) = max y ∈ R d TD ( flat ( S ′ ) , y ) ≥ max y ∈ R d TD ( flat ( S ) , y ) − M ( S ∖ S ′ ) ≥ max y ∈ R d TD ( flat ( S ) , y ) − ∑ j ∈ [ λ ] m i j . \begin{aligned}
\operatorname{TD}(\operatorname{flat}(S),f_{\mathrm{center}}(S'))&\ge\operatorname{TD}(\operatorname{flat}(S'),f_{\mathrm{center}}(S'))\\
&=\max_{y\in\mathbb{R}^{d}}\operatorname{TD}(\operatorname{flat}(S'),y)\\
&\ge\max_{y\in\mathbb{R}^{d}}\operatorname{TD}(\operatorname{flat}(S),y)-M(S\setminus S')\\
&\ge\max_{y\in\mathbb{R}^{d}}\operatorname{TD}(\operatorname{flat}(S),y)-\sum_{j\in[\lambda]}m_{i_j}.
\end{aligned} TD ( flat ( S ) , f center ( S ′ )) ≥ TD ( flat ( S ′ ) , f center ( S ′ )) = y ∈ R d max TD ( flat ( S ′ ) , y ) ≥ y ∈ R d max TD ( flat ( S ) , y ) − M ( S ∖ S ′ ) ≥ y ∈ R d max TD ( flat ( S ) , y ) − j ∈ [ λ ] ∑ m i j . Furthermore, the center point guarantee gives
TD ( flat ( S ) , f c e n t e r ( S ′ ) ) ≥ TD ( flat ( S ′ ) , f c e n t e r ( S ′ ) ) ≥ ∣ flat ( S ′ ) ∣ d + 1 = M − M ( S ∖ S ′ ) d + 1 ≥ M − ∑ j ∈ [ λ ] m i j d + 1 . \begin{aligned}
\operatorname{TD}(\operatorname{flat}(S),f_{\mathrm{center}}(S'))&\ge\operatorname{TD}(\operatorname{flat}(S'),f_{\mathrm{center}}(S'))\\
&\ge\frac{|\operatorname{flat}(S')|}{d+1}\\
&=\frac{M-M(S\setminus S')}{d+1}\\
&\ge\frac{M-\sum_{j\in[\lambda]}m_{i_j}}{d+1}.
\end{aligned} TD ( flat ( S ) , f center ( S ′ )) ≥ TD ( flat ( S ′ ) , f center ( S ′ )) ≥ d + 1 ∣ flat ( S ′ ) ∣ = d + 1 M − M ( S ∖ S ′ ) ≥ d + 1 M − ∑ j ∈ [ λ ] m i j . Both lower bounds hold for every S ′ ∈ N λ † ( S ) S'\in\mathcal{N}_{\lambda}^{\dagger}(S) S ′ ∈ N λ † ( S ) S ′ S' S ′
Corollary E.4. Proof of Corollary 6.9 .
Proof. Treat each user’s dataset S i ∈ X ∗ S_i \in\mathcal{X}^* S i ∈ X ∗ U = X ∗ \mathcal{U} = \mathcal{X}^* U = X ∗ Claim 6.5 with the black-box function f L f_{\mathcal{L}} f L
Since L ( S , ⋅ ) \mathcal{L}(S,\cdot) L ( S , ⋅ ) Claim 6.5 implies that, with probability at least 1 − β 1-\beta 1 − β
L ( S , y ^ ) ≤ max S ′ ∈ N λ ↓ ( S ) L ( S , f L ( S ′ ) ) . \mathcal{L}(S,\hat{y}) \le\max_{S' \in N^\downarrow_\lambda(S)} \mathcal{L}(S,f_{\mathcal{L}}(S')). L ( S , y ^ ) ≤ S ′ ∈ N λ ↓ ( S ) max L ( S , f L ( S ′ )) . Let y ∗ = f L ( S ) y^* = f_{\mathcal{L}}(S) y ∗ = f L ( S ) S ′ ∈ N λ ↓ ( S ) S' \in N^\downarrow_\lambda(S) S ′ ∈ N λ ↓ ( S ) f L ( S ′ ) f_{\mathcal{L}}(S') f L ( S ′ ) S ′ S' S ′
L ( S ′ , f L ( S ′ ) ) ≤ L ( S ′ , y ∗ ) . \mathcal{L}(S',f_{\mathcal{L}}(S')) \le\mathcal{L}(S',y^*). L ( S ′ , f L ( S ′ )) ≤ L ( S ′ , y ∗ ) . Consequently,
L ( S , f L ( S ′ ) ) = L ( S ′ , f L ( S ′ ) ) + ∑ S i ∈ S ∖ S ′ ϕ i ( S i , f L ( S ′ ) ) ≤ L ( S ′ , y ∗ ) + ∑ S i ∈ S ∖ S ′ ϕ i ( S i , f L ( S ′ ) ) = L ( S , y ∗ ) + ∑ S i ∈ S ∖ S ′ [ ϕ i ( S i , f L ( S ′ ) ) − ϕ i ( S i , y ∗ ) ] = min y ∈ Y L ( S , y ) + ∑ S i ∈ S ∖ S ′ [ ϕ i ( S i , f L ( S ′ ) ) − ϕ i ( S i , f L ( S ) ) ] . \begin{aligned}
\mathcal{L}(S,f_{\mathcal{L}}(S')) &= \mathcal{L}(S',f_{\mathcal{L}}(S')) + \sum_{S_i \in S\setminus S'} \phi_i(S_i,f_{\mathcal{L}}(S')) \\
&\le\mathcal{L}(S',y^*) + \sum_{S_i \in S\setminus S'} \phi_i(S_i,f_{\mathcal{L}}(S')) \\
&= \mathcal{L}(S,y^*) + \sum_{S_i \in S\setminus S'} \left[\phi_i(S_i,f_{\mathcal{L}}(S'))-\phi_i(S_i,y^*)\right] \\
&= \min_{y\in\mathcal{Y}} \mathcal{L}(S,y) + \sum_{S_i \in S\setminus S'} \left[\phi_i(S_i,f_{\mathcal{L}}(S'))-\phi_i(S_i,f_{\mathcal{L}}(S))\right].
\end{aligned} L ( S , f L ( S ′ )) = L ( S ′ , f L ( S ′ )) + S i ∈ S ∖ S ′ ∑ ϕ i ( S i , f L ( S ′ )) ≤ L ( S ′ , y ∗ ) + S i ∈ S ∖ S ′ ∑ ϕ i ( S i , f L ( S ′ )) = L ( S , y ∗ ) + S i ∈ S ∖ S ′ ∑ [ ϕ i ( S i , f L ( S ′ )) − ϕ i ( S i , y ∗ ) ] = y ∈ Y min L ( S , y ) + S i ∈ S ∖ S ′ ∑ [ ϕ i ( S i , f L ( S ′ )) − ϕ i ( S i , f L ( S )) ] . Taking the maximum over all S ′ ∈ N λ ↓ ( S ) S' \in N^\downarrow_\lambda(S) S ′ ∈ N λ ↓ ( S ) Theorem 2.6 .
Iterative log facts
Here, we collect several elementary facts about iterated logarithms that will be used to establish the utility bounds for our private quasi-concave optimizers. Throughout this section, all logarithms are to base 2.
Definition F.1 (Iterative floored logarithm). For N ≥ 0 N \ge0 N ≥ 0 log [ N ] ( ⋅ ) \log^{[N]}(\cdot) log [ N ] ( ⋅ ) N N N ⌊ log ( ⋅ ) ⌋ \lfloor\log(\cdot)\rfloor ⌊ log ( ⋅ )⌋ log [ 0 ] ( n ) = n \log^{[0]}(n)=n log [ 0 ] ( n ) = n
log [ N ] ( n ) = ⌊ log ⌊ log ⌊ … ⌊ log ( n ) ⌋ … ⌋ ⌋ ⌋ ⏟ N times . \log^{[N]}(n)=\underbrace{\lfloor\log\lfloor\log\lfloor\ldots\lfloor\log(n)\rfloor\ldots\rfloor\rfloor\rfloor}_{N\ \text{times}}. log [ N ] ( n ) = N times ⌊ log ⌊ log ⌊ … ⌊ log ( n )⌋ … ⌋⌋⌋ . Definition F.2 (Iterative floored log ∗ \log^* log ∗ n ≥ 1 n \ge1 n ≥ 1 log [ ∗ ] ( n ) \log^{[*]}(n) log [ ∗ ] ( n ) ⌊ log ( x ) ⌋ \lfloor\log(x)\rfloor ⌊ log ( x )⌋
log [ ∗ ] ( n ) = { 1 + log [ ∗ ] ( ⌊ log ( n ) ⌋ ) if n > 1 , 0 otherwise. \log^{[*]}(n)=
\begin{cases}
1+\log^{[*]}(\lfloor\log(n)\rfloor) & \text{if } n>1,\\
0 & \text{otherwise.}
\end{cases} log [ ∗ ] ( n ) = { 1 + log [ ∗ ] (⌊ log ( n )⌋) 0 if n > 1 , otherwise. Claim F.3. For every integer n ≥ 1 n \ge1 n ≥ 1 and every integer 0 ≤ N ≤ log ∗ ( n ) 0 \le N \le\log^*(n) 0 ≤ N ≤ log ∗ ( n ) we have
log ⌊ N ⌋ ( n ) ≤ log log … log ( n ) ⏟ N times \log^{\lfloor N\rfloor}(n) \le\underbrace{\log\log\ldots\log(n)}_{N\ \text{times}} log ⌊ N ⌋ ( n ) ≤ N times log log … log ( n ) Proof. The case N = 0 N = 0 N = 0 N ≤ log ∗ ( n ) N \le\log^*(n) N ≤ log ∗ ( n ) 1 1 1 0 0 0 N N N
For N = 1 N = 1 N = 1
log ⌊ 1 ⌋ ( n ) = ⌊ log ( n ) ⌋ . \log^{\lfloor1\rfloor}(n) = \lfloor\log(n)\rfloor. log ⌊ 1 ⌋ ( n ) = ⌊ log ( n )⌋ . Since ⌊ x ⌋ ≤ x \lfloor x\rfloor\le x ⌊ x ⌋ ≤ x x x x
log ⌊ 1 ⌋ ( n ) = ⌊ log ( n ) ⌋ ≤ log ( n ) . \log^{\lfloor1\rfloor}(n) = \lfloor\log(n)\rfloor\le\log(n). log ⌊ 1 ⌋ ( n ) = ⌊ log ( n )⌋ ≤ log ( n ) . Now, assume the claim holds for some integer k ≥ 1 k \ge1 k ≥ 1
log ⌊ k ⌋ ( n ) ≤ log log … log ( n ) ⏟ k times \log^{\lfloor k\rfloor}(n) \le\underbrace{\log\log\ldots\log(n)}_{k\ \text{times}} log ⌊ k ⌋ ( n ) ≤ k times log log … log ( n ) By definition,
log ⌊ k + 1 ⌋ ( n ) = ⌊ log ( log ⌊ k ⌋ ( n ) ) ⌋ . \log^{\lfloor k+1\rfloor}(n) = \left\lfloor\log\left(\log^{\lfloor k\rfloor}(n)\right)\right\rfloor. log ⌊ k + 1 ⌋ ( n ) = ⌊ log ( log ⌊ k ⌋ ( n ) ) ⌋ . Since both log ( ⋅ ) \log(\cdot) log ( ⋅ ) ⌊ ⋅ ⌋ \lfloor\cdot\rfloor ⌊ ⋅ ⌋
log ⌊ k + 1 ⌋ ( n ) = ⌊ log ( log ⌊ k ⌋ ( n ) ) ⌋ ≤ ⌊ log ( log log … log ( n ) ⏟ k times ) ⌋ ≤ log ( log log … log ( n ) ⏟ k times ) = log log … log ( n ) ⏟ k + 1 times . \begin{aligned}
\log^{\lfloor k+1\rfloor}(n)
&= \left\lfloor\log\left(\log^{\lfloor k\rfloor}(n)\right)\right\rfloor\\
&\le\left\lfloor\log\left(\underbrace{\log\log\ldots\log(n)}_{k\ \text{times}}\right)\right\rfloor\\
&\le\log\left(\underbrace{\log\log\ldots\log(n)}_{k\ \text{times}}\right) \\
&= \underbrace{\log\log\ldots\log(n)}_{k+1\ \text{times}}.
\end{aligned} log ⌊ k + 1 ⌋ ( n ) = ⌊ log ( log ⌊ k ⌋ ( n ) ) ⌋ ≤ log k times log log … log ( n ) ≤ log k times log log … log ( n ) = k + 1 times log log … log ( n ) . This completes the induction.
Claim F.4. For every integer n ≥ 1 n \ge1 n ≥ 1 we have
log ⌊ ∗ ⌋ ( n ) ≤ log ∗ ( n ) ≤ log ⌊ ∗ ⌋ ( n ) + 1. \log^{\lfloor*\rfloor}(n) \le\log^*(n) \le\log^{\lfloor*\rfloor}(n) + 1. log ⌊ ∗ ⌋ ( n ) ≤ log ∗ ( n ) ≤ log ⌊ ∗ ⌋ ( n ) + 1. Proof. For k ∈ N k \in\mathbb{N} k ∈ N
Tow ( k ) = { 1 if k = 0 , 2 Tow ( k − 1 ) if k ≥ 1. \operatorname{Tow}(k) =
\begin{cases}
1 & \text{if } k = 0,\\
2^{\operatorname{Tow}(k-1)} & \text{if } k \ge1.
\end{cases} Tow ( k ) = { 1 2 Tow ( k − 1 ) if k = 0 , if k ≥ 1. By definition,
log ∗ ( n ) = min { k : n ≤ Tow ( k ) } . \log^{*}(n) = \min\{k : n \le\operatorname{Tow}(k)\}. log ∗ ( n ) = min { k : n ≤ Tow ( k )} . Now, we claim that:
log ⌊ ∗ ⌋ ( n ) ≤ k ⟺ n < Tow ( k + 1 ) . \log^{\lfloor*\rfloor}(n) \le k \Longleftrightarrow n < \operatorname{Tow}(k+1). log ⌊ ∗ ⌋ ( n ) ≤ k ⟺ n < Tow ( k + 1 ) . We prove this by induction on k k k k = 0 k=0 k = 0 log ⌊ ∗ ⌋ ( n ) ≤ 0 \log^{\lfloor*\rfloor}(n) \le0 log ⌊ ∗ ⌋ ( n ) ≤ 0 n ≤ 1 n \le1 n ≤ 1 n n n n < 2 = Tow ( 1 ) n < 2 = \operatorname{Tow}(1) n < 2 = Tow ( 1 )
Now, suppose the statement holds for some k ≥ 0 k \ge0 k ≥ 0 n > 1 n > 1 n > 1
log ⌊ ∗ ⌋ ( n ) ≤ k + 1 ⟺ 1 + log ⌊ ∗ ⌋ ( ⌊ log ( n ) ⌋ ) ≤ k + 1 ⟺ log ⌊ ∗ ⌋ ( ⌊ log ( n ) ⌋ ) ≤ k ⟺ ⌊ log ( n ) ⌋ < Tow ( k + 1 ) ⟺ log ( n ) < Tow ( k + 1 ) ⟺ n < 2 Tow ( k + 1 ) ⟺ n < Tow ( k + 2 ) . \begin{aligned}
\log^{\lfloor*\rfloor}(n) &\le k+1 \Longleftrightarrow1+\log^{\lfloor*\rfloor}(\lfloor\log(n)\rfloor) \le k+1 \\
&\Longleftrightarrow\log^{\lfloor*\rfloor}(\lfloor\log(n)\rfloor) \le k \\
&\Longleftrightarrow\lfloor\log(n)\rfloor< \operatorname{Tow}(k+1) \\
&\Longleftrightarrow\log(n) < \operatorname{Tow}(k+1) \\
&\Longleftrightarrow n < 2^{\operatorname{Tow}(k+1)} \\
&\Longleftrightarrow n < \operatorname{Tow}(k+2).
\end{aligned} log ⌊ ∗ ⌋ ( n ) ≤ k + 1 ⟺ 1 + log ⌊ ∗ ⌋ (⌊ log ( n )⌋) ≤ k + 1 ⟺ log ⌊ ∗ ⌋ (⌊ log ( n )⌋) ≤ k ⟺ ⌊ log ( n )⌋ < Tow ( k + 1 ) ⟺ log ( n ) < Tow ( k + 1 ) ⟺ n < 2 Tow ( k + 1 ) ⟺ n < Tow ( k + 2 ) . Therefore,
log ⌊ ∗ ⌋ ( n ) = min { k : n < Tow ( k + 1 ) } . \log^{\lfloor*\rfloor}(n) = \min\{k : n < \operatorname{Tow}(k+1)\}. log ⌊ ∗ ⌋ ( n ) = min { k : n < Tow ( k + 1 )} . Comparing this with
log ∗ ( n ) = min { k : n ≤ Tow ( k ) } , \log^{*}(n) = \min\{k : n \le\operatorname{Tow}(k)\}, log ∗ ( n ) = min { k : n ≤ Tow ( k )} , we immediately get
log ⌊ ∗ ⌋ ( n ) ≤ log ∗ ( n ) ≤ log ⌊ ∗ ⌋ ( n ) + 1. \log^{\lfloor*\rfloor}(n) \le\log^{*}(n) \le\log^{\lfloor*\rfloor}(n)+1. log ⌊ ∗ ⌋ ( n ) ≤ log ∗ ( n ) ≤ log ⌊ ∗ ⌋ ( n ) + 1. Agnostic private QCO
In this section, we develop a one-dimensional private quasi-concave optimizer with an agnostic additive-error guarantee: it approximates the optimum without requiring its value or a lower bound as input. We then extend the construction to high dimensions using coordinatewise optimization.
Throughout this section, we sometimes evaluate quality functions on extensions of their original domains. The following remark describes a canonical extension that preserves quasi-concavity and sensitivity.
f ‾ ( x ) = { max ∅ ≠ A ⊆ Y x ∈ CH ( A ) min z ∈ A f ( z ) if x ∈ CH ( Y ) , m otherwise. \overline{f}(x)=
\begin{cases}
\max_{\substack{\varnothing\ne A\subseteq\mathcal{Y}\\x\in\operatorname{CH}(A)}}\ \min_{z\in A} f(z) & \text{if }x\in\operatorname{CH}(\mathcal{Y}),\\
m & \text{otherwise.}
\end{cases} f ( x ) = ⎩ ⎨ ⎧ max ∅ = A ⊆ Y x ∈ CH ( A ) min z ∈ A f ( z ) m if x ∈ CH ( Y ) , otherwise. Since Y \mathcal{Y} Y x ∈ CH ( Y ) x \in\operatorname{CH}(\mathcal{Y}) x ∈ CH ( Y ) A = { x } \mathcal{A} = \{x\} A = { x } f ˉ ( x ) = f ( x ) \bar{f}(x) = f(x) f ˉ ( x ) = f ( x ) x ∈ Y x \in\mathcal{Y} x ∈ Y t ∈ R t \in\mathbb{R} t ∈ R
{ x ∈ R d : f ˉ ( x ) ≥ t } = { CH ( { z ∈ Y : f ( z ) ≥ t } ) if t > m , R d if t ≤ m . \{x \in\mathbb{R}^{d}: \bar{f}(x) \geq t\} =
\begin{cases}
\operatorname{CH}(\{z \in\mathcal{Y}: f(z) \geq t\}) & \text{if } t > m,\\
\mathbb{R}^{d} & \text{if } t \leq m.
\end{cases} { x ∈ R d : f ˉ ( x ) ≥ t } = { CH ({ z ∈ Y : f ( z ) ≥ t }) R d if t > m , if t ≤ m . where CH ( ∅ ) = ∅ \operatorname{CH}(\varnothing) = \varnothing CH ( ∅ ) = ∅ f ˉ \bar{f} f ˉ f f f
For a quality function Q : U ∗ × Y → R Q : \mathcal{U}^{*} \times\mathcal{Y} \to\mathbb{R} Q : U ∗ × Y → R Q ( S , ⋅ ) Q(S, \cdot) Q ( S , ⋅ ) S S S
When running a solver on an enlarged domain, we map any final output outside the original CH ( Y ) \operatorname{CH}(\mathcal{Y}) CH ( Y ) Y \mathcal{Y} Y
With a slight abuse of notation, we use f f f
1-dimensional algorithm
We introduce Algorithm 5, a one-dimensional private QCO solver with an agnostic additive-error guarantee: it approximates the actual maximum without requiring its value or a lower bound as input. For a fixed sensitivity bound, the additive error is independent of the magnitude of the optimum. Our construction follows the core recursive approach of RecConcave [5 ] , whose stated guarantee is multiplicative relative to a supplied quality promise. We believe our formulation also admits a simpler implementation.
At a high level, the algorithm identifies the scale of an interval on which the quality is close to optimal. It formulates scale selection as another QCO problem over a domain of size O ( log ∣ Y ∣ ) O(\log|\mathcal{Y}|) O ( log ∣ Y ∣ )
For simplicity, we assume that ∣ Y ∣ |\mathcal{Y}| ∣ Y ∣ 2 2 2 1 1 1 Y = { 0 , 1 , ⋯ , R } \mathcal{Y} = \{0, 1, \cdots, R\} Y = { 0 , 1 , ⋯ , R } Y ~ = { 0 , 1 , ⋯ , R ~ } \widetilde{\mathcal{Y}} = \{0, 1, \cdots, \widetilde{R}\} Y = { 0 , 1 , ⋯ , R } R ~ + 1 \widetilde{R} + 1 R + 1 R + 1 R + 1 R + 1 Q Q Q y ~ \widetilde{y} y y ^ = min { y ~ , R } \widehat{y} = \min\{\widetilde{y}, R\} y = min { y , R } log ∗ ( R ~ + 1 ) = log ∗ ( R + 1 ) \log^{*}(\widetilde{R} + 1) = \log^{*}(R + 1) log ∗ ( R + 1 ) = log ∗ ( R + 1 )
All intervals below consist of integer points. For I = [ a , b ] I = [a,b] I = [ a , b ] J = b − a + 1 J = b-a+1 J = b − a + 1 I ⊗ 3 = [ a − J , b + J ] I^{\otimes3} = [a-J,b+J] I ⊗ 3 = [ a − J , b + J ] Y \mathcal{Y} Y max ∅ = − ∞ \max\varnothing= -\infty max ∅ = − ∞
Theorem G.2. Let C > 0 C > 0 C > 0 R ≥ 1 R \geq1 R ≥ 1 ε > 0 \varepsilon> 0 ε > 0 β , δ ∈ ( 0 , 1 ) \beta, \delta\in(0,1) β , δ ∈ ( 0 , 1 ) U \mathcal{U} U Y = { 0 , 1 , ⋯ , R } \mathcal{Y} = \{0,1,\cdots,R\} Y = { 0 , 1 , ⋯ , R } Q : U ∗ × Y → R Q : \mathcal{U}^{*} \times\mathcal{Y} \to\mathbb{R} Q : U ∗ × Y → R 1 1 1 ( ε , δ ) (\varepsilon,\delta) ( ε , δ )
Δ ≥ C 8 log ∗ ( R + 1 ) ( 1 + log ∗ ( R + 1 ) ε log ( 8 ( log ∗ ( R + 1 ) ) 2 β δ ) ) , \Delta\geq C 8^{\log^{*}(R+1)} \left(1 + \frac{\log^{*}(R+1)}{\varepsilon}\log\left(\frac{8(\log^{*}(R+1))^{2}}{\beta\delta}\right)\right), Δ ≥ C 8 l o g ∗ ( R + 1 ) ( 1 + ε log ∗ ( R + 1 ) log ( β δ 8 ( log ∗ ( R + 1 ) ) 2 ) ) , Algorithm 5 Private 1-dimensional Quasi-Concave Optimization
Input: Parameters ε ′ > 0 \varepsilon' > 0 ε ′ > 0 β ′ \beta' β ′ δ ′ ∈ ( 0 , 1 ) \delta' \in(0,1) δ ′ ∈ ( 0 , 1 ) U \mathcal{U} U Y = { 0 , 1 , … , R } \mathcal{Y} = \{0,1,\ldots,R\} Y = { 0 , 1 , … , R } Q : U ∗ × Y → R Q:\mathcal{U}^* \times\mathcal{Y} \to\mathbb{R} Q : U ∗ × Y → R H H H H = log ∗ ( ∣ Y ∣ ) H = \log^*(|\mathcal{Y}|) H = log ∗ ( ∣ Y ∣ ) Δ > 0 \Delta> 0 Δ > 0 S ∈ U ∗ S \in\mathcal{U}^* S ∈ U ∗
If ∣ Y ∣ = 1 |\mathcal{Y}| = 1 ∣ Y ∣ = 1
On the initial call only, set ε ← ε ′ / ( 2 H ) \varepsilon\leftarrow\varepsilon'/(2H) ε ← ε ′ / ( 2 H ) β ← β ′ / ( 2 H ) \beta\leftarrow\beta'/(2H) β ← β ′ / ( 2 H ) δ ← δ ′ / H \delta\leftarrow\delta'/H δ ← δ ′ / H
For j ∈ Y ′ = { 0 , 1 ⋯ , ⌊ log ( max ( Y ) ) ⌋ } j \in\mathcal{Y}' = \{0,1\cdots,\lfloor\log(\max(\mathcal{Y}))\rfloor\} j ∈ Y ′ = { 0 , 1 ⋯ , ⌊ log ( max ( Y ))⌋} I j = { [ a , b ] : a , b ∈ Y , b − a = 2 j − 1 } \mathcal{I}_j = \{[a,b]:a,b \in\mathcal{Y}, b-a = 2^j-1\} I j = {[ a , b ] : a , b ∈ Y , b − a = 2 j − 1 } ( I ⊗ 3 ) C = ∅ (I^{\otimes3})^C = \varnothing ( I ⊗ 3 ) C = ∅ + ∞ +\infty + ∞
Let r = max p ∈ Y Q ( S , p ) r = \max_{p\in\mathcal{Y}} Q(S,p) r = max p ∈ Y Q ( S , p )
q ( S , j ) = 1 2 max I ∈ I j { min { min p ∈ I Q ( S , p ) − ( r − Δ ) , r − max p ∈ ( I ⊗ 3 ) C Q ( S , p ) } } q(S,j) = \frac{1}{2}\max_{I\in\mathcal{I}_j}\left\{\min\left\{\min_{p\in I} Q(S,p) - (r-\Delta),\ r-\max_{p\in(I^{\otimes3})^C} Q(S,p)\right\}\right\} q ( S , j ) = 2 1 I ∈ I j max { min { p ∈ I min Q ( S , p ) − ( r − Δ ) , r − p ∈ ( I ⊗ 3 ) C max Q ( S , p ) } } Run the Algorithm 5 recursively with parameters ε , β , δ \varepsilon,\beta,\delta ε , β , δ U \mathcal{U} U Y ′ \mathcal{Y}' Y ′ q : U ∗ × Y ′ → R q:\mathcal{U}^* \times\mathcal{Y}' \to\mathbb{R} q : U ∗ × Y ′ → R H − 1 H-1 H − 1 Δ / 8 \Delta/8 Δ/8 S ∈ U ∗ S \in\mathcal{U}^* S ∈ U ∗ j ^ \hat{j} j ^
Let J = 2 j ^ J = 2^{\hat{j}} J = 2 j ^ K = max ( Y ) + 1 J K = \frac{\max(\mathcal{Y})+1}{J} K = J m a x ( Y ) + 1 C J = { [ 0 , J ) , [ J , 2 J ) , … , [ ( K − 1 ) J , K J ) } C_J = \{[0,J),[J,2J),\ldots,[(K-1)J,KJ)\} C J = {[ 0 , J ) , [ J , 2 J ) , … , [( K − 1 ) J , K J )}
Run the GAP-MAX algorithm (Theorem A.5) on C J C_J C J score ( S , I ) = max y ∈ I Q ( S , y ) \operatorname{score}(S,I) = \max_{y\in I} Q(S,y) score ( S , I ) = max y ∈ I Q ( S , y ) I ∈ C J I \in C_J I ∈ C J \hat{I} = \operatorname{GAP\mathchar`-MAX}(C_J,S,\operatorname{score},\Delta/40,\beta,\varepsilon,\delta,4) .
Run the Exponential Mechanism (Theorem A.2) on the integer endpoints { min I ^ , max I ^ } \{\min\hat{I},\max\hat{I}\} { min I ^ , max I ^ } I ^ \hat{I} I ^ score ( S , y ) = Q ( S , y ) \operatorname{score}(S,y) = Q(S,y) score ( S , y ) = Q ( S , y ) ε , β \varepsilon,\beta ε , β
and every dataset S ∈ U ∗ S \in\mathcal{U}^* S ∈ U ∗ y ^ ∈ Y \hat{y} \in\mathcal{Y} y ^ ∈ Y
Q ( S , y ^ ) ≥ max y ∈ Y Q ( S , y ) − Δ Q(S,\hat{y}) \ge\max_{y\in\mathcal{Y}} Q(S,y) - \Delta Q ( S , y ^ ) ≥ y ∈ Y max Q ( S , y ) − Δ with probability at least 1 − β 1-\beta 1 − β
Proof. By Remark G.1, padding preserves quasi-concavity, sensitivity 1, and the maximum quality. The final clamping cannot decrease the output’s quality and preserves privacy by post-processing. Since padding also preserves log ∗ ( R + 1 ) \log^*(R+1) log ∗ ( R + 1 ) ∣ Y ∣ = R + 1 |\mathcal{Y}| = R+1 ∣ Y ∣ = R + 1
Throughout the induction below, ε , β , δ \varepsilon,\beta,\delta ε , β , δ
First, we show that for every dataset S ∈ U ∗ S \in\mathcal{U}^* S ∈ U ∗ Y = { 0 , 1 , … , R } \mathcal{Y} = \{0,1,\ldots,R\} Y = { 0 , 1 , … , R } R ≥ 1 R \ge1 R ≥ 1 q : U ∗ × Y ′ → R q:\mathcal{U}^* \times\mathcal{Y}' \to\mathbb{R} q : U ∗ × Y ′ → R
q ( S , j ) = 1 2 max I ∈ I j { min { min p ∈ I Q ( S , p ) − ( r − Δ ) , r − max p ∈ ( I ⊗ 3 ) C Q ( S , p ) } } q(S,j) = \frac{1}{2}\max_{I\in\mathcal{I}_j}\left\{\min\left\{\min_{p\in I} Q(S,p) - (r-\Delta),\ r-\max_{p\in(I^{\otimes3})^C} Q(S,p)\right\}\right\} q ( S , j ) = 2 1 I ∈ I j max { min { p ∈ I min Q ( S , p ) − ( r − Δ ) , r − p ∈ ( I ⊗ 3 ) C max Q ( S , p ) } } is quasi-concave w.r.t. its second argument, where I j = { [ a , b ] : a , b ∈ Y , b − a = 2 j − 1 } \mathcal{I}_j = \{[a,b]:a,b \in\mathcal{Y},b-a=2^j-1\} I j = {[ a , b ] : a , b ∈ Y , b − a = 2 j − 1 } j ∈ Y ′ = { 0 , 1 ⋯ , ⌊ log ( max ( Y ) ) ⌋ } j \in\mathcal{Y}' = \{0,1\cdots,\lfloor\log(\max(\mathcal{Y}))\rfloor\} j ∈ Y ′ = { 0 , 1 ⋯ , ⌊ log ( max ( Y ))⌋} r = max p ∈ Y Q ( S , p ) r = \max_{p\in\mathcal{Y}} Q(S,p) r = max p ∈ Y Q ( S , p ) Δ > 0 \Delta> 0 Δ > 0
Let j 1 ≤ j 2 ≤ j 3 j_1 \le j_2 \le j_3 j 1 ≤ j 2 ≤ j 3 Y ′ \mathcal{Y}' Y ′ q ( S , j 2 ) ≥ min { q ( S , j 1 ) , q ( S , j 3 ) } = α q(S,j_2) \ge\min\{q(S,j_1),q(S,j_3)\} = \alpha q ( S , j 2 ) ≥ min { q ( S , j 1 ) , q ( S , j 3 )} = α j 2 = j 1 j_2 = j_1 j 2 = j 1 j 2 = j 3 j_2 = j_3 j 2 = j 3 j 1 < j 2 < j 3 j_1 < j_2 < j_3 j 1 < j 2 < j 3 I 1 ∈ I j 1 I_1 \in\mathcal{I}_{j_1} I 1 ∈ I j 1 I 3 ∈ I j 3 I_3 \in\mathcal{I}_{j_3} I 3 ∈ I j 3 q ( S , j 1 ) q(S,j_1) q ( S , j 1 ) q ( S , j 3 ) q(S,j_3) q ( S , j 3 ) Q Q Q L A = { y ∈ Y : Q ( S , y ) ≥ r − Δ + 2 α } L_A = \{y \in\mathcal{Y} : Q(S,y) \ge r - \Delta+ 2\alpha\} L A = { y ∈ Y : Q ( S , y ) ≥ r − Δ + 2 α } ( r − Δ + 2 α ) (r-\Delta+2\alpha) ( r − Δ + 2 α )
Note that q ( S , j ) ≥ α q(S,j) \ge\alpha q ( S , j ) ≥ α I ∈ I j I \in\mathcal{I}_j I ∈ I j min p ∈ I Q ( S , p ) ≥ 2 α + r − Δ \min_{p\in I} Q(S,p) \ge2\alpha+r-\Delta min p ∈ I Q ( S , p ) ≥ 2 α + r − Δ max p ∈ ( I ⊗ 3 ) C Q ( S , p ) ≤ r − 2 α \max_{p\in(I^{\otimes3})^C} Q(S,p) \le r-2\alpha max p ∈ ( I ⊗ 3 ) C Q ( S , p ) ≤ r − 2 α
So we get that I 1 , I 3 ⊆ L A I_1, I_3 \subseteq L_A I 1 , I 3 ⊆ L A ∣ L A ∣ ≥ 2 j 3 > 2 j 2 > 2 j 1 |L_A| \ge2^{j_3} > 2^{j_2} > 2^{j_1} ∣ L A ∣ ≥ 2 j 3 > 2 j 2 > 2 j 1 I 1 I_1 I 1 L A L_A L A I 2 I_2 I 2 2 j 2 2^{j_2} 2 j 2 I 2 I_2 I 2 2 j 2 2^{j_2} 2 j 2 I 1 ⊆ I 2 ⊆ L A I_1 \subseteq I_2 \subseteq L_A I 1 ⊆ I 2 ⊆ L A I 2 I_2 I 2
min p ∈ I 2 Q ( S , p ) ≥ 2 α + r − Δ . (1) \min_{p\in I_2} Q(S,p) \ge2\alpha+r-\Delta. \tag*{(1)} p ∈ I 2 min Q ( S , p ) ≥ 2 α + r − Δ. (1) We know that max p ∈ ( I 1 ⊗ 3 ) C Q ( S , p ) ≤ r − 2 α \max_{p\in(I_1^{\otimes3})^C} Q(S,p) \le r-2\alpha max p ∈ ( I 1 ⊗ 3 ) C Q ( S , p ) ≤ r − 2 α I 1 ⊆ I 2 I_1 \subseteq I_2 I 1 ⊆ I 2 I 1 ⊗ 3 ⊆ I 2 ⊗ 3 I_1^{\otimes3} \subseteq I_2^{\otimes3} I 1 ⊗ 3 ⊆ I 2 ⊗ 3 ( I 2 ⊗ 3 ) C ⊆ ( I 1 ⊗ 3 ) C (I_2^{\otimes3})^C \subseteq(I_1^{\otimes3})^C ( I 2 ⊗ 3 ) C ⊆ ( I 1 ⊗ 3 ) C
max p ∈ ( I 2 ⊗ 3 ) C Q ( S , p ) ≤ max p ∈ ( I 1 ⊗ 3 ) C Q ( S , p ) ≤ r − 2 α (2) \max_{p\in(I_2^{\otimes3})^C} Q(S,p) \le\max_{p\in(I_1^{\otimes3})^C} Q(S,p) \le r-2\alpha \tag*{(2)} p ∈ ( I 2 ⊗ 3 ) C max Q ( S , p ) ≤ p ∈ ( I 1 ⊗ 3 ) C max Q ( S , p ) ≤ r − 2 α (2) Putting (G.1) and (G.2) together, concludes the result q ( S , j 2 ) ≥ α q(S,j_2) \ge\alpha q ( S , j 2 ) ≥ α
Also, note that the q q q Q Q Q r = max y ∈ Y Q ( S , y ) r = \max_{y\in\mathcal{Y}} Q(S,y) r = max y ∈ Y Q ( S , y ) 1 / 2 1/2 1/2 S S S q q q
At recursive height 0 ≤ h ≤ H = log ∗ ( R + 1 ) 0 \le h \le H = \log^*(R+1) 0 ≤ h ≤ H = log ∗ ( R + 1 ) Y h \mathcal{Y}_h Y h q h q_h q h Δ h > 0 \Delta_h > 0 Δ h > 0 r h = max y ∈ Y h q h ( S , y ) r_h = \max_{y\in\mathcal{Y}_h} q_h(S,y) r h = max y ∈ Y h q h ( S , y ) y h ∈ Y h y_h \in\mathcal{Y}_h y h ∈ Y h
First, note that ∣ Y h ∣ = log [ H − h ] ( R + 1 ) = Tow ( h ) |\mathcal{Y}_h| = \log^{[H-h]}(R+1) = \operatorname{Tow}(h) ∣ Y h ∣ = log [ H − h ] ( R + 1 ) = Tow ( h ) Definition F.1 ) where;
Tow ( h ) = { 1 if h = 0 2 Tow ( h − 1 ) if h ≥ 1. \operatorname{Tow}(h) =
\begin{cases}
1 & \text{if } h=0 \\
2^{\operatorname{Tow}(h-1)} & \text{if } h\ge1.
\end{cases} Tow ( h ) = { 1 2 Tow ( h − 1 ) if h = 0 if h ≥ 1. Indeed, ∣ Y h − 1 ∣ = ⌊ log ( ∣ Y h ∣ − 1 ) ⌋ + 1 = log ( ∣ Y h ∣ ) = Tow ( h − 1 ) |\mathcal{Y}_{h-1}| = \lfloor\log(|\mathcal{Y}_h|-1)\rfloor+ 1 = \log(|\mathcal{Y}_h|) = \operatorname{Tow}(h-1) ∣ Y h − 1 ∣ = ⌊ log ( ∣ Y h ∣ − 1 )⌋ + 1 = log ( ∣ Y h ∣ ) = Tow ( h − 1 ) h ≥ 1 h \ge1 h ≥ 1 ∣ Y h ∣ |\mathcal{Y}_h| ∣ Y h ∣
Also, by definition, it holds that Δ h = Δ 8 H − h \Delta_h = \frac{\Delta}{8^{H-h}} Δ h = 8 H − h Δ
At recursive height h = 0 h=0 h = 0 ∣ Y 0 ∣ = log [ H ] ( R + 1 ) = Tow ( 0 ) = 1 |\mathcal{Y}_0| = \log^{[H]}(R+1) = \operatorname{Tow}(0) = 1 ∣ Y 0 ∣ = log [ H ] ( R + 1 ) = Tow ( 0 ) = 1 y 0 ∈ Y 0 = { 0 } y_0 \in\mathcal{Y}_0 = \{0\} y 0 ∈ Y 0 = { 0 } q 0 ( S , y 0 ) > max y ∈ Y 0 q 0 ( S , y ) − Δ 0 = q 0 ( S , y 0 ) − Δ 0 q_0(S,y_0) > \max_{y\in\mathcal{Y}_0} q_0(S,y) - \Delta_0 = q_0(S,y_0) - \Delta_0 q 0 ( S , y 0 ) > max y ∈ Y 0 q 0 ( S , y ) − Δ 0 = q 0 ( S , y 0 ) − Δ 0 Δ 0 = 8 − H Δ \Delta_0 = 8^{-H}\Delta Δ 0 = 8 − H Δ
By induction assumption, at the recursive height h > 0 h>0 h > 0 y h − 1 ∈ Y h − 1 = { 0 , 1 , ⋯ , ⌊ log ( max ( Y h ) ) ⌋ } y_{h-1} \in\mathcal{Y}_{h-1} = \{0,1,\cdots,\lfloor\log(\max(\mathcal{Y}_h))\rfloor\} y h − 1 ∈ Y h − 1 = { 0 , 1 , ⋯ , ⌊ log ( max ( Y h ))⌋}
q h − 1 ( S , y h − 1 ) ≥ max j ∈ Y h − 1 q h − 1 ( S , j ) − Δ h − 1 q_{h-1}(S,y_{h-1}) \ge\max_{j\in\mathcal{Y}_{h-1}} q_{h-1}(S,j) - \Delta_{h-1} q h − 1 ( S , y h − 1 ) ≥ j ∈ Y h − 1 max q h − 1 ( S , j ) − Δ h − 1 with probability at least 1 − 2 ( h − 1 ) β 1 - 2(h-1)\beta 1 − 2 ( h − 1 ) β
This means, there exists an interval I h ⊆ Y h I_h \subseteq\mathcal{Y}_h I h ⊆ Y h 2 y h − 1 2^{y_{h-1}} 2 y h − 1
1 2 min { min p ∈ I h q h ( S , p ) − ( r h − Δ h ) , r h − max p ∈ ( I h ⊗ 3 ) C q h ( S , p ) } ≥ max j ∈ Y h − 1 q h − 1 ( S , j ) − Δ h − 1 (3) \frac{1}{2}\min\left\{\min_{p\in I_h}q_h(S,p)-(r_h-\Delta_h),\ r_h-\max_{p\in(I_h^{\otimes3})^C}q_h(S,p)\right\}\geq\max_{j\in\mathcal{Y}_{h-1}}q_{h-1}(S,j)-\Delta_{h-1} \tag*{(3)} 2 1 min { p ∈ I h min q h ( S , p ) − ( r h − Δ h ) , r h − p ∈ ( I h ⊗ 3 ) C max q h ( S , p ) } ≥ j ∈ Y h − 1 max q h − 1 ( S , j ) − Δ h − 1 (3) Consider the level set L r h − Δ h 2 = { y ∈ Y h : q h ( S , y ) ≥ r h − Δ h 2 } L_{r_h-\frac{\Delta_h}{2}}=\left\{y\in\mathcal{Y}_h:q_h(S,y)\geq r_h-\frac{\Delta_h}{2}\right\} L r h − 2 Δ h = { y ∈ Y h : q h ( S , y ) ≥ r h − 2 Δ h } q h q_h q h I h ∗ I_h^* I h ∗ T = ∣ L r h − Δ h 2 ∣ T=\left|L_{r_h-\frac{\Delta_h}{2}}\right| T = L r h − 2 Δ h min p ∈ I h ∗ q h ( S , p ) ≥ r h − Δ h 2 \min_{p\in I_h^*}q_h(S,p)\geq r_h-\frac{\Delta_h}{2} min p ∈ I h ∗ q h ( S , p ) ≥ r h − 2 Δ h max p ∈ ( I h ∗ ) C q h ( S , p ) < r h − Δ h 2 \max_{p\in(I_h^*)^C}q_h(S,p)<r_h-\frac{\Delta_h}{2} max p ∈ ( I h ∗ ) C q h ( S , p ) < r h − 2 Δ h t = min { ⌊ log ( T ) ⌋ , ⌊ log ( max ( Y h ) ) ⌋ } t=\min\{\lfloor\log(T)\rfloor,\lfloor\log(\max(\mathcal{Y}_h))\rfloor\} t = min {⌊ log ( T )⌋ , ⌊ log ( max ( Y h ))⌋}
Then t ∈ Y h − 1 t\in\mathcal{Y}_{h-1} t ∈ Y h − 1 2 t ≤ T ≤ 2 t + 1 2^t\leq T\leq2^{t+1} 2 t ≤ T ≤ 2 t + 1 I h ∗ = Y h I_h^*=\mathcal{Y}_h I h ∗ = Y h 2 t = ∣ Y h ∣ / 2 2^t=|\mathcal{Y}_h|/2 2 t = ∣ Y h ∣/2 J h ∗ ⊆ I h ∗ J_h^*\subseteq I_h^* J h ∗ ⊆ I h ∗ 2 t 2^t 2 t I h ∗ ⊆ ( J h ∗ ) ⊗ 3 I_h^*\subseteq(J_h^*)^{\otimes3} I h ∗ ⊆ ( J h ∗ ) ⊗ 3 I h ∗ I_h^* I h ∗ T − 2 t ≤ 2 t T-2^t\leq2^t T − 2 t ≤ 2 t min p ∈ J h ∗ q h ( S , p ) ≥ r h − Δ h 2 \min_{p\in J_h^*}q_h(S,p)\geq r_h-\frac{\Delta_h}{2} min p ∈ J h ∗ q h ( S , p ) ≥ r h − 2 Δ h max p ∈ ( ( J h ∗ ) ⊗ 3 ) C q h ( S , p ) < r h − Δ h 2 \max_{p\in((J_h^*)^{\otimes3})^C}q_h(S,p)<r_h-\frac{\Delta_h}{2} max p ∈ (( J h ∗ ) ⊗ 3 ) C q h ( S , p ) < r h − 2 Δ h J h ∗ J_h^* J h ∗
max j ∈ Y h − 1 q h − 1 ( S , j ) ≥ q h − 1 ( S , t ) ≥ 1 2 min { min p ∈ J h ∗ q h ( S , p ) − ( r h − Δ h ) , r h − max p ∈ ( ( J h ∗ ) ⊗ 3 ) C q h ( S , p ) } ≥ 1 2 min { Δ h 2 , Δ h 2 } = Δ h 4 \begin{aligned}
\max_{j\in\mathcal{Y}_{h-1}}q_{h-1}(S,j)\geq q_{h-1}(S,t) \\
&\geq\frac{1}{2}\min\left\{\min_{p\in J_h^*}q_h(S,p)-(r_h-\Delta_h),\ r_h-\max_{p\in((J_h^*)^{\otimes3})^C}q_h(S,p)\right\} \\
&\geq\frac{1}{2}\min\left\{\frac{\Delta_h}{2},\frac{\Delta_h}{2}\right\}=\frac{\Delta_h}{4}
\end{aligned} j ∈ Y h − 1 max q h − 1 ( S , j ) ≥ q h − 1 ( S , t ) ≥ 2 1 min { p ∈ J h ∗ min q h ( S , p ) − ( r h − Δ h ) , r h − p ∈ (( J h ∗ ) ⊗ 3 ) C max q h ( S , p ) } ≥ 2 1 min { 2 Δ h , 2 Δ h } = 4 Δ h Putting together with (G.3), we get that:
1 2 min { min p ∈ I h q h ( S , p ) − ( r h − Δ h ) , r h − max p ∈ ( I h ⊗ 3 ) C q h ( S , p ) } ≥ Δ h 4 − Δ h − 1 = Δ h 8 (4) \frac{1}{2}\min\left\{\min_{p\in I_h}q_h(S,p)-(r_h-\Delta_h),\ r_h-\max_{p\in(I_h^{\otimes3})^C}q_h(S,p)\right\}\geq\frac{\Delta_h}{4}-\Delta_{h-1}=\frac{\Delta_h}{8} \tag*{(4)} 2 1 min { p ∈ I h min q h ( S , p ) − ( r h − Δ h ) , r h − p ∈ ( I h ⊗ 3 ) C max q h ( S , p ) } ≥ 4 Δ h − Δ h − 1 = 8 Δ h (4) with probability at least 1 − 2 ( h − 1 ) β 1-2(h-1)\beta 1 − 2 ( h − 1 ) β
This implies min p ∈ I h q h ( S , p ) ≥ r h − 3 Δ h 4 \min_{p\in I_h}q_h(S,p)\geq r_h-\frac{3\Delta_h}{4} min p ∈ I h q h ( S , p ) ≥ r h − 4 3 Δ h r h − Δ h 4 ≥ max p ∈ ( I h ⊗ 3 ) C q h ( S , p ) r_h-\frac{\Delta_h}{4}\geq\max_{p\in(I_h^{\otimes3})^C}q_h(S,p) r h − 4 Δ h ≥ max p ∈ ( I h ⊗ 3 ) C q h ( S , p )
Let C J C_J C J I ∈ C J I\in C_J I ∈ C J score ( S , I ) = max i ∈ I q h ( S , i ) \operatorname{score}(S,I)=\max_{i\in I}q_h(S,i) score ( S , I ) = max i ∈ I q h ( S , i )
∣ { I ∈ C J : score ( S , I ) ≥ sup I ∈ C J score ( S , I ) − 5 ( Δ h 40 ) } ∣ = ∣ { I ∈ C J : score ( S , I ) ≥ r h − Δ h 8 } ∣ ≤ 4 \begin{aligned}
\left|\left\{I\in C_J:\operatorname{score}(S,I)\geq\sup_{I\in C_J}\operatorname{score}(S,I)-5\left(\frac{\Delta_h}{40}\right)\right\}\right| \\
&=\left|\left\{I\in C_J:\operatorname{score}(S,I)\geq r_h-\frac{\Delta_h}{8}\right\}\right|\leq4
\end{aligned} { I ∈ C J : score ( S , I ) ≥ I ∈ C J sup score ( S , I ) − 5 ( 40 Δ h ) } = { I ∈ C J : score ( S , I ) ≥ r h − 8 Δ h } ≤ 4 This is because ( I h ∗ ) ⊗ 3 (I_h^*)^{\otimes3} ( I h ∗ ) ⊗ 3 C J C_J C J ( I h ∗ ) ⊗ 3 (I_h^*)^{\otimes3} ( I h ∗ ) ⊗ 3 r h − Δ h 4 r_h-\frac{\Delta_h}{4} r h − 4 Δ h Theorem A.5 , we can say the output I ^ = GAP-MAX ( C J , S , score , Δ h 40 , β , ε , δ , 4 ) \hat{I} = \operatorname{GAP\text{-}MAX}(C_J,S,\operatorname{score},\frac{\Delta_h}{40},\beta,\varepsilon,\delta,4) I ^ = GAP - MAX ( C J , S , score , 40 Δ h , β , ε , δ , 4 ) score ( S , I ^ ) ≥ r h − Δ h 40 \operatorname{score}(S,\hat{I}) \ge r_h-\frac{\Delta_h}{40} score ( S , I ^ ) ≥ r h − 40 Δ h 1 − β 1-\beta 1 − β Δ h ≥ 40 C 0 ( 1 + log ( 4 / ( δ β ) ) ε ) \Delta_h \ge40C_0\left(1+\frac{\log(4/(\delta\beta))}{\varepsilon}\right) Δ h ≥ 40 C 0 ( 1 + ε l o g ( 4/ ( δ β )) ) C 0 ≥ 1 C_0 \ge1 C 0 ≥ 1
Let the endpoints of I ^ \hat{I} I ^ { I ^ s , I ^ e } = { min I ^ , max I ^ } \{\hat{I}_s,\hat{I}_e\}=\{\min\hat{I},\max\hat{I}\} { I ^ s , I ^ e } = { min I ^ , max I ^ } r h − 3 Δ h 4 r_h-\frac{3\Delta_h}{4} r h − 4 3 Δ h i ∗ ∈ arg max i ∈ I ^ q h ( S , i ) i^* \in\mathop{\arg\max}_{i\in\hat{I}} q_h(S,i) i ∗ ∈ arg max i ∈ I ^ q h ( S , i ) q h ( S , i ∗ ) ≥ r h − Δ h 40 q_h(S,i^*) \ge r_h-\frac{\Delta_h}{40} q h ( S , i ∗ ) ≥ r h − 40 Δ h
If I ^ ∩ I h ≠ ∅ \hat{I}\cap I_h\ne\varnothing I ^ ∩ I h = ∅ J J J I ^ \hat{I} I ^ I h I_h I h r h − 3 Δ h 4 r_h-\frac{3\Delta_h}{4} r h − 4 3 Δ h
Otherwise, suppose that I ^ \hat{I} I ^ I h I_h I h a = min I h a=\min I_h a = min I h i ∗ ≤ I ^ e < a i^*\le\hat{I}_e<a i ∗ ≤ I ^ e < a q h q_h q h
q h ( S , I ^ e ) ≥ min { q h ( S , i ∗ ) , q h ( S , a ) } ≥ r h − 3 Δ h 4 . (5) q_h(S,\hat{I}_e)\ge\min\{q_h(S,i^*),q_h(S,a)\}\ge r_h-\frac{3\Delta_h}{4}. \tag*{(5)} q h ( S , I ^ e ) ≥ min { q h ( S , i ∗ ) , q h ( S , a )} ≥ r h − 4 3 Δ h . (5) The case where I ^ \hat{I} I ^ I h I_h I h I ^ s \hat{I}_s I ^ s max I h \max I_h max I h J = 1 J=1 J = 1
After running the Exponential Mechanism (Theorem A.2 ) on { I ^ s , I ^ e } \{\hat{I}_s,\hat{I}_e\} { I ^ s , I ^ e } q h q_h q h ε , β \varepsilon,\beta ε , β y ^ \hat{y} y ^
q h ( S , y ^ ) ≥ max y ∈ { I ^ s , I ^ e } q h ( S , y ) − 2 log ( 2 / β ) ε ≥ r h − 3 Δ h 4 − 2 log ( 2 / β ) ε ≥ r h − Δ h q_h(S,\hat{y})\ge\max_{y\in\{\hat{I}_s,\hat{I}_e\}}q_h(S,y)-\frac{2\log(2/\beta)}{\varepsilon}\ge r_h-\frac{3\Delta_h}{4}-\frac{2\log(2/\beta)}{\varepsilon}\ge r_h-\Delta_h q h ( S , y ^ ) ≥ y ∈ { I ^ s , I ^ e } max q h ( S , y ) − ε 2 log ( 2/ β ) ≥ r h − 4 3 Δ h − ε 2 log ( 2/ β ) ≥ r h − Δ h with probability at least 1 − 2 h β 1-2h\beta 1 − 2 h β Δ h ≥ 8 log ( 2 / β ) / ε \Delta_h\ge8\log(2/\beta)/\varepsilon Δ h ≥ 8 log ( 2/ β ) / ε β \beta β
Thus, at recursive height H = log ∗ ( R + 1 ) H=\log^*(R+1) H = log ∗ ( R + 1 ) y ^ \hat{y} y ^
q H ( S , y ^ ) = Q ( S , y ^ ) ≥ r H − Δ H = max y ∈ Y Q ( S , y ) − Δ H = max y ∈ Y Q ( S , y ) − Δ q_H(S,\hat{y})=Q(S,\hat{y})\ge r_H-\Delta_H=\max_{y\in\mathcal{Y}}Q(S,y)-\Delta_H=\max_{y\in\mathcal{Y}}Q(S,y)-\Delta q H ( S , y ^ ) = Q ( S , y ^ ) ≥ r H − Δ H = y ∈ Y max Q ( S , y ) − Δ H = y ∈ Y max Q ( S , y ) − Δ with probability at least 1 − 2 H β 1-2H\beta 1 − 2 H β
We now, prove the privacy of the algorithm. For every fixed output of the preceding private calls, the interval scores and endpoint scores have sensitivity 1. At each recursion, the algorithm invokes GAP-MAX (Theorem A.5 ) which is ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) Theorem A.2 ) which is ( ε , 0 ) (\varepsilon,0) ( ε , 0 ) ( 2 ε , δ ) (2\varepsilon,\delta) ( 2 ε , δ )
Now, we use (basic) composition over all the recursive calls of the algorithm. There are exactly H = log ∗ ( R + 1 ) H=\log^*(R+1) H = log ∗ ( R + 1 ) ( 2 H ε , H δ ) (2H\varepsilon,H\delta) ( 2 H ε , H δ )
At each nontrivial recursion call of the algorithm, it is sufficient that Δ h = Δ 8 H − h ≥ Δ 8 H ≥ 40 C 0 ( 1 + log ( 4 / ( δ β ) ) ε ) \Delta_h=\frac{\Delta}{8^{H-h}}\ge\frac{\Delta}{8^H}\ge40C_0\left(1+\frac{\log(4/(\delta\beta))}{\varepsilon}\right) Δ h = 8 H − h Δ ≥ 8 H Δ ≥ 40 C 0 ( 1 + ε l o g ( 4/ ( δ β )) ) ε ′ , β ′ , δ ′ \varepsilon',\beta',\delta' ε ′ , β ′ , δ ′ β = β ′ 2 H \beta=\frac{\beta'}{2H} β = 2 H β ′ ε = ε ′ 2 H \varepsilon=\frac{\varepsilon'}{2H} ε = 2 H ε ′ δ = δ ′ H \delta=\frac{\delta'}{H} δ = H δ ′ Δ ≥ 40 C 0 8 H ( 1 + 2 H ε ′ log ( 8 H 2 β ′ δ ′ ) ) \Delta\ge40C_0 8^H\left(1+\frac{2H}{\varepsilon'}\log\left(\frac{8H^2}{\beta'\delta'}\right)\right) Δ ≥ 40 C 0 8 H ( 1 + ε ′ 2 H log ( β ′ δ ′ 8 H 2 ) ) Q ( S , y ^ ) ≥ max y ∈ Y Q ( S , y ) − Δ Q(S,\hat{y})\ge\max_{y\in\mathcal{Y}}Q(S,y)-\Delta Q ( S , y ^ ) ≥ max y ∈ Y Q ( S , y ) − Δ 1 − β ′ 1-\beta' 1 − β ′ ( ε ′ , δ ′ ) (\varepsilon',\delta') ( ε ′ , δ ′ ) H = log ∗ ( R + 1 ) H=\log^*(R+1) H = log ∗ ( R + 1 ) C ≥ 80 C 0 C\ge80C_0 C ≥ 80 C 0
High-dimensional algorithm
We now extend the one-dimensional solver developed in the previous subsection to high dimensions by optimizing one coordinate at a time. Given the coordinates already optimized, we score each candidate coordinate value by the maximum quality attainable over all completions of the remaining coordinates. A suitable public extension of the coordinate domains ensures that each induced one-dimensional quality function attains its maximum within its finite candidate domain. The additive errors accumulate across the d d d d d d d \sqrt{d} d [4 , 18 ] .
After fixing the previously optimized coordinates, a maximizing completion of the remaining coordinates need not lie in the original finite grid. The following lemma constructs a public grid extension that contains a maximizing completion for every such prefix, while controlling the domain size.
Lemma G.3 (Domain pre-processing). Let Y = Y 1 × ⋯ × Y d ⊆ R d \mathcal{Y} = \mathcal{Y}_1 \times\cdots\times\mathcal{Y}_d \subseteq\mathbb{R}^d Y = Y 1 × ⋯ × Y d ⊆ R d non-empty finite grid domain . Then, there exists a finite domain Y ′ = Y 1 ′ × ⋯ × Y d ′ \mathcal{Y}' = \mathcal{Y}'_1 \times\cdots\times\mathcal{Y}'_d Y ′ = Y 1 ′ × ⋯ × Y d ′
(1) Y i ⊆ Y i ′ ⊆ [ min Y i , max Y i ] \mathcal{Y}_i \subseteq\mathcal{Y}'_i \subseteq[\min\mathcal{Y}_i, \max\mathcal{Y}_i] Y i ⊆ Y i ′ ⊆ [ min Y i , max Y i ] i ∈ [ d ] i \in[d] i ∈ [ d ] Y ⊆ Y ′ ⊆ CH ( Y ) \mathcal{Y} \subseteq\mathcal{Y}' \subseteq\operatorname{CH}(\mathcal{Y}) Y ⊆ Y ′ ⊆ CH ( Y )
(2) For any non-empty A ⊆ Y \mathcal{A} \subseteq\mathcal{Y} A ⊆ Y ( y 1 , … , y i ) ∈ Y 1 ′ × ⋯ × Y i ′ (y_1,\ldots,y_i) \in\mathcal{Y}'_1 \times\cdots\times\mathcal{Y}'_i ( y 1 , … , y i ) ∈ Y 1 ′ × ⋯ × Y i ′ ( y 1 , … , y i , y i + 1 ′ , … , y d ′ ) ∈ CH ( A ) (y_1,\ldots,y_i,y'_{i+1},\ldots,y'_d) \in\operatorname{CH}(\mathcal{A}) ( y 1 , … , y i , y i + 1 ′ , … , y d ′ ) ∈ CH ( A ) ( y 1 , … , y i , y i + 1 ′ ′ , … , y d ′ ′ ) ∈ CH ( A ) ∩ Y ′ (y_1,\ldots,y_i,y''_{i+1},\ldots,y''_d) \in\operatorname{CH}(\mathcal{A}) \cap\mathcal{Y}' ( y 1 , … , y i , y i + 1 ′′ , … , y d ′′ ) ∈ CH ( A ) ∩ Y ′
(3) For every i ∈ [ d ] i \in[d] i ∈ [ d ] ∣ Y i ′ ∣ ≤ 2 ∣ Y ∣ 2 i − 1 |\mathcal{Y}'_i| \leq2^{|\mathcal{Y}|^{2^{i-1}}} ∣ Y i ′ ∣ ≤ 2 ∣ Y ∣ 2 i − 1 ∣ Y ′ ∣ ≤ 2 ∣ Y ∣ ( 2 d − 1 ) |\mathcal{Y}'| \leq2^{|\mathcal{Y}|(2^{d-1})} ∣ Y ′ ∣ ≤ 2 ∣ Y ∣ ( 2 d − 1 ) log ∗ ∣ Y ′ ∣ ≤ log ∗ ∣ Y ∣ + 3 \log^*|\mathcal{Y}'| \leq\log^*|\mathcal{Y}| + 3 log ∗ ∣ Y ′ ∣ ≤ log ∗ ∣ Y ∣ + 3
Proof. We construct Y i ′ \mathcal{Y}'_i Y i ′ Y 1 ′ = Y 1 \mathcal{Y}'_1 = \mathcal{Y}_1 Y 1 ′ = Y 1 Y i ′ \mathcal{Y}'_i Y i ′ i ∈ { 2 , … , d } i \in\{2,\ldots,d\} i ∈ { 2 , … , d } Y i ′ = ∅ \mathcal{Y}'_i = \varnothing Y i ′ = ∅ ( y 1 ′ , … , y i − 1 ′ ) ∈ Y 1 ′ × ⋯ × Y i − 1 ′ (y'_1,\ldots,y'_{i-1}) \in\mathcal{Y}'_1 \times\cdots\times\mathcal{Y}'_{i-1} ( y 1 ′ , … , y i − 1 ′ ) ∈ Y 1 ′ × ⋯ × Y i − 1 ′ A ⊆ Y \mathcal{A} \subseteq\mathcal{Y} A ⊆ Y
min ( y 1 ′ , … , y i − 1 ′ , y i , y i + 1 , … , y d ) ∈ CH ( A ) y i \min_{\left(y'_1,\ldots,y'_{i-1},y_i,y_{i+1},\ldots,y_d\right)\in\operatorname{CH}(\mathcal{A})} y_i ( y 1 ′ , … , y i − 1 ′ , y i , y i + 1 , … , y d ) ∈ CH ( A ) min y i in Y i ′ \mathcal{Y}'_i Y i ′
To see property (1), fix any y = ( y 1 , … , y d ) ∈ Y y = (y_1,\ldots,y_d) \in\mathcal{Y} y = ( y 1 , … , y d ) ∈ Y y 1 ∈ Y 1 ′ = Y 1 y_1 \in\mathcal{Y}'_1 = \mathcal{Y}_1 y 1 ∈ Y 1 ′ = Y 1 ( y 1 , … , y i − 1 ) ∈ Y 1 ′ × ⋯ × Y i − 1 ′ (y_1,\ldots,y_{i-1}) \in\mathcal{Y}'_1 \times\cdots\times\mathcal{Y}'_{i-1} ( y 1 , … , y i − 1 ) ∈ Y 1 ′ × ⋯ × Y i − 1 ′ A = { y } \mathcal{A} = \{y\} A = { y } y i y_i y i Y i ′ \mathcal{Y}'_i Y i ′ Y i ⊆ Y i ′ \mathcal{Y}_i \subseteq\mathcal{Y}'_i Y i ⊆ Y i ′ i i i Y i ′ \mathcal{Y}'_i Y i ′ CH ( Y ) \operatorname{CH}(\mathcal{Y}) CH ( Y ) [ min Y i , max Y i ] [\min\mathcal{Y}_i,\max\mathcal{Y}_i] [ min Y i , max Y i ] Y \mathcal{Y} Y CH ( Y ) = ∏ j = 1 d [ min Y j , max Y j ] \operatorname{CH}(\mathcal{Y}) = \prod_{j=1}^d [\min\mathcal{Y}_j,\max\mathcal{Y}_j] CH ( Y ) = ∏ j = 1 d [ min Y j , max Y j ] Y ′ ⊆ CH ( Y ) \mathcal{Y}' \subseteq\operatorname{CH}(\mathcal{Y}) Y ′ ⊆ CH ( Y )
To see property (2), fix any non-empty A ⊆ Y \mathcal{A} \subseteq\mathcal{Y} A ⊆ Y ( y 1 , … , y i ) ∈ Y 1 ′ × ⋯ × Y i ′ (y_1,\ldots,y_i) \in\mathcal{Y}'_1 \times\cdots\times\mathcal{Y}'_i ( y 1 , … , y i ) ∈ Y 1 ′ × ⋯ × Y i ′ j > i j > i j > i j j j CH ( A ) \operatorname{CH}(\mathcal{A}) CH ( A ) Y j ′ \mathcal{Y}'_j Y j ′ CH ( A ) ∩ Y ′ \operatorname{CH}(\mathcal{A}) \cap\mathcal{Y}' CH ( A ) ∩ Y ′
Finally, let N = ∣ Y ∣ N = |\mathcal{Y}| N = ∣ Y ∣ ∣ Y 1 ′ ∣ = ∣ Y 1 ∣ ≤ N ≤ 2 N |\mathcal{Y}'_1| = |\mathcal{Y}_1| \leq N \leq2^N ∣ Y 1 ′ ∣ = ∣ Y 1 ∣ ≤ N ≤ 2 N i ≥ 2 i \geq2 i ≥ 2 A ⊆ Y A \subseteq\mathcal{Y} A ⊆ Y
∣ Y i ′ ∣ ≤ 2 N ∏ j < i ∣ Y j ′ ∣ ≤ 2 N 2 i − 1 . |\mathcal{Y}'_i| \leq2^N \prod_{j<i}|\mathcal{Y}'_j| \leq2^{N2^{i-1}}. ∣ Y i ′ ∣ ≤ 2 N j < i ∏ ∣ Y j ′ ∣ ≤ 2 N 2 i − 1 . As a result, ∣ Y ′ ∣ = ∏ i = 1 d ∣ Y i ′ ∣ ≤ 2 N ( 2 d − 1 ) |\mathcal{Y}'|=\prod_{i=1}^{d}|\mathcal{Y}'_i|\leq2^{N(2^d-1)} ∣ Y ′ ∣ = ∏ i = 1 d ∣ Y i ′ ∣ ≤ 2 N ( 2 d − 1 ) log ∗ ∣ Y ′ ∣ \log^*|\mathcal{Y}'| log ∗ ∣ Y ′ ∣ r = ∣ { i ∈ [ d ] : ∣ Y i ∣ > 1 } ∣ ≤ d r=|\{i\in[d]:|\mathcal{Y}_i|>1\}|\leq d r = ∣ { i ∈ [ d ] : ∣ Y i ∣ > 1 } ∣ ≤ d r r r ∣ Y ′ ∣ ≤ 2 N ( 2 r − 1 ) ≤ 2 N ( N − 1 ) |\mathcal{Y}'|\leq2^{N(2^r-1)}\leq2^{N(N-1)} ∣ Y ′ ∣ ≤ 2 N ( 2 r − 1 ) ≤ 2 N ( N − 1 ) 2 r ≤ ∏ i = 1 d ∣ Y i ∣ = N 2^r\leq\prod_{i=1}^{d}|\mathcal{Y}_i|=N 2 r ≤ ∏ i = 1 d ∣ Y i ∣ = N N = 1 N=1 N = 1 ∣ Y ′ ∣ = 1 |\mathcal{Y}'|=1 ∣ Y ′ ∣ = 1 ∣ Y ′ ∣ ≤ 2 2 2 N |\mathcal{Y}'|\leq2^{2^{2N}} ∣ Y ′ ∣ ≤ 2 2 2 N log ∗ ∣ Y ′ ∣ ≤ 2 + log ∗ ( 2 N ) ≤ log ∗ N + 3 \log^*|\mathcal{Y}'|\leq2+\log^*(2N)\leq\log^*N+3 log ∗ ∣ Y ′ ∣ ≤ 2 + log ∗ ( 2 N ) ≤ log ∗ N + 3
Algorithm 6 High-dimensional Quasi-Concave Optimization
Input: Parameters β , δ , ε ∈ ( 0 , 1 ) \beta,\delta,\varepsilon\in(0,1) β , δ , ε ∈ ( 0 , 1 ) U \mathcal{U} U Y ⊆ R d \mathcal{Y}\subseteq\mathbb{R}^d Y ⊆ R d ∣ Y ∣ ≥ 2 |\mathcal{Y}|\geq2 ∣ Y ∣ ≥ 2 S ∈ U ∗ S\in\mathcal{U}^* S ∈ U ∗ Q : U ∗ × Y → R Q:\mathcal{U}^*\times\mathcal{Y}\to\mathbb{R} Q : U ∗ × Y → R
if ∣ Y ∣ ≤ d + 1 |\mathcal{Y}|\leq d+1 ∣ Y ∣ ≤ d + 1 then
return The output of Exponential Mechanism (Theorem A.2) with quality function Q Q Q S S S Y \mathcal{Y} Y ε \varepsilon ε
end if
Use the canonical extension from Remark G.1 when evaluating Q Q Q Y \mathcal{Y} Y
For each i ∈ [ d ] i\in[d] i ∈ [ d ] G i = { y i : ( y 1 , … , y d ) ∈ Y } \mathcal{G}_i=\{y_i:(y_1,\ldots,y_d)\in\mathcal{Y}\} G i = { y i : ( y 1 , … , y d ) ∈ Y } G = G 1 × ⋯ × G d \mathcal{G}=\mathcal{G}_1\times\cdots\times\mathcal{G}_d G = G 1 × ⋯ × G d Y \mathcal{Y} Y
Preprocess G \mathcal{G} G Y ′ = Y 1 ′ × ⋯ × Y d ′ \mathcal{Y}'=\mathcal{Y}'_1\times\cdots\times\mathcal{Y}'_d Y ′ = Y 1 ′ × ⋯ × Y d ′
Set Δ 0 = C d 1.5 δ log ∗ ∣ Y ∣ 2 log ( 2 / δ ) ε log ( 16 ( d log ∗ ∣ Y ∣ ) 2 β δ ) \Delta_0=Cd^{1.5}\frac{\delta\log^*|\mathcal{Y}|\sqrt{2\log(2/\delta)}}{\varepsilon}\log\left(\frac{16(d\log^*|\mathcal{Y}|)^2}{\beta\delta}\right) Δ 0 = C d 1.5 ε δ l o g ∗ ∣ Y ∣ 2 l o g ( 2/ δ ) log ( β δ 16 ( d l o g ∗ ∣ Y ∣ ) 2 ) C > 0 C>0 C > 0
Set β ′ = β d \beta'=\frac{\beta}{d} β ′ = d β ε ′ = ε 2 2 d log ( 2 / δ ) \varepsilon'=\frac{\varepsilon}{2\sqrt{2d\log(2/\delta)}} ε ′ = 2 2 d l o g ( 2/ δ ) ε δ ′ = δ 2 d \delta'=\frac{\delta}{2d} δ ′ = 2 d δ
for i ∈ { 1 , 2 , … , d } i\in\{1,2,\ldots,d\} i ∈ { 1 , 2 , … , d } do
Define Q i : U ∗ × Y i ′ → R Q_i:\mathcal{U}^*\times\mathcal{Y}'_i\to\mathbb{R} Q i : U ∗ × Y i ′ → R
Q i ( S , y ) : = max ( y i + 1 ∗ , … , y d ∗ ) ∈ R d − i Q ( S , ( y ^ 1 , … , y ^ i − 1 , y , y i + 1 ∗ , … , y d ∗ ) ) . Q_i(S,y):=\max_{(y^*_{i+1},\ldots,y^*_d)\in\mathbb{R}^{d-i}}Q(S,(\hat y_1,\ldots,\hat y_{i-1},y,y^*_{i+1},\ldots,y^*_d)). Q i ( S , y ) := ( y i + 1 ∗ , … , y d ∗ ) ∈ R d − i max Q ( S , ( y ^ 1 , … , y ^ i − 1 , y , y i + 1 ∗ , … , y d ∗ )) . Run the QCO Algorithm 5 with parameters β ′ , ε ′ , δ ′ , Δ = Δ 0 d \beta',\varepsilon',\delta',\Delta=\frac{\Delta_0}{d} β ′ , ε ′ , δ ′ , Δ = d Δ 0 Q i Q_i Q i S S S U \mathcal{U} U Y i ′ \mathcal{Y}'_i Y i ′ y ^ \hat y y ^ y ^ i ← y ^ \hat y_i\leftarrow\hat y y ^ i ← y ^
end for
Set y ^ = [ y ^ 1 , … , y ^ d ] \hat y=[\hat y_1,\ldots,\hat y_d] y ^ = [ y ^ 1 , … , y ^ d ]
if y ^ ∉ CH ( Y ) \hat y\notin\operatorname{CH}(\mathcal{Y}) y ^ ∈ / CH ( Y ) then
return a fixed public point of Y \mathcal{Y} Y
end if
return y ^ \hat y y ^
The next theorem establishes the privacy and agnostic additive-error guarantees of the following high-dimensional QCO algorithm.
Theorem G.4. Let β , ε , δ ∈ ( 0 , 1 ) \beta,\varepsilon,\delta\in(0,1) β , ε , δ ∈ ( 0 , 1 ) C > 0 C>0 C > 0 Y ⊆ R d \mathcal{Y}\subseteq\mathbb{R}^d Y ⊆ R d ∣ Y ∣ ≥ 2 |\mathcal{Y}|\geq2 ∣ Y ∣ ≥ 2 Q : U ∗ × Y → R Q:\mathcal{U}^*\times\mathcal{Y}\to\mathbb{R} Q : U ∗ × Y → R
quasi-concave function with sensitivity 1. Then Algorithm 6 is ( ε , δ ) (\varepsilon,\delta) ( ε , δ )
Δ ≥ C d 1.5 8 log ∗ ∣ Y ∣ log ∗ ∣ Y ∣ 2 log ( 2 / δ ) ε log ( 16 ( d log ∗ ∣ Y ∣ ) 2 β δ ) , \Delta\ge C d^{1.5}\frac{8^{\log^*|\mathcal{Y}|}\log^*|\mathcal{Y}|\sqrt{2\log(2/\delta)}}{\varepsilon}\log\left(\frac{16(d\log^*|\mathcal{Y}|)^2}{\beta\delta}\right), Δ ≥ C d 1.5 ε 8 l o g ∗ ∣ Y ∣ log ∗ ∣ Y ∣ 2 log ( 2/ δ ) log ( β δ 16 ( d log ∗ ∣ Y ∣ ) 2 ) , and every dataset S ∈ U ∗ S \in\mathcal{U}^* S ∈ U ∗ y ^ ∈ CH ( Y ) \hat{y} \in\operatorname{CH}(\mathcal{Y}) y ^ ∈ CH ( Y )
Q ( S , y ^ ) ≥ max y ∈ Y Q ( S , y ) − Δ Q(S,\hat{y}) \ge\max_{y\in\mathcal{Y}} Q(S,y)-\Delta Q ( S , y ^ ) ≥ y ∈ Y max Q ( S , y ) − Δ with probability at least 1 − β 1-\beta 1 − β
Proof. First suppose that 2 ≤ ∣ Y ∣ ≤ d + 1 2 \le|\mathcal{Y}| \le d+1 2 ≤ ∣ Y ∣ ≤ d + 1 ( ε , 0 ) (\varepsilon,0) ( ε , 0 ) 1 − β 1-\beta 1 − β y ^ \hat{y} y ^
Q ( S , y ^ ) ≥ max y ∈ Y Q ( S , y ) − 2 log ( ( d + 1 ) / β ) ε . Q(S,\hat{y}) \ge\max_{y\in\mathcal{Y}} Q(S,y)-\frac{2\log((d+1)/\beta)}{\varepsilon}. Q ( S , y ^ ) ≥ y ∈ Y max Q ( S , y ) − ε 2 log (( d + 1 ) / β ) . For sufficiently large C C C Δ \Delta Δ ∣ Y ∣ > d + 1 |\mathcal{Y}|>d+1 ∣ Y ∣ > d + 1
Let G \mathcal{G} G d < ∣ Y ∣ d<|\mathcal{Y}| d < ∣ Y ∣ ∣ G ∣ ≤ ∣ Y ∣ d ≤ ∣ Y ∣ ∣ Y ∣ ≤ 2 2 ∣ Y ∣ |\mathcal{G}|\le|\mathcal{Y}|^d\le|\mathcal{Y}|^{|\mathcal{Y}|}\le2^{2^{|\mathcal{Y}|}} ∣ G ∣ ≤ ∣ Y ∣ d ≤ ∣ Y ∣ ∣ Y ∣ ≤ 2 2 ∣ Y ∣ log ∗ ∣ G ∣ ≤ log ∗ ∣ Y ∣ + 2 \log^*|\mathcal{G}|\le\log^*|\mathcal{Y}|+2 log ∗ ∣ G ∣ ≤ log ∗ ∣ Y ∣ + 2
Let Y ′ = Y 1 ′ × ⋯ × Y d ′ \mathcal{Y}'=\mathcal{Y}'_1\times\cdots\times\mathcal{Y}'_d Y ′ = Y 1 ′ × ⋯ × Y d ′ G \mathcal{G} G Lemma G.3 . In particular, Y ⊆ G ⊆ Y ′ \mathcal{Y}\subseteq\mathcal{G}\subseteq\mathcal{Y}' Y ⊆ G ⊆ Y ′ Q Q Q Y \mathcal{Y} Y
Fix an iteration i ∈ [ d ] i\in[d] i ∈ [ d ] ( y ^ 1 , … , y ^ i − 1 ) ∈ Y 1 ′ × ⋯ × Y i − 1 ′ (\hat{y}_1,\ldots,\hat{y}_{i-1})\in\mathcal{Y}'_1\times\cdots\times\mathcal{Y}'_{i-1} ( y ^ 1 , … , y ^ i − 1 ) ∈ Y 1 ′ × ⋯ × Y i − 1 ′ y ∈ Y i ′ y\in\mathcal{Y}'_i y ∈ Y i ′ { Q ( S , z ) : z ∈ Y } \{Q(S,z):z\in\mathcal{Y}\} { Q ( S , z ) : z ∈ Y } Q i ( S , y ) Q_i(S,y) Q i ( S , y ) i = d i=d i = d
Q d ( S , y ) = Q ( S , ( y ^ 1 , … , y ^ d − 1 , y ) ) . Q_d(S,y)=Q(S,(\hat{y}_1,\ldots,\hat{y}_{d-1},y)). Q d ( S , y ) = Q ( S , ( y ^ 1 , … , y ^ d − 1 , y )) . We next show that a maximizing completion exists in Y ′ \mathcal{Y}' Y ′ Q i ( S , y ) = min z ∈ Y Q ( S , z ) Q_i(S,y)=\min_{z\in\mathcal{Y}}Q(S,z) Q i ( S , y ) = min z ∈ Y Q ( S , z ) Y ′ \mathcal{Y}' Y ′ i i i Q i ( S , y ) Q_i(S,y) Q i ( S , y )
Otherwise, let A = { z ∈ Y : Q ( S , z ) ≥ Q i ( S , y ) } A=\{z\in\mathcal{Y}:Q(S,z)\ge Q_i(S,y)\} A = { z ∈ Y : Q ( S , z ) ≥ Q i ( S , y )} Q i ( S , y ) > min z ∈ Y Q ( S , z ) Q_i(S,y)>\min_{z\in\mathcal{Y}}Q(S,z) Q i ( S , y ) > min z ∈ Y Q ( S , z ) CH ( A ) \operatorname{CH}(A) CH ( A ) Remark G.1 . Since A ⊆ Y ⊆ G A\subseteq\mathcal{Y}\subseteq\mathcal{G} A ⊆ Y ⊆ G Lemma G.3 , applied to G \mathcal{G} G CH ( A ) ∩ Y ′ \operatorname{CH}(A)\cap\mathcal{Y}' CH ( A ) ∩ Y ′ i i i Q i ( S , y ) Q_i(S,y) Q i ( S , y ) Q i ( S , y ) Q_i(S,y) Q i ( S , y )
Q i ( S , y ) = max ( y i + 1 ∗ , … , y d ∗ ) ∈ Y i + 1 ′ × ⋯ × Y d ′ Q ( S , ( y ^ 1 , … , y ^ i − 1 , y , y i + 1 ∗ , … , y d ∗ ) ) . (6) Q_i(S,y)=\max_{(y^*_{i+1},\ldots,y^*_d)\in\mathcal{Y}'_{i+1}\times\cdots\times\mathcal{Y}'_d}Q(S,(\hat{y}_1,\ldots,\hat{y}_{i-1},y,y^*_{i+1},\ldots,y^*_d)). \tag*{(6)} Q i ( S , y ) = ( y i + 1 ∗ , … , y d ∗ ) ∈ Y i + 1 ′ × ⋯ × Y d ′ max Q ( S , ( y ^ 1 , … , y ^ i − 1 , y , y i + 1 ∗ , … , y d ∗ )) . (6) For i = d i=d i = d
Now, we prove that Q i ( S , ⋅ ) Q_i(S,\cdot) Q i ( S , ⋅ ) a , b , c ∈ Y i ′ a,b,c\in\mathcal{Y}'_i a , b , c ∈ Y i ′ c = λ a + ( 1 − λ ) b c=\lambda a+(1-\lambda)b c = λa + ( 1 − λ ) b λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] y a , y b ∈ Y ′ y_a,y_b\in\mathcal{Y}' y a , y b ∈ Y ′ Q i ( S , a ) Q_i(S,a) Q i ( S , a ) Q i ( S , b ) Q_i(S,b) Q i ( S , b ) i − 1 i-1 i − 1 i i i λ y a + ( 1 − λ ) y b \lambda y_a+(1-\lambda)y_b λ y a + ( 1 − λ ) y b [ y ^ 1 , … , y ^ i − 1 , c ] [\hat{y}_1,\ldots,\hat{y}_{i-1},c] [ y ^ 1 , … , y ^ i − 1 , c ]
Q i ( S , c ) ≥ Q ( S , λ y a + ( 1 − λ ) y b ) ≥ min { Q ( S , y a ) , Q ( S , y b ) } = min { Q i ( S , a ) , Q i ( S , b ) } . (7) \begin{aligned}
Q_i(S,c)\ge Q(S,\lambda y_a+(1-\lambda)y_b) \\
&\ge\min\{\mathcal{Q}(S,y_a),\mathcal{Q}(S,y_b)\}\\
= \min\{\mathcal{Q}_i(S,a),\mathcal{Q}_i(S,b)\}. \tag*{(7)}
\end{aligned} Q i ( S , c ) ≥ Q ( S , λ y a + ( 1 − λ ) y b ) = min { Q i ( S , a ) , Q i ( S , b )} . ≥ min { Q ( S , y a ) , Q ( S , y b )} (7) Next, we prove that Q i \mathcal{Q}_i Q i S , S ′ S,S' S , S ′ A ⊆ Y \mathcal{A} \subseteq\mathcal{Y} A ⊆ Y Q \mathcal{Q} Q Y \mathcal{Y} Y
∣ min z ∈ A Q ( S , z ) − min z ∈ A Q ( S ′ , z ) ∣ ≤ 1. \left|\min_{z\in\mathcal{A}}\mathcal{Q}(S,z)-\min_{z\in\mathcal{A}}\mathcal{Q}(S',z)\right|\le1. z ∈ A min Q ( S , z ) − z ∈ A min Q ( S ′ , z ) ≤ 1. Taking the maximum over the subsets whose convex hulls contain a fixed x ∈ CH ( Y ) x \in\operatorname{CH}(\mathcal{Y}) x ∈ CH ( Y ) ∣ Q ( S , x ) − Q ( S ′ , x ) ∣ ≤ 1 |\mathcal{Q}(S,x)-\mathcal{Q}(S',x)|\le1 ∣ Q ( S , x ) − Q ( S ′ , x ) ∣ ≤ 1 CH ( Y ) \operatorname{CH}(\mathcal{Y}) CH ( Y ) min z ∈ Y Q ( S , z ) \min_{z\in\mathcal{Y}}\mathcal{Q}(S,z) min z ∈ Y Q ( S , z ) x ∈ R d x \in\mathbb{R}^d x ∈ R d Q i \mathcal{Q}_i Q i ∣ Q i ( S , y ) − Q i ( S ′ , y ) ∣ ≤ 1 |\mathcal{Q}_i(S,y)-\mathcal{Q}_i(S',y)|\le1 ∣ Q i ( S , y ) − Q i ( S ′ , y ) ∣ ≤ 1
Now, we are ready to use the 1-dimensional QCO solver from Algorithm 5 on each Q i \mathcal{Q}_i Q i Lemma G.3 , log ∗ ∣ Y ′ ∣ ≤ log ∗ ∣ G ∣ + 3 ≤ log ∗ ∣ Y ∣ + 5 \log^*|\mathcal{Y}'| \le\log^*|\mathcal{G}|+3 \le\log^*|\mathcal{Y}|+5 log ∗ ∣ Y ′ ∣ ≤ log ∗ ∣ G ∣ + 3 ≤ log ∗ ∣ Y ∣ + 5 Theorem G.2 . The additive constant 5 is absorbed by taking the universal constant C C C 1 ε ′ = 2 2 d log ( 2 / δ ) ε \frac{1}{\varepsilon'}=\frac{2\sqrt{2d\log(2/\delta)}}{\varepsilon} ε ′ 1 = ε 2 2 d l o g ( 2/ δ ) 1 β ′ δ ′ = 2 d 2 β δ \frac{1}{\beta'\delta'}=\frac{2d^2}{\beta\delta} β ′ δ ′ 1 = β δ 2 d 2 Theorem G.2 , for sufficiently large C C C Δ 0 / d \Delta_0/d Δ 0 / d y ^ i \hat{y}_i y ^ i i i i
Q i ( S , y ^ i ) ≥ max y ∈ Y i ′ Q i ( S , y ) − Δ 0 d \mathcal{Q}_i(S,\hat{y}_i)\ge\max_{y\in\mathcal{Y}'_i}\mathcal{Q}_i(S,y)-\frac{\Delta_0}{d} Q i ( S , y ^ i ) ≥ y ∈ Y i ′ max Q i ( S , y ) − d Δ 0 with probability at least 1 − β ′ 1-\beta' 1 − β ′
We prove the utility guarantee on this event by induction. In the first iteration, Equation (G.6) gives
max y ∈ Y 1 ′ Q 1 ( S , y ) = max y ∈ Y ′ Q ( S , y ) = max y ∈ Y Q ( S , y ) . \max_{y\in\mathcal{Y}'_1}\mathcal{Q}_1(S,y)=\max_{y\in\mathcal{Y}'}\mathcal{Q}(S,y)=\max_{y\in\mathcal{Y}}\mathcal{Q}(S,y). y ∈ Y 1 ′ max Q 1 ( S , y ) = y ∈ Y ′ max Q ( S , y ) = y ∈ Y max Q ( S , y ) . The last equality follows because the canonical extension never exceeds the maximum quality on Y \mathcal{Y} Y Y ⊆ Y ′ \mathcal{Y}\subseteq\mathcal{Y}' Y ⊆ Y ′
Q 1 ( S , y ^ 1 ) ≥ max y ∈ Y Q ( S , y ) − Δ 0 d . \mathcal{Q}_1(S,\hat{y}_1)\ge\max_{y\in\mathcal{Y}}\mathcal{Q}(S,y)-\frac{\Delta_0}{d}. Q 1 ( S , y ^ 1 ) ≥ y ∈ Y max Q ( S , y ) − d Δ 0 . For the induction step, let i ∈ { 2 , … , d } i\in\{2,\ldots,d\} i ∈ { 2 , … , d } i − 1 i-1 i − 1 i i i
max y ∈ Y i ′ Q i ( S , y ) = Q i − 1 ( S , y ^ i − 1 ) , \max_{y\in\mathcal{Y}'_i}\mathcal{Q}_i(S,y)=\mathcal{Q}_{i-1}(S,\hat{y}_{i-1}), y ∈ Y i ′ max Q i ( S , y ) = Q i − 1 ( S , y ^ i − 1 ) , since both sides maximize Q \mathcal{Q} Q Y i ′ × ⋯ × Y d ′ \mathcal{Y}'_i\times\cdots\times\mathcal{Y}'_d Y i ′ × ⋯ × Y d ′ i − 1 i-1 i − 1
Q i ( S , y ^ i ) ≥ max y ∈ Y i ′ Q i ( S , y ) − Δ 0 d = Q i − 1 ( S , y ^ i − 1 ) − Δ 0 d ≥ max y ∈ Y Q ( S , y ) − i d Δ 0 . \begin{aligned}
\mathcal{Q}_i(S,\hat{y}_i)&\ge\max_{y\in\mathcal{Y}'_i}\mathcal{Q}_i(S,y)-\frac{\Delta_0}{d}\\
&=\mathcal{Q}_{i-1}(S,\hat{y}_{i-1})-\frac{\Delta_0}{d}\\
&\ge\max_{y\in\mathcal{Y}}\mathcal{Q}(S,y)-\frac{i}{d}\Delta_0.
\end{aligned} Q i ( S , y ^ i ) ≥ y ∈ Y i ′ max Q i ( S , y ) − d Δ 0 = Q i − 1 ( S , y ^ i − 1 ) − d Δ 0 ≥ y ∈ Y max Q ( S , y ) − d i Δ 0 . Let y ^ = [ y ^ 1 , … , y ^ d ] ∈ Y ′ \hat{y} = [\hat{y}_1,\ldots,\hat{y}_d] \in\mathcal{Y}' y ^ = [ y ^ 1 , … , y ^ d ] ∈ Y ′ 1 − d β ′ = 1 − β 1-d\beta' = 1-\beta 1 − d β ′ = 1 − β
Q ( S , y ^ ) = Q d ( S , y ^ d ) ≥ max y ∈ Y Q ( S , y ) − Δ 0 ≥ max y ∈ Y Q ( S , y ) − Δ . \mathcal{Q}(S,\hat{y}) = Q_d(S,\hat{y}_d) \ge\max_{y\in\mathcal{Y}} \mathcal{Q}(S,y) - \Delta_0 \ge\max_{y\in\mathcal{Y}} \mathcal{Q}(S,y) - \Delta. Q ( S , y ^ ) = Q d ( S , y ^ d ) ≥ y ∈ Y max Q ( S , y ) − Δ 0 ≥ y ∈ Y max Q ( S , y ) − Δ. If y ^ ∉ CH ( Y ) \hat{y} \notin\operatorname{CH}(\mathcal{Y}) y ^ ∈ / CH ( Y ) min z ∈ Y Q ( S , z ) \min_{z\in\mathcal{Y}} \mathcal{Q}(S,z) min z ∈ Y Q ( S , z ) Y \mathcal{Y} Y CH ( Y ) \operatorname{CH}(\mathcal{Y}) CH ( Y )
The privacy guarantee follows from the privacy of the 1-dimensional QCO algorithm (Theorem G.2 ). Recall that, for every fixed preceding transcript, the quality function Q i Q_i Q i ( ε ′ , δ ′ ) (\varepsilon',\delta') ( ε ′ , δ ′ ) Theorem A.1 ) with additional failure parameter δ / 2 \delta/2 δ /2 d d d ( ε ′ 2 d log ( 2 / δ ) + d ε ′ ( e ε ′ − 1 ) , d δ ′ + δ 2 ) (\varepsilon'\sqrt{2d\log(2/\delta)} + d\varepsilon'(e^{\varepsilon'} - 1), d\delta' + \frac{\delta}{2}) ( ε ′ 2 d log ( 2/ δ ) + d ε ′ ( e ε ′ − 1 ) , d δ ′ + 2 δ ) d δ ′ + δ / 2 = δ d\delta' + \delta/2 = \delta d δ ′ + δ /2 = δ ε ′ < 1 \varepsilon' < 1 ε ′ < 1 e u − 1 ≤ 2 u e^u - 1 \le2u e u − 1 ≤ 2 u u ∈ [ 0 , 1 ] u \in[0,1] u ∈ [ 0 , 1 ]
ε ′ 2 d log ( 2 / δ ) + d ε ′ ( e ε ′ − 1 ) ≤ ε 2 + 2 d ( ε ′ ) 2 = ε 2 + ε 2 4 log ( 2 / δ ) < ε \varepsilon'\sqrt{2d\log(2/\delta)} + d\varepsilon'(e^{\varepsilon'} - 1) \le\frac{\varepsilon}{2} + 2d(\varepsilon')^2 = \frac{\varepsilon}{2} + \frac{\varepsilon^2}{4\log(2/\delta)} < \varepsilon ε ′ 2 d log ( 2/ δ ) + d ε ′ ( e ε ′ − 1 ) ≤ 2 ε + 2 d ( ε ′ ) 2 = 2 ε + 4 log ( 2/ δ ) ε 2 < ε using ε < 1 \varepsilon< 1 ε < 1 log ( 2 / δ ) > log 2 > 1 / 2 \log(2/\delta) > \log2 > 1/2 log ( 2/ δ ) > log 2 > 1/2 ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) □ \square □
