1 Introduction↩︎

Training large-scale AI models using statistical machine learning is notoriously costly. Due to the resource demands of running ML algorithms, AI users rely upon pre-trained models from a handful of tech companies. These companies hold enough data—so they claim—to train general-purpose models that are effective across a wide range of settings. In this setup, however, users receive no guarantee that the AI models were trained appropriately. If users fear that the training data does not adequately reflect their setting, they must investigate, for themselves, whether the model produces errors (or worse, harms) within their application.

Inspired by these issues, Goldwasser, Shafer, Rothblum, and Yehudayoff [1] introduced and studied the problem of delegating machine learning, through the PAC Verification framework. Building on the classic model of interactive proofs [2], [3], PAC Verification formalizes the problem: a statistically-limited user (the verifier) interacts with a powerful, but untrusted learner (the prover), who aims to convince the user that a given model (the hypothesis) is valid. As in cryptographic proof systems, PAC Verification requires that protocols for delegating learning satisfy formal notions of completeness and soundness. To date, results in the area focus on developing protocols for verifying Agnostic PAC Learning [4]–[6] for specific concept classes [1], [7], [8]. As a notable exception, Mutreja and Shafer [7] also introduce a notion of delegation of Statistical Query (SQ) algorithms for loss minimization.

An essential element of prior works on delegation of learning is interaction. To establish whether a given hypothesis is valid, the prover and verifier exchange a sequence of messages in an online fashion, after which the verifier chooses to accept or reject the prover’s hypothesis. As a concrete example, the original work on PAC verification shows how to delegate the Goldreich-Levin algorithm [9] (which requires point query access to the unknown function), when the verifier only has i.i.d.labeled samples. In this proof system, the verifier uses its interactions with the prover to label the point queries, while cleverly hiding some points whose labels are known to the verifier to ensure soundness. The early works on PAC verification have demonstrated that interactive proof systems provide a powerful tool for efficiently checking the results of an expensive ML computation.³

Interaction, however, also presents challenges. Most immediately, running an interactive proof requires the verifier and prover to be online at the same time to execute the protocol. Additionally, each execution of the interactive proof may require the prover to answer execution-specific challenges, including re-running the original ML computation. Given the immense cost of training ML models in the first place, providers may be unwilling to participate in the interactive proof more than once (if at all). In such a setting, where the interactive proof is executed once—between the learner and a single verifier—many users would have to place their trust in a single entity. Even if users agree that the verifier is generally trustworthy, as before, individual users may worry that the verifier’s data does not represent their setting and applications.

1.0.0.1 This Work.

We initiate the study of non-interactive proofs of learning. Our study leads us to a new notion: Publicly-Verifiable Certificates of Statistical Validity (pvCSVs). pvCSVs allow for public, distributionally-robust certification that the result of a learning algorithm is valid. In particular, a pvCSV allows a learner to publish a hypothesis \(h\) and certificate of validity \(\pi\) that allows any downstream user to subsequently verify that the hypothesis is statistically valid on a user-specified distribution.

We can understand the semantics of a pvCSV by imagining two worlds.

• In the first world, a user collects a huge amount of data from a distribution \(\D\), relevant to their setting and application. Then, they correctly execute a statistical learning algorithm \(\A\) on top of this data to obtain a hypothesis \(h_\mathrm{ideal}\).

• In the second world, a centralized, well-resourced learner publishes a pvCSV \((h_\mathrm{real},\pi)\) for the algorithm \(\A\); the same user from before collects a much more modest amount of data from \(\D\), then reads and verifies \((h_\mathrm{real},\pi)\), using the small amount of user-specific data.

A pvCSV guarantees that if \((h_\mathrm{real},\pi)\) passes verification, the two worlds produced equally-valid hypotheses \(h_\mathrm{ideal} \approx_{\D,\A} h_\mathrm{real}\) according to the user-specific data distribution and the learning algorithm \(\A\). This guarantee must hold even though the user has no knowledge of the data distribution used to produce the pvCSV. As such, pvCSVs resolve the key shortcomings of interactive proofs for delegation of learning: the learner can execute the expensive training algorithm once and (with little overhead) generate a corresponding pvCSV certificate that any user can subsequently verify.

1.0.0.2 Certification of Adaptive Data Analysis.

We make our study of pvCSVs concrete by revisiting the question of Adaptive Data Analysis [10] in the Statistical Query Model [11]. Many tools for learning from data—including workhorse ML algorithms like gradient descent—can be framed as adaptive statistical algorithms. In such an algorithm, the learner is allowed to ask a sequence of queries of the data distribution (e.g., What is the gradient of the expected loss over \(\D\)?), where each query may depend on the results from prior queries.

Formally, we consider learning algorithms \(\A\) that interact with a Statistical Query (SQ) oracle \(\O\): given a tolerance \(\tau\) and a query \(q\), \(\O(q)\) responds with a \(\tau\)-accurate estimate of the expectation of the predicate \(q\) over the data distribution. Critical to our investigation, the algorithm may select its sequence of queries adaptively based on the prior responses. That is, the algorithm’s choice of the \(i\)-th query \(q_i\) may depend arbitrarily on prior queries \(q_1,\ldots,q_{i-1}\) and responses \(\O(q_1),\ldots,\O(q_{i-1})\), (e.g., What is the gradient at the \(i\)-th iterate, after taking \(i-1\) gradient descent steps?).

While the paradigm of adaptive data analysis is a versatile and powerful tool for learning, such algorithms are known to be statistically expensive. About a decade ago, [10] identified adaptivity as a key issue in statistical algorithms. To maintain the statistical validity of an adaptive analysis requires the learner to either resample fresh data to support every new query, or to employ sophisticated (differentially-private) algorithms for answering queries in a way to prevent overfitting to the data set [10], [12]–[18]. To answer \(k\) adaptively selected statistical queries, the best algorithms use a number of samples scaling (roughly) with \(\sqrt{k}\), and in fact, this dependence is essentially tight [19], [20].

In other words, no matter what techniques are employed, adaptive statistical algorithms require exponentially more data than non-adaptive (batch) statistical analyses of similar size. In this work, we ask when we can certify the results of adaptive data analysis more efficiently than learning.

1.1 Our Contributions↩︎

We develop proof systems for delegating arbitrarily-adaptive statistical algorithms where the verifier requires samples scaling only with the non-adaptive complexity. In doing so, we realize an exponential gap, between the sample complexity required for executing SQ algorithms versus verifying them. Moving beyond prior work on interactive proofs for learning, we build novel non-interactive proof systems—namely, publicly-verifiable Certificates of Statistical Validity—that enable a new form of distributionally-robust validation of statistical learning. Along the way, we develop a number of extensions to earlier models of proof systems for delegation of learning.

1.1.0.1 Publicly-Verifiable Certificates of Statistical Validity.

In Section 3, we introduce our primary contribution: a new notion of proof that allows for public, distributionally-robust certification of learning. A publicly-verifiable Certificate of Statistical Validity (pvCSV) is a non-interactive proof system that allows any verifier to certify the results of a statistical computation with respect to the verifier’s own distribution. A pvCSV allows a single, well-resourced learner—the prover—to publish the results of a statistical algorithm in a way that can be checked efficiently (with less resources) by any downstream verifier; in particular, the verifiers need not hold the same distribution as the prover. Instead, the proof system guarantees a universal soundness property such that if the verifier accepts the proof, then the results of the statistical algorithm are valid on the verifier’s distribution—even if the algorithm was executed using samples from a different distribution.

One way to understand the guarantee of pvCSVs is as a robust proof of statistical validity, without an explicit assumption about distributional shifts. Rather than positing some known relationship between the prover and verifier distributions, the verification procedure works for any \(\D_P\) and \(\D_V\) and results in acceptance whenever the published certificate—derived from the execution of a learning algorithm \(\A\) using the prover’s distribution—reflects some legitimate execution on the verifier’s distribution. While our notion of completeness assumes that \(\D_P = \D_V\), the guarantee is more subtle than this equality would suggest. The distributions \(\D_P\) and \(\D_V\) may differ significantly in composition, but if the verifier accepts, then (by universal soundness) the hypothesis \(h\) is valid for \(\D_V\) (because the distributions are indistinguishable according to some invocation of \(\A\)). The careful reader will note that this “universal soundness” condition is actually implied by standard soundness for delegation of learning,⁴ but holds new significance in the context of non-interactive proofs. Our view on soundness, paired with a non-interactive proof system, allows us to realize certificates of learning that can be verified publicly by any user.

