On the Power of Differentiable Learning versus PAC and SQ Learning

Introduction

A leading paradigm that has become the predominant approach to learning is that of differentiable learning, namely using a parametric function class $f_{{\bm{w}}}(x)$, and learning by performing mini-batch Stochastic Gradient Descent (${\mathsf{bSGD}}$) updates (using gradients of the loss on a mini-batch of $b$ independent samples per iteration) or full-batch Gradient Descent (${\mathsf{fbGD}}$) updates (full gradient descent on the empirical loss, using the same $m$ samples in all iterations). Feed-forward neural networks are a particularly popular choice for the parametric model $f_{{\bm{w}}}$. One approach to understanding differentiable learning is to think of it as a method for minimizing the empirical error of $f_{{\bm{w}}}$ with respect to ${\bm{w}}$, i.e. as an empirical risk minimization ($\mathsf{ERM}$). $\mathsf{ERM}$ is indeed well understood, and is in a sense a universal learning rule, in that any hypothesis class that is ${\mathsf{PAC}}$ learnable is also learnable using $\mathsf{ERM}$. Furthermore, since poly-sized feed-forward neural networks can represent any poly-time computable function, we can conclude that $\mathsf{ERM}$ on neural networks can efficiently learn any tractable problem. But this view of differentiable learning ignores two things.

Firstly, many $\mathsf{ERM}$ problems, including $\mathsf{ERM}$ on any non-trivial neural network, are highly non-convex and (stochastic) gradient descent might not find the global minimizer. As we just discussed, pretending that ${\mathsf{bSGD}}$ or ${\mathsf{fbGD}}$ do find the global minimizer would mean we can learn all poly-time computable functions, which is known to be impossibleSubject to mild cryptographic assumptions, such as the existence of one-way functions, i.e. the existence of cryptography itself, and where we are referring to ${\mathsf{bSGD}}/{\mathsf{fbGD}}$ running for polynomially many steps. (e.g. Kearns and Valiant, 1994; Klivans and Sherstov, 2009). In fact, even minimizing the empirical risk on a neural net with two hidden units, and even if we assume data is exactly labeled by such a network, is already NP-hard, and cannot be done efficiently with ${\mathsf{bSGD}}$/${\mathsf{fbGD}}$ (Blum and Rivest, 1992). We already see that ${\mathsf{bSGD}}$ and ${\mathsf{fbGD}}$ are not the same as $\mathsf{ERM}$, and asking “what can be learned by ${\mathsf{bSGD}}$/${\mathsf{fbGD}}$” is quite different from asking “what can be learned by $\mathsf{ERM}$”.

Furthermore, ${\mathsf{bSGD}}$ and ${\mathsf{fbGD}}$ might also be more powerful than $\mathsf{ERM}$. Consider using a highly overparametrized function class $f_{{\bm{w}}}$, with many more parameters than the number of training examples, as is often the case in modern deep learning. In such a situation there would typically be many empirical risk minimizers (zero training error solutions), and most of them would generalize horribly, and so the $\mathsf{ERM}$ principal on its own is not sufficient for learning (Neyshabur et al., 2015). Yet we now understand how ${\mathsf{fbGD}}$ and ${\mathsf{bSGD}}$ incorporate intricate implicit bias that leads to particular empirical risk minimizers which might well ensure learning (Soudry et al., 2018; Nacson et al., 2019).

All this justifies studying differentiable learning as a different and distinct paradigm from empirical risk minimization. The question we ask is therefore:

What can be learned by performing mini-batch stochastic gradient descent, or full-batch gradient descent, on some parametric function class $f_{{\bm{w}}}$, and in particular on a feed-forward neural network?

Answering this question is important not only for understanding the limits of what we could possibly expect from differentiable learning, but even more so in guiding us as to how we should study differentiable learning, and ask questions, e.g., about its power relative to kernel methods (e.g. Yehudai and Shamir, 2019; Allen-Zhu and Li, 2019, 2020; Li et al., 2020; Daniely and Malach, 2020; Ghorbani et al., 2019, 2020; Malach et al., 2021), or the theoretical benefits of different architectural innovations (e.g. Malach and Shalev-Shwartz, 2020).

A significant, and perhaps surprising, advance toward answering this question was recently presented by Abbe and Sandon (2020), who showed that ${\mathsf{bSGD}}$ with a single example per iteration (i.e. a minibatch of size $1$) can simulate any poly-time learning algorithm, and hence is as powerful as ${\mathsf{PAC}}$ learning. On the other hand, they showed training using population gradients (infinite batch size, or even very large batch sizes) and low-precision (polynomial accuracy, i.e. a logarithmic number of bits of precision), is no more powerful than learning with Statistical Queries (${\mathsf{SQ}}$), which is known to be strictly less powerful than ${\mathsf{PAC}}$ learning (Kearns, 1998; Blum et al., 2003). This seems to suggest non-stochastic ${\mathsf{fbGD}}$, or even ${\mathsf{bSGD}}$ with large batch sizes, is not universal in the same way as single-example ${\mathsf{bSGD}}$. As we will see below, it turns out this negative result depends crucially on the allowed precision, and its relationship to the batch, or sample, size.

In this paper, we take a more refined view of this dichotomy, and consider learning with ${\mathsf{bSGD}}$ with larger mini-batch sizes $b>1$, as is more typically done in practice, as well as with ${\mathsf{fbGD}}$. We ask whether the ability to simulate ${\mathsf{PAC}}$ learning is indeed preserved also with larger mini-batch sizes, or even full batch GD? Does this universality rest on using single examples, or perhaps very small mini-batches, or can we simulate any learning algorithm also without such extreme stochasticity? We discover that this depends on the relationship of the batch size $b$ and the precision $\rho$ of the gradient calculations. That is, to understand the power of differentiable learning, we need to also explicitly consider the numeric precision used in the gradient calculations, where $\rho$ is an arbitrary additive error we allow.

We first show that regardless of the mini-batch size, ${\mathsf{bSGD}}$ is always able to simulate any ${\mathsf{SQ}}$ method, and so ${\mathsf{bSGD}}$ is at least as powerful as ${\mathsf{SQ}}$ learning. When the mini-batch size $b$ is large relative to the precision, namely $b=\omega(\log(n)/\rho^{2})$, where $n$ is the input dimension and we assume the model size and number of iterations are polynomial in $n$, ${\mathsf{bSGD}}$ is not any more powerful than ${\mathsf{SQ}}$. But when $b<1/(8\rho)$, or in other words with fine enough precision $\rho<1/(8b)$, ${\mathsf{bSGD}}$ can again simulate any sample-based learning method, and is as powerful as ${\mathsf{PAC}}$ learning (the number of SGD iterations and size of the model used depend polynomially on the sample complexity of the method being simulated, but the mini-batch size $b$ and precision $\rho$ do not, and only need to satisfy $b\rho<1/8$—see formal results in Section 3). We show a similar result for ${\mathsf{fbGD}}$, with a dependence on the sample size $m$: with low precision (large $\rho$) relative to the sample size $m$, ${\mathsf{fbGD}}$ is no more powerful than ${\mathsf{SQ}}$. But with fine enough precision relative to the sample size, namely when $\rho<1/(8m)$, ${\mathsf{fbGD}}$ can again simulate any sample-based learning method based on $m$ samples (see formal results in Section 6).

