Efficient Adaptive Data Analysis over Dense Distributions Joon Suk Huh Abstract Modern data workflows are inherently adaptive, repeatedly querying the same dataset to refine and validate sequential decisions, but such adaptivity can lead to overfitting and invalid statistical inference. Adaptive Data Analysis (ADA) mechanisms address this challenge; however, there is a fundamental tension between computational efficiency and sample complexity. For T T rounds of adaptive analysis, computationally efficient algorithms typically incur suboptimal 𝒪 ⁡ ( T ) \mathcal{O}(\sqrt{T}) sample complexity, whereas statistically optimal 𝒪 ⁡ ( log ⁡ T ) \mathcal{O}(\log T) algorithms are computationally intractable under standard cryptographic assumptions. In this work, we shed light on this trade-off by identifying a natural class of data distributions under which both computational efficiency and optimal sample complexity are achievable. We propose a computationally efficient ADA mechanism that attains optimal 𝒪 ⁡ ( log ⁡ T ) \mathcal{O}(\log T) sample complexity when the data distribution is dense with respect to a known prior. This setting includes, in particular, feature–label data distributions arising in distribution-specific learning. As a consequence, our mechanism also yields a sample-efficient (i.e., 𝒪 ⁡ ( log ⁡ T ) \mathcal{O}(\log T) samples) statistical query oracle in the distribution-specific setting. Moreover, although our algorithm is not based on differential privacy, it satisfies a relaxed privacy notion known as Predicate Singling Out (PSO) security ( Cohen and Nissim 2020 ) . Our results thus reveal an inherent connection between adaptive data analysis and privacy beyond differential privacy. \coltauthor Computer Science Department, University of Wisconsin–Madison keywords Adaptive Data Analysis, Private Data Analysis 1 Introduction The inherent adaptivity prevalent in modern data science workflows, while undeniably powerful for discovery and iterative refinement, introduces significant challenges to statistical validity. The repeated interaction with and reuse of the same dataset for both hypothesis generation and subsequent validation can lead to overfitting or the generation of false discoveries (often colloquially termed “p-hacking” or attributed to “researcher degrees of freedom”). Such issues result in findings that may appear statistically significant within the analyzed sample but fail to generalize reliably to the underlying population from which the data were drawn. This breakdown of classical statistical guarantees contributes directly to the reproducibility crisis observed across various empirical scientific fields ( Ioannidis 2005 ; Gelman and Loken 2014 ) . The core problem, often termed “double-dipping”, arises when the same data is utilized first to inform the analysis strategy and then again to validate the resulting conclusions, thereby coupling the randomness in the inferential target with the randomness in the data used for inference. Adaptive data analysis (ADA) ( Dwork et al. 2015c ) is a modern algorithmic framework aimed at enabling statistically valid inference in adaptive settings, using as few samples as possible. At its core is the design of an intermediary, called an ADA mechanism, that mediates between the data and the analyst, providing answers to adaptively chosen queries while ensuring statistical validity. Since the foundational work of Hardt and Ullman 2014 ; Dwork et al. 2015c , there has been extensive progress in developing algorithmic techniques for preserving validity in adaptive settings ( Dwork et al. 2015a ; Dwork et al. 2015b ; Cummings et al. 2016 ; Russo and Zou 2016 ; Rogers et al. 2016 ; Bassily et al. 2016 ; Smith 2017 ; Feldman and Steinke 2017 ; Feldman and Steinke 2018 ; De Stefani and Upfal 2019 ; Zrnic and Hardt 2019 ; Jung et al. 2020 ; Fish et al. 2020 ; Rogers et al. 2020 ; Kontorovich et al. 2022 ; Dagan and Kur 2022 ; Marchant and Rubinstein 2024 ; Blanc 2025 ) , primarily based on Differential Privacy (DP) ( Dwork et al. 2014 ) and/or algorithmic stability ( Bassily et al. 2016 ; Smith 2017 ; Shenfeld and Ligett 2019 ; Shenfeld and Ligett 2023 ) . In the standard setting, an analyst asks linear queries q(x)\in\mathbb{R} and seeks to estimate expectations of the form \expec_{x\sim\mathcal{D}}[q(x)] . When the queries are fully adaptive, existing computationally efficient approaches achieve \mathcal{O}(\sqrt{T}) sample complexity, where T is the number of query rounds. This rate is tight for general data distributions: an \Omega(\sqrt{T}) lower bound holds for any computationally efficient ADA mechanism under standard cryptographic assumptions, such as the existence of one-way functions ( Steinke and Ullman 2015 ; Steinke and Ullman 2016 ; Bun et al. 2017 ; Ullman et al. 2018 ; Nissim et al. 2023 ; Dinur et al. 2023 ) . In contrast, data sketching-based methods such as Private Multiplicative Weights (PMW), which maintain an internal sketch of the dataset ( Hardt and Rothblum 2010 ) , can achieve \mathcal{O}(\log T) sample complexity, but are computationally intractable, as maintaining such a sketch often requires time exponential in the data dimension n . Hence, there is a general tension between computational efficiency and sample efficiency in adaptive data analysis. However, existing hardness results that rule out efficient o(\sqrt{T}) sample complexity assume that the mechanism must work for arbitrary data distributions. This observation raises a natural question: Is there a natural class of data distributions \mathcal{D} that admits both \mathcal{O}(\log T) sample complexity and computational efficiency? We answer this question in the affirmative. Specifically, we show that for any sufficiently well-spread (“dense”) distribution with respect to a known prior (which may be uniform), there exists an ADA mechanism that is both computationally efficient and sample efficient, with sample complexity growing only logarithmically in the number of queries. Such distributions arise naturally in distribution-specific learning ( Kharitonov 1993 ; Balcan and Long 2013 ; Shamir 2018 ; Blanc et al. 2025 ) , including distributions over pairs (x,f(x)) where x is drawn from a known marginal distribution over features and f is an unknown Boolean function. 1.1 Main Results Efficient ADA Mechanism for Dense Distributions. We first present a computationally efficient ADA mechanism for dense data distributions. Density is defined with respect to a known reference (prior) distribution. Specifically, we assume that both the mechanism and the analyst are given a prior distribution \mathcal{D}_{g} generated by a known, efficiently computable function g:\{0,1\}^{n}\rightarrow\mathcal{I} over a finite domain \mathcal{I} . We then consider an unknown target distribution \mathcal{D} that is \lambda -dense in \mathcal{D}_{g} , meaning that \Pr_{i\sim\mathcal{D}}[I=i]\leq\frac{1}{\lambda}\Pr_{i\sim\mathcal{D}_{g}}[I=i] for all i\in\mathcal{I} . Intuitively, this condition implies that one could sample from \mathcal{D} using \mathcal{D}_{g} via rejection sampling with acceptance probability at least \lambda . However, this form of “rejection samplability” does not imply that the analyst can perform data analysis over the unknown distribution \mathcal{D} , since rejection sampling requires explicit knowledge of the probability mass function of \mathcal{D} . Theorem 1 (Restatement of Theorem 5 , 6 ) . Let g:\{0,1\}^{n}\rightarrow\mathcal{I} be an efficiently computable function. For any distribution \mathcal{D} over \mathcal{I} that is \lambda -dense with respect to the distribution \mathcal{D}_{g} generated by g , there exists an ADA mechanism that answers \expec_{k\sim\mathcal{D}}[q_{t}(k)] to within \epsilon accuracy for any sequence of T adaptively chosen queries (q_{t})_{t\in[T]} , where each q_{t}:\mathcal{I}\rightarrow\{-1,1\} , using only M\in\mathcal{O}(\lambda^{-2}\epsilon^{-4}\cdot\log T) i.i.d. samples from \mathcal{D} , and running in time \mathsf{poly}(n,\epsilon^{-1},\lambda^{-1},T) . Notably, the sample complexity is independent of the ambient data dimension n , matching the \mathcal{O}(\log T) sample complexity achievable in the non-adaptive setting via Hoeffding’s inequality and the union bound. Sample-efficient Distribution-Specific Statistical Query Oracle. Why, then, do we care about dense target distributions? A natural example arises in canonical machine learning settings. Consider a distribution \mathcal{D} over pairs (X,Y) , where X\sim\mathcal{D}_{h} for some known marginal distribution \mathcal{D}_{h} over a feature space \mathcal{X} generated by h:\{0,1\}^{n-1}\rightarrow\mathcal{X} , and Y=f(X)\in\{-1,1\} for an unknown labeling function f:\mathcal{X}\rightarrow\{-1,1\} . In this case, we can choose a prior distribution \mathcal{D}_{g} generated by g(r)\coloneq(h(r_{1:n-1}),(r_{n}-1)/2) for an n -bit seed r , and one can verify that \mathcal{D} is (1/2) -dense in \mathcal{D}_{g} . Here, the distribution \mathcal{D} is unknown to the analyst due to the unknown labeling function f , while the marginal distribution over features, \mathcal{D}|_{X} , is known and efficiently samplable via h . This setting corresponds to the classical notion of distribution-specific learning, and any mechanism that answers (linear) queries with respect to such a distribution \mathcal{D} implements a distribution-specific Statistical Query (SQ) oracle ( Kearns 1998 ) . Consequently, our mechanism naturally yields a sample-efficient distribution-specific SQ oracle, as formalized in Theorem 7 . Privacy Guarantee. Many existing ADA mechanisms are built on differential privacy (DP) and thus often inherit formal DP guarantees. In contrast, our mechanism is not based on DP and does not provide DP guarantees. Nevertheless, perhaps surprisingly, it still offers a meaningful privacy guarantee: it satisfies Predicate Singling Out (PSO) security ( Cohen and Nissim 2020 ) , a notion designed to capture the “singling out” risk addressed by the European Union’s General Data Protection Regulation (GDPR). While PSO security is strictly weaker than DP, it rules out a broad class of privacy attacks and remains relevant in settings where DP may be unnecessarily conservative. In our case, PSO security (Theorem 9 ) follows from an argument that builds on a key lemma from our sample complexity analysis and, notably, requires no explicit noise addition. 1.2 Technical Overview Unlike many computationally efficient ADA mechanisms that achieve \mathcal{O}(\sqrt{T}) sample complexity, our mechanism does not rely on differential privacy or algorithmic stability arguments. Instead, it builds on an iterative data sketching strategy inspired by the Private Multiplicative Weights (PMW) algorithm ( Hardt and Rothblum 2010 ) . The goal is to maintain an internal sketch of the dataset S\subseteq\{0,1\}^{n} such that linear statistical queries evaluated on the sketch closely approximate their values on S . While PMW achieves this by maintaining a distribution over the data universe and updating it via multiplicative weights, this approach incurs computational cost proportional to the domain size 2^{n} , which is intractable. We avoid this intractability by using (unconstrained) Online Gradient Descent (OGD) ( Zinkevich 2003 ) over a unit ball and sketching S within this ball. Specifically, our algorithm can be viewed as a lazy version of OGD, where an update is performed only when the approximation error exceeds a prescribed threshold. This lazy update rule, together with the standard regret bound for OGD, implies that the number of such updates, and hence the number of vectors stored in the sketch, is bounded by \mathcal{O}(\lambda^{-2}\epsilon^{-2}) . Crucially, the intractability of PMW is avoided because answers can be reconstructed efficiently from the sketch via randomized inner-product estimation, as the sketch vectors lie within the unit ball of \ell^{2} geometry. Such sketch vectors can faithfully represent \mathcal{D} since \mathcal{D} is \lambda -dense in \mathcal{D}_{g} for some known sampling function g , which allows \mathcal{D} to be represented as a 2^{n} -dimensional vector in the seed space of g . The bounded number of updates (mistakes) of order \mathcal{O}(\lambda^{-2}\epsilon^{-2}) in constructing the internal sketch of the dataset implies the existence of a succinct transcript of the mechanism’s update behavior, of size \mathcal{O}(\lambda^{-2}\epsilon^{-2}\cdot\log T) bits. As this transcript can simulate the mechanism’s exact behavior, it can be used to reconstruct all queries asked by \mathcal{A} , using only the internal randomness of the mechanism and the analyst, and without access to the sample S . This transcript plays a central role in ensuring statistical validity. Since it determines the entire query sequence, we can apply standard concentration arguments, namely Hoeffding’s inequality and the union bound, over the small space of possible transcripts. This yields uniform convergence, guaranteeing that |q_{t}(S)-q_{t}(\mathcal{D})|\in\mathcal{O}(\epsilon) for all t\in[T] with high probability, with sample size |S|\in\mathcal{O}(\lambda^{-2}\epsilon^{-4}\log T) . 1.3 Related Work Many algorithmic frameworks for adaptive data analysis (ADA) are based on differential privacy or algorithmic stability, as studied in ( Bassily et al. 2016 ; Smith 2017 ; Feldman and Steinke 2018 ; Shenfeld and Ligett 2019 ; Jung et al. 2020 ; Blanc 2025 ) . These approaches provide strong generalization guarantees under adaptivity and run efficiently, but typically incur a sample complexity of \mathcal{O}(\sqrt{T}) . Closer to our approach, the idea of answering queries by reconstructing (or sketching) a dataset was introduced in Blum et al. 2013 , which used the exponential mechanism ( McSherry and Talwar 2007 ) both to reconstruct the dataset and to privately answer non-adaptive queries. This was extended in the seminal work of Hardt and Rothblum 2010 , which proposed the Private Multiplicative Weights (PMW) algorithm, based on the multiplicative weights framework ( Freund and Schapire 1999 ; Arora et al. 2012 ) , to handle adaptive queries while satisfying differential privacy. Notably, while PMW is designed as a differentially private algorithm, it also serves as an ADA mechanism with \mathcal{O}(\log T) sample complexity and later extended beyond linear queries ( Ullman 2015 ) . However, it is computationally intractable in general, as it requires sampling from Gibbs distributions over exponentially large domains like \{0,1\}^{n} . 1.4 Organization In § 2 , we introduce the adaptive data analysis framework and define (pseudo)dense data distributions. In § 3 , we present our efficient ADA mechanism, denoted \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} . In § 4 , we establish the correctness and sample complexity guarantees of \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} . Finally, in § 5 , we introduce the Predicate Singling Out (PSO) privacy notion and show that \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} satisfies PSO security. 2 Preliminaries In this section, we provide the necessary background on adaptive data analysis and introduce key definitions used throughout the paper. Notation. We denote the set \{1,\dots,N\} by [N] . The sign function \mathsf{sign}(x) returns +1 if x\geq 0 and -1 otherwise. The set of non-negative real numbers is denoted by \mathbb{R}_{+} . For any vector v\in\mathbb{R}^{N} , we write \|v\| to denote its Euclidean norm. The N -dimensional Euclidean unit ball is defined as \mathbb{B}^{N}\coloneq\{v\in\mathbb{R}^{N}:\|v\|\leq 1\} . For any finite set S , U_{S} denotes the uniform distribution over S . Finally, for any function q:[N]\rightarrow\mathbb{R} and any distribution \mathcal{D} over [N] , we define q(\mathcal{D})\coloneq\expec_{i\sim\mathcal{D}}[q(i)] as the expectation of q under \mathcal{D} . For any subset S\subseteq[N] , we write q(S)\coloneq q(U_{S})=\frac{1}{|S|}\sum_{i\sim S}q(i) , i.e., the average of q over elements in S . For the sake of presentation, we identify the n -bit Boolean cube \{0,1\}^{n} with [N] , where N=2^{n} , throughout the paper. \SetAlgorithmName GameGameList of Games {algorithm2e} [t] \mathsf{AQ}_{N,M,T}[\mathcal{A}\rightleftharpoons\mathcal{M}] : Adaptive Query Game \DontPrintSemicolon \mathcal{A} chooses a distribution \mathcal{D} over \mathcal{I} unknown to \mathcal{M} . A multiset S of M i.i.d. samples from \mathcal{D} is given to \mathcal{M} but not to \mathcal{A} . \For t\in[T] \mathcal{A} chooses a query q_{t}\in\{-1,1\}^{\mathcal{I}} given (q_{1},a_{1},\dots,q_{t-1},a_{t-1}) . \mathcal{M} outputs an answer a_{t}\in[-1,1] given (q_{1},a_{1},\dots,q_{t-1},a_{t-1},q_{t}) . 2.1 Problem Setting: Adaptive Data Analysis. An adaptive data analysis (ADA) mechanism \mathcal{M} is an algorithm that holds a sufficient amount of i.i.d. data S\subseteq\mathcal{I} drawn from an unknown distribution \mathcal{D} over a finite domain \mathcal{I} , and provides answers a_{t} to a sequence of adaptively chosen Boolean queries (q_{t})_{t\in[T]} , where each q_{t}:\mathcal{I}\rightarrow\{-1,1\} , selected by an analyst (or adversary) \mathcal{A} . The goal is to ensure that these answers are \epsilon -accurate; that is, |a_{t}-q_{t}(\mathcal{D})|\leq\epsilon for all t\in[T] . In the non-adaptive setting, where all queries are chosen in advance, it suffices for \mathcal{M} to hold |S|\in\mathcal{O}(\log T) samples, by standard concentration arguments (e.g., Hoeffding’s inequality and the union bound). Our goal is to retain this \mathcal{O}(\log T) sample complexity even when queries are chosen adaptively, under certain assumptions on the data distribution, while ensuring that the ADA mechanism remains computationally efficient ; that is, it runs in time \mathsf{poly}(\epsilon^{-1},\lambda^{-1},\log N,|S|,T) . We formalize adaptive data analysis as a game between the ADA mechanism \mathcal{M} and the analyst (or adversary) \mathcal{A} , referred to as the Adaptive Query Game , depicted in Game 2 . Note that allowing \mathcal{A} to choose the distribution \mathcal{D} in Game 2 only strengthens the \mathcal{A} ; thus, our result also applies to the more natural setting in which \mathcal{D} is unknown to both the analyst \mathcal{A} and the mechanism \mathcal{M} . Let \Pr_{\mathsf{AQ}_{N,M,T}[\mathcal{A}\rightleftharpoons\mathcal{M}]} denote the probability distribution over all random variables (such as the a_{t} s and q_{t} s) that are realized during the execution of the game \mathsf{AQ}_{N,M,T}[\mathcal{A}\rightleftharpoons\mathcal{M}] . We then define accuracy of \mathcal{M} as follows: Definition 2 (Accuracy) . A mechanism \mathcal{M} is said to be (\epsilon,\delta) -accurate with respect to \mathcal{A} with sample complexity M_{0} if, for all M\geq M_{0} , \displaystyle\Pr_{\mathsf{AQ}_{N,M,T}[\mathcal{A}\rightleftharpoons\mathcal{M}]}\Big[\forall t\in[T],\ \left|a_{t}-q_{t}(\mathcal{D})\right|\leq\epsilon\Big]\geq 1-\delta, where the probability is taken over the internal randomness of both \mathcal{M} and \mathcal{A} . Dense Data Distribution. We assume that both the analyst and the mechanism have access to a function g:[N]\rightarrow\mathcal{I} for some finite domain \mathcal{I} , and hence can sample from the distribution \mathcal{D}_{g} , where K\sim\mathcal{D}_{g} is given by I\coloneq g(X) with X\sim U_{[N]} . We further assume that g is efficiently computable, namely in \mathsf{poly}(\log N) time. We say that a distribution \mathcal{D} over \mathcal{I} is (\lambda,\mathcal{D}_{g}) -dense if \Pr_{i\sim\mathcal{D}}[I=i]\leq\frac{1}{\lambda}\Pr_{i\sim\mathcal{D}_{g}}[I=i] for all i\in\mathcal{I} . Our algorithm, in fact, applies to a slightly broader class of distributions that includes not only truly dense distributions but also pseudodense ones, namely distributions that are indistinguishable from dense distributions from the perspective of the analyst. We formalize this notion below. Definition 3 (Pseudodensity) . For any adversary \mathcal{A} , let \mathcal{Q}^{\mathcal{A}}\subseteq\{-1,1\}^{\mathcal{I}} denote the set of all queries that \mathcal{A} may output at any point, on any input, and under any internal randomness. We say that a distribution \mathcal{D} over \mathcal{I} is (\epsilon,\lambda,\mathcal{D}_{g}) - pseudodense with respect to \mathcal{A} if there exists a (\lambda,\mathcal{D}_{g}) -dense distribution \mathcal{D}^{\prime} over \mathcal{I} such that |q(\mathcal{D})-q(\mathcal{D}^{\prime})|\leq\epsilon for all q\in\mathcal{Q}^{\mathcal{A}} . Moreover, if \mathcal{A} almost surely selects a distribution \mathcal{D} that is (\epsilon,\lambda,\mathcal{D}_{g}) -pseudodense with respect to itself, we say that \mathcal{A} is an (\epsilon,\lambda,\mathcal{D}_{g}) - pseudodense challenger . Working in the Seed Space Without Loss of Generality. Since the prior generator g is known, it is fixed throughout the AQA game. We can therefore absorb g into the analyst’s queries by composing them with g . Concretely, we replace each query q_{t}:\mathcal{I}\rightarrow\{-1,1\} with the pullback query q_{t}\circ g:[N]\rightarrow\{-1,1\} , so that the analyst effectively asks q_{t}(g(\cdot)) over the seed space [N]=\{0,1\}^{n} . Under this viewpoint, we may work directly over the seed space and identify \mathcal{I}=[N] without loss of generality. From this point onward, we adopt this convention throughout the remainder of the paper. Accordingly, we focus on (\epsilon,\lambda,U_{[N]}) -pseudodense distributions and challengers. 2.2 Application: Implementing Distribution-Specific Statistical Query Oracle The above setting also captures a standard distribution specific learning scenario. Consider a distribution \mathcal{D}_{h,f} over labeled examples (X,Y) , where X is drawn from a known marginal distribution \mathcal{D}_{h} over a finite feature space \mathcal{X} , generated by an efficient sampler h , and Y\coloneq f(X)\in\{-1,1\} for an unknown labeling function f:\mathcal{X}\to\{-1,1\} . Define a prior distribution \mathcal{D}_{g} by letting I\sim\mathcal{D}_{g} be given as I\coloneq g(R)\coloneq(h(R_{1:n-1}),R_{n}) for a uniformly random seed R\sim U_{[N]} . Equivalently, \mathcal{D}_{g} samples a feature vector X\sim\mathcal{D}_{h} together with an independent uniform label bit. Under this construction, the true labeled distribution \mathcal{D} is (1/2) -dense with respect to \mathcal{D}_{g} . Consequently, an ADA mechanism designed for (\lambda,\mathcal{D}_{g}) -dense distributions can be interpreted as providing a distribution-specific statistical query interface for the labeled distribution \mathcal{D}_{h,f} . Definition 4 (Distribution-specific SQ oracle ( Kearns 1998 ) ) . Fix a known distribution \mathcal{D}_{h} over a feature space \mathcal{X} and an unknown labeling function f:\mathcal{X}\to\{-1,1\} . Let \mathcal{D}_{h,f} denote the induced distribution over \mathcal{X}\times\{-1,1\} obtained by sampling X\sim\mathcal{D}_{h} and setting Y\coloneq f(X) . A distribution-specific statistical query oracle, denoted \mathsf{DSQ}_{h}(f,\epsilon) , takes as input a query function \phi:\mathcal{X}\times\{-1,1\}\to[-1,1] and returns a value v satisfying \displaystyle\left|v-\phi(\mathcal{D}_{h,f})\right|\leq\epsilon. An algorithm that interacts with the unknown f only through calls to \mathsf{DSQ}_{h}(f,\epsilon) is called a distribution-specific SQ algorithm (with respect to \mathcal{D}_{h} ). From the discussion above, it is straightforward that an efficient ADA mechanism yields an implementation of \mathsf{DSQ}_{h}(f,\epsilon) using only \mathcal{O}(\log T) samples, up to a minor mismatch in the query range. In the standard DSQ model, a query \phi may take values in [-1,1] , whereas in our setting the queries are Boolean-valued in \{-1,1\} . This mismatch can be handled by a standard randomization argument: for any fixed \phi:X\times\{-1,1\}\rightarrow[-1,1] , one can sample i.i.d. Boolean queries (q^{\phi}_{i})_{i\in[B]} , where each q^{\phi}_{i}:X\times\{-1,1\}\rightarrow\{-1,1\} satisfies \expec[q^{\phi}_{i}(x,y)|(x,y)]=\phi(x,y) . Then \frac{1}{B}\sum_{i=1}^{B}q^{\phi}_{i}(\mathcal{D}_{h,f}) is an unbiased estimator of \phi(\mathcal{D}_{h,f}) , and by Hoeffding’s inequality it concentrates around \phi(\mathcal{D}_{h,f}) at rate \mathcal{O}(B^{-1/2}) . Choosing B sufficiently large, we obtain \frac{1}{B}\sum_{i=1}^{B}q^{\phi}_{i}(\mathcal{D}_{h,f})\approx\phi(\mathcal{D}_{h,f}) , which reduces [-1,1] -valued queries to Boolean queries in our framework. {algorithm2e} [t] \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} : Adaptive Query Answering via Online Gradient Descent \SetKwComment Comment \color blue \triangleright \DontPrintSemicolon Oracle: Adversary \mathcal{A} . Input: Data S\subseteq[N] (multiset), accuracy \epsilon>0 , failure probability \delta>0 , and density \lambda>0 . \mathcal{G}\leftarrow\emptyset \Comment * \color blue \mathcal{G} is a maintained multiset of gradients. \For t\in[T] Get a query q_{t} from \mathcal{A} . \hat{u}_{t}\leftarrow\mathsf{IP}_{\mathsf{est}}(q_{t},\mathcal{G};\lambda\epsilon/8,\delta/2T) \Comment * \color blue \mathsf{IP}_{\mathsf{est}} is given in Alg. 3 \If |\hat{u}_{t}-\lambda q_{t}(S)|>\lambda\epsilon/2 and |\mathcal{G}|\leq 128(\lambda\epsilon)^{-2} s_{t}\leftarrow\mathsf{sign}(\hat{u}_{t}-\lambda q_{t}(S)) \mathcal{G}\leftarrow\mathcal{G}\cup\big\{-\lambda\epsilon s_{t}q_{t}/16\big\} \Comment * \color blue Update \mathcal{G} . a_{t}\leftarrow\ Round q_{t}(S) to the nearest multiple of \epsilon/2 . \Else a_{t}\leftarrow\hat{u}_{t}/\lambda Send a_{t} to \mathcal{A} . 3 ADA Mechanism via Online Gradient Descent In this section, we present our main contribution, the ADA mechanism \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} , described in Alg. 2.2 . The mechanism achieves both sample efficiency with sample complexity \mathcal{O}(\lambda^{-2}\epsilon^{-4}\log T) and computational efficiency with runtime \mathsf{poly}(\epsilon^{-1},\log N,M,T) . Overview of \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} . Given samples S\subseteq[N] , \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} aims to answer queries using an approximation (sketch) of S whenever possible, rather than answering with q_{t}(S) directly for every t . To enable this, \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} maintains a multiset \mathcal{G}\subseteq\mathbb{R}^{N} consisting of vectors proportional to previous queries q_{t}\in\{-1,1\}^{N} , interpreted as vectors in \mathbb{R}^{N} . Internally, each of these vectors is proportional to a subgradient of the convex objective function f_{t}(x)\coloneq\left|\left\langle\frac{q_{t}}{\sqrt{N}},x\right\rangle-\lambda q_{t}(S)\right| . For this reason, we refer to the set \mathcal{G} as the collection of “gradient” vectors. {algorithm2e} [t] \mathsf{IP}_{\mathsf{est}}(q,\mathcal{G};\epsilon,\delta) \SetKwComment Comment \color blue \triangleright \color blue \DontPrintSemicolon Input: Query q\in\{-1,1\}^{N} , gradient vectors \mathcal{G} , accuracy \epsilon>0 and failure probability \delta>0 . Output: An \epsilon -accurate estimate of \left\langle q,y\right\rangle/N , where y\coloneq\sum_{v\in\mathcal{G}}v . Sample (i_{1},\dots,i_{B})\stackrel{{\scriptstyle\mathclap{iid}}}{{\,\sim\,}}U_{[N]} where B\coloneq\left\lceil 0.5\epsilon^{-2}T^{2}\ln\frac{\delta}{2T}\right\rceil . \Return \frac{1}{B}\sum_{v\in\mathcal{G}}\sum_{k=1}^{B}q(i_{k})v(i_{k}) In each round, at Line 6, \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} attempts to approximate the desired answer using the \mathsf{IP}_{\mathsf{est}} subroutine, defined in Alg. 3 , based on the current collection of gradients \mathcal{G} . The desired answer is encoded in \left\langle q_{t},y\right\rangle/N for y\coloneq\sum_{v\in\mathcal{G}}v , which is designed to approximate \lambda q_{t}(S) . The subroutine \mathsf{IP}_{\mathsf{est}} approximates \left\langle q_{t},y\right\rangle/N by taking the sample mean of q_{t}(i)y(i) . This randomized estimation avoids the prohibitive cost of full-dimensional computation and ensures that the mechanism runs in time \mathsf{poly}\log N . After estimating the tentative answer \hat{u}_{t}/\lambda in Line 6, \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} checks whether this estimate is sufficiently close to q_{t}(S) . If so, it outputs a_{t}=\hat{u}_{t}/\lambda ; otherwise, it updates \mathcal{G} according to Line 9, effectively performing a gradient step on f_{t} , and returns the answer using q_{t}(S) . We refer to this mechanism as AQA-OGD, as it follows an online gradient descent procedure to maintain an approximate representation of S . The key insight lies in the second condition of Line 7: \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} uses q_{t}(S) directly only a bounded number of times, at most \mathcal{O}(\lambda^{-2}\epsilon^{-2}) , independent of the total number of queries T or the domain size N . As shown in § 4 , this limitation is crucial to our analysis, ensuring that the accuracy of each a_{t} is preserved via uniform concentration of q_{t}(S)\approx q_{t}(\mathcal{D}) for all t\in[T] . Accuracy and Efficiency of \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} . We now provide the computational efficiency and sample complexity guarantees for \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} . We begin with its computational efficiency. The construction of \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} in Algorithms 2.2 and 3 immediately yields the following bound. Theorem 5 . [Computational Efficiency] Under Game 2 , given that \mathcal{A} issues queries computable in \mathsf{poly}(\log N) time, \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} runs in time \mathsf{poly}(\epsilon^{-1},\log N,M,T) . More importantly, we state the accuracy and sample complexity guarantees for \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} in the following theorem, which is proved in § 4 . Theorem 6 . [Sample Efficiency] If \mathcal{A} is an (\epsilon/16,\lambda) -pseudodense challenger, then \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} is (\epsilon,\delta) -accurate with respect to \mathcal{A} , with any sample size M\geq\frac{4096}{\lambda^{2}\epsilon^{4}}\log(T/\epsilon)+\frac{32}{\epsilon^{2}}\log(10/\delta) . Sample-efficient Implementation of Distribution-specific SQ Oracle. Our ADA mechanism also yields a sample-efficient implementation of a distribution-specific SQ oracle. As discussed in § 2.2 , the labeled distribution \mathcal{D}_{h,f} is (1/2) -dense with respect to the prior \mathcal{D}_{g} , which samples X\sim\mathcal{D}_{h} together with an independent uniform label bit, and thus Theorem 6 applies. The only remaining mismatch is that DSQ queries may take values in [-1,1] rather than \{-1,1\} , which we address via a standard Boolean randomization. This result is summarized in the following theorem, whose proof is given in Appendix A . Theorem 7 . [Sample-efficient DSQ Oracle from \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} ] Fix a feature distribution \mathcal{D}_{h} over a finite domain \mathcal{X} generated by an efficient sampler h , and an unknown labeling function f:\mathcal{X}\to\{-1,1\} . Let \mathcal{D}_{h,f} denote the induced distribution over (X,Y) given by X\sim\mathcal{D}_{h} and Y=f(X) . Then there exists an implementation of the distribution-specific SQ oracle \mathsf{DSQ}_{h}(f,\epsilon) with the following guarantee: for any analyst issuing a sequence of T adaptively chosen queries \phi_{1},\ldots,\phi_{T} with \phi_{t}:\mathcal{X}\times\{-1,1\}\to[-1,1] , the implementation answers each query to within \epsilon accuracy with probability at least 1-\delta , using \displaystyle M\in\mathcal{O}\left(\epsilon^{-4}\log(T/\epsilon)\right) i.i.d. samples from \mathcal{D}_{h,f} , and running in time \mathsf{poly}(\log N,\epsilon^{-1},T) . {algorithm2e} [t] \mathsf{Replay}(Z;\mathcal{A},\omega) : Reconstruct queries (q_{1},\dots,q_{T}) without samples S \SetKwInOut InputInput \SetKwInOut OutputOutput \SetKwComment Comment \color blue \triangleright \color blue \DontPrintSemicolon Input: • Update transcript Z\coloneq\left\{(t_{1},(a_{t_{1}},s_{t_{1}})),\dots\right\} , represented as key-value pairs, where each key t_{i} denotes a round in which \mathcal{G} was updated, and the corresponding value (a_{t_{i}},s_{t_{i}}) records the answer given to \mathcal{A} and the sign of the update at round t_{i} . • Adversary’s algorithm \mathcal{A} and random bits \omega=(\omega_{\mathcal{A}},\omega_{\mathcal{M}}) , where \omega_{\mathcal{A}}\in\{0,1\}^{\star} are used by \mathcal{A} , and \omega_{\mathcal{M}}\in\{0,1\}^{\star} are used by \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} during calls to \mathsf{IP}_{\mathsf{est}} (Alg. 3 ). Output: A tuple of reconstructed queries (q_{1},\dots,q_{T}) . \mathcal{G}\leftarrow\emptyset \For t\in[T] q_{t}\leftarrow\mathcal{A}^{\omega_{\mathcal{A}}}(q_{1},a_{1},\dots,q_{t-1},a_{t-1}) \Comment * \color blueRun \mathcal{A} with randomness \omega_{\mathcal{A}} and previous query-answer history. \hat{u}_{t}\leftarrow\mathsf{IP}_{\mathsf{est}}^{\omega_{\mathcal{M}}}(q_{t},\mathcal{G};\lambda\epsilon/8,\delta/2T) \Comment * \color blue Run \mathsf{IP}_{\mathsf{est}} using \omega_{\mathcal{M}} , reading from where the last \mathsf{IP}_{\mathsf{est}} call left off. \If t\in Z.\mathsf{Keys} (a_{t},s_{t})\leftarrow Z.\mathsf{Get}(t) \Comment * \color blueGet the entry with key t . \mathcal{G}\leftarrow\mathcal{G}\cup\big\{-\lambda\epsilon s_{t}q_{t}/16\big\} \Comment * \color blueUpdate \mathcal{G} . Z.\mathsf{Remove}(t) \Comment * \color blueRemove the entry with key t . \Else a_{t}\leftarrow\hat{u}_{t}/\lambda \Return (q_{1},\dots,q_{T}) 4 Sample Complexity Analysis In this section, we analyze the sample complexity of \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} as stated in Theorem 6 . Analysis Overview. Our analysis consists of two parts. 1. We establish the following uniform concentration guarantee: with high probability, it holds that for all t\in[T] , |q_{t}(S)-q_{t}(\mathcal{D})|\in\mathcal{O}(\epsilon) , provided that the sample size |S| exceeds the threshold specified in Theorem 6 . 2. Then, we show that the answers a_{t} output by \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} are close to q_{t}(S) , i.e., for all t\in[T] , |a_{t}-q_{t}(S)|\in\mathcal{O}(\epsilon) with high probability. To establish the first part, |q_{t}(S)-q_{t}(\mathcal{D})|\in\mathcal{O}(\epsilon) for all t , we outline the following approach. We argue that the sequence of queries (q_{t})_{t\in[T]} issued during the execution of \mathsf{AQ}_{N,M,T}[\mathcal{A}\rightleftharpoons\mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}}] can be reconstructed from a transcript of the internal update trajectory of \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} (specifically, the decisions made in Lines 7–11 of Alg. 2.2 ) without access to the underlying sample set S . When this transcript admits a succinct representation, using only \mathcal{O}(\log T) bits, standard arguments based on Hoeffding’s inequality and the union bound can then be used to obtain the uniform concentration bound |q_{t}(S)-q_{t}(\mathcal{D})|\in\mathcal{O}(\epsilon) with high probability, using |S|\in\mathcal{O}(\log T) samples. The second part, |a_{t}-q_{t}(S)|\in\mathcal{O}(\epsilon) , can be understood as a consequence of the fact that a mistake budget of |\mathcal{G}|\leq 128(\lambda\epsilon)^{-2} is sufficient, which will be justified via the regret bound of OGD. Therefore, the condition in Line 7 of Alg. 2.2 is equivalent to the condition |\hat{u}_{t}-\lambda q_{t}(S)|>\lambda\epsilon/2 . Hence, if this condition is not triggered (Lines 12–14), the output \hat{u}_{t}/\lambda is \epsilon/2 -close to q_{t}(S) . 4.1 Proof Sketch of Theorem 6 Here we provide a proof sketch of our main result, Theorem 6 , which establishes the sample complexity of \mathcal{M}_{{\mathsf{AQA}\textup{-}\mathsf{OGD}}} . The full proof appears in Appendix B.1 . Step 1. Reconstructing queries from succinct transcript. A central component of our analysis is the procedure \mathsf{Replay}\big(Z;\mathcal{A},\omega\big) , described in Alg. 3 , which “replays” all queries issued by \mathcal{A} during the execution of \mathsf{AQ}_{N,M,T}[\mathcal{A}\rightleftharpoons\mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}}] , when both \mathcal{A} and \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} are run with fixed internal randomness \omega_{\mathcal{A}} and \omega_{\mathcal{M}} , respectively. The main input to \mathsf{Replay} is a set of key-value pairs Z\coloneq\left\{(t_{1},(a_{t_{1}},s_{t_{1}})),\dots\right\} , where each key t_{i} denotes a round in which \mathcal{G} was updated, and the corresponding value (a_{t_{i}},s_{t_{i}}) is the answer given to \mathcal{A} and the sign of the update, s_{t_{i}}\coloneq\mathsf{sign}(\hat{u}_{t_{i}}-\lambda q_{t}(S)) , as recorded in Line 8 of \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} (Alg. 2.2 ) at round t_{i} . We refer to Z as the update transcript. Given fixed randomness \omega\coloneq(\omega_{\mathcal{A}},\omega_{\mathcal{M}}) , samples S and the analyst’s algorithm \mathcal{A} , by construction, there exists a transcript Z(\omega,S) such that \mathsf{Replay}(Z(\omega,S);\mathcal{A},\omega) faithfully reproduces all queries issued by \mathcal{A} , assuming \mathcal{A} and \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} are executed with frozen randomness \omega_{\mathcal{A}} and \omega_{\mathcal{M}} , respectively. This can be interpreted as simulating the behavior of \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} from the transcript alone: each a_{t} constructed by \mathsf{Replay} is indistinguishable from the one produced by \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} with the same random coins \omega_{\mathcal{M}} . Moreover, the transcript Z(\omega,S) can be described succinctly using only \mathcal{O}\big(\lambda^{-2}\epsilon^{-2}\cdot\log T\big) bits, since \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} performs at most \mathcal{O}(\lambda^{-2}\epsilon^{-2}) updates among T rounds. Therefore, the number of possible update transcripts is about at most T^{\mathcal{O}(\lambda^{-2}\epsilon^{-2})} . This succinctness enables us to derive uniform concentration bounds of |q_{t}(S)-q_{t}(\mathcal{D})|\leq\mathcal{O}(\epsilon) for all t\in[T] with high probability, even for logarithmic sample sizes |S|\in\mathcal{O}\big(\lambda^{-2}\epsilon^{-4}\cdot\log T\big) , as formally shown in Lemma 10 . Step 2. \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} outputs a_{t}\approx q_{t}(S) . Assuming |q_{t}(S)-q_{t}(\mathcal{D})|\in\mathcal{O}(\epsilon) holds for all t\in[T] , it remains to show that |a_{t}-q_{t}(S)|\in\mathcal{O}(\epsilon) for all t\in[T] . This follows from the logic of the if-condition on Line 7 of \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} , which determines whether to update \mathcal{G} . This condition is a conjunction of two parts: |\hat{u}_{t}-\lambda q_{t}(S)|>\lambda\epsilon/2 and |\mathcal{G}|\leq 128\lambda^{-2}\epsilon^{-2} . When |\mathcal{G}| never exceeds 128\lambda^{-2}\epsilon^{-2} during execution, the second condition is always satisfied, so updates occur only when the first condition is met. In this case, the mechanism enters the else-branch with the guarantee that |\hat{u}_{t}-\lambda q_{t}(S)|\in\mathcal{O}(\lambda\epsilon) . Therefore, as long as |\mathcal{G}|\leq 128\lambda^{-2}\epsilon^{-2} throughout the execution, we have |a_{t}-q_{t}(S)|\in\mathcal{O}(\epsilon) for all t\in[T] . This is because \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} either outputs q_{t}(S) (rounded to \mathcal{O}(\epsilon) accuracy) when an update occurs, or outputs \hat{u}_{t}/\lambda when no update occurs. In the latter case, our earlier argument shows that \hat{u}_{t}/\lambda is within \mathcal{O}(\epsilon) of q_{t}(S) , so in both cases, a_{t}\approx q_{t}(S) for every t . Indeed, we show that, with high probability, |\mathcal{G}|\leq 128\lambda^{-2}\epsilon^{-2} holds throughout the execution. This is established by leveraging a regret argument for OGD: if too many updates were made, the cumulative objective values would violate the regret bound stated in Lemma 11 . This contradiction allows us to bound the total number of updates (or “mistakes”), which is a key step in the proof of Theorem 6 . 5 Privacy Guarantee In this section, we establish the privacy-preserving properties of \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} . Although \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} does not satisfy stronger guarantees such as differential privacy ( Dwork et al. 2014 ) , we show that it enjoys a form of meaningful privacy protection known as Predicate Singling Out (PSO) security ( Cohen and Nissim 2020 ) . This notion was introduced as a formal counterpart to the concept of “singling out” as defined in the European Union’s General Data Protection Regulation (GDPR). Predicate Singling Out (PSO). The main privacy leakage mode we consider is Predicate Singling Out (PSO), which formalizes the GDPR’s notion of identifying an individual. Specifically, given a dataset S\subseteq[N] , a PSO adversary attempts to produce a predicate p:[N]\rightarrow\{0,1\} that isolates a single entry in S . Formally, this is captured by the row isolation event: Definition 8 (Row isolation) . Let S be a dataset of size M over [N]\simeq\left\{0,1\right\}^{n} , and let p:[N]\rightarrow\left\{0,1\right\} be a predicate. We say that p isolates a row in S if there exists a unique i\in S such that p(i)=1 , or equivalently, if p(S)=1/M . We denote this event by \mathsf{iso}(p,S) . \SetAlgorithmName GameGameList of Games {algorithm2e} [t] \mathsf{PSO}_{M,T,\mathcal{P}}[\mathcal{A}\rightleftharpoons\mathcal{M}] : Predicate Singling Out Game \DontPrintSemicolon A multiset S of M i.i.d. samples from \mathcal{D} is given to \mathcal{M} but not to \mathcal{A} . \For t\in[T] \mathcal{A} chooses a query q_{t}\in\{-1,1\}^{N} given (q_{1},a_{1},\dots,q_{t-1},a_{t-1}) . \mathcal{M} outputs an answer a_{t}\in[-1,1] given (q_{1},a_{1},\dots,q_{t-1},a_{t-1},q_{t}) . \mathcal{A} outputs p\in\mathcal{P} . We now define PSO security in the context of the adaptive data analysis. Let \mathcal{P}\subseteq\{0,1\}^{N} be a class of admissible predicates. PSO security is formalized via a game between the ADA mechanism \mathcal{M} and an adversary (or analyst) \mathcal{A} , as depicted in Game 5 . As in the adaptive query (AQ) game (Game 2 ), we allow \mathcal{A} to have full power: not only does \mathcal{A} know the data distribution \mathcal{D} , but may also choose \mathcal{D} arbitrarily. As before, any guarantee established against such a powerful \mathcal{A} automatically applies to more realistic settings where \mathcal{D} is unknown to both \mathcal{M} and \mathcal{A} . In fact, the original definition and analysis of PSO security by Cohen and Nissim 2020 allow for adversaries with this level of power. We define the adversary’s success probability in the PSO game as: \displaystyle\mathsf{Succ}^{\mathcal{A},\mathcal{M}}_{\mathcal{P},\mathcal{D}}(M,T)\coloneq\Pr_{\mathsf{PSO}_{M,T,\mathcal{P}}[\mathcal{A}\rightleftharpoons\mathcal{M}]}\big[\,\mathsf{iso}(p,S)\text{ and }p\in\mathcal{P}\,\big]. The predicate classes \mathcal{P} relevant for PSO security are \displaystyle\mathcal{P}_{\mathsf{low}} \displaystyle\coloneq\Big\{p\in\left\{0,1\right\}^{N}:p(\mathcal{D})\in\mathsf{negl}(M)\Big\}, \displaystyle\mathcal{P}_{\mathsf{high}} \displaystyle\coloneq\left\{p\in\left\{0,1\right\}^{N}:p(\mathcal{D})\in\omega\left(\frac{\log M}{M}\right)\right\}, where \mathsf{negl}(M) denotes functions decreasing faster than any inverse polynomial in M , i.e., \mathsf{negl}(M)=\cup_{c\in\mathbb{N}}\,o(M^{-c}) . Constraining the predicate class relevant for privacy (or, equivalently, specifying which predicates count as meaningful attacks) is necessary. Without such a restriction, even a trivial adversary that does not observe the mechanism’s output can isolate a row of S with non-negligible probability via the (generalized) leftover hash lemma ( Dodis et al. 2008 ; Cohen and Nissim 2020 ) . The restriction to \mathcal{P}_{\mathsf{low}} and \mathcal{P}_{\mathsf{high}} ensures that the baseline PSO success probability of such trivial adversaries remains negligible in dataset size M . Intuitively, row isolation by a predicate in \mathcal{P}_{\mathsf{low}} constitutes a particularly severe privacy violation, as it suggests that the adversary has likely identified a unique individual in the data universe. We now state the PSO security guarantee of \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} , with the full proof deferred to Appendix C . Theorem 9 . [PSO security guarantee] For any \mathcal{P}\in\{\mathcal{P}_{\mathsf{low}},\mathcal{P}_{\mathsf{high}}\} , there exists a function \delta(M)\in\mathsf{negl}(M) such that \displaystyle\mathsf{Succ}^{\mathcal{A},\,\mathcal{M}_{{\mathsf{AQA}\textup{-}\mathsf{OGD}}}}_{\mathcal{P},\mathcal{D}}(M,T)\;\leq\;\epsilon^{-1}\,T^{128/(\lambda\epsilon)^{2}}\,\delta(M). A practical interpretation of Theorem 9 is as follows. Let \delta_{\mathsf{PSO}} be a target upper bound on the adversary’s PSO success probability. Then, for any fixed constant \beta>0 , there exists M_{\beta}>0 depending only on \beta such that whenever \displaystyle M\;\geq\;\left(\frac{T^{128/(\lambda\epsilon)^{2}}}{\epsilon\,\delta_{\mathsf{PSO}}}\right)^{\beta}\vee M_{\beta}, we have \displaystyle\mathsf{Succ}^{\mathcal{A},\,\mathcal{M}_{{\mathsf{AQA}\textup{-}\mathsf{OGD}}}}_{\mathcal{P},\mathcal{D}}(M,T)\;\leq\;\delta_{\mathsf{PSO}} for \mathcal{P}\in\{\mathcal{P}_{\mathsf{low}},\mathcal{P}_{\mathsf{high}}\} . acknowledgments-disclosure-of-funding. We thank a bunch of people and funding agency. Appendix A Proof of Theorem 7 In this appendix, we provide a proof of Theorem 7 , which states that \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} yields a sample-efficient implementation of a distribution-specific statistical query oracle. For convenience, we restate the theorem below. See 7 Proof. of Theorem 7 . As discussed above, \mathcal{D}_{h,f} is (1/2) -dense with respect to the prior \mathcal{D}_{g} that samples X\sim\mathcal{D}_{h} together with an independent uniform label bit. To handle [-1,1] -valued queries, for each \phi_{t} the oracle samples B=\Theta(\epsilon^{-2}\log(T/\delta)) Boolean queries q_{t,1},\ldots,q_{t,B}:\mathcal{X}\times\{-1,1\}\to\{-1,1\} such that \expec[q_{t,j}(x,y)\mid(x,y)]=\phi_{t}(x,y) for all (x,y) . By Hoeffding’s inequality and a union bound over t\in[T] , with probability at least 1-\delta/2 we have \displaystyle\left|\frac{1}{B}\sum_{j\in[B]}q_{t,j}(\mathcal{D}_{h,f})-\phi_{t}(\mathcal{D}_{h,f})\right|\leq\epsilon/2\qquad\text{for all }t\in[T]. (A.1) We then run \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} on the resulting sequence of T^{\prime}=BT Boolean queries with accuracy parameter \epsilon/2 and failure probability \delta/2 , which requires M\in\mathcal{O}(\epsilon^{-4}\log(BT/\epsilon)) samples. By Theorem 6 with \lambda=1/2 , with probability at least 1-\delta/2 , \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} answers every q_{t,j} to within \epsilon/2 . Let \widehat{\phi}_{t} denote the average of the B answers corresponding to (q_{t,j})_{j\in[B]} . This averaging introduces no additional error and approximates \frac{1}{B}\sum_{j\in[B]}q_{t,j}(\mathcal{D}_{h,f}) within \epsilon/2 error. Combining this with ( A.1 ), we conclude that |\widehat{\phi}_{t}-\phi_{t}(\mathcal{D}_{h,f})|\leq\epsilon for all t\in[T] with probability at least 1-\delta . ∎ Appendix B Proof of Sample Complexity of \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} In this appendix, we provide a complete proof of our main result, Theorem 6 , which establishes the sample complexity of \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} . B.1 Proof of Theorem 6 Step 1. Proving |q_{t}(S)-q_{t}(D)|\in\mathcal{O}(\epsilon) . In this step, we prove the following lemma, which establishes the sample complexity required to guarantee uniform concentration between q_{t}(S) and q_{t}(\mathcal{D}) over all t\in[T] . {algorithm2e} [t] \mathsf{Replay}(Z;\mathcal{A},\omega) : Reconstruct queries (q_{1},\dots,q_{T}) without samples S \SetKwInOut InputInput \SetKwInOut OutputOutput \SetKwComment Comment \color blue \triangleright \color blue \DontPrintSemicolon Input: • Update transcript Z\coloneq\left\{(t_{1},(a_{t_{1}},s_{t_{1}})),\dots\right\} , represented as key-value pairs, where each key t_{i} denotes a round in which \mathcal{G} was updated, and the corresponding value (a_{t_{i}},s_{t_{i}}) records the answer given to \mathcal{A} and the sign of the update at round t_{i} . • Adversary’s algorithm \mathcal{A} and random bits \omega=(\omega_{\mathcal{A}},\omega_{\mathcal{M}}) , where \omega_{\mathcal{A}}\in\{0,1\}^{\star} are used by \mathcal{A} , and \omega_{\mathcal{M}}\in\{0,1\}^{\star} are used by \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} during calls to \mathsf{IP}_{\mathsf{est}} (Alg. 3 ). Output: A tuple of reconstructed queries (q_{1},\dots,q_{T}) . \mathcal{G}\leftarrow\emptyset \For t\in[T] q_{t}\leftarrow\mathcal{A}^{\omega_{\mathcal{A}}}(q_{1},a_{1},\dots,q_{t-1},a_{t-1}) \Comment * \color blueRun \mathcal{A} with randomness \omega_{\mathcal{A}} and previous query-answer history. \hat{u}_{t}\leftarrow\mathsf{IP}_{\mathsf{est}}^{\omega_{\mathcal{M}}}(q_{t},\mathcal{G};\lambda\epsilon/8,\delta/2T) \Comment * \color blue Run \mathsf{IP}_{\mathsf{est}} using \omega_{\mathcal{M}} , reading from where the last \mathsf{IP}_{\mathsf{est}} call left off. \If t\in Z.\mathsf{Keys} (a_{t},s_{t})\leftarrow Z.\mathsf{Get}(t) \Comment * \color blueGet the entry with key t . \mathcal{G}\leftarrow\mathcal{G}\cup\big\{-\lambda\epsilon s_{t}q_{t}/16\big\} \Comment * \color blueUpdate \mathcal{G} . Z.\mathsf{Remove}(t) \Comment * \color blueRemove the entry with key t . \Else a_{t}\leftarrow\hat{u}_{t}/\lambda \Return (q_{1},\dots,q_{T}) Lemma 10 . [Uniform Concentration] Let \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} be the ADA mechanism given in Alg. 2.2 . Then, for any adversary \mathcal{A} and \delta>0 , \displaystyle\Pr_{\mathsf{AQ}_{N,M,T}[\mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}}\rightleftharpoons\mathcal{A}]}\Big[\,\forall t\in[T],\ \left|q_{t}(S)-q_{t}(\mathcal{D})\right|\leq\frac{\epsilon}{8}\,\Big]\geq 1-\frac{\delta}{2}, whenever M\geq\frac{4096}{\lambda^{2}\epsilon^{4}}\log(T/\epsilon)+\frac{32}{\epsilon^{2}}\log(10/\delta) . Proof. of Lemma 10 . We prove the lemma by explicitly constructing an algorithm, \mathsf{Replay} given in Alg. B.1 , that reconstructs queries (q_{1},\dots,q_{T}) asked by \mathcal{A} during game \mathsf{AQ}_{N,M,T}[\mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}}\rightleftharpoons\mathcal{A}] , from a succinct transcript. A main input to \mathsf{Replay} is the update transcript, Z\coloneq\{(t_{1},(a_{t_{1}},s_{t_{1}})),\dots\} represented by a set of key-value pairs (t_{i},(a_{t_{i}},s_{t_{i}})) where the key t_{i}\in[T] is a round in which \mathcal{G} was updated and (a_{t_{i}},s_{t_{i}}) is the pair of the answer provided to \mathcal{A} and the sign of the update, \mathsf{sign}(\hat{u}_{t_{i}}-\lambda q_{t_{i}}(S)) , at round t_{i} . Since \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} updates \mathcal{G} at most \frac{128}{(\lambda\epsilon)^{2}} times, the number of entries in Z is at most \frac{128}{(\lambda\epsilon)^{2}} . Combining this with the fact that a_{t}\in[-1,1] is rounded to a multiple of \epsilon/2 in each updated round and s_{t}\in\{\pm 1\} , there are at most 8\epsilon^{-1}T^{128/(\lambda\epsilon)^{2}} possible choices for Z . Let the set of all such logs be denoted by \mathcal{Z} . Then, for any fixed random bits \omega used by \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} and \mathcal{A} (including those used by \mathcal{A} to select the distribution \mathcal{D} ), we have \displaystyle\Pr_{S\sim\mathcal{D}^{M}}\bigg[\forall(t,Z)\in[T]\times\mathcal{Z},\ \left|q_{t}(S)-q_{t}(\mathcal{D})\right| \displaystyle\leq\sqrt{\frac{64\log(10T/\epsilon)}{\lambda^{2}\epsilon^{2}M}+\frac{\log(1/\delta)}{2M}}, \displaystyle\hskip-14.45377pt\text{where}\ (q_{t})_{t\in[T]}\leftarrow\mathsf{Replay}(Z;\mathcal{A},\omega)\,\bigg]\geq 1-\frac{\delta}{2} (B.1) by applying the union bound over [T]\times\mathcal{Z} to the Hoeffding bound. For each randomness \omega and sample S , there is Z(\omega,S)\in\mathcal{Z} such that \mathsf{Replay}(Z(\omega,S),\mathcal{A};\omega) reconstructs the queries (q_{t})_{t\in[T]} asked in game \mathsf{AQ}_{N,M,T}[\mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}}\rightleftharpoons\mathcal{A}] when run with fixed \omega and S . Hence, taking the expectation over \omega in ( B.1 ), this fact yields the bound stated in the lemma. ∎ Step 2. Finalizing the proof by showing |a_{t}-q_{t}(S)|\in\mathcal{O}(\epsilon) . With the high-probability concentration bound |q_{t}(S)-q_{t}(\mathcal{D})|\in\mathcal{O}(\epsilon) established in Step 1, we now complete the proof of Theorem 6 by showing that |a_{t}-q_{t}(S)|\in\mathcal{O}(\epsilon) for all t\in[T] . This follows from the fact that the number of updates made by Alg. 2.2 remains small, i.e., |\mathcal{G}|\leq 128/(\lambda\epsilon)^{2} , as ensured by a regret argument. In particular, we obtain a contradiction by showing that exceeding this number of updates would violate the regret bound for OGD. Consequently, the condition |\mathcal{G}|\leq 128/(\lambda\epsilon)^{2} in the if-statement of Alg. 2.2 is redundant, and \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} therefore outputs approximately correct answers. Before proceeding, we formally state the regret bound for unconstrained OGD. While this result is standard (see, e.g., Bubeck 2015 ; Hazan 2016 ; Zinkevich 2003 ), we include a self-contained proof in Appendix B.2 for completeness. Lemma 11 . [Regret Bound for Unconstrained OGD] For any finite ordered set \mathcal{T}\coloneq\{t_{1},\dots,t_{|\mathcal{T}|}\}\subset\mathbb{N} such that t_{1}<\cdots0 and x^{\star}\in\mathbb{B}^{N} , \displaystyle\sum_{t\in\mathcal{T}}\big[f_{t}(x_{t})-f_{t}(x^{\star})\big]\leq\frac{1}{2\alpha}+\frac{\alpha|\mathcal{T}|}{2}, (B.2) where x_{t} is defined recursively as \displaystyle x_{t_{i+1}}\coloneq x_{t_{i}}-\alpha\nabla f_{t_{i}}(x_{t_{i}})\quad\textup{and}\quad x_{t_{1}}\coloneq 0. (B.3) With all the necessary ingredients established so far, we now present the proof of Theorem 6 , which we restate below for convenience. See 6 Proof. of Theorem 6 . Let \mathcal{T}_{\textup{mis}}\subseteq[T] denote the set of rounds in which |\hat{u}_{t}-\lambda q_{t}(S)|>\lambda\epsilon/2 occurred. The key observation is that whenever |\mathcal{T}_{\textup{mis}}|\leq\frac{128}{(\lambda\epsilon)^{2}} , all answers of \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} lie within [q_{t}(S)-\epsilon/2,q_{t}(S)+\epsilon/2] . This is because the condition |\mathcal{G}|\leq\frac{128}{(\lambda\epsilon)^{2}} in the if-statement in \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} becomes redundant in this case, ensuring that |\hat{u}_{t}/\lambda-q_{t}(S)|\leq\epsilon/2 in the other branch. Let \mathsf{E} be the event from Lemma 10 , that is \forall t\in[T],\ |q_{t}(S)-q_{t}(\mathcal{D})|\leq\epsilon/8 , and \mathsf{F} be the event that \mathsf{IP}_{\mathsf{est}} produces a \lambda\epsilon/8 -accurate estimate for all t\in[T] . We show that when both events occur (i.e., \mathsf{E}\cap\mathsf{F} ), we have |\mathcal{T}_{\textup{mis}}|\leq\frac{128}{(\lambda\epsilon)^{2}} , hence |a_{t}-q_{t}(S)|\leq\epsilon/2 for all t\in[T] . Moreover, under \mathsf{E} we have |q_{t}(S)-q_{t}(\mathcal{D})|\leq\epsilon/8 for all t\in[T] . Hence, under \mathsf{E}\cap\mathsf{F} , we have |a_{t}-q_{t}(\mathcal{D})|\leq\epsilon for all t\in[T] , which is the theorem’s claim. Therefore, it suffices to show following two claims: Claim 1. \Pr_{\mathsf{AQ}_{N,M,T}[\mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}}\rightleftharpoons\mathcal{A}]}[\mathsf{E}\cap\mathsf{F}]\geq 1-\delta . Claim 2. Given that \mathsf{E}\cap\mathsf{F} occurs and \mathcal{D} is (\epsilon/16,\lambda) -pseudodense w.r.t. \mathcal{A} , |\mathcal{T}_{\textup{mis}}|\leq\frac{128}{(\lambda\epsilon)^{2}} . Proof of Claim 1. Lemma 10 shows that \Pr_{\mathsf{AQ}_{N,M,T}[\mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}}\rightleftharpoons\mathcal{A}]}[\mathsf{E}]\geq 1-\delta/2 . Hence, it is enough to show that \displaystyle\mathsf{F}\coloneq\left\{\forall t\in[T],\ \left|\hat{u}_{t}-\frac{1}{N}\left\langle q_{t},y\right\rangle\right|\leq\frac{\lambda\epsilon}{8}\right\}, occurs with probability at least 1-\delta/2 under \mathsf{AQ}_{N,M,T}[\mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}}\rightleftharpoons\mathcal{A}] , where \hat{u}_{t} is the output of \mathsf{IP}_{\mathsf{est}}(q_{t},\mathcal{G};\lambda\epsilon/8,\delta/2T) . Since the randomness used by \mathsf{IP}_{\mathsf{est}} to estimate \left\langle q_{t},y\right\rangle/N is independent from q_{t} and \mathcal{G} , we can apply the union bound over Lemma 12 , which yields \displaystyle\Pr_{\mathsf{AQ}_{N,M,T}[\mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}}\rightleftharpoons\mathcal{A}]}[\,\mathsf{F}\,]\geq 1-\frac{\delta}{2}. ∎ Proof of Claim 2. For each t\in\mathcal{T}_{\textup{mis}} , define f_{t}:\mathbb{B}^{N}\rightarrow\mathbb{R} as \displaystyle f_{t}(x)\coloneq\left|h_{t}(x)\right|,\quad h_{t}(x)\coloneq\left\langle\frac{q_{t}}{\sqrt{N}},x\right\rangle-\lambda q_{t}(\mathcal{D}). so that f_{t} is convex, and its sub-gradient satisfies \|\nabla f_{t}(x)\|=\|\mathsf{sign}(h_{t}(x))q_{t}/\sqrt{N}\|=1 , since q_{t}\in\{\pm 1\}^{N} . For each t\in\mathcal{T}_{\textup{mis}} , let x_{t}\coloneq y/\sqrt{N} , where y\coloneq\sum_{v\in\mathcal{G}}v is computed using the gradient set \mathcal{G} at round t . Notice that, by construction, \mathcal{G} consists of vectors -\lambda\epsilon s_{t}q_{t}/16 , where s_{t}\coloneq\mathsf{sign}(\hat{u}_{t}-\lambda q_{t}(S)) and |\hat{u}_{t}-\lambda q_{t}(S)|>\lambda\epsilon/2 . Now, we list two key implications under \mathsf{E}\cap\mathsf{F} : • Given that \mathsf{E}\cap\mathsf{F} has occurred, |\hat{u}_{t}-\lambda q_{t}(S)|>\lambda\epsilon/2 implies \displaystyle\mathsf{sign}(\hat{u}_{t}-\lambda q_{t}(S))=\mathsf{sign}\left(\left\langle\frac{q_{t}}{\sqrt{N}},x_{t}\right\rangle-\lambda q_{t}(\mathcal{D})\right)=\mathsf{sign}(h_{t}(x_{t})), as \left|\hat{u}_{t}-\left\langle q_{t},y\right\rangle/N\right|=\left|\hat{u}_{t}-\left\langle q_{t}/\sqrt{N},x_{t}\right\rangle\right|\leq\lambda\epsilon/8 under \mathsf{F} and |q_{t}(S)-q_{t}(D)|\leq\epsilon/8 under \mathsf{E} . Hence, \mathcal{G} consists of vectors of the form -\alpha\sqrt{N}\nabla f_{t}(x_{t}) with \alpha=\lambda\epsilon/16 , and thus x_{t}\coloneq\sum_{v\in\mathcal{G}}v/\sqrt{N} follows the OGD update rule given in ( B.3 ), with learning rate \lambda\epsilon/16 . • Similarly, under \mathsf{E}\cap\mathsf{F} , |\hat{u}_{t}-\lambda q_{t}(S)|>\lambda\epsilon/2 implies f_{t}(x_{t})>\lambda\epsilon/4 . From the above implications together with the OGD regret bound ( B.2 ), we observe the following: For any x^{\star}\in\mathbb{B}^{N} , \displaystyle\frac{\lambda\epsilon}{4}|\mathcal{T}_{\textup{mis}}|-\sum_{t\in\mathcal{T}_{\textup{mis}}}f_{t}(x^{\star}) \displaystyle\leq\sum_{t\in\mathcal{T}_{\textup{mis}}}\big[f_{t}(x_{t})-f_{t}(x^{\star})\big]\leq\frac{8}{\lambda\epsilon}+\frac{\lambda\epsilon}{32}|\mathcal{T}_{\textup{mis}}| \displaystyle\hskip-36.135pt\implies\frac{\lambda\epsilon|\mathcal{T}_{\textup{mis}}|}{8}-\sum_{t\in\mathcal{T}_{\textup{mis}}}f_{t}(x^{\star})\leq\frac{8}{\lambda\epsilon}. Hence, provided that there is some x^{\star}\in\mathbb{B}^{N} such that \displaystyle\sum_{t\in\mathcal{T}_{\textup{mis}}}f_{t}(x^{\star})\leq\frac{\lambda\epsilon|\mathcal{T}_{\textup{mis}}|}{16}, we obtain the desired upper bound on the mistake set: |\mathcal{T}_{\textup{mis}}|\leq 128/(\lambda\epsilon)^{2} . Indeed, this holds when \mathcal{D} is (\epsilon/16,\lambda) -pseudodense, as we show below: Claim 3. When \mathcal{D} is (\epsilon/16,\lambda) -pseudodense, there is x^{\star}\in\mathbb{B}^{N} such that \sum_{t\in\mathcal{T}_{\textup{mis}}}f_{t}(x^{\star})\leq\lambda\epsilon|\mathcal{T}_{\textup{mis}}|/16 . Proof of Claim 3. Since \mathcal{A} is an (\epsilon/16,\lambda) -pseudodense challenger (Def. 3 ), we have the following statement almost surely: there exists a \lambda -dense distribution \mathcal{D}^{\prime} such that \displaystyle\forall x\in\mathbb{B}^{N},\quad\sum_{t\in\mathcal{T}_{\textup{mis}}}f_{t}(x)\leq\sum_{t\in\mathcal{T}_{\textup{mis}}}\left|\left\langle\frac{q_{t}}{\sqrt{N}},x\right\rangle-\lambda q_{t}(\mathcal{D}^{\prime})\right|+\frac{\lambda\epsilon|\mathcal{T}_{\textup{mis}}|}{16}. Let p_{i} denote the probability mass of i\in[N] under \mathcal{D}^{\prime} . Since \mathcal{D}^{\prime} is \lambda -dense, we have \max_{i\in[N]}p_{i}\leq(\lambda N)^{-1} , and therefore 0\leq\max_{i\in[N]}\lambda\sqrt{N}p_{i}\leq 1/\sqrt{N} . Thus, x^{\star}\coloneq(\lambda\sqrt{N}p_{i})_{i\in[N]} gives a valid choice, as x^{\star} lies within \mathbb{B}^{N} . Plugging x^{\star}=(\lambda\sqrt{N}p_{i})_{i\in[N]} into the above inequality, as \big\langle q_{t}/\sqrt{N},x^{\star}\big\rangle=\lambda q_{t}(\mathcal{D}^{\prime}) , we obtain \sum_{t\in\mathcal{T}_{\textup{mis}}}f_{t}(x^{\star})\leq\lambda\epsilon|\mathcal{T}_{\textup{mis}}|/16 . ∎ Therefore, we conclude the proof of Claim 2. ∎ Together with Claim 1 and 2, we prove Theorem 6 . ∎ B.2 Proofs for Technical Lemmas In this subsection, we collect technical lemmas and their proofs used in the proof of Theorem 6 . We first restate, for convenience, the regret bound for unconstrained OGD and provide its proof ( Zinkevich 2003 ) for completeness. See 11 Proof. of Lemma 11 . Fix any x^{\star}\in\mathbb{B}^{N} . We begin by observing that \displaystyle\|x_{t_{i+1}}-x^{\star}\|_{2} \displaystyle=\|x_{t_{i}}-\alpha\nabla f_{t_{i}}(x_{t_{i}})-x^{\star}\|^{2} \displaystyle=\|x_{t_{i}}-x^{\star}\|^{2}-2\alpha\left\langle\nabla f_{t_{i}}(x_{t_{i}}),x_{t_{i}}-x^{\star}\right\rangle+\alpha^{2}\|\nabla f_{t_{i}}(x_{t_{i}})\|^{2}. As \|\nabla f_{t_{i}}(x_{t_{i}})\|\leq 1 , rearranging the above, we have that \displaystyle\left\langle\nabla f_{t_{i}}(x_{t_{i}}),x_{t_{i}}-x^{\star}\right\rangle\leq\frac{\|x_{t_{i}}-x^{\star}\|^{2}-\|x_{t_{i+1}}-x^{\star}\|^{2}}{2\alpha}+\frac{\alpha}{2}. Since f_{t} s are convex, f_{t_{i}}(x_{t_{i}})-f_{t_{i}}(x^{\star})\leq\left\langle\nabla f_{t_{i}}(x_{t_{i}}),x_{t_{i}}-x^{\star}\right\rangle for all i . Thus summing the above over all i=1,\dots,|\mathcal{T}| , \displaystyle\sum_{t\in|\mathcal{T}|}f_{t}(x_{t})-f_{t}(x^{\star}) \displaystyle\leq\sum_{i=1}^{|\mathcal{T}|}\left\langle\nabla f_{t_{i}}(x_{t_{i}}),x_{t_{i}}-x^{\star}\right\rangle \displaystyle\leq\frac{\|x_{t_{1}}-x^{\star}\|^{2}-\|x_{t_{|\mathcal{T}|}}-x^{\star}\|^{2}}{2\alpha}+\frac{\alpha|\mathcal{T}|}{2} \displaystyle\leq\frac{1}{2\alpha}+\frac{\alpha|\mathcal{T}|}{2}, as x_{t_{1}}=0 . ∎ Finally, we provide a simple proof of correctness for the subroutine \mathsf{IP}_{\mathsf{est}} . Lemma 12 . [Correctness of \mathsf{IP}_{\mathsf{est}} ] The output of \mathsf{IP}_{\mathsf{est}}(q,\mathcal{G};\epsilon,\delta) (Alg. 3 ) lies in the interval \big[\left\langle q,y\right\rangle/N-\epsilon,\left\langle q,y\right\rangle/N+\epsilon\big] where y\coloneq\sum_{v\in\mathcal{G}}v , with probability at least 1-\delta . Proof. of Lemma 12 . The estimand is \displaystyle\frac{1}{N}\left\langle q,v\right\rangle=\expec_{i\sim U_{[N]}}[q_{i}v_{i}]. Since every vector v\in\mathcal{G} can be written as v=\alpha q^{\prime} for some |\alpha|\leq 1 and q^{\prime}\in\{-1,1\}^{N} , and q\in\{-1,1\}^{N} , we have |q_{i}v_{i}|\leq 1 for all i\in[N] . The correctness of \mathsf{IP}_{\mathsf{est}}(q,\mathcal{G};\epsilon,\delta) then follows from a standard application of Hoeffding’s inequality and a union bound over \mathcal{G} . ∎ Appendix C Proof of Theorem 9 In this appendix, we provide a proof of Theorem 9 , which establishes the PSO security guarantee of \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} . For convenience, we restate the theorem below. See 9 Proof. of Theorem 9 . Fix the random strings used by \mathcal{A} and \mathcal{M} , denoted by \omega_{\mathcal{A}} and \omega_{\mathcal{M}} respectively, and let \omega\coloneq(\omega_{\mathcal{A}},\omega_{\mathcal{M}}) . Then, we may use \mathsf{Replay}(Z;\mathcal{A},\omega) from Alg. 3 to simulate the interaction between \mathcal{A} and \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}} and recover the predicate p chosen by \mathcal{A} , which corresponds to the last query issued by \mathcal{A} . By the same argument used in the proof of Lemma 10 , there exists a transcript Z(\omega,S)\in\mathcal{Z} such that \mathsf{Replay}(Z(\omega,S);\mathcal{A},\omega) outputs the correct predicate p\in\mathcal{P} . Furthermore, the total number of possible transcripts satisfies |\mathcal{Z}|\leq 8\epsilon^{-1}T^{128/(\lambda\epsilon)^{2}} (see the proof of Lemma 10 in Appendix B.1 ). Let \mathcal{A}(\omega_{\mathcal{A}}) (resp. \mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}}(\omega_{\mathcal{M}}) ) denote the adversary (resp. the mechanism) executed with fixed random coins \omega_{\mathcal{A}} (resp. \omega_{\mathcal{M}} ) and \mathsf{Succ}^{\perp,\,\mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}}}_{\mathcal{P},\mathcal{D}}(M,T) denote the maximum PSO success probability over all trivial adversaries. Then, \displaystyle\mathsf{Succ}^{\mathcal{A},\,\mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}}}_{\mathcal{P},\mathcal{D}}(M,T) \displaystyle=\Pr_{\mathsf{PSO}_{M,T,\mathcal{P}}[\mathcal{A}\rightleftharpoons\mathcal{M}]}\big[\,\mathsf{iso}(p,S)\text{ and }p\in\mathcal{P}\,\big] \displaystyle=\expec_{\omega_{\mathcal{A}},\omega_{\mathcal{M}},S}\left[\,\Pr_{\mathsf{PSO}_{M,T,\mathcal{P}}[\mathcal{A}(\omega_{\mathcal{A}})\rightleftharpoons\mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}}(\omega_{\mathcal{M}})]}\big[\,\mathsf{iso}(p,S)\text{ and }p\in\mathcal{P}\,\big]\,\right] (by Fubini’s theorem) \displaystyle=\expec_{\omega_{\mathcal{A}},\omega_{\mathcal{M}},S}\left[\,\Pr_{p\leftarrow\mathsf{Replay}(Z(\omega,S);\mathcal{A},\,\omega)}\big[\,\mathsf{iso}(p,S)\text{ and }p\in\mathcal{P}\,\big]\,\right] \displaystyle\leq|\mathcal{Z}|\cdot\begin{array}[t]{@{}c@{}}\underbrace{\expec_{\omega_{\mathcal{A}},\omega_{\mathcal{M}},S}\left[\,\Pr_{\begin{subarray}{c}Z\sim U_{\mathcal{Z}}\\ p\leftarrow\mathsf{Replay}(Z;\mathcal{A},\,\omega)\end{subarray}}\big[\,\mathsf{iso}(p,S)\text{ and }p\in\mathcal{P}\,\big]\,\right]}\\ \text{$p$ is independent of $S$.}\end{array} \displaystyle\leq|\mathcal{Z}|\cdot\mathsf{Succ}^{\perp,\,\mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}}}_{\mathcal{P},\mathcal{D}}(M,T), and the claim follows from |\mathcal{Z}|\leq 8\epsilon^{-1}T^{128/(\lambda\epsilon)^{2}} and \mathsf{Succ}^{\perp,\,\mathcal{M}_{\mathsf{AQA}\textup{-}\mathsf{OGD}}}_{\mathcal{P},\mathcal{D}}(M,T)\in\mathsf{negl}(M) for \mathcal{P}\in\{\mathcal{P}_{\mathsf{low}},\mathcal{P}_{\mathsf{high}}\} ( Cohen and Nissim 2020 ) . ∎