--- abstract: | We study the query complexity of a learner-private sequential learning problem, motivated by the privacy and security concerns due to eavesdropping that arise in practical applications such as pricing and Federated Learning. A learner tries to estimate an unknown scalar value, by sequentially querying an external database and receiving binary responses; meanwhile, a third-party adversary observes the learner's queries but not the responses. The learner's goal is to design a querying strategy with the minimum number of queries (optimal query complexity) so that she can accurately estimate the true value, while the eavesdropping adversary even with the complete knowledge of her querying strategy cannot. We develop new querying strategies and analytical techniques and use them to prove tight upper and lower bounds on the optimal query complexity. The bounds almost match across the entire parameter range, substantially improving upon existing results. We thus obtain a complete picture of the optimal query complexity as a function of the estimation accuracy and the desired levels of privacy. We also extend the results to sequential learning models in higher dimensions, and where the binary responses are noisy. Our analysis leverages a crucial insight into the nature of private learning problem, which suggests that the query trajectory of an optimal learner can be divided into distinct phases that focus on pure learning versus learning and obfuscation, respectively. author: - 'Jiaming Xu, Kuang Xu, and Dana Yang[^1]' bibliography: - 'bibliography.bib' title: Optimal query complexity for private sequential learning against eavesdropping --- Introduction ============ Rapid developments in machine learning and data science have compelled organizations and individuals to increasingly rely on data to solve inference and decision problems. It quickly became clear, however, that collecting and disseminating data in bulk can expose data owners to serious privacy breaches @Dwork08. To address the privacy concerns of data owners, researchers and practitioners have been advocating a new learning framework, known as *learning with external workers* @konevcny2015federated. Under this framework, instead of allowing a learner to possess the entire data set and conduct analysis in an offline manner, data sets are kept secure by their owners, and the learner must interact with data owners by submitting queries and receiving responses. While substantial progress has been achieved in protecting data owners' privacy in such systems @Dwork08 [@geyer2017differentially; @song2013stochastic; @agarwal2018cpsgd], the *learner's* privacy has largely been overlooked. Because a learner has to communicate frequently with data owners in order to perform analysis, their queries can be subject to eavesdropping by a third-party adversary. That adversary, in turn, could use the observed queries to reconstruct the learned model, thus allowing them to free-ride at the learner's expense, or worse, leverage such information in future sabotages. In this paper, we focus on understanding how to protect the learner's privacy against eavesdropping attacks, and precisely quantifying the fundamental privacy-complexity trade-offs in such an interactive learning system. We base our analysis on the Private Sequential Learning model proposed by @tsitsiklis2018private. Suppose that a learner is trying to estimate an unknown target value $X^* \in [0,1]$, by submitting $n$ queries sequentially, $(q_1, \ldots, q_n) \in [0,1]^n$, for some $n \in {{\mathbb{N}}}$. For each query $q_i$, the learner receives a binary response $r_i=\mathds{1}\{X^*\geq q_i\}$, indicating the position of $X^*$ relative to the query, where $\mathds{1}\{\cdot\}$ denotes the indicator function. Meanwhile, there is an adversary who observes all of the learner's queries $(q_1, \ldots, q_n)$, but not the responses $(r_1, \ldots, r_n)$. The adversary then tries to estimate $X^*$. The learner's goal is to design a querying strategy with a minimal $n$ (optimal query complexity) so that she can estimate $X^*$ up to an additive error of $\epsilon/2$ with probability $1$ (accuracy), while *no adversary* can estimate $X^*$ up to an additive error of $\delta/2$ with probability larger than $1/L$ for some integer $L\ge 2$ (privacy), even if they are equipped with the complete knowledge of the learner's querying strategy. The parameter $L$ thus captures the learner's privacy level. In the special case of $L=1$ (corresponding to having no privacy constraint) this learning model reduces to the classical problem of sequential search with binary feedback, with numerous applications such as data transmission with feedback @horstein1963sequential, finding the roots of a continuous function @waeber2011bayesian, and even the game of "twenty questions" @jedynak2012twenty. ![Our results in Theorem \[thm:bayes\] (solid) versus the best known bounds (dashed, upper bound: @tsitsiklis2018private, lower bound: @xu2018query) under the noiseless Bayesian setting, with $L=15$ and $\delta= 4\epsilon^{0.5}$. The figure is cut off to the right at the point where $\delta$ hits the upper limit, $1/L$, beyond which it is easy to show that no learning strategy can be private.<span data-label="fig:old_new_bayes"></span>](bayes_plot.pdf) <span>**Our contributions.**</span> The primary contributions of our paper are two fold: 1. We settle the optimal query complexity of the Private Sequential Learning problem in both the Bayesian setting (where $X^*$ is random) and deterministic setting (where $X^*$ is fixed but arbitrary). We do so by establishing query complexity upper and lower bounds that almost match in the entire parameter range, thus obtaining a complete picture of the optimal query complexity as a function of the estimation accuracy and the learner's privacy level. Our results substantially improve upon the best known upper and lower bounds @tsitsiklis2018private [@xu2018query], and the improvements are most drastic over an important range of parameters, where both the adversary and the learner aim to locate $X^*$ within small errors ; see Figure \[fig:old\_new\_bayes\] for an illustrative example. 2. We propose and analyze an important variant of the private learning model with noisy responses, a feature that is especially salient in real-world operations and machine learning applications where the functional evaluations are often stochastic. In this setting, we prove upper and lower bounds on the optimal query complexity which match up to multiplicative constants that only depend on the level of noise in the responses. This mirrors the best known characterizations available in the non-private version of the problem, which also has a dependency on the noise level @waeber2013bisection. *Methodological contribution*. Our results are rooted in new insights into the nature of learner-private sequential learning problems, which could have broader implications. For instance, in the Bayesian setting, one driving insight is that the portion of the learning process that demands the most privacy protection is *after* the learner has already obtained a reasonably accurate estimate of $X^*$. We further demonstrate that, as an implication of this observation, the querying trajectory of an optimal learner can be roughly divided into two phases: 1. A *pure-learning* phase, where the primary objective is to narrow the search down to a smaller interval that contains $X^*$ and privacy is not a top priority. 2. A *private-refinement* phase, where the learner refines her estimate of $X^*$ within the said interval, while allocating significantly more querying budget towards obfuscation. We develop new learning strategies and analytical techniques to make this intuition precise. The algorithmic implications are significant. On the one hand, it suggests more efficient learner strategies that allocate more obfuscation budget towards the latter stages of learning. On the other hand, it can be used to design more powerful adversary strategies that focus on latter stages of a learner's query trajectory, and obtain a more accurate estimator. In analogous manner, our analysis of the deterministic setting also leverages a two-phase approach, although the obfuscation budget is now skewed towards the earlier stages of learning. Motivating Examples {#sec:motivation} ------------------- We examine in this sub-section several motivating applications of the Private Sequential Learning model. To be clear, the private learning model we study is highly stylized, and as such applying our algorithms in an application would require caution and necessary modifications. However, it appears likely that the rigorous study we carry out and the structural properties it unveils would, at the very least, yield valuable insights and help guild policy design in real-world systems. #### Learning the optimal price: {#learning-the-optimal-price .unnumbered} As discussed in @tsitsiklis2018private, dynamics similar to those in the Private Sequential Learning model arise in the domain of dynamic pricing. Suppose a company is conducting market experiments to determine the release price of a product. The goal is to learn a global parameter about the entire consumer base, e.g., $X^*$ equals the highest price to charge so that at least 50% of the consumers would purchase the product. At each epoch of the experiment, the company samples a subset of the consumers and experiment on a test price (query). Under the sequential learning model, the response $r_i$ corresponds to the indicator function of whether at least 50% of the sampled consumers would purchase the product at price $q_i$. Note that, due to individual differences and the sampling process, the response is a noisy version of its population variant, which can be captured by the noisy variant of the model we study in this paper. In this example, a competitor (adversary) can easily access the sequence of test prices by participating in the experiments, but does not observe the responses. The optimal query complexity refers to the minimum number of epochs the company takes to estimate $X^*$ accurately, while making sure the eavesdropping adversary cannot infer the final release price. Notice the distinction between our privacy incentive and the incentive to protect the data owners' privacy. The latter aims to ensure that the query sequence does not reveal the price each individual participant is willing to pay, which varies from person to person and can be far from $X^*$. #### Federated Learning: {#federated-learning .unnumbered} As mentioned in the Introduction, our study of Private Sequential Learning is motivated in part by wanting to protect the privacy of the learner, rather than data owners, in a learning-with-external-workers system. Among these systems, Federated Learning is an emerging machine learning model training paradigm that has been gaining traction over the past few years @konevcny2015federated [@konevcny2016federated; @ChenSuXu17; @su2019securing; @kairouz2019advances; @bagdasaryan2020backdoor; @yin2018byzantine; @bhagoji2019analyzing; @alistarh2018byzantine; @yang2020federated; @yin2019defending; @xie2018generalized; @li2019rsa; @ding2019distributed; @wu2019federated], and has been deployed in products by companies such as Apple @hao_2019 and Google @FL_google2017. Before explaining how the Private Sequential Learning model applies in this context, we briefly review the basic mechanisms of Federated Learning. A typical Federated Learning training process is sequential in nature and works as follows (see e.g. @mcmahan2016communication [Algorithm 1]). A central learner trains a global model by aggregating local model updates across a large number of users on mobile devices. At each iteration $t$, the learner broadcasts the current model parameter $w_t$ to all (or a subset) of the users. Using their local data, each user $i$ then trains an individual model update $w_t^i$ starting from $w_t$, and sends it back to the central learner. The learner aggregates all the model updates $w_t^i$ across all user $i$ to produce $w_{t+1}$, the model parameter for the next iteration. Importantly, like most systems in its category, Federated Learning is designed with the goal of protecting the privacy of data owners (the users) @geyer2017differentially [@mcmahan2017learning; @agarwal2018cpsgd], while offering no explicit privacy guarantees on the central learner's learned model parameters under eavesdropping attacks. [^2] Our focus, in contrast, would be on the privacy concern of the latter. Specifically, when training with thousands of users, as the learner lacks enough administrative power over those external workers, the Federated Learning system is highly vulnerable to eavesdropping attacks @kairouz2019advances. An *honest-but-curious* adversary can participate in the training stage by pretending to be an user, and eavesdrop on the sequence of broadcasted model parameters. Simply by taking the last set of model parameters, the adversary can approximate the learner's final model fairly well. Sophisticated models can be worth millions. The eavesdropper can use the stolen model to profit or even leverage them for illicit purposes @juuti2019prada. It not only saves the eavesdropper from investing the tremendous amounts of funding into training the model, but it could also devalue the learner's model. Therefore, it is of paramount importance to protect the learner's privacy from eavesdropping attacks. There are several potential techniques to conceal the model parameters from the users in Federated Learning, such as restricting each user to run the local computation inside a Trusted Executation Envrionments (TEE) @subramanyan2017formal or encrypting the model parameters under a homomorphic encryption scheme before broadcasting it to the users @mohassel2017secureml. Unfortunately, as pointed out by the recent survey @kairouz2019advances [Section 4.3.3], TEEs may not be generally available across all workers especially when these workers represent end-devices such as smartphones. Moreover, TEEs and homomorphic encryption are often costly to implement and incurs large overhead. There is an emerging line of research on preventing model theft in the evaluation stage, where an adversary attempts to extract the deployed model by repeatedly querying the model and obtaining estimation on the input feature vectors @tramer2016stealing [@papernot2017practical; @shi2017steal; @wang2018stealing; @juuti2019prada; @orekondy2019prediction; @orekondy2019knockoff; @kariyappa2020defending]. However, this line of work does not address the unique challenge of concealing the model parameters from the users during the training stage in Federated Learning. This consideration prompts us to investigate whether we can offer provable guarantees on the learner's privacy against the eavesdropping attack in Federated learning. In particular, we aim to address the following two natural but fundamental questions: 1. Can the learner arrive at an accurate model, while ensuring that the eavesdropping adversary cannot learn the same model with a high level of accuracy? 2. What is the minimal number of iterations needed in the training process, for accurate and private learning? The sequential learning problem we study can be viewed as a special case of the problem faced by the central learner in a Federated Learning framework, where the true model parameter $X^*$ is in one dimension. In particular, at iteration $t$ the learner broadcasts the current model parameter $w_t$ (viewed as the query). Then instead of the local model update $w_t^i$, each user $i$ sends back to the learner only the directional information $\text{sign}(w_t^i-w_t)$ of the update. The majority vote of $\text{sign}(w_t^i-w_t)$ is viewed as the response, which is often noisy due to noise in the users' local data. All users, including the adversarial ones, observe the broadcasted queries. Moreover, it is reasonable to assume that the adversary does not observe the responses. That is because in order to observe the responses, the adversary would have to access the updates generated by all users in the system, a formidable task that is not realistic for an adversary that only controls up to a small subset of the users. Note that in Federated Learning, communication bandwidth is a scarce resource, as the data transmission between the external workers and the learner typically suffers from high latency and low throughput. Thus, determining the optimal query complexity (i.e. the minimum communication rounds) is of fundamental importance in both theory and practice. #### Other applications: {#other-applications .unnumbered} There are many other applications in which a learner would naturally suffer from privacy breaches if the learning process can be eavesdropped by a third party, for example in crowdsourced learning @howe2006rise @vukovic2009crowdsourcing. Similar scenarios also arise in conducting surveys or medical inspections, where we hope to adaptively collect information, while preventing the adaptive questionnaires from giving away respondents' private information. While the Private Sequential Learning model may not yet directly apply, the fundamental tradeoff between privacy and complexity of learning unveiled by our investigation is likely to speak to similar strategic considerations arising in these applications. Comparison with prior work -------------------------- The Private Sequential Learning model with noiseless responses was proposed by @tsitsiklis2018private and further studied by @xu2018query. While simple, this model already captures a core tension between learning and privacy. To see why a naive learning strategy can put the learner's privacy at risk, consider the vanilla bisection strategy which recursively queries the mid-point of the interval that the learner knows to contain the target $X^*$. It can be shown that the bisection strategy achieves the minimum sample complexity of $\log(1/\epsilon)$ queries[^3], but it almost entirely compromises the learner's privacy. If the adversary sets their estimator to be equal to the learner's last query, then $X^*$ is within a distance of at most $\epsilon.$ On the other extreme, consider the non-adaptive grid search strategy, where the learner partitions the interval $[0,1]$ into subintervals of length $\epsilon$ and queries the endpoints of all the subintervals. While this non-adaptive strategy offers the best protection for the learner's privacy (the adversary can learn nothing about $X^*$ by observing the locations of the queries), it suffers a very high query complexity of $1/\epsilon$. This observation suggests that an optimal learning strategy would have to strike a delicate balance between adaptive querying and willful obfuscation in order to achieve the optimal trade-off between query complexity and privacy. Prior works @tsitsiklis2018private and @xu2018query developed upper and lower bounds for the optimal query complexity, and quantify the impact of the privacy level $L$ under two formulations of the Private Sequential Learning problem: a *deterministic setting* where $X^* \in [0,1]$ is fixed but arbitrary, and a *Bayesian setting* where $X^*$ is uniformly distributed over $[0,1]$. These results, however, mostly focus on the subset of parameters where the adversary's accuracy requirement, $\delta$, is substantially larger than that of the learner's, $\epsilon$. Under the deterministic setting where $\delta=1/L$, it is shown that the upper and lower bounds almost coincide, yielding an optimal query complexity of about $\log(1/\epsilon)+2L$ @tsitsiklis2018private. In contrast, under the Bayesian setting, it is shown that if we keep both $\delta$ and $L$ fixed, then the optimal query complexity scales as $L\log(1/\epsilon)$ as $\epsilon$ tends to $0$ @xu2018query. Unfortunately, the existing results are not tight, and moreover can perform very poorly within an important parameter regime, where the adversary accuracy requirement $\delta$ can be small or even comparable to that of the learner. For example, under the Bayesian setting, when $\epsilon$ and $\delta$ go to 0 proportionally while $L$ stays fixed, the upper bound proved in @tsitsiklis2018private is of order $L\log(1/\epsilon)$, while the lower bound given in @xu2018query is of order $L$, leaving a large gap. This regime of parameters, however, is of both practical and theoretical interest. On the practical front, it is often the case that an adversary is interested in obtaining the learner's model for the same use as that of the learner. As a result, an estimator with a disproportionately large error margin might be of no practical use to the adversary. On the theoretical front, allowing both $\epsilon$ and $\delta$ to vary simultaneously significantly increases the difficulty of analysis. Indeed, as we explain in detail in Section \[sec:newIdeas\], there is strong evidence that the learner strategies and proof techniques developed in @tsitsiklis2018private and @xu2018query are not sufficiently refined to achieve the optimal query complexity bounds in this regime. By developing new insights and algorithmic ideas, we will establish a tight characterization of the optimal query complexity as a function of $\epsilon, \delta,$ and $L$, improving the existing upper *and* lower bounds over the entire range of these parameters. We further depart from the existing noiseless private learning model by incorporating noisy query responses in the Bayesian setting, a crucial feature for many practical applications including the pricing example and Federated Learning considered in Section \[sec:motivation\]. In this case, we establish query complexity bounds that match up to a constant multiplicative factor that only depends on the noise level. Note that even without privacy considerations, the binary search problem with noisy responses admits highly non-trivial dynamics, and has been studied extensively @feige1994computing [@burnashev1974interval; @waeber2013bisection]; see @pelc2002searching for a more comprehensive survey. Sophisticated search algorithms, such as the probabilistic bisection algorithm @waeber2013bisection and the Burnashev-Zigangirov algorithm @burnashev1974interval, have been developed based on the idea of recursively refining a posterior belief distribution on $X^*$. Unfortunately, just like the bisection strategy, none of these algorithms provide privacy protections for the learner since their query trajectories eventually concentrate around the target $X^*$. Existing private learning strategies designed for the noiseless case also do not admit trivial extensions to the noisy setting. This is not a coincidence: existing strategies heavily exploit the learner's ability to determine, with absolute certainty, a certain small sub-interval that contains the target $X^*$ using only a constant number of queries @tsitsiklis2018private [@xu2018query], which is impossible when responses are noisy. A further challenge arises in the noisy response model where the analysis must carefully track the posterior distributions of $X^*$ for both the learner and the adversary simultaneously. On the one hand, we want the posterior distribution of $X^*$ given the responses to concentrate fast, so that the learner can accurately estimate $X^*$ despite the noises. On the other hand, we need to make sure the posterior distribution given the queries does not concentrate too rapidly, ensuring that the adversary cannot accurately learn. This greatly complicates the design and the analysis of the optimal querying strategy, as a closed-form expression for the posterior distributions is out of reach in this case. #### Relation to data-owner privacy models As mentioned in the Introduction, the Private Sequential Learning model differs significantly from the existing literature on private iterative learning, such as private stochastic gradient descent @song2013stochastic [@abadi2016deep; @agarwal2018cpsgd], private online learning @jain2012differentially, and private Federated Learning @geyer2017differentially [@mcmahan2017learning; @nasr2019comprehensive; @melis2019exploiting]. The focus therein is to protect *data owners' privacy* by preventing the adversary inferring about a data owner from the outputs of learning algorithms, often using the notion of differential privacy @Dwork08. In that setting, a common privacy-preserving mechanism is to inject calibrated noise at each iteration of the learning algorithms. In contrast, our work aims to protect *the learner's privacy* by preventing the adversary inferring the learned model from the learner's queries. As a result, our problem setup, privacy-preserving mechanisms, and main results are significantly different from those in this literature. Our focus on a decision maker's obfuscation task is related, at a high level, to recent studies of information-theoretically sound obfuscation in various sequential decision-making problems @fanti2015spy [@luo2016infection; @tsitsiklis2018delay; @erturk2019dynamically; @tang2020privacy]. However, most of these models focus on protecting data and information already in the position of the decision-maker. As such, they do not address the unique privacy challenges arising in learning, where the learner has to protect a piece of information that they themselves are just in the process of discovering. Summary of main results ----------------------- We offer a preview of our main results in this sub-section. For noiseless responses, we prove almost matching upper and lower bounds on the optimal query complexity in both Bayesian and deterministic settings, including an extension to multi-dimensional private learning. For models with noisy responses, we focus on the Bayesian setting and prove upper and lower bounds that match up to constant multiplicative factor that only depend on the noise level, which coincide with the state-of-the-art noise-dependent characterizations in non-private version of the noisy learning problem @waeber2013bisection. ### Noiseless Responses For noiseless responses, we establish the following characterization of the optimal query complexity $N(\epsilon,\delta,L)$: - Bayesian setting: $$N(\epsilon,\delta,L) \approx \log \frac{1}{L\delta} + L \log \frac{\delta}{\epsilon}.$$ - Deterministic setting: $$N(\epsilon,\delta,L) \approx 2L + \log \frac{\max\left\{ 2^{-L}, \delta \right\}}{\epsilon};$$ Our upper and lower bounds are tight up to an additive factor of $4L$ and 8 for the Bayesian and deterministic settings, respectively. Notably, under the Bayesian setting, when $\delta$ is a constant multiple of $\epsilon$, the optimal query complexity scales as $\log(1/\epsilon)$ plus a constant multiple of $L$, implying that in this regime the correct price for privacy is only additive in $L$, as opposed to multiplicative, as suggested by the upper bound $L\log(1/\epsilon)$ in @tsitsiklis2018private. A comparison between our results and the existing bounds is given in Table \[tab:compare\], with examples illustrated in Figures \[fig:old\_new\_bayes\] and \[fig:old\_new\_det\], under the Bayesian and deterministic settings, respectively. ![Our results in Theorem \[thm:freq\] (solid) versus the best known bounds @tsitsiklis2018private (dashed) for the noiseless deterministic setting, $L=15$ and $\delta= 4\epsilon^{0.9}$. <span data-label="fig:old_new_det"></span>](det_plot.pdf) We further extend these results to a model of high dimensional learning. Suppose the learner aims to estimate a target value $X^*\in [0,1]^d$ by submitting queries along different dimensions: each query provides a binary response on the position of $X_i^*$ relative to the query location, for some dimension $i$. We show that the optimal query complexity $N_d(\epsilon,\delta,L)$ in $d$ dimensions behaves as follows: - Bayesian setting: $$N_d(\epsilon,\delta,L) \approx d\left(\log \frac{1}{L^{1/d}\delta} + L^{1/d} \log \frac{\delta}{\epsilon} \right).$$ - Deterministic setting: $$N_d(\epsilon,\delta,L) \approx d\left(2L^{1/d} + \log \frac{\max\left\{ 2^{-L^{1/d}}, \delta \right\}}{\epsilon}\right).$$ We see that the optimal query complexity suffers from a multiplicative factor of $d$, analogous to the optimal query complexity $d\log(1/\epsilon)$ when there is no privacy constraint. However, the query complexity per dimension depends on $L^{1/d}$, which decreases in $d$. Bayesian setting Deterministic setting ------------------------------- --------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------------------------------- \[-1em\] Existing upper bound $L\lceil\log\frac{1}{L\epsilon}\rceil+L-1$ @tsitsiklis2018private $\left\lceil\log\frac{1}{L\epsilon}\right\rceil+2L$ @tsitsiklis2018private \[-1em\] \[-1em\] Existing lower bound $L\left(\log\frac{\delta}{\epsilon}-3\log\log\frac{\delta}{\epsilon}-1\right)$ @xu2018query $\max\left\{\left\lceil\log\frac{1}{\epsilon}\right\rceil, \left\lceil\log\frac{\delta}{\epsilon}\right\rceil+2L-4\right\}$ @tsitsiklis2018private \[-1em\] \[-1em\] Our upper bound $\left\lfloor \log \frac{1}{L\delta}\right\rfloor+ L\left(\left\lceil\log \frac{\delta}{\epsilon}\right\rceil+2\right)-1$ $\max\left\{\left\lceil\log\frac{1}{\epsilon}\right\rceil+L, \left\lceil\log\frac{\delta}{\epsilon}\right\rceil+2L\right\}$ \[-1em\] \[-1em\] Our lower bound $\left\lfloor \log \frac{1}{L\delta}\right\rfloor+ L\left(\log\frac{\delta}{\epsilon} -2\right)-1$ $\max\left\{\left\lceil\log\frac{1}{\epsilon}\right\rceil+L-8, \left\lceil\log\frac{\delta}{\epsilon}\right\rceil+2L-4\right\}$ : A comparison of our upper and lower bounds on the optimal sample complexity with existing bounds, under the Bayesian and deterministic settings with noiseless query responses.<span data-label="tab:compare"></span> ### Noisy Responses We further consider the noisy response model, where each response can be incorrect with probability $1-p$ for some noise level $p \in (0,1)$. In this case, we need to redefine learner's accuracy, since it is no longer possible for the learner to estimate $X^*$ well with probability 1. We consider two natural definitions of accuracy: say the learner is accurate (a) on average if $\mathbb{E}|\widehat{X}-X^*|\leq \epsilon/2$; and (b) with high probability if $\mathbb{P}\left\{|\widehat{X}-X^*|\leq \epsilon/2\right\}\geq 1-1/M$. Below is our main result for the noisy response model. The optimal query complexities under accuracy definitions (a), (b) satisfy $$\label{eq:noisy.na} N_{\mathsf{avg}}(\epsilon, \delta, L) \asymp L\log \frac{\delta}{\epsilon} + \log \frac{1}{\epsilon};$$ $$\label{eq:noisy.nb} N_{\mathsf{whp}}(\epsilon, M, \delta,L) \asymp L\log\frac{M\delta}{\epsilon} + \log \frac{1}{\epsilon},$$ where $\asymp$ denotes bounds from above and below, up to multiplicative constants that only depend on $p$. By manipulating the constants, can be rewritten as $N_\mathsf{avg}(\epsilon,\delta,L)\asymp \log(1/(L\delta))+L\log(\delta/\epsilon)$. Comparing with the optimal query complexity under the noiseless Bayesian setting, we see that under definition (a), the noise level (parametrized by $p$) only affects the optimal query complexity through the constant multiplier; when the learner needs to be accurate with probability at least $1-1/M$, as per definition (b), there is an extra cost of $\Theta(L\log M)$ queries. As in the noiseless setting, the multiplier $L$ only acts on the terms $\log(\delta/\epsilon)$ and $\log(M\delta/\epsilon)$ under accuracy requirements (a) and (b) respectively, indicating that the learner only starts paying the price for privacy after entering the $\delta$-accurate regime. We comment that even for the vanilla noisy binary search problem with no privacy constraints, finding the exact $p$-dependent multiplicative constant is an open problem. We also comment that as $p\rightarrow 1/2$, we obtain constants in the upper and lower bounds that go to infinity at the same rate of $(p-1/2)^{-2}$. New insights and algorithmic ideas {#sec:newIdeas} ================================== In this section we highlight the new algorithmic ideas and analysis techniques that enable us to obtain sharp bounds. A fundamental difficulty in the design of private learning strategies is that the learner's queries simultaneously serve two, sometimes competing, goals: (1) to gather information about the target $X^*$, and (2) to deceive the adversary as to the target's location. More specifically, our approach begins by recognizing that a single learner query can be used to accomplish one, or multiple, of the following tasks: (i) to obtain information in order to identify a small interval that contains $X^*$ (diameter of this interval depends on the privacy level and adversary accuracy); (ii) to obtain information in order pin-point $X^*$ within the said small interval, down to an $\epsilon$-accuracy; (iii) to serve as a "decoy" to throw off the adversary. The key to our analysis is to put emphasis on understanding the interaction of the queries serving these different types of tasks. We design more efficient querying strategies where multiple tasks are accomplished simultaneously. We also provide sharp analysis on the maximum number of queries that can be used for more than one purpose. In contrast, it appears that prior work has not clearly identified or articulated these separate roles of learner queries. As a result, the existing learner strategies either leave certain types of tasks out of the analysis, or have each of the three types of tasks to be served by separate queries, leading to inefficiencies. Specifically, starting with the Bayesian setting, recall that privacy is breached if an adversary can estimate $X^*$ up to an additive error of $\delta/2$ with probability at least $1/L$. That makes $\delta L$ an appropriate choice for the diameter of the small interval. Queries leading to the identification of such an interval (type (i)) do not significantly compromise the learner's privacy, because the interval's size is too large for the adversary to extract useful information. Beyond this point, however, the learner must submit further queries to narrow the range of $X^*$ down to $\epsilon$, and these queries must be carefully obfuscated. In other words, effective queries at this point should serve to accomplish tasks (ii) and (iii) simultaneously. As such, in the design of the optimal strategy, we will divide learning into two phases: 1. a <span>*pure-learning phase*</span>, corresponding to task (i), where the sole focus of the learner is to identify a small interval containing the target $X^*$, and 2. a <span>*private-refinement phase*</span>, corresponding to tasks (ii) and (iii), where queries serve to simultaneously refine and obfuscate a fine-grained estimate of $X^*$. In comparison, the strategy proposed in @tsitsiklis2018private is more wasteful as the learner would try to tackle all three tasks at the same time, despite there being no need to worry about privacy in the pure-learning phase. For the lower bound, previous work @xu2018query adopts a genie-aided reduction argument, where a $\delta$-length interval containing $X^*$ is assumed to be revealed to the learner from the get-go. Although this reduction simplifies the proof, it cannot lead to a tight lower bound as it ignores all type (i) queries. In order to capture these queries, our lower bound proof introduces an adversary who adopts a more intelligent "truncated proportional-sampling" strategy. The key to this strategy is to disregard a certain number of queries which could negatively impact the adversary's estimator. It is worth pointing out that the number of queries the adversary should disregard is exactly the number of queries submitted in the <span>*pure-learning phase*</span> under the learner's optimal strategy, revealing an elegant duality between the learner and the adversary. The story is slightly different under the deterministic setting. Unlike the Bayesian setting where the adversary only needs to perform well when averaging over a random $X^*$, here the adversary can no longer make guesses. Knowing that the adversary cannot guess, the learner only needs to worry about privacy breaches in a $\delta$-width interval containing $X^*$. Moreover, before reaching this interval, the learner can ensure privacy by injecting possible alternative locations of $X^*$ along each query sequence. That corresponds to reusing queries for tasks (i) and (iii). In particular, we will design a query strategy that mirrors the two-phase architecture described for the Bayesian setting, with a coarse learning phase (i) followed by that of a refinement (ii) . However, obfuscation efforts (iii) are now implemented during the first phase. Our upper bound proof involves designing an efficient strategy that maximizes the number of reused queries. For the lower bound, previous work @tsitsiklis2018private once again assumes that $X^*$ is in a $\delta$-length interval known to the learner, therefore ignoring all the type (i) queries. To obtain the sharp lower bound, our analysis dissects the query sequence, and separately investigates those queries that can be used both for protecting privacy and searching for $X^*$, and those queries that only fulfill one purpose. These intuitions are used also for the extensions of our results to the multi-dimensional model, and the model with noisy responses. However when the responses are noisy, we encounter some additional challenges. For proof of the upper bound in the noisy response model, as we previously mentioned, the main difficulty is caused by an intractable posterior distribution of $X^*$ given the queries. Even queries that are far from $X^*$ can change the shape of the posterior distribution and potentially leak the location of $X^*$ to the adversary. Therefore it is harder to show that a strategy is private. To overcome this difficulty, our analysis involves the design of a querying strategy that forces certain conditional independence structures between the query sequence and some local neighborhood of $X^*$. We then use the conditional independence to carefully control the privacy leakage across all phases of learning. For the lower bound proof, we need to establish a tight lower bound on the learner's probability of error. To that end, two sets of tools are deployed. Part of the proof utilizes information-theoretic arguments. The key step is to establish an upper bound on the <span>*rate of information transfer*</span>, which governs the speed at which the learner can gather information from the responses. For the second part of the proof, we reduce the learner's estimation problem to a family of binary hypothesis testing problems, and bound the testing errors from below using the Bhattacharyya coefficient @kailath1967divergence. #### Organization The remainder of this paper is organized as follows. Section \[sec:problem\] contains the problem formulation and definitions of accuracy and privacy, under both the noiseless and noisy response settings. In Section \[sec:results\] we state the main results on the optimal query complexities. In Section \[sec:alg.noiseless\] we give the construction of our querying strategies when the responses are noiseless. In Section \[sec:lower.noiseless\] we outline the lower bound proof strategies, again with noiseless responses. In Section \[sec:alg.noisy\] we give the construction of our querying strategies and discuss the lower bound proof techniques under the noisy response setting. In Section \[sec:conclusion\] we conclude the paper and give a brief discussion on future work. The full proofs of all the results are contained in the appendix. Problem formulation {#sec:problem} =================== Consider the problem of learning some unknown true value $X^*\in [0,1]$. Let $\widehat{X}$ be the learner's estimator of $X^*$ and $\widetilde{X}$ be the adversary's. The learner submits queries $q_1,q_2,...\in [0,1]$ sequentially. Each time a query $q_i$ is submitted, the learner receives a response $r_i$. When the responses are noiseless, $r_i=\mathds{1}\{X^*\geq q_i\}$. Under the noisy response setting, we assume that $$r_i\sim \text{Bernoulli}(p)\quad \text{ if } X^*\geq q_i, \text{ and }r_i\sim \text{Bernoulli}(1-p)\quad \text{ if } X^*< q_i$$ for some $p\in (1/2,1)$. That is, each observed response can be erroneous with probability $1-p$. The learner's query $q_i$ can depend on all the past queries and responses, and is allowed to incorporate outside randomness. Since all random variables and all random vectors with finite alphabets can be simulated from a random variable uniformly distributed on $[0,1]$, without loss of generality, let $Y\sim \text{Unif}[0,1]$ be the random seed that the learner may use to generate queries. Then $q_i$ can be written as $f_{i-1}(q_1,...,q_{i-1},r_1,..., r_{i-1},Y)$ for some function $f_{i-1}$. Note that the first query $q_1$ is submitted without any information and is only a function of $Y$. Thus we have $q_2=f_1(q_1,r_1, Y)=f_1(f_0(Y), r_1, Y) := \phi_1(r_1, Y)$. It is easy to see that all $q_i$ can be written iteratively as a function of only the past responses and $Y$, i.e., $q_i=\phi_{i-1}(r_1,...,r_{i-1}, Y)$. Then a querying strategy $\phi$ is defined by an initial mapping $f_0: [0,1]\rightarrow [0,1]$ used to generate $q_1$ from $Y$, a sequence of mappings $(\phi_i)_i$ with $\phi_i: \{0,1\}^i\times [0,1]\rightarrow [0,1]$ used to generate the rest of the query sequence, and a final estimator $\widehat{X}$, which can depend on $Y$ and all the queries and responses. The adversary's estimator $\widetilde{X}$, on the contrary, is formed with only access to the queries and the querying strategy $\phi$ but not the responses or the random seed $Y$. The goal of the learner is to design a querying strategy to ensure that she can accurately estimate $X^*$, but the adversary cannot. Different ways to quantify the estimators' performance arise naturally when the responses are noisy versus noiseless. We discuss the two settings separately. Noiseless responses ------------------- Following @tsitsiklis2018private, we consider both the Bayesian setting where $X^*\in [0,1]$ is uniformly distributed on $[0,1]$ and the setting where $X^*$ is deterministic. The two settings call for different definitions for accuracy and privacy, which we shall discuss separately. #### Bayesian setting {#bayesian-setting .unnumbered} We assume $X^*$ is uniformly distributed on $[0,1]$, which is independent from the random seed $Y$, as the learner does not know the true value $X^*$ a priori. We say a strategy $\phi$ is - $\epsilon$-accurate for $\epsilon>0$, if $ \mathbb{P}\{ |\widehat{X}-X^* | \leq \epsilon/2 \}=1; $ - $(\delta,L)$-private for $\delta>0$ and an integer $L\geq 2$, if there is *no* adversary $\widetilde{X}$ such that $$\mathbb{P}\left\{ \left|\widetilde{X}-X^* \right| \leq \delta/2 \right \}> \frac{1}{L}.$$ #### Deterministic setting {#deterministic-setting .unnumbered} Suppose $X^*$ is a deterministic but arbitrary number on $[0,1]$. Then the only source of randomness in the querying strategy is from $Y$. We say a strategy $\phi$ is - $\epsilon$-accurate for $\epsilon>0$, if $$\mathbb{P}\left\{ \left|\widehat{X}-X^* \right|\leq \epsilon/2 \right\}=1, \quad \forall X^* \in [0,1];$$ - $(\delta,L)$-private for $\delta>0$ and an integer $L\geq 2$, if for each query sequence $\bar{q}$, the $\delta$-covering number [^4] of the information set $\mathcal{I}(\bar{q})$ is at least $L$. The information set is defined as the set of all true values that could lead to the query sequence $\bar{q}$ under strategy $\phi$ with non-negligible probability. Note that the query sequence $q$ is a random vector that depends on $X^*$ and $Y$, i.e., $q=q(X^*,Y)$. Formally we define $$\mathcal{I} \left( \bar{q} \right)=\left\{ X^*\in [0,1]: \mathbb{P} \left\{ q(X^*,Y)=\bar{q} \right\}>0 \right\}.$$ Unlike the Bayesian setting, the definition for privacy no longer involves an adversary's estimator $\widetilde{X}$. However, the definition does admit a probabilistic interpretation. One can show (see @tsitsiklis2018private [Appendix A] for a proof) that this definition of privacy is equivalent to the following: for each query sequence $\bar{q}$, there is *no* adversary estimator $\widetilde{X}$ such that for all $X^*\in \mathcal{I}(\bar{q})$, $\mathbb{P}\{ |\widetilde{X}-X^* |\leq \delta/2 \}> \frac{1}{L}$. Compare this to the definition of $(\delta,L)$-privacy in the Bayesian setting, the difference is that when $X^*$ is deterministic, the adversary can no longer average over some prior distribution of $X^*$; instead, for some query sequence she needs to learn well for all admissible values of $X^*$. Knowing that the adversary is not allowed to make guesses, the learner can ensure privacy more easily, by injecting admissible values of $X^*$ into each query sequence. This distinction from the Bayesian setting is reflected by a smaller optimal query complexity, as our results show. For both Bayesian and deterministic settings, we define the optimal query complexity as $$N\left(\epsilon,\delta,L\right)= \min\{ n: \exists\phi\text{ that is both }\epsilon\text{-accurate and }(\delta,L)\text{-private and submits at most }n\text{ queries}\}.$$ Note that for a larger $\delta$ or a larger $L$, the $(\delta,L)$-private constraint is a stronger requirement. Therefore $N(\epsilon,\delta,L)$ is monotone nondecreasing in $\delta$ and $L$. Same as @tsitsiklis2018private, we focus on the regime of parameters $$2\epsilon\leq\delta \leq \frac{1}{L},$$ which is natural and without loss of generality. To see this, on one end of the spectrum, if $\delta>1/L$, then the adversary can make an arbitrary guess to break the privacy constraint: simply choosing $\widetilde{X}=1/2$ yields $\mathbb{P}\{|\widetilde{X}-X^*|\leq \delta/2\}=\delta>1/L$. In this regime the $(\delta,L)$-privacy constraint is too strong to be satisfied by any querying strategy. On the other end of the spectrum, the regime $\delta\leq 2\epsilon$ is arguably not that interesting, as it is unnatural to require an adversary, who only have access to queries but not responses, to estimate $X^*$ almost as accurately as the learner does. Noisy responses under the Bayesian setting ------------------------------------------ In the noisy response setting, we only consider the Bayesian formulation where $X^*\sim \text{Unif}[0,1]$. Since the responses contain noise, no learner that submits a finite number of queries can estimate accurately with probability one. Hence the definition for the learner's accuracy needs to be modified. We consider the following two natural definitions. (a) (accurate on average) We say a querying strategy is $\epsilon$-accurate for $\epsilon>0$ if $\mathbb{E}|\widehat{X}-X^*|\leq \epsilon/2$; (b) (accurate with high probability) We say a querying strategy is $(\epsilon,M)$-accurate for $\epsilon>0$ and $M\geq 2$ ($M$ is not necessarily an integer) if $\mathbb{P}\{|\widehat{X}-X^*|> \epsilon/2\}\leq 1/M$. For any estimator $\widehat{X}$ taking values in $[0,1]$, $\mathbb{E}|\widehat{X}-X^*|\leq \mathbb{P}\{|\widehat{X}-X^*|> \epsilon/2\} + \epsilon/2$. On the other hand it is possible to have $\mathbb{E}|\widehat{X}-X^*|\leq \epsilon/2$ but $\mathbb{P}\{|\widehat{X}-X^*|>\epsilon/2\}>1/2$ however small $\epsilon$ is. Therefore accuracy with high probability is a more stringent constraint on the learner than accuracy on average when $M$ is large compared to $1/\epsilon$. Compared with the noiseless response setting, there is an additional parameter $M$ to be taken into consideration. When designing the querying strategy, the learner needs to control not only the size, but also the probability of error in the presence of noise. The definition of privacy is the same as that in the noiseless case. A querying strategy is called $(\delta,L)$-private if no adversary's estimator $\widetilde{X}$ can achieve $\mathbb{P}\{|\widetilde{X}-X^*|\leq \delta/2\}>1/L$. Define the optimal query complexity under accuracy definition (a) as $$N_\mathsf{avg}\left(\epsilon,\delta,L\right)=\min\left\{n: \exists\phi\text{ that is }\epsilon\text{-accurate, }(\delta,L)\text{-private and submits at most }n\text{ queries}\right\}.$$ Similarly define $$N_\mathsf{whp}\left(\epsilon,M,\delta,L\right)=\min\left\{n: \exists\phi\text{ that is }(\epsilon,M)\text{-accurate, }(\delta,L)\text{-private and submits at most }n\text{ queries}\right\}.$$ Main results {#sec:results} ============ In this section we present the main results in this paper. When the responses are noiseless, we give almost matching upper and lower bounds on the optimal query complexity in both the Bayesian and deterministic settings. When the responses are noisy, under the Bayesian setting, we give upper and lower bounds that match up to multiplicative constants. Noiseless responses {#sec:results.noiseless} ------------------- When the responses are noiseless, we discuss the Bayesian and the deterministic settings separately. #### Bayesian setting {#bayesian-setting-1 .unnumbered} We first focus on the Bayesian setting. It was shown in @tsitsiklis2018private [Proposition B.2] that if $2\epsilon<\delta\leq 1/L$, then $$\label{eq:old.bayes.upper} N(\epsilon,\delta,L) \leq L\log (1/(L\epsilon))+L-1.$$ Notice that this upper bound does not change with $\delta$. Since the private learning task becomes easier for smaller $\delta$, this upper bound is not tight. Subsequently, it was shown in @xu2018query [Theorem 2.1] that if $4\epsilon<\delta< 1/L$, then $$N(\epsilon,\delta,L)\geq L\log(1/\epsilon)-L\log(2/\delta)-3L\log\log(\delta/\epsilon).$$ As pointed out by @xu2018query [Corollary 2.2], if $\delta,L$ stay as fixed constants while $\epsilon\rightarrow 0$, then the above upper and lower bounds imply that the optimal query complexity scales as $L\log (1/\epsilon)$. However if $\delta\rightarrow 0$ as well and is comparable to $\epsilon$, then the upper and lower bounds above can be quite far apart. The following is our first main result. We relax the $\delta>4\epsilon$ constraint in the lower bound to $\delta\geq 2\epsilon$ and obtain sharper upper and lower bounds that almost match in the entire parameter regime. \[Bayesian setting\]\[thm:bayes\] If $2\epsilon \leq \delta\leq 1/L$, then $$\left\lfloor \log \frac{1}{L\delta}\right\rfloor+ L\left(\log\frac{\delta}{\epsilon} -2\right)-1 \leq N(\epsilon, \delta, L) \leq \left\lfloor \log \frac{1}{L\delta}\right\rfloor+ L\left(\left\lceil\log \frac{\delta}{\epsilon}\right\rceil+2\right)-1.$$ The above result captures the impact of the privacy requirement up to an additive gap of $4L$ and has the following nice physical interpretations. The $\log \frac{1}{L\delta}$ factor is the number of queries needed for the learner to estimate $X^*$ within an interval of length $L\delta$, before which the learner does not need to worry about privacy breach by the adversary. The $L\log \frac{\delta}{\epsilon}$ factor is due to the fact that the learner needs to submit at least $\log \frac{\delta}{\epsilon}$ queries within an $\delta$-length interval containing $X^*$ to fulfill the $\epsilon$-accuracy requirement and the extra multiplicative $L$ factor is the price to pay for hiding this $\delta$-length interval from the adversary. If $\delta$ is a constant multiple of $\epsilon$, Theorem \[thm:bayes\] implies that the optimal query complexity scales as $\log(1/\epsilon)$ plus a constant multiple of $L$. Since the bisection method takes $\log(1/\epsilon)$ queries, in this regime the query complexity price to pay for privacy, in terms of $L$, is additive in $L$, in contrast to multiplicative as suggested by . #### Deterministic setting {#deterministic-setting-1 .unnumbered} Next we shift to the deterministic setting. It was shown in @tsitsiklis2018private [Theorem 4.1] that $$\label{eq:freq.lower} \max\left\{\log\frac{1}{\epsilon},\log \frac{\delta}{\epsilon}+2L-4\right\} \leq N(\epsilon,\delta,L) \leq \log \frac{1}{L\epsilon}+2L.$$ Again the upper bound cannot be tight because it does not vary with $\delta$. In the following theorem we sharpen both the upper and lower bounds, shrinking the gap between them to only 8 queries. \[Deterministic setting\]\[thm:freq\] If $2\epsilon\leq \delta\leq 1/L$, then $$\max\left\{\left\lceil\log\frac{1}{\epsilon}\right\rceil+L-8, \left\lceil \log\frac{\delta}{\epsilon}\right\rceil+2L-4\right\} \leq N(\epsilon,\delta,L) \leq \max\left\{\left\lceil\log\frac{1}{\epsilon}\right\rceil+L, \left\lceil \log\frac{\delta}{\epsilon}\right\rceil+2L\right\}.$$ The above result captures the impact of the privacy requirement up to an additive gap of 8 queries and can be understood intuitively as follows. Note that the by Theorem \[thm:freq\], the optimal query complexity is approximately $\max\{2L,L+\log(1/\delta)\}+\log(\delta/\epsilon)$. Recall that to protect privacy in the deterministic setting, the $\delta$-covering number of the information set needs to be at least $L$. To this end, the learner needs to "plant" at least $L$ pairs of $\epsilon$-separated queries such that each pair is at least $\delta$ away from the others. The $\max\{ 2L, L+\log (1/\delta) \} $ factor is the number of queries needed for the learner to plant these $L$ pairs of neighboring queries, while searching for a $\delta$-length interval containing $X^*$. The $\log (\delta/\epsilon)$ factor is the number of extra queries that the learner needs to submit within the $\delta$-length interval to fulfill the $\epsilon$-accuracy requirement. Adding up these two factors yields the optimal query complexity established in Theorem \[thm:freq\]. We can see from Theorem \[thm:freq\] that the lower bound in is tight when $\delta\geq 2^{-L}$. However when $\delta< 2^{-L}$, the optimal query complexity is roughly $2L+\log (2^{-L}/\epsilon)=L+\log(1/\epsilon)$; and the query complexity price to pay for privacy, in terms of $L$, is an additive factor of $L$. Multidimensional private learning {#sec:multi.dim} --------------------------------- In this section we extend our results in Section \[sec:results.noiseless\] to $d$ dimensions for $d>1$. Suppose the true value $X^*$ is in $\mathbb{R}^d$. The closeness of estimators to $X^*$ is measured with respect to the $\|\cdot\|_\infty$ norm, and the accuracy and privacy levels of a querying strategy are defined accordingly. By using the $\|\cdot\|_\infty$ norm to measure the adversary's accuracy, we are allowing the adversary to accurately estimate one or some of the coordinates of $X^*$. That is because in high dimensions, a single coordinate of the model parameter often does not provide meaningful predictive power. As a result, we only declare privacy breach when the adversary gets "close" to $X^*$ in $\mathbb{R}^d$. Here we use the $\|\cdot\|_\infty$ norm to measure closeness. But we comment that as a consequence of our result, if the Euclidean norm were used, the complexity would only differ by a multiplicative constant. We assume that the learner is only allowed to ask questions of the type "is $X_i^*\geq q$?" for some $i\in [d]$ and $q\in [0,1]$. Denote the optimal query complexity in $d$-dimensions as $N_d(\epsilon,\delta,L)$. Below we state our results for the Bayesian and deterministic settings. The proofs are contained in the appendix. #### Bayesian setting {#bayesian-setting-2 .unnumbered} Suppose $X^*$ is uniformly distributed on $[0,1]^d$. We say a querying strategy $\phi$ is - $\epsilon$-accurate for $\epsilon>0$, if $ \mathbb{P} \{ \|\widehat{X}-X^* \|_\infty \leq \epsilon/2 \}=1; $ - $(\delta,L)$-private for $\delta>0$ and an integer $L\geq 2$, if there is no adversary $\widetilde{X}$ such that $ \mathbb{P}\{\|\widetilde{X}-X^*\|_\infty\leq \delta/2\}>1/L. $ We focus on the parameter regime $2\epsilon\leq \delta \leq 1/\lceil L^{1/d}\rceil$. We have argued in Section \[sec:problem\] why $2\epsilon\leq\delta$ is reasonable to assume. To justify the other end of the spectrum, note that if $\delta>1/L^{1/d}$, then the naive estimator $\widetilde{X}=1/2$ achieves $\mathbb{P}\{\|\widetilde{X}-X^*\|_\infty\leq \delta/2\}=\delta^d>1/L$, making it impossible to fulfill the privacy constraint. Denote ${\gamma}={\gamma}(L,d)=L^{1/d}$. Below is our main result on the multidimensional optimal query complexity in the Bayesian setting. \[Bayesian setting\]\[thm:bayes.ddim\] If $2\epsilon\leq \delta \leq 1/\lceil {\gamma}\rceil$, then $$N_d(\epsilon,\delta,L)\leq d\left(\left\lfloor \log\frac{1}{\lceil {\gamma}\rceil \delta}\right\rfloor + \left\lceil {\gamma}\right\rceil \left(\left\lceil \log\frac{\delta}{\epsilon}\right\rceil+2\right)-1\right).$$ Furthermore, assuming that the queries on $X_i^*$ depend only on the responses to the previous queries on $X_i^*$ and some random seed $Y_i$, with $Y_1,...,Y_d$ mutually independent, then $$N_d(\epsilon,\delta,L)\geq d\left(\left\lfloor \log\frac{1}{{\gamma}\delta}\right\rfloor + {\gamma}\left(\log\frac{\delta}{\epsilon}-2\right)-1\right).$$ #### Deterministic setting {#deterministic-setting-2 .unnumbered} Suppose $X^*\in [0,1]^d$ is deterministic, we say a querying strategy $\phi$ is - $\epsilon$-accurate for $\epsilon>0$, if $ \mathbb{P}\{ \|\widehat{X}-X^* \|_\infty\leq \epsilon/2 \}=1$ for all $X^* \in [0,1]^d$; - $(\delta,L)$-private for $\delta>0$ and an integer $L\geq 2$, if for each query sequence $\bar{q}$, the $\delta$-covering number of the information set $\mathcal{I}(\bar{q})$ is at least $L$. [^5] \[Deterministic setting\]\[thm:freq.ddim\] If $2\epsilon\leq \delta \leq 1/\lceil {\gamma}\rceil$, then $$d\left(2{\gamma}+ \log\frac{\max\{2^{-\lceil {\gamma}\rceil}, \delta\}}{\epsilon}-8\right)\leq N_d(\epsilon,\delta,L) \leq d\left(2\left\lceil {\gamma}\right\rceil + \left\lceil \log\frac{\max\{2^{-\lceil {\gamma}\rceil}, \delta\}}{\epsilon}\right\rceil+1\right).$$ From the upper and lower bounds in the theorem statements, we see that in $d$-dimensions the optimal query complexity suffers from a multiplicative factor of $d$. This is consistent with the optimal query complexity $d\log (1/\epsilon)$ when there is no privacy constraint. The query complexity for each dimension depends on ${\gamma}=L^{1/d}.$ As $d$ grows, the price to pay for privacy per dimension decreases. In the extreme case where $d\rightarrow \infty$ with $L$ fixed, the optimal query complexity behaves like $d\log (1/\epsilon)$ in both the Bayesian and the deterministic settings, making the privacy constraint obsolete in high dimensions. One interesting direction to strengthen Theorem \[thm:bayes.ddim\] and Theorem \[thm:freq.ddim\] is to allow the learner to query "is $X^*$ in $H$?" where $H$ is an arbitrary half-space in $\mathbb{R}^d$. The upper bounds are still valid since every comparison query corresponds to a half-space. However for both the Bayesian and the deterministic setting, our current lower bound proof strategies do not accommodate this wider class of queries. This variant of the problem was studied by @xu2019query [Theorem 2] under the Bayesian setting, where the author gives a lower bound of $c_1\delta^{d-1}L\log(\delta/\epsilon)-c_2 L$ for constants $c_1,c_2$ that depend on $d$. The lower bound is obtained via a hyperplane transversality argument. More specifically, divide $[0,1]^d$ into $\delta$-wide cubes and consider an adversary who samples from the cubes that intersect
{'source': 'arXiv_out/1909'}