We see then, that with fine enough precision, differentiable learning with any mini-batch size, or even using full-batch gradients (no stochasticity in the updates), is as powerful as any sample-based learning method. The required precision does depend on the mini-batch or sample size, but only linearly. That is, the number of bits of precision required is only logarithmic in the mini-batch or sample sizes. And with a linear (or even super-logarithmic) number of bits of precision (i.e. $\rho=2^{-n}$), ${\mathsf{bSGD}}$ and ${\mathsf{fbGD}}$ can simulate arbitrary sample-based methods with any polynomial mini-batch size; this is also the case if we ignore issue of precision and assume exact computation (corresponding to $\rho=0$).

On the other hand, with low precision (high $\rho$, i.e. only a few bits of precision, which is frequently the case when training deep networks), the mini-batch size $b$ plays an important role, and simulating arbitrary sample based methods is provably not possible using ${\mathsf{fbGD}}$, or with ${\mathsf{bSGD}}$ with a mini-batch size that is too large, namely $b=\omega(\log(n)/\rho^{2})$. Overall, except for an intermediate regime between $1/\rho$ and $\log(n)/\rho^{2}$, we can precisely capture the power of ${\mathsf{bSGD}}$.

Computationally Bounded and Unbounded Learning.

Another difference versus the work of Abbe and Sandon is that we discuss both computationally tractable and intractable learning. We show that poly-time ${\mathsf{PAC}}$ and ${\mathsf{SQ}}$ are related, in the sense described above, to ${\mathsf{bSGD}}$ and ${\mathsf{fbGD}}$ on a poly-sized neural network, whereas computationally unbounded ${\mathsf{PAC}}$ and ${\mathsf{SQ}}$ (i.e. limited only by the number of samples or number of statistical queries, but not runtime) are similarly related to ${\mathsf{bSGD}}$ and ${\mathsf{fbGD}}$ on an arbitrary differentiable model $f_{{\bm{w}}}$. In fact, to simulate ${\mathsf{PAC}}$ and ${\mathsf{SQ}}$, we first construct an arbitrary $f_{{\bm{w}}}$, and then observe that if the ${\mathsf{PAC}}$ or ${\mathsf{SQ}}$ method is poly-time computable, then the computations within it can be expressed as poly-size circuits, which can in turn be simulated as poly-size sub-networks, allowing us to implement $f_{{\bm{w}}}$ as a neural net.

Answering 𝗦𝗤𝗦𝗤{\mathsf{SQ}}s using Samples.

Our analysis relies on introduction of a variant of ${\mathsf{SQ}}$ learning which we refer to as mini-batch Statistical Queries (${{\mathsf{bSQ}}}$, and we similarly introduce a full-batch variant, ${{\mathsf{fbSQ}}}$). In this variant, which is related to the $\mathsf{Honest}$-${\mathsf{SQ}}$ model (Yang, 2001, 2005), statistical queries are answered using a mini-batch of samples drawn from the source distribution, up to some precision. We first show that ${{\mathsf{bSQ}}}$ methods can always be simulated by ${\mathsf{bSGD}}$, by constructing a differentiable model where at each step the derivatives with respect to some of the parameters contain the answers to the statistical queries. We then relate ${{\mathsf{bSQ}}}$ to ${\mathsf{SQ}}$ and ${\mathsf{PAC}}$, based on the relationship between the mini-batch size and precision. In order to simulate ${\mathsf{PAC}}$ using ${{\mathsf{bSQ}}}$, we develop a novel “sample extraction” that uses mini-batch statistical queries (on independently sampled mini-batches) to extract a single sample drawn from the source distribution. This procedure might be of independent interest, perhaps also in studying privacy, where such an extraction is not desirable. Our study of the relationship of ${{\mathsf{bSQ}}}$ to ${\mathsf{SQ}}$ and ${\mathsf{PAC}}$, summarized in Section 4, also sheds light on how well the ${\mathsf{SQ}}$ framework captures learning by answering queries using empirical averages on a sample, which is arguably one of the main motivations for the inverse-polynomial tolerance parameter in the SQ framework.

Learning Paradigms

where $g_{t}$ is a $\rho$-approximate rounding of the mini-batch (empirical) clipped gradient

Precision, Rounding and Clipping.

Learning with 𝗯𝗦𝗚𝗗𝗯𝗦𝗚𝗗{\mathsf{bSGD}}.

Full-batch Gradient Descent (𝗳𝗯𝗚𝗗𝗳𝗯𝗚𝗗{\mathsf{fbGD}}).

𝗣𝗔𝗖𝗣𝗔𝗖{\mathsf{PAC}} and 𝗦𝗤𝗦𝗤{\mathsf{SQ}} Learning.

Relating Classes of Methods.

That is, $\mathcal{C}^{\prime}\preceq_{\delta}\mathcal{C}$ means that $\mathcal{C}^{\prime}$ is at least as powerful as $\mathcal{C}$. Observe that for all classes of methods $\mathcal{C}_{1},\mathcal{C}_{2},\mathcal{C}_{3}$, if $\mathcal{C}_{1}\preceq_{\delta_{1}}\mathcal{C}_{2}$ and $\mathcal{C}_{2}\preceq_{\delta_{2}}\mathcal{C}_{3}$ then $\mathcal{C}_{1}\preceq_{\delta_{1}+\delta_{2}}\mathcal{C}_{3}$.

Main Results : 𝗯𝗦𝗚𝗗𝗯𝗦𝗚𝗗{\mathsf{bSGD}} versus 𝗣𝗔𝗖𝗣𝗔𝗖{\mathsf{PAC}} and 𝗦𝗤𝗦𝗤{\mathsf{SQ}}

Our main result, given below as a four-part Theorem, establishes the power of ${\mathsf{bSGD}}$ learning relative to ${\mathsf{PAC}}$ (i.e. arbitrary sample based) and ${\mathsf{SQ}}$ learning. As previously discussed, the exact relation depends on the mini-batch size $b$ and gradient precision $\rho$. First, we show that for any mini-batch size $b$, with fine enough precision $\rho$, ${\mathsf{bSGD}}$ can simulate ${\mathsf{PAC}}$.

For all $b$ and $\rho<1/(8b)$, and for all $m,r,\delta$, it holds that

To establish equivalence (when Theorem 1a holds), we also note that ${\mathsf{PAC}}$ is always at least as powerful as ${\mathsf{bSGD}}$ (since ${\mathsf{bSGD}}$ can be implemented using samples):

For all $b$, $\rho$ and $T,p,r$, it holds that

Furthermore, for all poly-time computable activations $\sigma$, it holds that

On the other hand, if the mini-batch size is large relative to the precision, ${\mathsf{bSGD}}$ cannot go beyond ${\mathsf{SQ}}$:

There exists a constant $C$ such that for all $\delta>0$, for all $T$, $\rho$, $b$, $p$, $r$, such that $b\rho^{2}>C\log(Tp/\delta)$, it holds that

Furthermore, for all poly-time computable activations $\sigma$, it holds that

To complete the picture, we also show that regardless of the mini-batch size, i.e. even when ${\mathsf{bSGD}}$ cannot simulate ${\mathsf{PAC}}$, ${\mathsf{bSGD}}$ can always, at the very least, simulate any ${\mathsf{SQ}}$ method. This also establishes equivalence to ${\mathsf{SQ}}$ when Theorem 1c holds:

There exists a constant $C$ such that for all $\delta>0$, for all $b$ and all $k,\tau,r$, it holds that