We can use various measures of complexity to evaluate the quality of a pvCSV construction. Principle to our work is sample complexity: we aim for pvCSVs where the verifier saves considerably in the number of samples needed from \(\D_V\) compared to the number of samples required for learning (or proving). Further, we can track other measures like time complexity (of both the verifier and the honest prover) and proof length as well. We define pvCSVs formally in Section 3 and provide a thorough discussion of the notion and its properties (like validity and universal soundness) therein.

With this key definition in place, the main technical contributions of this work are to construct pvCSVs for adaptive statistical algorithms within the SQ learning framework. Our pvCSVs achieve an exponential gap in the sample complexity between SQ verification and SQ learning. While the core idea of each of our constructions is similar, the resulting protocols differ in important ways based on properties of the original SQ algorithm. As we show, the way that the algorithm uses randomness and the way the SQ oracle is allowed to adapt to the algorithm’s internal state are key factors in building universally-sound pvCSVs.

1.1.0.2 pvCSVs for Deterministic SQ Algorithms.

In Section 3.1, we consider SQ algorithms that do not use internal randomness. These “deterministic” SQ algorithms are considerably simpler to reason about, and as such, we obtain strong, statistically-sound pvCSVs for all such algorithms.⁵

In other words, even though the best learning algorithms use \(\tilde{O}(\sqrt{k})\) samples to support \(k\) adaptively-chosen queries, there is a short certificate (namely, the results of the queries) that convinces a verifier with considerably less information about the distribution in \(O(\log(k))\) samples. The bounds of Theorem [result:deterministic] follow from the prover and verifier collectively executing a direct simulation of the original SQ algorithm with no overhead for the honest prover; in this sense, the delegation scheme can be thought of as doubly-efficient in its statistical complexity, à la [21]. Computationally, both the prover and the verifier need to simulate the execution of the underlying SQ algorithm, so the time-complexity scales roughly linearly in the running time of the original algorithm.

1.1.0.3 pvCSVs for Randomized SQ Algorithms and SQ Protocols.

In Section 4, we investigate how to build pvCSVs for SQ algorithms that use randomness. Randomness introduces significant technicality in the resulting proof systems. Here, we give an informal description of our results, including various definitions we develop to obtain the results.

Towards a pvCSV for randomized SQ algorithms, we need to reason about how the algorithm—and the (possibly-adversarial) SQ oracle—may act adaptively to the randomness. First, we say that a randomized SQ algorithm operates in \(\ell\) “epochs” if it can be broken down into a series of \(\ell\) deterministic SQ algorithms, which each take a fresh random string as an input. Next, we say that an SQ oracle is “public-state” if it may choose its query responses as a function of the SQ algorithm’s internal randomness (in contrast to an “oblivious” oracle, which has no knowledge of the algorithm’s randomness). We construct pvCSVs in the Random Oracle Model (ROM) [22] for all constant-epoch randomized SQ algorithms that are correct using a public-state SQ oracle.

In fact, Theorem [result:randomized] follows from a much more general result. We start by adapting the definition of delegation of learning [1] to the statistical query setting, yielding a format for interactive learning which we call SQ protocols. We show that a large class of interactive SQ protocols (of which randomized SQ algorithms are a special case) can be compiled into a canonical SQ protocol with desirable properties. The class consists of SQ protocols where the verifier may send random and non-random challenges to the prover and may make private statistical queries (not sent to the prover) to its public-state oracle; we call these protocols “mixed-message, private-query” SQ protocols. After compilation, we obtain a canonical SQ protocol with the same completeness and soundness guarantees as the original, but which is public-coin (verifier only sends random challenges) and public-query (verifier reveals all SQs to the prover). Importantly, the canonical verifier still only makes a single batch of statistical queries.

This canonical SQ protocol can then be compiled into a pvCSV via a Fiat-Shamir transformation [23], whose blow-up in soundness scales exponentially with the “epoch complexity” of the original protocol. The sample complexities claimed in Theorem [result:randomized] follow by giving sample-based implementations of an adaptive SQ oracle (for the prover) and non-adaptive SQ oracle (for the verifier). As a consequence, we obtain computationally-sound pvCSVs for a much broader class of learning goals—those that can be solved by an interactive SQ protocol according to Lemma [result:canonical].

As may be evident, to appropriately reason about delegation of learning in this context, we need to reason about a number of novel concepts (e.g., SQ protocols, public-coin, public-query, epoch complexity, etc.). An additional key contribution of our work is laying out precise definitions for these notions that arise in the study of proof systems for learning, presented formally in Section 4.1. We discuss our construction of pvCSVs for randomized algoirthms/SQ protocols in greater detail within the Technical Overview.

1.1.0.4 Beyond pvCSVs: The Limits of SQ Protocols.

Building pvCSVs, particularly for randomized SQ algorithms, required investigating aspects of more general interactive protocols for statistical query learning. We complement our constructions of pvCSVs with a few results about the strengths and limitations of SQ protocols.

We show that, quite generically, verification of SQ protocols can be made statistically non-adaptive, in the sense that the verifier issues a single batch of statistical queries, and thus, has sample complexity scaling logarithmically in the number of queries. The exact class of protocols which we can delegate soundly in this manner is a bit technical, but it consists of a large class of “public-query” SQ protocols. In particular, the class of protocols includes private-coin protocols, where the verifier maintains secret randomness from the prover, but allows the prover to know which statistical queries the verifier issues.

This result shows that statistical validation of a large class of SQ protocols can be done in non-adaptive sample complexity. A natural question, then, is whether this statistically-efficient verification scheme can be made computationally-efficient. Unfortunately, we show a barrier to generic computational savings in the SQ model. Piggybacking off of a sample complexity lower bound given by [7] for PAC Verfication, we obtain a lower bound on the verifier’s query complexity for the same class of SQ protocols from Proposition [result:protocol].

1.1.0.5 SQ Verification under Differential Privacy.

Finally, we show that the verifiers of all of our pvCSVs and interactive SQ protocols can be implemented under Differential Privacy [24]. Differential Privacy (DP) is the de facto notion to protect individuals’ data in statistical analyses, but it can be statistically costly: implementing SQ algorithms under DP requires sample complexity akin to adaptive data analysis. This result shows that a verifier can validate the results of a statistical analysis much more efficiently, while still maintaining privacy over their own data set.

The new private verifiers use essentially the same number of samples as the non-private verifiers. Concretely, we state the result for the pvCSV verifiers.

1.2 Technical Overview and Discussion of Results↩︎

In the remainder of the introduction, we give a more detailed overview of our models and results. Throughout, we aim to provide pointers into the main text for formal presentation. We include discussion of the significance of the results, connections to prior works, as well as possible extensions.

The primary goal of our work is to take an arbitrarily-adaptive SQ algorithm \(\A\) and turn it into a pvCSV that can be verified efficiently. At a high-level our approach is simple: require the prover to run a direct simulation of \(\A\); then, check the prover’s work. In particular, the statistically-expensive aspect of adaptive data analysis is generating the sequence of queries \(q_1,\ldots,q_k\). Once the sequence has been generated, however, the answers to the queries \(q_1,\ldots,q_k\) can be checked in a single, non-adaptive batch of \(k\) statistical queries.

This observation immediately suggests a non-interactive proof system for delegating “deterministic” SQ algorithms that do not use any internal randomness, which is the focus of Section 3.1.

Note that even though we think of \(\A\) as deterministic since it does not use randomness, its adaptivity to the SQ oracle responses introduces non-determinism, so verifying the consistency of the transcript is a non-trivial aspect of the verifier’s check.

Given the simplicity of this delegation scheme, both the honest prover and verifier can be implemented very efficiently. The only overhead of the honest prover is to record the results of their statistical queries to be sent to the verifier (or posted for public verification), so the sample and time complexities scale precisely with the original complexities of the SQ algorithm \(\A\). To answer a sequence of adaptive queries to \(\tau\)-accuracy, the prover can be implemented in \(\tilde{O}(\sqrt{k}/\tau^2)\) samples [14], [17], [18]. The verifier also has to execute the algorithm \(\A\), so there is no computational savings, but the statistical savings are exponential. By concentration bounds, checking a batch of \(k\) statistical queries to \(\tau\)-accuracy can be achieved from \(O(\log(k)/\tau^2)\) samples.