In the above Theorems, the reductions hold with parameters on the left-hand-side (the parameters of the model being reduced to) that are polynomially related to the dimension and the parameters on the right-hand-side. But the mini-batch size $b$ and gradient precision $\rho$ play an important role. In Theorem 1a, we may choose $b$ and $\rho$ as we wish, as long as they satisfy $b\rho<1/8$—they do not need to be chosen based on the parameters of the ${\mathsf{PAC}}$ method, and we can always simulate ${\mathsf{PAC}}$ with any $b$ and $\rho$ satisfying $b\rho<1/8$. Similarly, in Theorem 1d, we may chose $b\geq 1$ arbitrarily, and can always simulate ${\mathsf{SQ}}$, although $\rho$ does have to be chosen according to $\tau$. The reverse reduction of Theorem 1c, establishing the limit of when ${\mathsf{bSGD}}$ cannot go beyond ${\mathsf{SQ}}$, is valid when $b\rho^{2}=\omega(\log n)$, if the size of the model $p$ and number of SGD iterations $T$ are restricted to be polynomial in $n$.

Focusing on the mini-batch size $b$, and allowing all other parameters to be chosen to be polynomially related, Theorems 1a, 1b, 1c and 1d can be informally summarized as:

where the left relationship is tight if $b<1/(8\rho)$ and the right relationship is tight if $b>\omega((\log n)/\rho^{2})$. Equivalently, focusing on the precision $\rho$ and how it depends on the mini-batch size $b$, and allowing all other parameters to be polynomially related, Theorems 1a, 1b, 1c and 1d can be informally summarized as:

For any (poly bounded, possible constant) dependence $b(n,\rho)$, and for the activation function $\sigma$ in Figure 1, it holds that

Moreover, if $\forall_{n,\rho}\ b(n,\rho)<1/(8\rho)$, then inclusions $(2)$ and $(4)$ are tight, and if $b(n,\rho)\geq\omega(\log n)/\rho^{2}$, then inclusions $(1)$ and $(3)$ are tight.

For any (poly bounded, possibly constant) $b(n),\rho(n)$, and $\sigma$ from Figure 1:

In Corollaries 1 and 2, for the sake of simplicity, we focused on realizable learning problems, where the minimal loss $\inf_{f}\mathcal{L}_{\mathcal{D}_{n}}(f)=0$ for each $\mathcal{D}_{n}\in\mathcal{P}_{n}$. However, we note that Theorems 1a, 1b, 1c and 1d are more general, as they preserve the performance of learning methods (up to an additive $\delta$) on all source distributions $\mathcal{D}$. So, a result similar to Corollary 1 could be stated for other forms of learning, such as agnostic learning, weak learning etc.

Activation Functions and Fixed Weights.

The neural net simulations in Theorems 1a and 1d use a specific “stage-wise ramp” piecewise linear activation function with five linear pieces, depicted in Figure 1. A convenient property of this activation function is that it is has a central flat piece, making it easier for us to deal with weight drift due to rounding errors during training, and in particular drift of weights we would rather not change at all. Since any piecewise linear activation function can be simulated with ReLU activation, we could instead use a more familiar ReLU activation. However, the simulation “gadget” would involve weights that we would need fixed during training. That is, if we allow neural networks where some of the weights are fixed while others are trainable, we could use ReLU activation to simulate sample-based methods in Theorem 1a and SQ methods in Theorem 1d. As stated, we restrict ourselves only to neural nets where all edges have trainable weights, for which it is easier to prove the theorems with the specific activation function of Figure 1.

The Mini-Batch Statistical Query Model

En route to proving Theorems 1a, 1b, 1c and 1d, we introduce the model of mini-batch Statistical Queries (${{\mathsf{bSQ}}}$). In this model, similar to the standard Statistical Query (${\mathsf{SQ}}$) learning model, learning is performed through statistical queries. But in ${{\mathsf{bSQ}}}$, these queries are answered based on an empirical average over a mini-batch of $b$ i.i.d. samples from the source distribution. That is, each query $\Phi_{t}:\mathcal{X}\times\mathcal{Y}\to^{p}$ is answered with a response $v_{t}$ s,t,

Note that we allow $p$-dimensional vector “queries”, that is, $p$ concurrent scalar queries are answered based on the same mini-batch $S_{t}$, drawn independently for each vector query.

The first step of our simulation of ${\mathsf{PAC}}$ and ${\mathsf{SQ}}$ with ${\mathsf{bSGD}}$ is to simulate (a variant of) ${{\mathsf{bSQ}}}$ using ${\mathsf{bSGD}}$. But beyond its use as an intermediate model in studying differentiable learning, ${{\mathsf{bSQ}}}$ can also be though of as a realistic way of answering statistical queries. In fact, one of the main justifications for allowing errors in the ${\mathsf{SQ}}$ model, and the demand that the error tolerance $\tau$ be polynomial, is that it is possible to answer statistical queries about the population with tolerance $\tau$ by calculating empirical averages on samples of size $O(1/\tau^{2})$. In the ${{\mathsf{bSQ}}}$ model we make this explicit, and indeed answer the queries using such samples. We do also allow additional arbitrary error beyond the sampling error, which we might think of as “precision”. The ${{\mathsf{bSQ}}}$ model can thus be thought of as decomposing the ${\mathsf{SQ}}$ tolerance to a sampling error $O(1/\sqrt{b})$ and an additional arbitrary error $\tau$. If the arbitrary error $\tau$ indeed captures “precision”, it is reasonable to take it to be exponentially small (corresponding to polynomially many bits of precision), while the sampling error would still be polynomial in a poly-time poly-sample method. Studying the ${{\mathsf{bSQ}}}$ model can reveal to us how well the standard ${\mathsf{SQ}}$ model captures what can be done when most of the error in answering statistical queries is due to the sampling error.

Our ${{\mathsf{bSQ}}}$ model is similar to the honest-SQ model studied by Yang (2001, 2005), who also asked whether answering queries based on empirical averages changes the power of the model. But the two models have some significant differences, which lead to different conclusions, namely: $\mathsf{Honest}$-${\mathsf{SQ}}$ does not allow for an additional arbitrary error (i.e. it uses $\tau=0$ in our notation), but an independent mini-batch is used for each single-bit query $\Phi_{t}:\mathcal{X}\times\mathcal{Y}\to\{0,1\}$, whereas ${{\mathsf{bSQ}}}$ allows for $p$ concurrent real-valued scalar queries on the same mini-batch. Yang showed that, with a single bit query per mini-batch, and even if $\tau=0$, it is not possible to simulate arbitrary sample-based methods, and honest-SQ is strictly weaker than ${\mathsf{PAC}}$. But we show that once multiple bits can be queried concurrentlyWe do so with polynomially many binary-valued queries, i.e. $\Phi_{t}(x)\in\left\{0,1\right\}^{p}$, and $p$ polynomial. It is also possible to encode this into a single real-valued query with polynomially many bits of precision. Once we use real-valued queries, if we do not limit the precision at all, i.e. $\tau=0$, and do not worry about processing time, its easy to extract the entire minibatch $S_{t}$ using exponentially many bits of precision. Theorem 2a shows that polynomially many bits are sufficient for extracting a sample and simulating ${\mathsf{PAC}}$. the situation is quite different.

In fact, we show that when the arbitrary error $\tau$ is small relative to the sample size $b$ (and thus the sampling error), ${{\mathsf{bSQ}}}$ can actually go well beyond ${\mathsf{SQ}}$ learning, and can in fact simulate any sample-based method. That is, ${\mathsf{SQ}}$ does not capture learning using statistical queries answered (to within reasonable precision) using empirical averages:

(${\mathsf{PAC}}$ to ${{\mathsf{bSQ}}}$) For all $\delta>0$, for all $b$, and $\tau<1/(2b)$, and for all $m,r$, it holds for $k^{\prime}=10m(n+1)/\delta$, $p^{\prime}=n+1$, $r^{\prime}=r+k\log_{2}b$ that

The main ingredient is a ${{\mathsf{bSQ}}}$ method Sample-Extract (Algorithm 1) that extracts a sample $(x,y)\sim\mathcal{D}$ by performing mini-batch statistical queries over independently sampled mini-batches. For ease of notation, let $\mathcal{Z}:=\mathcal{X}\times\mathcal{Y}$ identifying it with $\left\{0,1\right\}^{n+1}$ and denote $z\in\mathcal{Z}$ as $(z_{1},\ldots,z_{n+1})=(y,x_{1},\ldots,x_{n})$. Sample-Extract operates by sampling the bits of $z$ one by one, drawing $\widehat{z}_{i}$ from the conditional distribution $\left\{z_{i}\mid z_{1,\ldots,i-1}\right\}_{\mathcal{D}}$.

To complement the Theorem, we also note that sample-based learning is always at least as powerful as ${{\mathsf{bSQ}}}$, since ${{\mathsf{bSQ}}}$ is specified based on a sample of size $kb$ (see Section A.1 for a complete proof):

(${{\mathsf{bSQ}}}$ to ${\mathsf{PAC}}$) For all $b$, $\tau$ and $k,p,r$, it holds that

On the other hand, when the the mini-batch size $b$ is large relative to the precision (i.e. the arbitrary error $\tau$ is large relative to the sampling error $1/\sqrt{b}$), ${{\mathsf{bSQ}}}$ is no more powerful than standard ${\mathsf{SQ}}$:

(${{\mathsf{bSQ}}}$ to ${\mathsf{SQ}}$) There exists a constant $C\geq 0$ such that for all $\delta>0$, for all $k$, $\tau$, $b$, $p$, $r$, such that $b\tau^{2}>C\log(kp/\delta)$, it holds that

When $b\gg 1/\tau^{2}$, the differences between the empirical and population averages become (with high probability) much smaller than the tolerance $\tau$, the population statistical query answers are valid responses to queries on the mini-batch, and we can thus simulate ${{\mathsf{bSQ}}}$ using ${\mathsf{SQ}}$. We do need to make sure this holds uniformly for the $p$ parallel scalar queries, and across all $k$ rounds—see Section A.3 for a complete proof. ∎

Finally, we show that with any mini-batch size, and enough rounds of querying, we can always simulate any ${\mathsf{SQ}}$ method using ${{\mathsf{bSQ}}}$:

(${\mathsf{SQ}}$ to ${{\mathsf{bSQ}}}$) There exists a constant $C\geq 0$ such that for all $\delta>0$, for all $b$ and all $k,\tau,r$, it holds that

To obtain an answer to a statistical query on the population, even if the sample-size $b$ per query is small, we can average the responses for the same query over multiple mini-batches (i.e. over multiple rounds). This allows us to reduce the sampling error arbitrarily, and leaves us with only the arbitrary error $\tau^{\prime}$ (the arbitrary errors also get averaged, and since each element in the average is no larger than $\tau^{\prime}$, the magnitude of this average is also no large than $\tau^{\prime}$). See full proofs in Section A.3. ∎

Simulating Mini-Batch Statistical Queries with Differentiable Learning

Instead of working with, and simulating, any ${{\mathsf{bSQ}}}$ method, we consider only alternating methods, denoted ${{\mathsf{bSQ^{0/1}}}}$, where in each round, only one of the two possible labels is involved in the query. Formally, we say that a (mini-batch) statistical query $\Phi:\mathcal{X}\times\mathcal{Y}\to^{p}$ is a $\overline{y}$-query for $\overline{y}\in\mathcal{Y}$ if $\Phi(x,y)=0$ for all $y\neq\overline{y}$, or equivalently $\Phi(x,y)=\mathds{1}_{\left\{y=\overline{y}\right\}}\cdot\Phi_{\mathcal{X}}(x)$ for some $\Phi_{\mathcal{X}}:\mathcal{X}\to^{p}$. A ${{\mathsf{bSQ^{0/1}}}}$ (analogously, ${{\mathsf{bSQ_{TM}^{0/1}}}}$) method is a ${{\mathsf{bSQ}}}$ (analogously, ${{\mathsf{bSQ_{TM}}}}$) method such that for all odd rounds $t$, $\Phi_{t}$ is a $1$-query, and at all even rounds $t$, $\Phi_{t}$ is a -query. As minor extensions of Theorems 2a and 2d (simulation ${\mathsf{PAC}}$ and ${\mathsf{SQ}}$ using ${{\mathsf{bSQ}}}$ methods), we show that these simulations can in-fact be done using alternating queries, thus relating ${\mathsf{PAC}}$ and ${\mathsf{SQ}}$ to ${{\mathsf{bSQ^{0/1}}}}$. We present the full details in Sections A.1 and A.3 respectively.

(${\mathsf{PAC}}$ to ${{\mathsf{bSQ^{0/1}}}}$) For all $\delta>0$, for all $b$, and $\tau<1/(2b)$, then and for all $m,r$, it holds for $k^{\prime}=20m(n+1)/\delta$, $p^{\prime}=n+1$, $r^{\prime}=r+k\log_{2}b$ that

(${\mathsf{SQ}}$ to ${{\mathsf{bSQ^{0/1}}}}$) There exists a constant $C>0$, such that for all $\delta>0$, for all $b$ and all $k,\tau,r$, it holds that

We now show how to to simulate a ${{\mathsf{bSQ^{0/1}}}}$ method with ${\mathsf{bSGD}}$, with corresponding mini-batch and precision:

We first show how a single $\overline{y}$-query can be simulated using a single step of ${\mathsf{bSGD}}$ on a specific differentiable model. Given a -query $\Phi:\mathcal{X}\times\mathcal{Y}\to^{p}$, consider the following model:

With ${\bm{w}}^{(0)}=0$, the model $f_{{\bm{w}}^{(0)}}$ “guesses” the label to be $1$ for all examples, and therefore suffers a loss only for examples with the label . Using a simple gradient calculations we get:

Combining Lemma 3a with Lemmas 1 and 2 establishes the first statements (about computationally unbounded learning) of Theorems 1a and 1d; full details in Appendix D.

Implementing the differentiable model as a Neural Network.

The simulation in Lemma 3a, as described above, uses some arbitrary differentiable model $f_{\bm{w}}(x)$, that is defined in terms of the mappings from responses to queries in the ${{\mathsf{bSQ^{0/1}}}}$ method. If the ${{\mathsf{bSQ^{0/1}}}}$ method is computationally bounded, the simulation can also be done using a neural network:

Combining Lemma 3b with Lemmas 1 and 2 establishes the second statements (about computationally bounded learning) of Theorems 1a and 1d; full details in Appendix D.

In order to establish Theorems 1b and 1c we rely on Theorems 2b and 2c and for that purpose note that ${\mathsf{bSGD}}$ can be directly implemented using ${{\mathsf{bSQ}}}$ (proof in Appendix D):

(${\mathsf{bSGD}}$ to ${{\mathsf{bSQ}}}$) For all $T,\rho,b,p,r$, it holds that

Furthermore, for every poly-time computable activation $\sigma$, it holds that