1.2.0.1 Understanding Universal Soundness.

One of the key selling points of pvCSVs is the universal soundness condition: that any verifier holding \(\D_V\) which may differ significantly from the prover’s distribution \(\D_P\) can check the certificate while maintaining soundness. As described above, our pvCSV construction does not explicitly distinguish between the prover’s distribution \(\D_P\) and the verifier’s \(\D_V\). But in a sense that can be made formal, to obtain universal soundness, we only need for standard soundness to hold from the verifier’s perspective. Specifically, even if the pvCSV \((h,\pi)\) was generated honestly by a prover \(P\) holding \(\D_P\), to the verifer holding \(\D_V\), we can imagine \(P\) to be a potential cheating prover. In this case, the verifier may reject outright, or may accept if \(h\) actually satisfies the learning goal over \(\D_V\). The verifier’s final statistical validation—paired with the correctness guarantee of SQ algorithms—ensures that if the reported query responses from \(\pi\) are sufficiently close to the expectations on the verifier’s distribution \(\D_V\), then \(h\) is the result of some valid invocation of the SQ algorithm \(\A\) over \(\D_V\).

1.2.0.2 Handling Randomness.

For algorithms that use randomness, we cannot simply trust the prover to report a direct simulation of the execution of \(\A\), using untrusted randomness. Instead, a natural idea for a pvCSV is to convert the randomized algorithm into a public-coin protocol, then apply a Fiat-Shamir transformation [23], to obtain a non-interactive proof. In Section 4, we show that this approach works to yield pvCSVs, but we need to be careful in how we reason about the algorithm’s use of randomness, as well as how the SQ oracle affects the proof of soundness.

Starting from a randomized SQ algorithm \(\A\), we imagine breaking the algorithm into a series of “epochs” where in the \(i\)-th epoch, the algorithm samples fresh randomness \(r_i\), and then executes a deterministic SQ algorithm \(\A_i\) until the end of the epoch. Every randomized algorithm can be broken into epochs, but different algorithms require more or fewer epochs. At the low extreme, an algorithm that uses a random initialization, then executes deterministically, would have epoch complexity \(1\); at the other extreme, a stochastic optimization algorithm that makes random choices at every iteration based on fresh independent coins will have high epoch complexity. The epoch complexity of the algorithm \(\A\) controls the complexity of the resulting proof system.

In particular, we can turn any SQ algorithm of epoch complexity \(\ell\) into a public-coin interactive proof in the SQ model of round complexity \(\ell\). At the start of each epoch \(i\), the verifier \(V\) sends randomness \(r_i\) to the prover \(P\). Then, the honest prover \(P\) simulates the deterministic algorithm \(\A_i(r_i)\) using its own oracle \(\O_P\) to answer any statistical queries. At the end of the epoch, the prover can return a transcript, similar to in the deterministic case, that summarizes the statistical queries and oracle responses. At the end of all epochs, the verifier can issue a non-adaptive batch of queries to \(\O_V\) to ensure that the responses were all sufficiently accurate.

As described, the SQ protocol is complete, but has a subtle issue with soundness without further assumptions. In the original algorithm, \(\A\) issues its queries to an SQ oracle \(\O\), whereas in the protocol, the verifier \(V\) simulates \(\A\) but delegates the SQs to the prover. The key distinction between these two setups is that the prover also receives the internal randomness of the algorithm \(r_i\), as the public-coin message at the start of each epoch. In other words, to ensure soundness, the original randomized algorithm \(\A\) must be correct even for SQ oracles that have full knowledge of the state of \(\A\). Algorithms whose correctness hinges on the obliviousness of \(\O\) to the randomness of \(\A\) cannot be delegated in this way while maintaining soundness. Formally, we define “public-state” SQ oracles in Section 4.1, along with the corresponding correctness notion for SQ algorithms.

Once we restrict our delegation to randomized SQ algorithms which are correct under this more powerful SQ oracle, then we obtain a sound public-coin protocol. To obtain pvCSVs, we appeal to the Random Oracle Model (ROM), and show how to apply the Fiat-Shamir transform to our protocol. There is some subtlety in defining the notion of universal soundness for pvCSVs in the ROM and then subsequently arguing that Fiat-Shamir applied to our protocol obtains such soundness. With the appropriate definitions in place, the soundness proof follows by following the state restoration approach of [25], [26].

1.2.0.3 Beyond SQ Algorithms.

Building pvCSVs for randomized SQ algorithms required us to define and investigate a number of more general models of proof systems in the SQ model. A key result we show in Section 4.2 is that a diverse class of interactive SQ protocols can be compiled into a canonical public-coin SQ protocol. In a sense, this result is an analogue of the established understanding of public-coin protocols for delegation of computation. We show that, quite generically, if an SQ protocol consists of a verifier that reveals its randomness to the prover, there is a canonical version of the protocol where the only messages the verifier sends to the prover are its randomness. Further, the verifier need not maintain any private statistical queries, but can delegate all of its queries to the prover, then execute one final non-adaptive validation. This result holds in the same model of public-state SQ oracle, which may adapt to the state of the verifier. With this canonical compiler for SQ protocols, we can similarly obtain computationally-sound pvCSVs in the ROM, by applying Fiat-Shamir to the canonical protocol.

1.2.0.4 Towards Computationally-Efficient Certification of Learning.

In this work, our focus is on developing statistically-efficient proofs of learning. We make no effort to optimize the verifier’s running time. Our pvCSV verifier for an SQ algorithm \(\A\) runs in time proportional to the running time of \(\A\). A natural question in the study of proof systems is whether we can save on computation time during verification.

In Section 5, we show some barrier to generic speed-ups (at least within the SQ framework). In particular, Corollary [result:lb] shows that there are statistically learnable VC classes, for which there is no computationally-efficient SQ verification scheme, even if we allow for interaction. Our SQ lower bound is actually a consequence of the efficiency of our verification schemes (in terms of the number of statistical queries) and an existing lower bound on the samples required for verification from [7] in terms of the VC dimension. In other words, a fast SQ verification scheme (which doesn’t make many SQ queries) would imply an impossibly-statistically-efficient verification scheme for the VC class studied by [7].

Nevertheless, in some sense, our exploration of pvCSVs and SQ protocols provides new design principles for simultaneously statistically and computationally efficient verification. Recall that the canonical protocol of Lemma [result:canonical], which compiles into a pvCSV as in Theorem [result:randomized], applies not just to randomized algorithms but to a broad class of SQ protocols. Further, the verifier in the resulting pvCSV runs in time proportional to (or less than) the verifier in the original protocol—not the full simulation of \((P,V)\). In other words, if we can design SQ protocols that reduce verification time, then we may get simultaneous statistical and computational efficiency for free (provided the protocol is covered by Lemma [result:canonical]).

Concretely, our results show that minimizing the epoch complexity of a learning procedure—even if that entails designing an interactive proof system—may actually lead to more efficient pvCSVs than simply focusing on delegating algorithms for learning. Such observations may also motivate a deeper study of pseudorandomness in machine learning; for instance, if a randomized SQ algorithm can actually be proved correct under a weaker source of randomness, it may reduce the epoch complexity and improve efficiency.

1.2.0.5 Publicly-Verifiable End-to-End DP.

Finally, in Section 6, we show Proposition [result:dp], which implies a mechanism for verifying pvCSVs statistically efficiently under Differential Privacy with respect to the verifier’s samples. Given such a verifier, it’s tempting to wonder whether we can achieve End-to-End DP over both the prover’s samples from \(\D_P\) and the verifier’s from \(\D_V\). The existence of a DP verifier implies an honest prover strategy to achieve such a goal. Due to the connections between adaptive data analysis and DP, this honest prover strategy is no more expensive than accounting for adaptivity.

That said, in our setting, we’d have no guarantees about the behavior of the cheating prover, who might violate DP arbitrarily. To handle the possibility of a cheating prover, we could employ a scheme for Certified DP of [27]. Certified DP ensures that a prover’s release of statistical queries follows a DP mechanism with respect to some committed-to, but untrusted database \(X \sim \D_P\), in a manner that can be verified publicly. In this sense, adding our DP statistical validation scheme as post-processing to the output of a Certified DP mechanism would allow the verifier to be convinced of End-to-End DP, while also ensuring statistical accuracy of queries from the untrusted database \(X\) under the verifier’s distribution \(\D_V\).

1.3 Related Works↩︎

Our study of pvCSVs and SQ protocols lives in the intersection of learning theory and cryptographic proof systems. We highlight some of the most relevant related lines of work.

1.3.0.1 Proof Systems for Learning and Statistics.

Proof systems for statistical algorithms grew out of the literature on interactive (cryptographic) proof systems [2], [3]. The PAC Verification, introduced in [1], led to a number of results about strengths and limitations of interactive proofs of learning [7], [8]. Most related to our work is the work of Mutreja and Shafer [7], who also thought about the issue of delegating SQ algorithms in the context of loss minimization. In fact, in a subsequent journal version [28], the authors independently include a result analogous to Proposition [result:protocol], on the interactive delegation of adaptive SQ algorithms.

Other works have investigated certifying properties of learning algorithms. [27] recently designed mechanisms for public cerification of differential privacy (and other private probabilistic mechanisms) in the release of statistical queries. Following this work, [29] extended the techniques to give a publicly-verifiable implementation of DP Stochastic Gradient Descent, without appealing to heavy-handed cryptographic primitives for certifying generic computations.

Beyond proofs for learning algorithms, there has been significant work investigating proof systems for properties of distributions. Initiated by [30], a sequence of works [31]–[34] has established doubly-efficient proof systems for distribution testing.

1.3.0.2 Adaptive Data Analysis.

Since its identification as a key algorithmic challenge [10], [12], [13], Adaptive Data Analysis has seen significant developments, in line with the developments of sophisticated tools for Differential Privacy [24]. The majority of work studying adaptive data analysis focuses on the problem of answering statistical queries. [14] first showed near-optimal \(\tilde{O}(\sqrt{k})\) dependence on the number of adaptively chosen queries. Subsequently, a sequence of papers has simplified their analysis and techniques and improved their bounds [15]–[17]. Recently, [18] showed that a much simpler subsampling mechanism actually suffices for optimal adaptive data analysis—despite the fact that it does not suffice for DP. Indeed, the analysis of [18] does not go through the standard “transfer theorem” that DP implies adaptive generalization, but rather analyzes the effects of subsampling directly.

2 Preliminaries↩︎

We give formal definitions of the statistical query model of learning [11] that we adopt, as well as proof systems developed in the context of verifying machine learning [1], [7]. We start with background on the SQ Model. Then, we discuss our formalisms for algorithms and proof systems that use SQ oracles. We defer some technical aspects of our learning model (particularly those related to algorithms’ use of randomness) to the relevant technical section (Section 4.1). Finally, we review background on adaptive data analysis and the complexity of implementing SQ algorithms from samples [12].

2.1 The Statistical Query Model↩︎

The Statistical Query (SQ) Model [11] abstracts away the notion of learning from samples to the notion of learning from approximate statistics. In this model, the learning algorithm is allowed to specify predicates \(q:\X \to \{0,1\}\) from a collection⁶ \(\Q \subseteq \{0,1\}^\X\) and receive—from the statistical query oracle—the (rough) expectation of the queried predicate on the distribution of interest \(\D\).

Many notable learning algorithms can be described in the SQ Model, including most (Agnostic) PAC Learning algorithms⁷ [11] as well as more modern ML algorithms like Gradient Descent.

We remark that, per the definition, the SQ oracle \(\O\) with \(\tau\)-accuracy must always report approximate expectations within \(\tau\) of the true expectation. As such, given access to an SQ oracle, we can hope to design algorithms that always succeed. In Section 2.3, we discuss concrete, sample-based implementations of the SQ oracle abstraction, which necessarily introduce a failure probability.

2.1.0.1 Learning Goal.

We consider an abstract setting of learning over distributions \(\D\) supported on a domain \(\X\), such as \(\X = \{0,1\}^d\) for some finite dimension \(d \in \mathbb{N}\). Additionally, we consider an abstract collection of hypotheses \(\H\). We define the goal of learning in terms of identifying a hypothesis within some “good” set of hypotheses \(\G(\D)\subseteq \H\), parameterized by the distribution \(\D\).

For instance, in the context of Agnostic PAC learning, we can take \(\H\) to be the concept class \(\H \subseteq \{h: \{0,1\}^d \to \{0,1\}\}\), and the good subset \(\G(\D)\subseteq \H\) to be all hypotheses achieving classification error \(\Pr[g(x) \neq y] \le \Pr[h^*(x) \neq y] + \eps\) competitive with the best \(h^* \in \H\) over \(\D\). We adopt this abstract notion of learning, rather than a concrete notion like the PAC framework, in order to emphasize the generality of our approach. At the extreme, we may take the hypotheses \(\H\) to be the collection of sequences of statistical queries and expectations, and the good set \(\G(\D)\) to be sequences that arise as a valid execution of a statistical algorithm on \(\D\). (We comment further on our choice of abstract Learning Goal after Definition 7 of protocols for delegating SQ learning.)

2.1.0.2 Statistical Query Algorithms.

Naturally, we define SQ algorithms as algorithms that may make calls to an SQ oracle. For SQ algorithms that solve a learning goal, we need to specify the approximation parameter \(\tau > 0\) necessary to guarantee correctness. Formally, we distinguish between deterministic and randomized SQ algorithms.

When \(\A\) is deterministic, without loss of generality, we can think of the SQ oracle \(\O\) as a pre-specified function where \(\O(q)\) is defined for all \(q \in \Q\) up front, rather than a stateful algorithm responding sequentially. Specifically, if the queries that \(\A\) issues are a deterministic function of the input to \(\A\) and the responses given by \(\O\) so far, then a pre-specified function can simulate any stateful oracle, by simply running \(\A\) ahead of time. Note the output of running \(\A\) with \(\tau\)-accurate oracle \(\O\) may still be nondeterministic based on the choice of \(\O\), even if \(\A\) doesn’t flip coins. That said, we insist that given a \(\tau\)-accurate (idealized) oracle \(\O\), the algorithm \(\A\) always succeeds.

2.1.0.3 Randomized SQ Algorithms.

In our study of SQ proof systems, the distinction between deterministic and randomized algorithms is significant. In contrast to deterministic algorithms, when \(\A\) is randomized, it becomes important to think of the SQ oracle \(\O\) as a stateful adversary, who responds with knowledge of prior queries/responses, subject to \(\tau\)-accuracy. That is, for a sequence of queries \(q_1,q_2,\ldots,q_k\), the response \(a_i = \O(q_i)\) may depend on \(\langle q_1,a_1,q_2,a_2,\ldots,q_{i-1},a_{i-1},q_i\rangle\). An SQ algorithm that learns \(\G\) must output a good hypothesis with high probability, no matter what decisions the oracle makes in response to the sequence of queries.

With this high-level definition in place, we defer significant details and definitions about randomized SQ algorithms to Section 4.1, which are essential to understanding our pvCSVs for randomized SQ algorithms and SQ protocols. In particular, we consider two flavors of SQ oracles for randomized algorithms, “oblivious” oracles (as in Definition 1) and “public-state” oracles (see Definition 14).

2.1.0.4 Complexity Measures for SQ algorithms.

An important complexity measure of SQ algorithms is the number of statistical queries the algorithm makes \(B\), as well as the adaptivity to prior query responses \(k\). The adaptivity of an SQ algorithm \(\A\) is the number of rounds in which batches of queries are issued to \(\O\). At the extremes of adaptivity, \(k = B\) is a fully-adaptive algorithm, where the choice of each query \(q_i\) is determined as an arbitrary function of the prior queries and responses \(\langle q_1,\O(q_1),q_2,\O(q_2),\ldots,q_{i-1},\O(q_{i-1}) \rangle\); whereas \(k = 1\) is a non-adaptive SQ algorithm and all of the queries are issued in a single batch. As we discuss in Section 2.3, the adaptive query complexity determines how efficiently we can implement the SQ oracle from samples.

Additionally, we will informally track the running time of SQ algorithms (eliding details of computation over real-valued responses from the SQ oracle).

For simplicity’s sake, in both query and time complexity, we assume that randomized SQ algoirthms provide a deterministic guarantee on the complexity (that is, a BPP-style guarantee).

2.2 Proof Systems for Statistical Learning↩︎