So far we considered learning with mini-batch stochastic gradient descent (${\mathsf{bSGD}}$), where an independent mini-batch of examples is used at each step. But this stochasticity, and the use of independent fresh samples for each gradient step, is not crucial for simulating ${\mathsf{PAC}}$ and ${\mathsf{SQ}}$, provided enough samples overall, and a correspondingly fine enough precision. We show that analogous results hold for learning with full-batch Gradient Descent (${\mathsf{fbGD}}$), i.e. gradient descent on the (fixed) empirical loss.

For all $m$ and $\rho<1/(8m)$ and for all $r$, it holds that

For all $m$, $\rho$ and $T,p,r$, it holds that

Furthermore, for all poly-time computable activations $\sigma$, it holds that

There exists a constant $C$ such that for all $\delta>0$, for all $T$, $\rho$, $m$, $p$, $r$, such that $m\rho^{2}>C(Tp\log(1/\rho)+\log(1/\delta))$, it holds that

Furthermore, for all poly-time computable activations $\sigma$, it holds that

There exists a constant $C$ such that for all $\delta>0$, for all $k,\tau,r$, it holds for $m,\rho$ such that $\rho=\tau/16$, $m\rho^{2}>C(k\log(1/\rho)+\log(1/\delta))$ that

The above theorems are analogous to Theorems 1a, 1b, 1c and 1d. They are proved in an analogous manner in Appendix E, by going through the intermediate model of fixed-batch statistical query ${{\mathsf{fbSQ}}}$, in place of ${{\mathsf{bSQ}}}$. An ${{\mathsf{fbSQ}}}(k,\tau,m,p,r)$ method is described identically to an ${{\mathsf{bSQ}}}(k,\tau,b=m,p,r)$ method, except that the responses for all queries are obtained using the same batch of samples in all rounds (i.e. $S_{t}=S$ for all $t$, where $S\sim\mathcal{D}^{m}$ in Equation 8). Simulating ${{\mathsf{fbSQ}}}$ methods using ${\mathsf{fbGD}}$, or ${\mathsf{fbGD_{NN}}}$ can be done using the exact same constructions as in Lemmas 3a and 3b. To establish Theorem 3a, we use an algorithm similar to (and simpler than) Algorithm 1 to extract all the samples batch of samples (see details in Lemma 5a in Section A.2). Relating ${{\mathsf{fbSQ}}}$ to ${\mathsf{SQ}}$ and establishing Theorems 3c and 3d requires more care, because of the adaptive nature of ${\mathsf{fbGD}}$ on the full-batch. Instead, we consider all possible queries the method might make, based on previous responses. Since we have at most $Tp\log(1/\rho)$ or $kp\log(1/\tau)$ bits of response to choose a new query based on, we need to take a union bound over a number of queries exponential in this quantity, which results in the sample sized required to ensure validity scaling linear in $kp\log(1/\tau)$. See Section A.4 for complete proofs and details.

${\mathsf{fbGD}}={\mathsf{PAC}}\quad$ and $\quad{\mathsf{fbGD_{NN}}}={\mathsf{PAC_{TM}}}$.

But a significant difference versus ${\mathsf{bSGD}}$ is that with ${\mathsf{fbGD}}$ the precision depends (even if only polynomially) on the total number of samples used by the method. This is in contrast to ${\mathsf{bSGD}}$, where the precision only has to be related to the mini-batch size used, and with constant precision (and constant mini-batch size), we could simulate any sample based based method, regardless of the number of samples used by the method (only the number $T$ of SGD iterations and the size $p$ of the model increase with the number of samples used). Viewed differently, consider what can be done with some fixed precision $\rho$ (that is not allowed to depend on the problem size $n$ or sample size $m$): methods that use up to $1/(8\rho)$ samples can be simulated even with ${\mathsf{fbGD}}$. But ${\mathsf{bSGD}}$ allows us to simulate methods that use even more samples, by keeping the mini-batch size below $1/(8\rho)$.

Perhaps the most realistic differentiable learning approach is to use a fixed training set $S$, and then at each iteration calculate a gradient estimate based on a mini-batch $S_{t}\subset S$ chosen at random, with replacement, from within the training set $S$ (as opposed to using fresh samples from the population distribution, as in ${\mathsf{bSGD}}$). Analogs of Theorems 1a and 1d and Theorem 3c should hold also for this hybrid class, but we do not provide details here.

Summary and Discussion

We provided an almost tight characterization of the learning power of mini-batch SGD, relating it to the well-studied learning paradigms ${\mathsf{PAC}}$ and ${\mathsf{SQ}}$, and thus (nearly) settling the question of “what can be learned using mini-batch SGD?”. That single-sample SGD is able to simulate ${\mathsf{PAC}}$ learning was previously known, but we extended this result considerably, studied its limit, and showed that even outside this limit, ${\mathsf{bSGD}}$ can still always simulate ${\mathsf{SQ}}$. A gap still remains, when the mini-batch size is between $1/\rho$ and $\log(n)/\rho^{2}$, where we do not know where ${\mathsf{bSGD}}$ sits between ${\mathsf{SQ}}$ and ${\mathsf{PAC}}$. We furthermore showed that with sufficient (polynomial) precision, even full Gradient Descent on an empirical loss can simulate ${\mathsf{PAC}}$ learning.

It is tempting to view our results, which show the theoretical power of differentiable learning, as explaining the success of this paradigm. But we do not think that modern deep learning behaves similar to the constructions in our work. While we show how any ${\mathsf{SQ}}$ or ${\mathsf{PAC}}$ algorithm can be simulated, this requires a very carefully constructed network, with an extremely particular initialization, which doesn’t look anything like deep learning in current practice. Our result certainly does not imply that SGD on a particular neural net can learn anything learnable by ${\mathsf{PAC}}$ or ${\mathsf{SQ}}$, as this would imply that such network can learn any computationally tractable functionObserve that for any tractable function $f$, there exists a trivial learning algorithm that returns $f$ regardless of its input, which means that the class $\{f\}$ is ${\mathsf{PAC}}$ learnable., which is known to be impossible (subject to mild cryptographic assumptions).

Rather, we view our work as guiding us as to what questions we should ask toward understanding how actual deep learning works. We see that understanding differentiable learning in such a broad generality as we did here is probably too strong, as it results in answers involving unrealistic initialization, and no restriction, and thus no insight, as to what makes learning problems learnable using deep learning. Can we define a class of neural networks, or initializations, which is broad enough to capture the power of deep learning, yet disallows such crazy initialization and does provide insight as to when deep learning is appropriate? Perhaps even mild restrictions on the initialization can already severely restrict the power of differentiable learning. E.g., Malach et al. (2021) recently showed that even just requiring that the output of the network at initialization is close to zero can significantly change the power of differentiable learning, Abbe et al. (2021) showed that imposing certain additional regularity assumptions on the architecture/initialization of neural networks restricts the learning power of (S)GD to function classes with a certain hierarchical property. An interesting direction for future work is understanding the power of differentiable learning under these, or other, restrictions. Does this lead to a different class of learnable problems, distinct from ${\mathsf{SQ}}$ and ${\mathsf{PAC}}$, which is perhaps more related to deep learning in practice?

This work was done as part of the NSF-Simons Sponsored Collaboration on the Theoretical Foundations of Deep Learning. Part of this work was done while PK was at TTIC, and while NS was visiting EPFL. PK and NS were supported by NSF BIGDATA award 1546500 and NSF CCF/IIS award 1764032.

References

In this section, we prove Theorems 2a, 2b, 2c and 2d. Additionally, we state and prove analogous statements relating ${{\mathsf{fbSQ}}}$ to ${\mathsf{PAC}}$ and ${\mathsf{SQ}}$.