We consider proof systems for statistical learning based off of the classic notions from complexity theory and cryptography [2], [3], and more recently the notion of PAC Verification [1]. In this setting, a prover \(P\) and a verifier \(V\) interact in order for the verifier to be convinced that a given hypothesis \(g \in \G(\D)\) is good for a learning goal. We model \(P\) and \(V\) as randomized algorithms and denote their interaction as \((P,V)\). We adapt the notions from recent works on PAC Verification to define a model of interactive proof system where the parties have access to SQ oracles as follows.

In other words, in an SQ protocol, there exists an honest prover strategy that allows the verifier to accept a good hypothesis \(g \in \G(\D)\) with high probability, and conversely, if the verifier accepts a hypothesis \(\tilde{g}\), then with high probability,⁸ the hypothesis \(\tilde{g} \in \G(\D)\), even if it was generated through an interaction with a different prover.

Note that, as is standard, we imagine the cheating prover \(\tilde{P}\) is all-powerful and may have arbitrary knowledge of the distribution \(\D\). Additionally, we equip the cheating prover with the verifier’s oracle \(\O_V\); that is, for any query that the verifier asks \(q \in \Q\), the precise value \(a = \O_V(q)\) is known to both \(V\) and \(\tilde{P}\). (That said, the verifier may choose to keep queries private from the prover.)

There are many properties of SQ protocols that may be of interest. For instance, we consider both private- and public-coin protocols (or, as hinted above, private- and public-query protocols). We defer these definitions—particularly those related to our construction of pvCSVs—to Section 4.1.

Implementing the oracles from samples will necessarily incur some additional failure probability \(\delta > 0\), distinguished from soundness error \(\gamma\) of the original protocol. Accounting for the failure probability \(\gamma\) of the oracle-based protocol separately from the failure probability \(\delta\) that arises from sampling actually leads to improved analysis of the soundness of some of our protocols. We discuss background on the sample complexity of adaptive SQ algorithms in Section 2.3.

2.2.0.1 Comparison to PAC Verification.

Definition 7 is directly inspired by the notion of PAC Verification of statistical algorithms [1], [7], but departs in a few key ways.

First off, our notion of learning is not tied directly to Agnostic PAC learning (or loss minimization as in [7]). Instead, we elect to use our abstract learning goal (Definition 2) as the basis for SQ Protocols. We make this choice because the protocols we design are not actually tied to any properties of loss minimization, but instead run a direct simulation of a given SQ algorithm. So, provided we start with a learning algorithm \(\A\) that achieves its learning goal with good probability, we can turn it into a SQ protocol that also learns \(\G\).⁹

Second, we define SQ protocols in the SQ oracle model, rather than in terms of direct samples from the distribution. In reality, we will be interested in understanding the statistical resources (i.e., samples) necessary to implement the verifier and honest prover strategies. As in the earlier works on PAC verification, the goal is to design SQ protocols where the verifier’s oracle \(\O_V\) can be implemented more efficiently than the honest prover’s \(\O_P\). For instance, quantitatively, perhaps \(P\) requies an oracle with much tighter tolerance than \(V\), \(\tau_P < \tau_V\); or as in our work, qualitatively, \(P\) may require an adaptive oracle, whereas \(V\) uses a non-adaptive oracle. That said, nothing precludes a hybrid definition, where the verifier only has SQ oracle-access to \(\D\), but the prover has more refined access through samples or point evaluations..

2.2.0.2 Computational Soundness and The Random Oracle Model.

Definition 7 assumes that cheating provers are computationally-unbounded. We refer to this property as statistical soundness. In contrast, we say that computational soundness holds when we prove soundness against probabilistic polynomial-time cheating provers \(\tilde{P}\). When we consider computational soundness, we will still assume that \(\tilde{P}\) may hold prior, detailed knowledge of \(\D\) (so need not be given an SQ oracle), but does not have the computational resources to break cryptographic primitives.

We will be particularly interested in computational soundness when designing pvCSVs for randomized SQ algorithms. To do so, we leverage a key cryptographic paradigm: The Fiat-Shamir Transformation [23]. The heuristic takes a public-coin interactive protocol and removes interaction by emulating the verifier’s random messages with calls to a cryptographic hash function. Classically, the soundness of Fiat-Shamir is proved in the Random Oracle Model (ROM) [22], which models public access to an (idealized) hash function.

Note that when we consider protocols that operate in the ROM, the probability of violating computational soundness is over the verifier’s random coins as well as the draw of the random oracle.

While, in full generality, soundness does not transfer from the ROM to realizable models of computation [35], [36], proofs of soundness in the ROM are generally considered as strong evidence of security and sufficient for many practical applications. Our pvCSVs for randomized SQ algorithms will be proved computationally-sound in the ROM.

2.3 Sample-Based Implementation of SQ Oracles↩︎

To run SQ learning algorithms/protocols, we need a concrete implementation of the SQ oracle abstraction based on samples drawn from \(\D\). The number of samples required to guarantee statistical validity of the oracle’s responses depends on features of the SQ algorithm \(\A\).

In particular, the sample complexity depends on the number of queries issued \(B\), the desired accuracy \(\tau\), as well as the adaptivity \(k\). The adaptivity of an SQ algorithm \(\A\) is the number of rounds in which batches of queries are issued to \(\O\). At the extremes of adaptivity, \(k = B\) is a completely adaptive algorithm, where the choice of each query \(q_i\) is determined as an arbitrary function of the prior queries and responses \(\langle q_1,\O(q_1),q_2,\O(q_2),\ldots,q_{i-1},\O(q_{i-1}) \rangle\); whereas \(k = 1\) is a non-adaptive SQ algorithm and all of the queries are issued in a single batch. The following definition captures these dependencies.

We define the notion of an SQ Oracle implementation in terms of the rounds of adaptivity and the total number of queries, because certain mechanisms are able to exploit limited adaptivity to achieve better sample complexity [10], [37]. Note that, in order to guarantee \(\tau\)-accurate queries, we can assume that our implementation returns values using \(O(\log(1/\tau))\) bits of precision.

Crucially for our work, the sample complexity required to answer a non-adaptive batch of queries is an exponential improvement over the complexity required to answer an adaptively-selected sequence of queries. For a non-adaptive batch of queries, the empirical SQ oracle that takes \(m\) samples \(x_1,\ldots,x_m \sim \D\) and reports \(\O(q) = \frac{1}{m} \sum_{i=1}^m q(x_i)\) achieves logarithmic dependence on the number of queries.

Proposition [prop:non-adaptive] follows by a standard application of Hoeffding’s inequality. The sample complexity for answering an adaptively-selected sequence of statistical queries, however, requires much more sophisticated analysis. The complexity was only established in the past decade, after connecting the problem of adaptive data analysis with the technique of Differential Privacy [24].

In the case of fully-adaptive algorithms, where \(k = B\) statistical queries are issued adaptively, the (roughly) optimal sample complexity scales with \(\sqrt{k}\), rather than \(\log(k)\). Initially, the upper bounds followed by leveraging the stability properties of differentially-private query release [14], [17], but the most recent result of [18] leverages a subsampling technique without DP.¹⁰

The lower bound holds based on the construction of (interactive) fingerprinting codes [19], [20], and holds unconditionally in large-domain settings and assuming the existence of one-way functions in all settings.

In other words, there is a provable exponential gap in the sample complexity required to answer \(k\) queries adaptively versus non-adaptively.

3 Publicly-Verifiable Certificates of Statistical Validity↩︎

In this section, we introduce the main conceptual contribution of this work—publicly-verifiable Certificates of Statistical Validity—which allows a prover to publish a digest from the execution of a learning algorithm that any verifier can subsequently test for statistical validity. Importantly, the verifier of a publicly-verifiable Certificate of Statistical Validity (pvCSV) need not hold the same distribution as the prover. Instead, the verifier can test for statistical validity with respect to their own distribution \(\D_V\), through an SQ oracle or samples.

To formalize pvCSVs, we must first introduce the notion of soudness that makes proofs “publicly-verifiable.” We define universal soundness to ensure soundness holds no matter what distribution the verifier holds.

It is easy to see that universal soundness of SQ Protocols is actually just a restatement of standard soundness; syntactically, our definition simply renames the distribution \(\D\) to be in terms of \(\D_V\). But importantly, the restatement of the property allows us to reason rigorously about proof systems when the prover and verifier hold different distributions. Under universal soundness, when the verifier has access to \(\D_V\), running the protocol results in \(V\) rejecting or \(V\) accepting a hypothesis that is good for the verifier’s distribution, regardless of the prover’s distribution \(\D_P\).