For all $b$, $\tau$ satisfying $b\tau<1/2$, we first design a ${{\mathsf{bSQ}}}(k=10(n+1),\tau,b,p=n+1,r)$ algorithm Sample-Extract (Algorithm 1) that generates a single sample $(x,y)\sim\mathcal{D}$; technically, this algorithm runs in at most $10(n+1)$ expected number of steps, but as we will see this is sufficient to complete the proof. For ease of notation, we let $\mathcal{Z}:=\mathcal{X}\times\mathcal{Y}$ and we identify $\mathcal{Z}$ with $\left\{0,1\right\}^{n+1}$ and denote $z\in\mathcal{Z}$ as $(z_{1},\ldots,z_{n+1})=(y,x_{1},\ldots,x_{n})$. Sample-Extract operates by sampling the bits of $z$ one by one, drawing $\widehat{z}_{i}$ from the conditional distribution $\left\{z_{i}\mid z_{1,\ldots,i-1}\right\}_{\mathcal{D}}$. We show two things: (i) Once the algorithm is at a prefix $s$, the algorithm indeed returns a sample $\widehat{z}$ drawn from the conditional distribution $\left\{z\mid z_{1,\ldots,k}=s\right\}_{\mathcal{D}}$, and (ii) The algorithm returns a sample in $T\leq 10(n+1)$ expected number of steps.

Thus, the expected number of steps before we get at least one sample starting with $s$ is at most $2/bp_{s}$. Also, $\Pr[b_{s}>0]=1-(1-p_{s})^{b}\leq bp_{s}$. So, for $p_{0}:=p_{s\circ 0}$ and $p_{1}:=p_{s\circ 1}$ (that is, the probabilities that a sample from $\mathcal{D}$ starts with $s\circ 0$ and $s\circ 1$ respectively), the expected number of steps remaining in the algorithm is at most

as claimed. Next, we show that if the algorithm currently has a prefix $s$ and $bp_{s}>1/5$, then the expected number of steps remaining is at most $10(n+1-|s|)$. We again prove this with a reverse induction on $|s|$. The base case of $|s|=n+1$ is trivial. With $bp_{s}>1/5$, the probability that a batch of $b$ samples has at least one sample starting with prefix $s$ is at least $1/8$. So, the expected remaining number of steps before the algorithm terminates is at most

as desired. That completes the induction argument. The algorithm starts with $s=\epsilon$, which every sample will start with, so the expected number of steps before the algorithm terminates is at most $10(n+1)$.

This is immediate, since a ${\mathsf{PAC}}(m=kb,r)$ method can generate valid ${{\mathsf{bSQ}}}$ responses using $b$ samples for each of the $k$ rounds by simply computing the empirical averages per batch. The number of random bits used remains unchanged. ∎

Finally we show that with a slight modification, Sample-Extract can be implemented as a ${{\mathsf{bSQ^{0/1}}}}$ algorithm, thereby proving Lemma 1, restated below for convenience.

Since $z_{1}=y$, all queries of Sample-Extract are already of the form $\mathds{1}\left\{y=\overline{y}\right\}\wedge\Phi_{\mathcal{X}}(x)$ for $\overline{y}\in\{0,1\}$. It can also be implemented as a ${{\mathsf{bSQ^{0/1}}}}$ algorithm as follows: After the first query we fix $y=s_{1}\in\{0,1\}$. If $s_{1}=0$, we use only even rounds to perform the queries as done by Sample-Extract and when $s_{1}=1$, we use only odd rounds. This increases the total number of rounds by a factor of $2$. ∎

A.2 𝗳𝗯𝗦𝗤𝗳𝗯𝗦𝗤{{\mathsf{fbSQ}}} versus 𝗣𝗔𝗖𝗣𝗔𝗖{\mathsf{PAC}}

We show the analogs of Theorems 2a and 2b for ${{\mathsf{fbSQ}}}$.

(${\mathsf{PAC}}$ to ${{\mathsf{fbSQ}}}$) For all $m$, and $\tau<1/(2m)$ and for all $r$, it holds that

Starting with the prefix $s=\epsilon$ (empty string) and knowledge of $|S_{\epsilon}|=m$, we can recover all samples using at most $m(n+1)$ ${{\mathsf{fbSQ}}}$s, after which we can simply simulate the ${\mathsf{PAC}}(m,r)$ method. Note that unlike the reduction to ${{\mathsf{bSQ}}}$, here the algorithm always succeeds in extracting $m$ samples in $m(n+1)$ steps. Hence there is no loss in the error ensured. ∎

(${{\mathsf{fbSQ}}}$ to ${\mathsf{PAC}}$) For all $m$, $\tau$ and $k,p,r$, it holds that

This is immediate, since a ${\mathsf{PAC}}(m,r)$ method can generate valid ${{\mathsf{fbSQ}}}$ responses using $m$ samples for each of the $k$ rounds by simply computing the empirical averages over the entire batch of samples. The number of random bits used remains unchanged. ∎

Finally, we show that with a slight modification, in the same regime of Lemma 5a, any ${\mathsf{PAC}}$ method can be simulated by a ${{\mathsf{fbSQ^{0/1}}}}$ method, analogous to Lemma 1.

(${\mathsf{PAC}}$ to ${{\mathsf{fbSQ^{0/1}}}}$) For all $m$, and $\tau<1/(2m)$, and for all $r$, it holds that

By modifying proof of Lemma 5a, analogous to the modification to proof of Theorem 2a to get Lemma 1. ∎

A.3 𝗯𝗦𝗤𝗯𝗦𝗤{{\mathsf{bSQ}}} versus 𝗦𝗤𝗦𝗤{\mathsf{SQ}}

Fix a ${{\mathsf{bSQ}}}(k,\tau,b,p,r)$ method $\mathcal{A}$, and consider any ${{\mathsf{bSQ}}}$ query $\Phi:\mathcal{X}\times\mathcal{Y}\to^{p}$. Using Chernoff-Hoeffding’s bound and a union bound over $p$ entries, we have that

Finally we show that any ${\mathsf{SQ}}$ method can be simulated by a ${{\mathsf{bSQ^{0/1}}}}$ method thereby proving Lemma 2, restated below for convenience. The proof goes via an intermediate ${\mathsf{SQ^{0/1}}}$ method (defined analogous to ${{\mathsf{bSQ^{0/1}}}}$).

Finally, we use essentially the same argument as in Theorem 2d to obtain a ${{\mathsf{bSQ^{0/1}}}}$ method from $\mathcal{A}^{\prime}$. The only change needed to preserve the alternating nature of $\mathcal{A}^{\prime}$ is that we perform all the $1$-queries in $q$ odd rounds, interleaved with -queries in $q$ even rounds. This completes the proof. ∎

A.4 𝗳𝗯𝗦𝗤𝗳𝗯𝗦𝗤{{\mathsf{fbSQ}}} versus 𝗦𝗤𝗦𝗤{\mathsf{SQ}}

We show the analogs of Theorems 2c and 2d for ${{\mathsf{fbSQ}}}$. The number of samples required depends linearly on the number of queries, instead of logarithmically. The reason for this is that unlike in the proof of Theorems 2c and 2d, a naive union bound does not suffice, since the queries can be adaptive.