In a bit more detail, we can imagine an honest prover with oracle access to \(\O_P\) for a distribution \(\D_P\), while a verifier has access to an oracle \(O_V\) for a completely different distribution \(\D_V\). In effect, we can view the honest prover \(P^{\O_P}\), as a possible cheating prover for any downstream verifier \(V^{\O_V}\). Still, if the verifier accepts the proof of some non-\(\bot\) hypothesis, then universal soundness guarantees that \(h \in \G(\D_V)\). The appeal of universal soundness shows itself when we consider non-interactive proofs, where a prover wants to publish a fixed certificate, which any verifier (holding any \(\D_V\)) can verify for themselves. In this context, we can define pvCSVs as a non-interactive SQ protocol satisfying universal soundness.

The construction of a pvCSV allows a prover with access to a distribution \(\D_P\) to execute an algorithm \(\A\) that learns \(\G\) once and publish the results \((h,\pi)\). Then, any party who is interested in running \(\A\) on their own distribution \(\D_V\) can, instead, run the verification algorithm \(V\) on \((h,\pi)\). If \((h,\pi)\) is accepted, then by universal soundness, \(h \in \G(\D_V)\) is guaranteed to be valid for the verifier’s distribution.

3.0.0.1 Remarks.

A few remarks about the definition of pvCSVs are in order.

• Distributional Access:  We describe our pvCSVs as SQ protocols, then give sample-based implementations. That said, pvCSVs could equally encompass non-interactive protocols for verification of learning, with more general distributional access, provided we define a more general notion of universal soundness. As in [1], the type of statistical access available may serve as a qualitative difference in the complexity of the prover and verifier.

• Complexity Measures:  Quantitatively, there are many measures of complexity one could track for pvCSVs. We will be most interested in the sample complexity (using i.i.d.random draws) of the honest prover and verifier from \(\D_P\) and \(\D_V\), respectively. In general, we may also track other natural complexity measures, such as the time complexity or size of the certificate.

• Computational Soundness:  Definition 11 considers universal soundness with respect to computationally-unbounded provers. We also consider computationally-sound pvCSVs, where soundness only holds with respect to PPT algorithms. Concretely, we will prove soundness in the Random Oracle Model, where the failure probability is taken over the random draw of random oracle (in addition to the verifier’s coins).

• On Robust Completeness?   Note that in our notion of completeness, we assume that the honest prover and verifier have access to exactly the same distribution \(\D_P = \D_V\). Given the motivating perspective on pvCSVs, we might hope for a weaker notion of distributional closeness required for completeness. Such a guarantee may be formally defined in future work. We remark that—paired with universal soundness—we still get some notion of robustness. If the verifier accepts \((h,\pi)\) then the distributions are indistinguishable, according to the queries asked by (a specific execution of) \(\A\), regardless of how close they are in any standard notion of statistical/computational indistinguishability.

3.1 A pvCSV for Every Deterministic SQ Algorithm↩︎

Our first construction establishes that every deterministic SQ algorithm has a statistically-sound pvCSV where the verifier answers \(k\) queries non-adaptively and has sample complexity \(O(\log(k))\), whereas the best known, efficient prover must answer \(k\) possibly adaptive queries with sample complexity scaling with \(\tilde{O}(\sqrt{k})\). We present the pvCSV scheme as a non-interactive SQ protocol, Protocol 1. To generate the certificate, the honest prover first simulates the execution of \(\A\) using the prover’s SQ oracle \(\O_P\), returning a hypothesis \(h\). Along the way, the prover writes down the list of queries \(\vec{q}\) and answers \(\O_P(\vec{q})\) provided by the oracle as the certificate. Then, the verifier also simulates the execution of \(\A\), but uses the digest of query-answer pairs \((\vec{q}, \O_P(\vec{q}))\) provided by the certificate, rather than making any adaptive statistical queries. Finally, the verifier runs a batch statistical validation of the answers provided in the certificate using its oracle \(\O_V\) for \(\D_V\). The key insight is that the verifier can non-adaptively check every (adaptively-chosen) query produced during the execution of \(\A\).

We prove that Protocol 1 is a pvCSV where the verifier’s sample complexity scales “non-adaptively” even when an adaptive algorithm is necessary for learning. We start with the following lemma.

- *$P$ has $\tau/3$-query complexity $(1,B)$;*

- *$V$ has $\tau/3$-query complexity $(k,B)$*

With this lemma in place, establishing our main theorem of this section is straightforward. To achieve an improved bound on the size of the certificate, we make the following optimization. Notice that our proof of correctness does not actually use the fact that the queries \(\vec{q}\) used by the prover are the same as the queries derived by the verifier’s simulation of \(\A\); instead, we only need that the answers in the certificate, \(\vec{a}\) are valid for the verifier’s queries. Thus, we do not need to include queries in the certificate at all: we need only the certificate be the list of answers, that is, \(\pi:=\vec{a}\). While including the names of the queries improves the clarity of the proof system, we derive an equally-valid SQ protocol where \(\pi:=\vec{a}\) in the following theorem.

Finally, we remark informally on the time complexities of the honest prover and verifier. Both parties run a direct simulation of the original SQ algorithm \(\A\). Additionally, the honest prover must implement the mechanism of [18] for adaptive data analysis to answer the queries to \(\O_P\), whereas \(\O_V\) may respond with the empirical statistics from its sample. In most settings, the overall running time for both will be dominated by the simulation of \(\A\).

4 Delegation of Randomized SQ Learning↩︎

In this section, we address delegating SQ learning algorithms that use randomness. Our investigation leads us to develop a number of new definitions and tools for understanding SQ protocols. With these tools in place, we obtain (computationally-sound) pvCSVs, not only for randomized SQ algorithms, but for a large class of SQ protocols.

We start by giving essential definitions, highlighting important properties of randomized SQ algorithms and protocols. Using these definitions, we then show that for a large class of SQ protocols, there exists a reformulation into a Canonical SQ Protocol. This canonical protocol allows for non-adaptive verification of the statistical queries, leading to exponential savings in sample complexity for the verifier, for any original SQ protocol (including randomized algorithms that make adaptive statistical queries). We conclude the section with a construction of pvCSVs for this class, by showing how to apply a Fiat-Shamir transformation to the canonical protocol.

4.1 Definitions for Randomized SQ Learning and SQ Protocols↩︎

To begin, we fix a standard, mechanical format for describing randomized SQ algorithms that proceed in epochs. In the \(t\)-th epoch,

• \(\A\) samples randomness \(r_t \in \{0,1\}^{d_t}\), for some (efficiently-bounded) \(d_t \in \mathbb{N}\)

• \(\A\) then executes a deterministic SQ algorithm \(\A_t\) as a subroutine, with \(r_t\) as fixed input, which may issue adaptive statistical queries.

The choice of the \(t\)-th subroutine \(\A_t\) may be chosen adaptively as a function of prior randomness, as well as any statistical queries issued. In terms of expressivity, formatting randomized algorithms into epochs is not a restriction, as we can simulate any algorithm in this format. But the number of epochs turns out to be a key quantity that affects the complexity of our proof systems.

Extending the notion of epoch complexity to SQ protocols, we standardize the verifier’s execution similarly. In the \(t\)-th epoch,

• \(V\) samples randomness \(r_t\in\{0,1\}^{d_t}\) for some (efficiently-bounded) \(d_t\in\N\)

• \(V\) executes a deterministic, interactive SQ algorithm \(V_t\) as a subroutine, with \(r_t\) as a fixed input, which may issue adaptive statistical queries and communicate with \(P\).

Again, the choice of the \(t\)-th subroutine \(V_t\) can be chosen adaptively based on prior randomness, \(V\)’s internal state, and messages from the prover.

Intuitively, formatting randomized algorithms (and SQ verifiers) into epochs allows us to separate “adaptivity” of \(\A\) based on fresh randomness and adaptivity based on the results of statistical queries (and prover messages). In the extreme, each epoch could issue a single statistical query, so adaptivity to the randomness and queries are essentially the same. At the other extreme, we might consider algorithms that start with a random initialization, but then proceed deterministically. Such algorithms may still make adaptive SQ queries, but could be implemented in a single epoch. The number of epochs serves as a natural complexity measure of the algorithm’s use of its randomness.

4.1.0.1 Oblivious vs.Public-State SQ Oracles.

Recall that we model an SQ oracle as a stateful algorithm, who may respond adversarially (within \(\tau\)-accuracy) based on the state of the algorithm \(\A\). When our algorithms leverage randomness, we need to reason about what knowledge the oracle \(\O\) has about the algorithm’s internal state—namely, the randomness sampled at the current epoch.

One standard notion of SQ oracle allows the algorithm to maintain private state from the oracle. In this case, the algorithm need not reveal any of its random coins to the oracle. We refer to such oracles as oblivious SQ oracles, which follow the earlier notion given in Definition 1.

For randomized SQ algorithms, we mainly focus on oracles, who may respond adversarially with full knowledge of the algorithm’s randomness. This notion is captured by a public-state SQ oracle.

In other words, a randomized algorithm equipped with a public-state SQ oracle may, as usual, specify the query \(q \in \Q\) of interest, but necessarily reveals the randomness sampled so far. By the standardization into epochs, the randomness captures all of the state of \(\A\).

Note that any algorithm/protocol that succeeds with access to a public-state oracle also works with an oblivious oracle, but the converse is not true. Correctness with respect to a public-state oracle is a stronger guarantee: no matter what information is leaked to the oracle through interaction, the algorithm will work. That said, proving correctness may be more challenging, so designing correct algorithms with a public-state oracle may be harder than with an oblivious oracle.

4.1.0.2 Public-Coin SQ Protocols.

As with traditional interactive protocols, we can distinguish SQ protocols based on the verifier’s communication of its randomness. Key to our study of non-interactive proof systems for randomized SQ algorithms, we first consider public-coin interactive SQ protocols. Defining public-coin protocols when the verifier is equipped with an SQ oracle (which may introduce non-determinism) is nuanced. We consider two alternative definitions.

In other words, a standard public-coin SQ protocol adopts the formalism that the only messages the verifier sends to the prover are its randomness, whereas a mixed-message SQ protocol must reveal its randomness to the prover, but may also send non-random challenges. Without an SQ oracle, the distinction is moot: in the \(t\)-th epoch, \(V_t\) is a deterministic algorithm, so the prover can simulate any challenges it would receive and respond accordingly. But with an SQ oracle—which may respond adversarially within its tolerance—\(V_t^{\O_V}\) may have non-deterministic behavior, even conditioned on \(r_t\). Thus, in principle, mixed-message SQ protocols could be more expressive than public-coin SQ protocols. Despite this distinction, our main result in Section 4.2 (Protocol 3) implies that (as in standard interactive proofs) any mixed-message SQ protocol can be compiled into a public-coin SQ protocol with the same completeness and soudness guarantees.

4.1.0.3 Public-Query SQ Protocols.

A final consideration in classifying SQ protocols is whether the verifier’s queries are kept private or made public to the prover. A public-query protocol reveals its queries to the prover at every round of communication.

Note that, per the discussion above, whether the verifier’s queries are public or private is orthogonal to whether the verifier’s coins are public or private. That said, Protocol 3 also implies that any public-coin, private-query protocol can be made public-query. In this sense, we use the term “public-query” to refer to private-coin, public-query SQ protocols. We explore public-query protocols further when we consider the strength and limits of SQ proof systems beyond pvCSVs in Section 5.

4.2 A Canonical Public-Coin SQ Protocol↩︎

With the preliminaries on randomized SQ algorithms and SQ protocols in place, we are ready to describe protocols for delegating randomized SQ algorithms. We describe, in Protocol 3, an interactive public-coin SQ protocol for delegating any randomized SQ algorithm that SQ-learns a concept \(\G\) with public state. In fact, our protocol is much more general, and can take any mixed-message, private-query SQ protocol that SQ-verifies \(\G\) with public verifier state (which include all randomized SQ algorithms with public state) and compile it into a canonical public-coin SQ protocol, where the verifier issues a single non-adaptive batch of statistical queries.

4.2.0.1 Protocol Description.

Protocol 3 works as follows. We start with a mixed-message SQ protocol \((P,V)\) where the verifier may make private statistical queries, and each player is arbitrarily-adaptive in their queries. Note that randomized SQ algorithms are the special case of such protocols, where the algorithm must accept \(h\) or output \(\bot\) without assistance from any prover. We want to build a public-coin, public-query SQ protocol \((\mathsf{P}_\mathsf{can},\mathsf{V}_\mathsf{can})\) where the verifier issues a single batch of statistical queries. As in Protocol 1, the verifier will delegate its queries to the prover and check them at the end.

Because \((P,V)\) is mixed-message, we know that the verifier \(V\) starts each epoch by sending its randomness to the prover. This random message will be the only message \(\mathsf{V}_\mathsf{can}\) sends to \(\mathsf{P}_\mathsf{can}\) per epoch; then, \(\mathsf{P}_\mathsf{can}\) will be responsible for simulating the remaining interactive execution of that epoch. \(\mathsf{P}_\mathsf{can}\) will use its own SQ oracle \(\O_{\mathsf{P}_\mathsf{can}}\) to make any queries. This aspect of the protocol—where the prover simulates the queries of the verifier with knowledge of its randomness—is where we need to leverage the assumption that \((P,V)\) learns \(\G\) with public verifier state; that is, even if the oracle (or in this case the prover) can respond adversarially based on the state of the verifier, the protocol is still sound. Once the epoch finishes, \(\mathsf{P}_\mathsf{can}\) will send the transcript of the execution to \(\mathsf{V}_\mathsf{can}\), who can update state and move to the next epoch.

At the end, the canonical verifier \(\mathsf{V}_\mathsf{can}\) checks to ensure that the prover faithfully simulated the execution of \(P\) and \(V\). Finally, \(\mathsf{V}_\mathsf{can}\) runs a statistical check to make sure all of the query values reported by the prover are actually within the required tolerance of the original protocol.

In all, we obtain the following guarantee on our canonical public-coin SQ protocol.

- *$\mathsf{V}_\mathsf{can}$ has $\tau_V'$-query complexity
  $(1,B_V)$;*

- *$\mathsf{P}_\mathsf{can}$ has $\tau_P'$-query complexity
  $(k_P+k_V,B_P+B_V)$*

- *$\mathsf{V}_\mathsf{can}$ runs in time $O(T_V(\tau_V))$*

- *$\mathsf{P}_\mathsf{can}$ runs in time
  $O(T_V(\tau_V) + T_P(\tau_P))$*

4.3 pvCSVs from the Canonical Protocol and Fiat-Shamir↩︎

Next, we construct pvCSVs for SQ computations that use randomness. Specifically, we compile the canonical Protocol 3 from above into non-interactive SQ protocols using a Fiat-Shamir transformation [23]. We prove soundness of the transformation in the Random Oracle Model (ROM), which allows us to replace the public coins of the verifier with non-interactive calls to the random oracle. We begin with preliminaries defining correctness and soundness in the ROM. Then, we describe our Fiat-Shamir transformation over canonical SQ protocols in Protocol 4.

4.3.0.1 pvCSVs in the ROM.

In the Random Oracle Model [22], both the prover and verifier have query access to a shared random function called the random oracle \(f:\{0,1\}^*\to\{0,1\}^m\) for some output size \(m\in\Nbb\). Completeness and soundness take probabilities over the sampling of the random oracle which is denoted \(f\gets\U\). Furthermore, we restrict the cheating prover to at most \(t\in\Nbb\) queries of the random oracle, called the random oracle budget, typically taken to be polynomial in some security parameter. We adapt Definition 11 of pvCSVs to define computationally-sound pvCSVs in the ROM.