(${{\mathsf{fbSQ}}}$ to ${\mathsf{SQ}}$) There exist a constant $C\geq 0$ such that for all $\delta>0$, for all $k,{\bm{\tau}},{\bm{m}},p,r$ such that $m\tau^{2}>C(kp\log(1/\tau)+\log(1/\delta))$, it holds that

Using Chernoff-Hoeffding’s bound (Equation 10) and a union bound over all these $(1/\alpha+1)^{kp}$ possible queries we have that with probability at least $1-2p(1+1/\alpha)^{kp}\cdot e^{-\eta^{2}m/2}$ over sampling $S\sim\mathcal{D}^{m}$, it holds for each such query $\Phi:\mathcal{X}\times\mathcal{Y}\to^{p}$ that

(${\mathsf{SQ}}$ to ${{\mathsf{fbSQ}}}$) There exist a constant $C\geq 0$ such that for all $\delta>0$, $k,\tau,r$, it holds for $\tau^{\prime}=\frac{\tau}{2}$ and all $m$ such that $m\tau^{2}>C(k\log(1/\tau)+\log(1/\delta))$ that

Finally, we show that with a slight modification, in the same regime of Lemma 5d, any ${\mathsf{SQ}}$ method can be simulated by a ${{\mathsf{fbSQ^{0/1}}}}$ method, analogous to Lemma 2.

(${\mathsf{SQ}}$ to ${{\mathsf{fbSQ^{0/1}}}}$) There exist a constant $C\geq 0$ such that for all $\delta>0$, $k,\tau,r$, it holds for $\tau^{\prime}=\frac{\tau}{4}$ and all $m$ such that $m\tau^{2}>C(k\log(1/\tau)+\log(1/\delta))$ that

By modifying proof of Lemma 5d, analogous to the modification to proof of Theorem 2d to get Lemma 2. ∎

Appendix B Simulating 𝗯𝗦𝗤𝗯𝗦𝗤{{\mathsf{bSQ}}} with 𝗯𝗦𝗚𝗗𝗯𝗦𝗚𝗗{\mathsf{bSGD}} : Proof of Lemma 3a

In this section, we show how to simulate any ${{\mathsf{bSQ^{0/1}}}}$ method $\mathcal{A}$ as ${\mathsf{bSGD}}$ on some differentiable model constructed according to $\mathcal{A}$, and thus prove Lemma 3a:

As a first step towards showing Lemma 3a, we show how a single $\overline{y}$-query can be simulated using a single step of ${\mathsf{bSGD}}$. We consider parameterized queries, that can depend on some of parameters of the differentiable model. Namely, $\Phi:^{q}\times\mathcal{X}\times\mathcal{Y}\to^{p}$ is a query that given some parameters $\theta\in^{q}$, an input $x\in\mathcal{X}$ and a label $y\in\mathcal{Y}$, returns some vector value $\Phi(\theta,x,y)$. We show the following:

$\left\lVert\theta^{(1)}-\frac{1}{b}\sum_{(x,y)\in S}\Phi(\widehat{\theta}^{(0)},x,y)\right\rVert_{\infty}\leq\varepsilon+\rho$,

Assume $\Phi$ is a -query, namely $\Phi(x,y)=(1-y)\Phi(\widehat{\theta},x,0)$. Then, we define a differentiable model as follows:

Then, after performing one step of ${\mathsf{bSGD}}$ we have:

And therefore, after one step of ${\mathsf{bSGD}}$ we have $\kappa^{(1)}\geq\varepsilon-\rho$.

Assume $\Phi$ is a $1$-query, namely $\Phi(x,y)=y\Phi(\widehat{\theta},x,0)$. Then, we define a differentiable model as follows:

Then, after performing one step of ${\mathsf{bSGD}}$ we have:

And therefore, after one step of ${\mathsf{bSGD}}$ we have $\kappa^{(1)}\geq\varepsilon-\rho$.∎

Our goal is to use Lemma 8 to simulate a ${{\mathsf{bSQ^{0/1}}}}$ method. Any ${{\mathsf{bSQ^{0/1}}}}$ method $\mathcal{A}$ is completely described by a sequence of (potentially adaptive) queries $\Phi_{1},\dots,\Phi_{T}$, and a predictor $h$ which depends on the answer to previous queries, namely:

$\Phi_{t}$ depends on $r$ random bits, and on the answers of the previous $t-1$ queries, namely:

For every compact set $K$ and open set $U$ such that $K\subseteq U\subseteq^{q}$, there exists a smooth function $\Psi:^{q}\to$ such that $\Psi(x)=1$ for every $x\in K$ and $\Psi(x)=0$ for every $x\notin U$.

Our differentiable model will use the following parameter:

$T$ “clock” parameters $\kappa_{1},\dots\kappa_{T}$, that indicate which query should be issued next. We initialize $\kappa_{1},\dots,\kappa_{T}=0$.

We denote by $\theta^{(t,i)},\kappa_{t}^{(i)}$ the value of the $t$-th set of parameters in the $i$-th iteration of SGD. The differentiable model is defined as follows:

Now, denote $v_{0}:=\theta^{(0,0)}$, and for every $t>0$ denote $v_{t}:=\theta^{(t,t)}$. We have the following claim:

Claim: for every iteration $i$ of ${\mathsf{bSGD}}$,

For every $t>i$ we have $\theta^{(t,i)}=0$ and $\kappa^{(i)}_{t}=0$.

For $t<i$ we have $\theta^{(t,i)}=\theta^{(t,t)}$.

For $t\leq i$ we have $\kappa_{t}^{(i)}\geq\rho$.

For $i=1$, notice that by the initialization, $\kappa_{t}^{(0)}=0$ for every $t$. Fix some $t>1=i$, and note that $c(\kappa_{t-1},\kappa_{t},\alpha)=0$, so the gradient w.r.t $\theta^{(t,i)}$, $\kappa_{t}^{(i)}$ is zero, and so condition 1 hold (the initialization is zero, and the gradient is zero). For $t=1=i$, notice that since $c(\kappa_{0},\kappa_{1}^{(0)},\alpha)=\alpha$, we have:

and by applying Lemma 8 with $\varepsilon=2\rho$ we get:

and so condition 4 follows. Finally, condition 3 is vacuously true.

Fix some $i>0$, and assume the claim holds for $i$. We will prove the claim for $i+1$. By the assumption, we have $\kappa_{t}^{(i)}=0$ for every $t>i$ and $\kappa_{t}^{(i)}\geq\rho$ for every $t\leq i$. Therefore, by definition of $c$, we have $c(\kappa_{t-1}^{(i)},\kappa_{t}^{(i)},\alpha)=\mathds{1}_{t=i+1}\alpha$. So,

Therefore, conditions 1 and 3 follow from the fact that the gradient with respect to $\theta^{(t,i)}$ and $\kappa_{t}^{(i)}$, for every $t\neq i+1$, is zero. Now, using Lemma 8 with $\varepsilon=2\rho$, condition 2 follows, and we also have $\kappa_{i+1}^{(i+1)}\geq\rho$. Finally, for every $t<i+1$, by the assumption we have $\kappa_{t}^{(i)}\geq\rho$, and since the gradient with respect to $\kappa_{t}^{(i)}$ is zero, we also have $\kappa_{t}^{(i+1)}\geq\rho$. Therefore, condition 4 follows.

Finally, to prove the Theorem, observe that by the previous claim, for every $t$:

So, $v_{t}$ is a valid response for the $t$-th query.

By the previous claim, we have $\kappa_{t}^{(T)}\geq\rho$ for every $1\leq t\leq T$. Therefore, we have:

and, using the fact that $v_{0},\dots,v_{T}$ are valid responses to the method’s queries, we get the required. ∎

B.1 From Arbitrary Differentiable Models to Neural Networks.

In this section we proved the key lemma for our main results, showing that alternating batch-SQ methods can be simulated by gradient descent over arbitrary differentiable models. We would furthermore like to show that if the alternative batch-SQ method is computationally bounded, the differentiable model we defined can be implemented as a neural network of bounded size.

Indeed, observe that when the method can be implemented using a Turing-machine, each query (denoted by $\Phi$ in the proof) can be simulated by a Boolean circuit [see Arora and Barak, 2009], and hence by a neural network with some fixed weights. Therefore, one can show with little extra effort that the differentiable model introduced in the proof of Lemma 3a can be written as a neural network, with some of the weights being fixed. To show that the same behavior is guaranteed even when all the weights are trained, it is enough to show that all the relevant weights (e.g., $\theta^{(0)},\dots,\theta^{(T)}$) have zero gradient, unless they are correctly updated. This can be achieved using the “clock” mechanism (the function $c(\alpha_{1},\alpha_{2},\alpha_{3})$ in the construction), which in turn can be implemented by a neural network that is robust to small perturbations of its weights, and hence does not suffer from unwanted updates of gradient descent. One possible way to implement the clock mechanism using a neural network that is robust to small perturbations is to rely either on large weight magnitudes and small step-sizes, or on the clipping of large gradients.

We do not include these details, Instead, in the next Section, we provide complete details and a rigorous proof of an alternate, more direct, construction of a neural network defining a differentiable model that simulates a given ${{\mathsf{bSQ_{TM}^{0/1}}}}$ method. This direct neural-network construction is based on the same ideas, but is different in implementation from the construction shown in this section, involving some technical details to ensure that the network is well behaved under the gradient descent updates.

In this section, we show a direct construction of a neural network such that gradient descent on the neural net simulates a given ${{\mathsf{bSQ_{TM}^{0/1}}}}$ method, thus proving Lemma 3b:

Given a ${{\mathsf{bSQ}}}$ algorithm with a specified bounded runtime, we will design a neural network such that the mini-batch gradients at each step correspond to responses to queries of the ${{\mathsf{bSQ}}}$ algorithm. Our proof of this is based on the fact that any efficient ${{\mathsf{bSQ_{TM}^{0/1}}}}$ algorithm must decide what query to make next and what to output based on some efficient computation performed on random bits and the results of previous queries. Any efficient algorithm can be performed by a neural net, and it is possible to encode any circuit as a neural net of comparable size in which every vertex is always at a flat part of the activation function. Doing that would ensure that none of the edge weights ever change, and thus that the net would continue computing the desired function indefinitely. So, that allows us to give our net a subgraph that performs arbitrary efficient computations on the net’s inputs and on activations of other vertices.

Also, we can rewrite any ${{\mathsf{bSQ_{TM}^{0/1}}}}$ algorithm to only perform binary queries by taking all of the queries it was going to perform, and querying the $i$th bit of their binary representation for all sufficiently small $i$ instead. For each of the resulting binary queries, we will have a corresponding vertex with an edge going to it from the constant vertex and no other edges going to it. So, the computation subgraph of the net will be able to determine the current weights of the edges leading to the query vertices by checking their activations. Also, each query vertex will have paths from it to the output vertex with intermediate vertices that will either get inputs in the flat parts of their activation function or not depending on the output of some vertices in the computation subgraph. The net effect of this will be to allow the computation subgraph to either make the value encoded by the query edge stay the same or make it increase if the net’s output differs from the sample output based on any efficiently computable function of the inputs and other query vertices’ activations. This allows us to encode an arbitrary ${{\mathsf{bSQ^{\text{fgt}}}}}$ algorithm as a neural net.

In order to prove the capabilities of a neural net trained by batch stochastic gradient descent, we will start by proving that any algorithm in ${{\mathsf{bSQ}}}$ can be emulated by a neural net trained by batch stochastic gradient descent under appropriate parameters. In this section our net will use an activation function $\sigma$, as defined in Figure 1, namely

Any ${{\mathsf{bSQ}}}$ algorithm repeatedly makes a query and then computes what query to perform next from the results of the previous queries. So, our neural net will have a component designed so that we can make it update targeted edge weights by an amount proportional to the value of an appropriate query on the current batch and a component designed to allow us to perform computations on these edge weights. We will start by proving that we can make the latter component work correctly. More formally, we assert the following.

Let $h:\{0,1\}^{m}\rightarrow\{0,1\}^{m^{\prime}}$ be a function that can be computed by a circuit made of AND, OR, and NOT gates with a total of $b$ gates. Also, consider a neural net with $m$ inputNote that these will not be the $n$ data input of the general neural net that is being built; these input vertices take both the data inputs and some inputs from the memory component. vertices $v^{\prime}_{1},...,v^{\prime}_{m}$, and choose real numbers $y_{i}^{(0)}<y_{i}^{(1)}$ for each $1\leq i\leq m$. It is possible to add a set of at most $b$ new vertices to the net, including output vertices $v^{\prime\prime}_{1},...,v^{\prime\prime}_{m^{\prime}}$, along with edges leading to them such that for any possible addition of edges leading from the new vertices to old vertices, if the net is trained by bSGD, the output of $v^{\prime}_{i}$ is either less than $y_{i}^{(0)}$ or more than $y_{i}^{(1)}$ for every $i$ in every timestep, then the following hold:

The derivative of the loss function with respect to the weight of each edge leading to a new vertex is in every timestep, and no paths through the new vertices contribute to the derivative of the loss function with respect to edges leading to the $v^{\prime}_{i}$.

In any given time step, if the output of $v^{\prime}_{i}$ encodes $x_{i}$ with values less than $y_{i}^{(0)}$ and values greater than $y_{i}^{(1)}$ representing and $1$ respectively for each $i$, then the output of $v^{\prime\prime}_{j}$ encodes $h_{j}(x_{1},...,x_{m})$ for each $j$ with $-2$ and $2$ encoding and $1$ respectively.

In order to do this, we will add one new vertex for each gate and each input in a circuit that computes $h$. When the new vertices are used to compute $h$, we want each vertex to output $2$ if the corresponding gate or input outputs a $1$ and $-2$ if the corresponding gate or input outputs a , and we want the derivative of its activation with respect to its input to be . In order to do that, we need the vertex to receive an input of more than $2$ if the corresponding gate outputs a $1$ and an input of less than $-3$ if the corresponding gate outputs a .

In order to make one new vertex compute the NOT of another new vertex, it suffices to have an edge of weight $-2$ to the vertex computing the NOT and no other edges to that vertex. We can compute an AND of two new vertices by having a vertex with two edges of weight $2$ from these vertices and an edge of weight $-4$ from the constant vertex. Similarly, we can compute an OR of two new vertices by having a vertex with two edges of weight $2$ from these vertices and an edge of weight $4$ from the constant vertex. For each $i$, in order to make a new vertex corresponding to the $i$th input, we add a vertex and give it an edge of weight $8/(y^{(1)}-y^{(0)})$ from the associated $v^{\prime}_{i}$ and an edge of weight $-(4y^{(1)}+4y^{(0)})/(y^{(1)}-y^{(0)})$ from the constant vertex. These provide an overall input of at least $4$ to the new vertex if $v^{\prime}_{i}$ has an output greater than $y^{(1)}$ and an input of at most $-4$ if $v^{\prime}_{i}$ has an output less than $y^{(0)}$.