We denote ROM soundness against \(t\)-query provers as \(\gamma'(t)\) where \(\gamma'\) is a function and \(t\in\Nbb\) is the random oracle query budget. Additionally, since soundness is parameterized whereas completeness is not, we split completeness and soundness error into \((\gamma,\gamma')\).

4.3.0.2 Applying Fiat-Shamir to the Canonical Protocol.

We transform the Canonical SQ protocol \((\mathsf{P}_\mathsf{can},\mathsf{V}_\mathsf{can})\) into a pvCSV in the ROM by applying the Fiat-Shamir transformation to the initial phase of public-coin interaction. As is standard in Fiat-Shamir, the canonical verifier’s randomness in the \(i\)-th round is the query of the random oracle with the partial transcript of interaction up to round \(i\). We describe the resulting protocol \((\mathsf{P}_\mathsf{FS},\mathsf{V}_\mathsf{FS})\) in Protocol 4. The honest prover \(\mathsf{P}_\mathsf{FS}\) simulates the interaction \((\mathsf{P}_\mathsf{can},\mathsf{V}_\mathsf{can})\) where \(\mathsf{V}_\mathsf{can}\)’s randomness is sampled via the random oracle \(f\). Then, the verifier \(\mathsf{V}_\mathsf{FS}\) runs the second and third phase of the canonical protocol as before, checking the correctness of the computational simulation and the statistical validity of the relevant SQs via a batch evaluation of the queries of \(\mathsf{V}_\mathsf{can}\).

The correctness of the resulting pvCSV follows from the state restoration argument of [25], with some subtleties that arise in the SQ protocol setting. The structure of the Canonical protocol simplifies the analysis considerably: the protocol naturally divides into a phase of public-coin interaction, followed by (computational and statistical) verification of the transcript. Completeness of the protocol follows from completeness of Protocol 3, since the honest prover can execute the same sequence of queries and computations. Thus, we focus on establishing soundness.

There are two key aspects of Protocol 4 that require us to be careful in establishing soundness of the transformation. First, in our setting, the cheating prover has considerable powers related to the statistical learning problem, with full knowledge of the underlying distribution \(\D\) and access to the verifier’s SQ oracle. But, importantly, the cheating prover in the Fiat-Shamir protocol and Canonical protocol are afforded the same powers. The approach of establishing Fiat-Shamir soundness via state restoration is a black-box reduction, so we can apply the same argument even in our setting where the provers have non-standard computational and statistical powers. Second, our application of Fiat-Shamir is used to generate a legitimate prover-verifier transcript, which produces a hypothesis \(h\), rather than directly certifying a known predicate (e.g., certifying a given \(h \in \G(\D_V)\)). That said, once we have a sound transcript, Phase 2 and Phase 3 of the original protocol allow us to validate that the \(h\) is actually good for the verifier’s distribution.

Specifically, we invoke the following guarantee about the Fiat-Shamir transformation applied to public-coin protocols.

Specifically, the reduction goes through a state restoration game and demonstrates how, given a cheating prover for the Fiat-Shamir proof system \(\tilde{\mathsf{P}}_\mathsf{FS}\), there exists a cheating prover \(\tilde{P}\) for the original interactive protocol that makes calls to \(\tilde{\mathsf{P}}_\mathsf{FS}\), at a \(\binom{t+\ell}{\ell}\)-factor loss in success probability. With this fact, we establish the correctness of Protocol 4.

4.3.0.3 pvCSVs for all mixed-message protocols with public-verifier state.

We conclude with a statement of the overall pvCSV guarantee established in this section within the ROM. In Lemma 2, we argue that for the class of mixed-message, private-query SQ protocols with public verifier state can be transformed into a Canonical public-coin SQ protocol. Then, in Lemma 3, we apply the Fiat-Shamir transform to turn any Canonical protocol into a pvCSV in the ROM. Chaining these lemmas together, we obtain the following theorem.

- *$\mathsf{V}_\mathsf{FS}$ has $\tau_V'$-query complexity
  $(1,B_V)$;*

- *$\mathsf{P}_\mathsf{FS}$ has $\tau_P'$-query complexity
  $(k_P+k_V,B_P+B_V)$*

- *$\mathsf{V}_\mathsf{can}$ runs in time $O(T_V(\tau_V))$*

- *$\mathsf{P}_\mathsf{can}$ runs in time
  $O(T_V(\tau_V) + T_P(\tau_P))$*

By application of known implementations for adaptive and non-adaptive SQ oracles in Proposition [prop:full-adaptive-upper] and Proposition [prop:non-adaptive], we have the following.

5 Beyond pvCSVs: Strengths and Limits of SQ Protocols↩︎

In this section, we consider the power and limitations of SQ protocols. First, we reiterate that, statistically, SQ protocols are very powerful. In even more generic settings than our pvCSV constructions, SQ algorithms/protocols can be delegated via interactive SQ protocol such that the verifier’s sample complexity scales logarithmically in the number of queries. Then, we show that SQ protocols—despite their sample efficiency—do not generically provide a computationally efficient verification scheme. In particular, by a lower bound of [7] on the sample complexity required to PAC Verify certain VC classes, we show a subexponential lower bound on the query complexity of SQ verification for the same class.

5.0.0.1 Interactive Non-Adaptive SQ Verification.

One of the key limitations in our construction of pvCSVs is the reliance on correctness under a public-state SQ oracle. We show that it is possible to achieve non-adaptive statistical verification of SQ algorithms that are only correct under an oblivious SQ oracle, albeit with interaction. This result is analogous to a result showed in the recent journal version of [7]. Given any SQ algorithm, the verifier simply executes the algorithm using the prover as its oracle. The prover responds interactively to each query. And then at the end, the verifier checks the answers of the prover non-adaptively.

In fact, this simple idea also establishes that a large class of SQ protocols—even more general than those covered by Lemma 2—can be verified using non-adaptive statistical complexity. Specifically, for any public-query (private-coin) SQ protocol that verifies \(\G\) with public verifier state, there is an implementation of the protocol that only requires non-adaptive verifier sample complexity.

Proposition [prop:public-query] follows, again, by asking the prover to make the verifier’s statistical queries. The completeness, soundness, and resulting bounds are analogous to those established by Lemma 2.

5.0.0.2 Query Lower Bound for SQ Verification of a VC Class.

We show that the statistical upper bound we achieve for the SQ verifier actually implies a computational lower bound for SQ protocols. Specifically, there exists a hypothesis class of VC dimension \(d\) that cannot be SQ verified, even using the most general interactive SQ protocols, using polynomially many queries in \(d\). Our lower bound piggybacks off of the lower bound proved in [7] for PAC Verification.¹²

Stringing this lower bound on the sample complexity of PAC verifying a VC class with our upper bound on the sample complexity of SQ verification, we immediately get a query complexity lower bound for SQ verification. Taking our upper bound of \(\log(k)/\tau^2\) from Proposition [prop:public-query], in terms of the number of statistical queries \(k\), and their lower bound of \(\sqrt{d}/\eps^2\) in terms of the VC dimension \(d\), we obtain the following corollary.

That is, even for the strongest model of SQ protocol we consider—interactive, public-query SQ protocols that use a public-state SQ oracle—when the tolerance of the SQ oracle is fixed \(\tau_V \approx \eps\), verification may be computationally inefficient, despite statistical efficiency.

6 Differential Privacy and SQ Verification↩︎

In many statistical analyses, Differential Privacy (DP) [24] is a desirable property to satisfy to maintain the privacy of individuals’ data within a database.¹³ DP protects individuals’ privacy by requiring stability in a randomized algorithm’s behavior on neighboring databases \(D,D'\) that differ on a single element.

DP provides rigorous protections to individuals, but comes at a cost. Even for non-adaptive statistical queries, in high-dimensional settings (\(d \ge k\)), answering \(k\) queries requires sample complexity scaling polynomially in \(k\). Concretely, to answer \(k\) queries with \(\tau\) tolerance under pure \((\eps,0)\)-DP requires \(\Omega(k/\tau\eps)\) i.i.d.samples from \(\D\) [42]; under approximate \((\eps,\delta)\)-DP requires \(\Omega(\sqrt{k \cdot \log(1/\delta)}/\tau\eps)\) [43]. Both of these results are tight (up to poly-logarithmic factors); in fact, the upper bound on answering adaptive statistical queries is tightly connected to the upper bound on answering queries under approximate DP.

Certifying the results of a statistical analysis, while maintaining DP with respect to the verifier’s samples, offers a potential for significant savings. We show, generically, that the verifiers for our pvCSVs (in fact, for all of our SQ protocols) can be implemented under DP using essentially the same non-adaptive sample complexity.

Acknowledgements↩︎

The authors thank Noah Stephens-Davidowitz for significant conversations at the start of this work and feedback throughout the project. We also thank Robert Kleinberg, Jonathan Shafer, and Nick Spooner for helpful discussions.

References↩︎