On the Power of Differentiable Learning versus PAC and SQ Learning
Authors: Emmanuel Abbe
Pritish Kamath
eran malach
Colin Sandon
Nathan Srebro
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Differentiable Learning
PAC Learning
Statistical Query Learning
mini-batch SGD

Abstract: We study the power of learning via mini-batch stochastic gradient descent (SGD) on the loss of a differentiable model or neural network, and ask what learning problems can be learnt using this paradigm. We show that SGD can always simulate learning with statistical queries (SQ), but its ability to go beyond that depends on the precision $\rho$ of the gradients and the minibatch size $b$. With fine enough precision relative to minibatch size, namely when $b \rho$ is small enough, SGD can go beyond SQ learning and simulate any sample-based learning algorithm and thus its learning power is equivalent to that of PAC learning; this extends prior work that achieved this result for $b=1$. Moreover, with polynomially many bits of precision (i.e. when $\rho$ is exponentially small), SGD can simulate PAC learning regardless of the batch size. On the other hand, when $b \rho^2$ is large enough, the power of SGD is equivalent to that of SQ learning.

On the Power of Differentiable Learning versus PAC and SQ Learning
Emmanuel Abbe EPFL email
Pritish Kamath Google Research
Eran Malach HUJI email
pritish@ttic.ed edu
Colin Sandon'
Nathan Srebro TTIC nati@ttic.edi
MIT csandon@mit.cm edu
Abstract
We study the power of learning via mini-batch stochastic gradient descent (SGD) the population loss, and batch Gradient Descent (GD) the empirical loss, a differentiable model or neural network, and ask what learning problems can be learnt using these paradigms. We show that SGD and GD can always simulate learning with statistical queries (SQ), but their ability to go beyond that depends the precision p of the gradient calculations relative the minibatch size b (for SGD) and sample size m (for GD). With fine enough precision relative to minibatch size, namely when bp is small enough, SGD go beyond SQ learning and simulate any sample-based learning algorithm and thus its learning power is equivalent to that of PAC learning; this extends prior work that achieved this result for = Similarly, with fine enough precision relative to the sample size m, GD can also simulate any sample-based learning algorithm based on m samples. In particular, with polynomially many bits of precision (i.c. when is exponentially small). SGD and GD can both simulate PAC learning regardless of the mini-batch size. On the other hand, when bp² is large enough, the power of SGD is equivalent that of SQ learning.
Introduction
leading paradigm that has become the predominant approach to learning is that of differentiable learning, namely using parametric function class fu (x), and learning by performing mini-batch Stochastic Gradient Descent (bSGD) updates (using gradients of the loss on a mini-batch of b inde- pendent samples per iteration) full-batch Gradient Descent (fbGD) updates (full gradient descent on the empirical loss, using the same m samples in all iterations). Feed-forward neural networks are particularly popular choice for the parametric model fw. One approach understanding differentiable learning is to think of it as method for minimizing the empirical error of fw with respect to w, i.c. as an empirical risk minimization (ERM). ERM is indeed well understood, and is in a sense a universal learning rule, in that any hypothesis class that is PAC learnable is also learnable using ERM. Furthermore, since poly-sized rerdfforarr neural networks can represent any poly-time computable function, we can conclude that ERM on neural networks can efficiently learn any tractable problem. But this view differentiable learning ignores two things.
Firstly, many ERM problems, including ERM on any non-trivial neural network, are highly non- convex and (stochastic) gradient descent might not find the global minimizer. As just discussed,
Authors in alphabetical order.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

pretending that bSGD foGD do find the global minimizer would mean we can learn all poly-time computable functions, which is known to he impossible" [e.g. 12, 13]. In fact, even minimizing the empirical risk on 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 bSGD/fbGD [6]. We already see that bSGD and fbGD are not the same as ERM, and asking "what can be learned by bSGD/fbGD" is quite different from asking "what can be learned by ERM".
Furthermore, bSGD and fbGD might also be more powerful than ERM. Consider using highly overparametrized function class fw. with many more parameters than the number of training examples, as is often the case in modern deep learning. In such situation there would typically be many empirical risk minimizers (zero training error solutions), and most of them would generalize horribly, and the ERM principal on its own not sufficient for learning [18]. Yet we now understand how fbGD and bSGD incorporate intricate implicit bias that leads to particular empirical risk minimizers which might well ensure learning [19, 17].
All this justifies studying differentiable learning as a different and distinct paradigm from empirical risk minimization. The question ask is therefore: What can be learned by performing mini- batch stochastic gradient descent, or full-batch gradient descent, on some parametric function class fw, and in particular important not only for understanding the limits of what we could possibly expect from differentiable learning, but even more in guiding us as to how should study differentiable learning, and ask questions, e.g., about its power relative to kernel methods [e.g. 22, 3, 4, 14, 8-10, 16), or the theoretical benefits of different architectural innovations [e.g. 15].
feed-forward neural network? Answering this question is
significant, and perhaps surprising, advance toward answering this question was recently presented by Abbe and Sandon [1], who showed that bSGD with single example per iteration (i.e. minibatch of size 1) can simulate any poly-time learning algorithm, and hence is as powerful as PAC learning. On the other hand, they showed training using population gradients (infinite batch size, or very large batch sizes) and low- -rw-ricciion (polynomial accuracy, i.e. a logarithmic number of bits of precision), is more powerful than learning with Statistical Queries (SQ). which is known to be strictly less powerful than PAC learning [11, 7]. This seems to suggest non-stochastic fbGD, or even bSGD with large batch sizes, is not universal in the same way as single-example 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.
Our Contributions. In this paper, we take a more refined view of this dichotomy, and consider learning with bSGD with larger mini-batch sizes b > 1, as is more typically done in practice, as well as with fbGD. We ask whether the ability to simulate PAC learning is indeed preserved also with larger mini-batch sizes, 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 the relationship of the batch size b and the precision p 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 p is an arbitrary additive eтror we allow.
We first show that regardless of the mini-batch size, bSGD is always able to simulate any SQ method, and so bSGD is at least as powerful as SQ learning. When the mini- batch size b is large relative to the precision, namely b w(log(n)/p and number of iterations are polynomial in n, bSGD is not any more powerful than SQ. But when b < 1/ 1/(8)), or in other words with fine enough precision p < 1/(SD), bSGD can again simulate any sample-based learning method, and is as powerful as 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 and precision p do not, and only need to satisfy hp < 1/8 see formal results in Section 3). We show a similar result for fbGD, with a dependence on the sample size m: with low precision (large p) relative to the sample size m, fbGD is no more powerful than SQ. But with fine enough precision relative the sample size, namely when p < 1/(8m), fbGD can again simulate any sample-basee learning method based on m samples (formal results are deferred to supplementary material).
where is the input dimension and we assume the model size
'Subject to mild cryptographic assumptions, such as the existence of one-way functions, i.c. the existence of cryptography itself, and where referring to bSGD /fbGG running for polynomially many steps.

---

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-logarihmie) number of bits of precision (i.e. p 2 2-"), bSGD and 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 0).
On the other hand, with low precision (high p. i.e. only 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 fbGD, or with bSGD with mini-batch size that is too large, namely = w(log(n)/ pp) Overall, except for an intermediate regime between 1/p and log(n)/p², we can precisely capture the power of 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 PAC and SQ are related, in the sense described above, to bSGD and fbGD on a poly-sized neural network, whereas computationally unbounded PAC and SQ (i.e. limited only by the number of samples number of statistical queries, but not runtime) are similarly related to bSGD and fbGD on an arbitrary differentiable model fu. In fact, to simulate PAC and SQ, we first construct an arbitrary Su. and then observe that if the PAC or 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 pily-size sub-networks, allowing us to implement fw as a neural net.
Answering SQs using Samples. Our analysis relies on introduction of a variant of SQ learning which we refer to as mini-batch Statistical Queries (bSQ, and we similarly introduce a full-batch variant, fbSQ). In this variant, which is related to the Honest-SQ model [20, 21J. statistical queries answered using mini-batch of samples drawn from the source distribution, up to some precision. We first show that bSQ methods can always be simulated by 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 bSQ to SQ and PAC, based on the relationship between the mini- batch size and precision. In order to simulate PAC using bSQ, we develop a novel "sample extraction" " that uses mini-bated 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 bSQ to SQ and PAC, summarized in Section 4, also sheds light on how well the SQ framework captures learning by answering queries using empirical averages on sample, which is arguably one of the main motivations for the polynomao tolerance parameter in the SQ framework.
2 Learning Paradigms
We consider learning a predictor f X IR over input space X, so to minimize its population loss LD(f) == E(mw)>D {(f(x), y) with respect to a source distribution D over X' x Y, where e: R x ) - R20 loss function. Unless noted otherwise, we take the loss function to be the squarc-loss (ū. = (0 y)². For concreteness, always take y {0, 1) and X {0, 1)".
Differentiable Learning. We study learning by (approximate) gradient descent on a differentiable model. Formally, a differentiable model of size p is a mapping f RR X - R, denoted fw (2), where w E IR" are the parameters, or "weights", of the model, and for every x E X there exists gradient fw (x) for almost every E Rp (i.e, outside of a measure-zero set of weights). A notable special case of differentiable models we study is that of feed-forward neural networks.
For differentiable model In (z). an initialization distribution W over RP, mini-batch size b, gra- dient precision/ p. and stepsize* 4 y, the mini-batch Stochastic Gradient Descent (bSGD) method
"Allowing fo (1r) to be non-differentiable on a measure zero set might seem overly generous, but it's simpler to state, and a more conservative restriction wouldn't 't affect our results. Our simulations use either everywhere differentiable models, or neural networks with piece-wise linear activation, resulting in piece-wise linear models with a finite number of pieces.
'The stepsize doesn't play an important role in our analysis. We can also allow variable or adaptive stepsize sequences without changing the results for simplicity of presentation we stick with a fixed stepsize, and in fact in our constructions just use fixed constant (not dependent on other parameters) stepsize of 7 = 1 7 = 2.
3

---

operates by computing iterates of the form: w)()) W and w((+1)
wn(t) T9h, where
Sr is a p-approximate rounding of the mini-batch (empirical) clipped gradient VLs, (f == E Ve(f (z(,)), Vt.a)l1. where the
S = ((z)1) Vt.1)..... (z,,b, )c,b)) Db containing b samples each are sampled independently at each iteration, and [a]1 denotes entry-wise clipping of a to [-1, 1]. We say that u E [-1, 1J is a p-approximate rounding of u E [-1, 1]
E p Z" (namely, each entry of u is an integral multiple of p). and ||u ol I 3p/4. Thus,
overall gt. a valid gradient estimate if satisfies
9t p Z
and
l1g: - VLs, (Sunte) s 3p/4
(1)
Precision, Rounding and Clipping. The clipping and rounding use captures using d = 1 -lo P bits of precision, and indeed we generally consider 2 where d E N.
We consider clipped gradients because the precision p makes sense only when considered relative to the scale of the gradients. Clipping is an easy way to ensure we do not "cheat" by using very large magnitude gradients to circumvent the precision limit, and can be thought of as way of handling overflow. We note however that in all our simulation constructions, we always have [[V[(J (1r), y) llso S 1 for all w and all (at, y), and hence clipping plays no role. We could have alternatively said the method "fails" or is "invalid" if a larger magnitude gradient is encountered.
In our rounding error model, for any integer q. values in (qp- f. qp + f) get rounded to qp. whereas, values in [gp + p/4, qp + 3p/4] can get rounded either to qp or (q + 1)p. This error model is a proxy for rounding errors in real finite precision arithmetic, where we have uncertainty about the least significant bit when representing real numbers in [-1, with d bits of precision, as this final bit represents a rounding of the ignored lower order bits. Viewed another way, p-approximate rounding of E [-1, 1] can be obtained by considering p/ /-aaprroximation of v. i.e. U [-1, s.t. |c 5| S p/ 4, and then (deterministically) rounding to the nearest integer multiple of p.
Learning with bSGD. A learning method A is said to be bSGD p. b, p, method if operates by computing bSGD iterates for some differentiable model f: RR X + R (i.e., with p parameters), starting from some (randomized) initialization W which uses r random bits, with some stepsize 7 given p-approximate gradients over batches of size b; the output of A is the final iterate Ju : + I.. We say that A ensures error ε on a source distribution D if E[sup LD (faprr)) S e, where the expectation over both the initialization (n))) and the mini-batches S, ~ DD, and the sup is over all gradient estimates 9r satisfying (1) at iterates where fw is differentiable w(t) for all Z1,; E S, 6.7 We denote by bSGD pT b, r) the family of bSGD methods where the differentiable model is implemented by neural network with p parameters, using the poly-time computable" activation function a and where the initialization distribution W can be sampled from in poly (n) time.
We also consider learning with full-batch Gradient Descent, i.e. gradient descent on an empirical loss, where the entire training set of size m is used in each iteration. We defer details of this definition and corresponding results to supplementary material.
PAC and SQ Learning. A learning method A is said to be a PAC(m, r) method it takes in set of samples S C X' x y' of size m, uses r bits of randomness and returns a predictor f: + R. We say that A ensures error e on a source distribution D if IF [[D( < e, where the expectation is over
$ NNaeely, W {0. 13" + R" such that (0) ~ ((s) for a ~ uniform over (0. 13"
FFormally, and for simplicity, if fur is not differentiable at (ht)) for some 21. consider any gi E [[1, as valid. But recall that (x) is differentiable almost everywhere. We could have required a more conservative behaviour without affecting any of our results. In particular, in all our simulation constructions, fa (x) is always differentiable (t) encountered.
Definingg the error as E[sup [D(Fr))))]] can be interpreted as allowing the rounding errors on gr to also depend on random samples in future steps. A more conservative definition would involve F To) Ts, sup,, ... Sy supey LD (f((,,,r)). However, this distinction does not change any of our results and we stick to the simpler L sup definition for convenience.
*ee say that o R + R is "polynomial time computable" if there exists a Turing machine that, for any given z E IR and desired precision, computes
(z)) and o' (z) to within the desired precision in time that is polynomial the bit length of the representation of = and the number desired bits precision.
'The usage of the acronym PAC here is technically improper as we use it to refer to method and not class of leamning problems. We use it for notational convenience and historical reasons.

---

Dm and the randomness in A. Similarly, say that A is P TIME) algorithm if it a PAC(m, r) method which can be implemented using a Turing machine that runs in time TIME,
A learning method A is said to be statistical-query SQ(k, T,r) method, if it operates in & rounds where in round t the method produces a statistical-query 2t X' x y + [-1,1] for which receives response Vt, and finally outputs predictor X' + I. Formally, each & is function of random string R E {0, 1}" and past responses v1....: 11 We say that A ensures error e on a source distribution D if Eglsup [p(f)] Σ E, where the sup over all "valid" 2/ [-1, namely |0 - Ep (z, y) v т. Similarly, we say that AA is a SQTM T, r, TIME) algorithm if A is a SQ(k; r, method that can be implemented using Turing machine that runs in time TIME, using queries that can be computed in time TIME.
Relating Classes of Methods. The subject of this work is to compare between what can be learnt with different classes of methods. To do so, we define general notion of when methods in class C can be simulated by methods C', and thus C' can be said to be at least as powerful as C. For any method/algorithh A and for any source distribution D, let err(A, D) be the infimum over such that A ensures emror E on D. We now define:
Definition For two classes of methods C, C,C', and any 2 we write C' 38 if for every method A E C there exists method A' E C' such that for every source distribution 'D we have err(A (A', D) S err(A,
That is, C¹ 3s C means that C' is at least powerful as C. Observe that for all classes of methods C1, C2, C3. if C1 3o, C2 and C2 38a C3 then C1 18, +b2 C3.
3 Main Results: bSGD versus PAC and SQ
Our main result, given below as a four-part Theorem, establishes the power of bSGD learning relative to PAC (i.e. arbitrary sample based) and SQ learning. As previously discussed, the exact relation depends on the mini-batch size b and gradient precision p. First, we show that for any mini-batch size b, with fine enough precision p. bSGD
simulate PAC.
Theorem 1a (PAC to bSGD). For all b and < 1/bb)), and for all m, r, 6, it holds that r + O(T'(n (n + log b)), r') 3s PAC(m,r).
bS = (mm/0))m))))mmmmmm b. b.
where r' =r O(T" log b). Furthermore, if p < min {1/( 1/12], using a piecewise linear activation function a, for every runtime TIME, holds for p' poly (n, m, TIME, p 1 b, b-) and the same T", r' above that
bSGDAN (T', b. ,',''r) Ia PACTM(m, TIME)
To establish equivalence (when Theorem la holds), we also note that PAC is always at least as powerful as bSGD (since bSGD can be implemented using samples): Theorem 1b (bSGD to PAC). For all b, and T, p,r, it holds that PAC(m' = -bbrr' =)) Zo bSGD(T, p. p, Furthermore, for all poly-time computable activations a, holds that PM = Tb, TIME' = pTly b, log Zo (T,
If the mini-batch size is large relative the precision, bSGD cannot go beyond SQ: Theorem 1c (bSGD to SQ). There exists constant C such that for all ō >> 0, for all T, b such that bp² log(Tp/8) it holds that
r' SQ(K' = Tp, - 2s bSGD(T, p. p.
Furthermore, for all poly-time computable activations a, it holds that
SQTM W'= Tp, r' 0 8'
= TIME' = poly(TT (T, b.,,, 1. )) Is bSGD (T, b.p,r..
5

---

To complete the picture, we also show that regardless of the mini-batch size, i.e. even when bSGD cannot simulate PAC, bSGD can always, at the very least, simulate any SQ method. This also establishes equivalence SQ when Theorem Ie holds:
Theorem 1d (SQ to bSGD). There exists a constant such that for all 5 > O, for all b and all k,T, r, it holds that
bSGD(T', p
T = - 2 =r) 3s SQ(k, 16
where T = (6 Furthermore, using piecewise linear activation function o, it holds for poly I/T,r, TIME, 1/5) that
DSGDNN (T", p 16 b. b.p',r'=r)) 3s SQTM(K, T,T, TIME).
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 Is and gradient precision p play an important role. In Theorem la, we may choose b and p as we wish, as long they satisfy bp < <1/8-ther do not need to be chosen based on the parameters of the PAC method, and we can always simulate PAC with any b and p satisfying bp 1/8. Similarly, in Theorem 1d, may chose 6 > arbitrarily, and can always simulate SQ, although p does have to be chosen according to т. The reverse reduction of Theorem Ic, establishing the limit of when bSGD cannot go beyond SQ, is valid when 6p wlog n). if the size of the model p and number SGD iterations 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 la Id can be informally summarized as:
PAC bSGD(b) = SQ
(2)
where the left relationship is tight i < 1/(8p) and the right relationship is tight if > w((lg p?)))) Equivalently, focusing the precision P and how depends on the mini-batch size b, and allowing all other parameters to be polynomially related, Theorems la to Id can be informally summarized as:
p < 1/(8)),
bSGD(b, p) R PAC
(3)
p > w " (V(lon)/b)
PAC Σ SQ(O(p)) bSGD(b, p)
(4)
And in any case,
bSGD p) = SQ(e(p))
(5)
More formally, the results can also be viewed as a relationship between classes of learning problems. A learning problem is sequence (Px)neN, where each P,, is set of distributions D, over (0. 1)" R x x... For parametrized class of methods C(O). we say a learning problem is poly-learnable with C if for every polynomial ((n) there polynomial (n) such that for every there method in C(O(n)) that ensures error at most e (n) on all distributions in Pn. We slightly abuse notation and use C to denote the set of learning problems poly-learnable with C methods, so that, e.g. PAC, PACTM. SQ and SQTM. are the familiar classes of PAC and SQ (poly) learnable problems. For bSGD we also define bSGD(b(n)) p(z)). where b and p are only allowed depend on n via the specified (polynomially bounded, possibly constant) dependence, and not arbitrarily (the other parameters may grow as an arbitrary polynomial), and bSGD [b(n, (n. p)], where 1/p can grow as an arbitrary polynomial, but the choice of b as function of n and is constrained. With this notation, our results imply the following relationships between these classes of learning problems:
Corollary 1. For any (poly bounded, possible constant) dependence b(n, p), and for a piecewise linear activation function a, holds that
SQ (()) bSGD
((2) PAC
SQTM ((3) bS
((4) PACTM
Moreover, V b(n, p) < 18(8)). then inclusions (2) and (4) are tight, and if b(n, p) Z w wlog /p² then inclusions (1) and (3) are tight.
Corollary 2. For any (poly bounded, possibly constant) b(n), p(n), and a piecewise linear activation function a:
Vn bp < 1/8 then If bp² w (logn) then
bSGD PAC
and bSGD lb, -PACTM
bSGD C SQ C PAC and bSGD pl C SQTM & PACTM

---

In Corollaries 1 and 2, for the sake of simplicity, we focused on realizable learning problems, where the minimal loss inf LD, (f) = 0 for each Dn, E Pa.- However, we note that Theorems 1a to I are more general, as they preserve the performance of learning methods (up an additive 8) on all source distributions D. So, a result similar to Corollary could be stated for other forms of learning, such agnostic learning, weak learning etc.
Proof Outline. In order to prove Theorems Ia to 1d, first relate bSGD to intermediate model, mini-batch Statistical Queries (bSQ), which we introduce in Section 4. This is a variant of SQ-learning. but where statistical queries are answered based on bani-batches of samples. In the supplementary material we discuss how to simulate arbitrary statistical queries as gradient calculations for specifically crafted model, and thus establish how simulate (a large enough subclass of) bSQ methods using bSGD on some model fw. Furthermore, if the bSQ method has runtime TIME, then fu is also computable in time (TIME), and so can be implemented as a circuit, and thus a neural net of size poly (TIME). With this ability to simulate bSQ methods with bSGD in mind, what remains relate bSQ SQ and PAC, which is the subject of Section 4. Simulating an SQ method with bSQ method is fairly straightforward, as each statistical query on the population can be simulated by averaging a large enough number of empirical statistical queries (with the resulting precision being bounded by the precision of each of the empirical statistical queries). This can be done using any sample size, unrelated to the precision. More surprising, we show how to simulate any sample based (PAC) method using b5Q, provided the precision is fine enough relative to the mini-bate size. This is done using novel sample extraction procedure, which can extract single sample sampled from D using polynomial number of mini-batch statistical queries, and with precision linear in the mini-batch size (this required so that each element in the mini-batch has a noticeable effect on the gradients). To complete the picture, we show that with low precision, statistical queries on sample and on the population are indistinguishable (i.e. queries on an empirical mini-batch can be simulated by population queries, up to the required precision) and neither bSQ nor bSGD, can go beyond SQ (establishing Theorem Ic). Finally, simulating bSGD using PAC (Thcorem 1b) is straightforward, as bSGD is defined in terms of samples. The full proof's of Theorems la to 1d are presented in the supplementary material, with key components regarding bSQ developed in Section 4.
4 The Mini-Batch Statistical Query Model
En route to proving Theorems la to 1d, we introduce the model of mini- Statistical Queries (bSQ). In this model, similar to the standard Statistical Query (SQ) learning model, learning is performed through statistical queries. But in bSQ, these queries are answered based on an empirical average over mini-batch of b i.i.d. samples from the source distribution. That is, each query X' ;
+
[-1, 1]2 is answered with a response 1/ s.t.
U1
Σ
( Me.s)
ST.
where S. = (1,,,),1,,)); ~ D=
(6)
Note that we allow p-dimensional vector "queries", that is, p concurrent scalar queries are answered based on the same mini- batch St, drawn independently for each vector query.
Formally, a learning method A is said to be a bSQ(k, T, r, p.r) method, if it operates in k rounds where in round I, the method produces query d, X'' x ) - [-1, 1|2 for which it receives response v, satisfying (6) and finally outputs a predictor f X + IR. To be precise, each o, is a function of a random string R E 13" and past responses UI.... 1t-1, and the output is function of the random string R. and all responses. We say that A ensures error E on a source distribution D Elsup LD [f) < E, where the expectation is over R and the mini-batches S, ~ D6 and the sup is over all "valid" Un E [-1, 1]f satisfying (6). A learning method is said to be bSQ (ks, T, b, P, r, TIME) if in addition it can be implemented with computational time at most TIME
The first step of our simulation of PAC and SQ with bSGD is to simulate (a variant of) bsQ using bSGD. But beyond its use as an intermediate model in studying differentiable learning, 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 SQ model, and the demand that the error tolerance be polynomial, is that it possible to answer statistical queries about the population with tolerance T by calculating empirical averages on samples of size ((1/?)). In the bSQ model we make this explicit, and indeed answer
7

---

the queries using such samples. We do also allow additional arbitrary error beyond the sampling error, which we might think of as "precision". The bSQ model can thus be thought of as decomposing the SQ tolerance to a sampling error ((1/vb) and an additional arbitrary eπror т. If the arbitrary error 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 bSQ model can reveal us how well the standard SQ model captures what can be done when most of the error in answering statistical queries is due to the sampling error.
Our bSQ model is similar to the honest-SQ model studied by [20, 21], 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: Honest-SQ does not allow for an additional arbitrary error (i.e. it uses = 0 in our notation), but an independent mini-batch is used for each single-bit query 4; : X' x y + {0, 13. whereas bSQ allows for concurrent real-valued scalar queries on the same mini-batch. Yang showed that, with single bit query per mini- batch, and even if r = O. it is not possible to simulate arbitrary sample-based methods, and honest-SQ is strictly weaker than PAC. But we show that once multiple bits can be queried concurrently" 10 the situation is quite different.
In fact, we show that when the arbitrary error t is small relative the sample size b (and thus the sampling error), bSQ can actually go well beyond 5Q learning, and can fact simulate any sample-based basel method. That is, SQ does not capture learning using statistical queries answered (to within reasonable precision) using empirical averages:
Theorem 2a. (PAC to bSQ) For all 8 > O, for all b, and T < 1/(2)). and for all m, r, holds for k' = 10m(n + 1)/6, p' 1, = r le logg that
bSQ(k', "',,T,,,''' ,T,,,''rr) Is PAC(m,r).
Proof Sketch. The main ingredient is bSQ method -EPPREEETTAACTT (Algorithm 1) that extracts sample (z, y) ~ D by performing mini-batch statistical queries over independently sampled mini- batches. For ease of notation, let 2 == X x y identifying it with {0, 1] and denote z E as (z1,..., , (y, #,, ). drawing 2, from the conditional distribution {2/ 21.....-1hpp
operates by sampling the bits of one by one,
The main reason why < 1/26 enables this method to work is that for any query of the form & X' x - {0. 1). given any valid response v such that |/e- - Eg (xx, l> S r. is possible to exactly recover Eg (2x, y). by simply rounding each entry to the nearest integral multiple of 1/b. We show that SAMPLE- -XTLEECTTTAATT returns a sample drawn from D in O(n) expected number of queries. Thus, k' (mm/ / 5) queries suffice to recover m samples, with failure probability of at most d. Once we can simulate sample access, it is straightforward to simulate the entire PAC method. The details are deferred to the supplementary material.
To complement the Theorem, we also note that sample-based learning is always at least as powerful as bSQ, since bSQ is specified based on sample of size kb (see the supplementary material for complete proof):
Theorem 2b. (bSQ PAC) For all b, and k. p.r, r, it holds that
PAC(m' = kb, = Zo bSQ(k, T, b.
On the other hand, when the the mini-batch size b is large relative to the precision (i.e. the arbitrary error 7 is large relative to the sampling error 1/Vb), bsQ is no more powerful than standard SQ: Theorem 2c, (bSQ SQ) There exists a constant C 2 0 such that for all 8 > 0. for all k. T. b, p. r. such that bt > C' Log(kp/ ()), it holds that
SQ(K' = kp. = -,
T
Sa bSQ(k: T, b.
We do so with polynomially many binary-valued queries, i.e. (x) E {0. 1)", and p polynomial. It is also possible to encode this into single real-valued query with polynomially many bits precision. Once we use real-valued queries, if we do not limit the precision at all, i.e. 7 = 0, and do not worry about processing time, its easy to extract the entire minibatch S, using exponentially many bits of precision. Theorem 2a shows that polynomially many bits are sufficient for extracting sample and simulating PAC.
8

---

Algorithm 1 SAMPLE-EXTRACT bSQ algorithm (lines in green contain high-level idea of algorithm)
Input: Batch size b, Tolerance satisfying bt
1/2.
Output: Sample 2 ~ 'D
6 repeat
(empty prefix string)
# Let ~ Do be the independently sampled mini-batch
For := length(s)). issue bSQ + - {0, n given as
Øo(z) = ( - {}
not required when L = for all 1 S j - n +
(2(=) = (21..... and 2Øー = 1}
Let 1]=1]==t+2 be any valid answer, namely ||0 Es ( T for independently sampled S ~ D'. Round each vú to the nearest integral multiple of 1/b.
Since T 1/26, this ensures ;; = [=]),
Let: w bup, w1 + bu1, Wg k b(vg - v1).
# w / wo / w1 < number of samples in S that match prefix s / o 0/ s o.
if w 0 then
# Do nothing; repeat the loop with new sample. else if w = 1 then
(No sample matches prefix)
# Return (unique) sample in S that matches prefix 8. > (Exactly one sample matches)
return (s1,...,, Ze+1,
1n- 2,,
where žt+; {u, = 1/b} for all S S n 1
else
# Extend prefix s to reduce expected number of sample points with the prefix.
8 with probability wn/w
> (More than one sample matches prefix)
sol 1 with probability w1/w # Return 8 if fully specifies a sample point (æ, y). if length(s) n + 1: return s.
# Otherwise, repeat loop with the longer prefix (with new samples).
end if
until sample is returned
Proof Sketch. When b >> 1/72, the differences between the empirical and population averages become (with high probability) much smaller than the tolerance т, the population statistical query answers are valid responses to queries on the mini-batch, and we can thus simulate bSQ using SQ. do need make sure this holds uniformly for the p parallel scalar queries, and across all rounds-see the supplementary material for complete proof.
Finally, we show that with any mini-batch size, and enough rounds of querying, we can always simulate any SQ method using bSQ:
Theorem 2d. (SQ to bSQ) There exists a constant C 2 O such that for all 5 > O, for all b and all T,Y, holds that
bSQ k = [Cloog(//0)] b
1, +' b. -.,'='1''' -.r
Sa SQ(K,
Proof Sketch. To obtain an answer to 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 batches (i.c. over multiple rounds). This allows us to reduce the sampling error arbitrarily, and leaves us with only the arbitrary error r' (the arbitrary errors also get averaged, and since each element in the average is no larger than r'. the magnitude of this average is also no large than r'). See full proofs in the supplementary material.
Computationally tractable versions of Theorems 2a to 2d hold analogously relating bSQTM to SQTM//ACTM with only a polynomial increase runtime. We defer the formal statements to the supplementary material.

---

Proof Sketch of Theorems 1a and 1d. In order simulate PAC and SQ methods using bSGD, we first show how bSGD can simulate (a subelass of) bSQ (with corresponding mini-batch size and precision, and without any restriction on their relationship), and then rely in turn on Theorems 2a and 2d showing how bSQ can simulate PAC and SQ. We first show how a gradient computation can encode a statistical query, and use this, for bSQ method A, construct a differentiable model f. that is defined in terms of the queries performed by A and their dependence on previous responses, such that bSGD on f simulates A. This construction does not rely on being computationally tractable. We then note that if .A is computable in time TIME, i.e. all the queries are computable in time TIME, and the mapping from responses to queries are likewise computable in time TIME, then these mappings can be implemented as circuits of size poly(TIME)) enabling us to implement / as neural network, with these circuits as subnetworks. Finally, we discuss how bSGD can be simulated on neural network where all edges have trainable weights, using a modified version of the above construction, as well as a standalone alternate approach. Full details of these proof' are deferred to the supplementary material.
5 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 PAC and SQ, and thus (nearly) settling the question of "what can be learned using mini-batch SGD?". That single-sample SGD is able to simulate PAC learning was previously known, but we extended this result considerably, studied its limit, and showed that even outside this limit, bSGD can still always simulate SQ. A gap still remains, when the mini-bated size is between 1/p and log(n)/pr We furthermore showed that with sufficient (polynomial) precision, even full Gradient Descent on an empirical loss can simulate PAC learning.
where we do not know where bSGD sits between SQ and PAC.
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 SQ or PAC algorithm can be simulated, this requires 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 particular neural net can learn anything learnable by PAC or SQ, as this would imply that such network can learn any computationally tractable function," !! which is known to be impossible (subject mild cry 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 broad generality as we did here is probably too strong, as results in answers involving unrealistic initialization, and restriction, and thus no insight, to what makes learning problems learnable using deep learning. Can we define a class of neural networks, or initializations, which is broad enough 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. F.g., Malach al. [16) 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 additional regularity assumptions on the learning, Abbe al. [2] showed that imposing certain 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 different class of learnable problems, distinct from SQ and PAC, which is perhaps more related to deep learning in practice?
Acknowledgements
This work was done as part of the NSF-Simons Sponsored Collaboration on the Theoretical Foun- dations 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 1760032.
O'servv that for any tractable function f. there exists trivial learning algorithm that return f regardless of its input, which means that the class ( is PAC learnable.
10

---

References
[1] E. Abbe and C. Sandon. On the universality of deep learning. In Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL hash/e7
www.diiinnnnnnnsssooooeeoo cc/paper/202/ 1ar000Abbtraeee Abstract html.
[2] E. Abbe, Boix-Adserà, M. Brennan, G. Bresler, and D. M. Nagaraj. The staircase property: How hicrarchical structure can guide deep learning. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors. Advances in Neural Information Processing Systems, 2021. URL (jrumiid=f66FFcAAp
net/ nete
[3] 7. Allen-Zhu and Y. Li. What resnet learn efficiently, going beyond kernels? In Advances Neural Information Processing Systems 32: Annual Conference on Neural In- formation Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC. Canada, pages 9015-9025, 2019. URL https://proceedti becceeddnng.neuriippee wwtpppppee///////aeeeeeee 2019//hash (857468ca288009940998888222 Att. Abstract. html.
[4] Z. Allen-Zhu and Y. Li. Backward feature correction: How deep learning performs deep learning. arXiv, abs/2001.044 2020.
httttpp:/aaxiv.orr///// wwwp///0............. .04413.
[5] S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, USA. 1st edition, 2009. ISBN 0521424267.
[6] A. Blum and R. L. Rivest. Training 3-node neural network np-complete. Neural Networks, 5(1):117- 127, 1992. doi: (0066/58893--000055888880000
URI.httpa://aoi wtt.:/...rr.r.1.11//0000/222 (000000988000000333303000000 (05)
80010-3.
[7] Blum, A. Kalai, and H. Wasserman. Noise-tolerant learning, the parity problem, and statistical query model. Journal of the ACM 5004)550 2003.
[8] Daniely and F. Malach. Learning parities with neural networks. Advances Neural Information Processing Systems 33; Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URI.https: /ttpa///////o/oppaaa seuripa.cc/paper. hash/ 0aaaaa0000220099af555151f666eee2
Absttaasttt html.
[9] B. Ghorbani, S. Mei, T. Misiakiewicz, and Montanari. Linearized two-layers neural networks in high dimension. arXiv, 12s/19944.1299,, 2019. URL http:///txiiii wwwpor/g//aaaa/aeeeeeeeeeeegeeee 12191.
[10] B. Ghorbani, Mei, T. Misiakiewicz, and A. Montanari. When do neural networks outperform kernel methods? Advances in Neural Information Processing Systems, volume 33, pages 14820- 14830. Curran Associates, Inc., 2020. URL atttps:/ppooceddie nwurggs...uups.... cctppaper/22////iLL.. Paper Pafer.pdf.
[11] M. Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6): 983-1006, 1998.
[12] M. Kearns and L. Valiant. Cryptographic limitations on learning boolean formulae and finite automata. Journal of the ACM (JACM), 41(1):67-95, 1994.
[13] A. R. Klivans and A. A. Sherstov. Cryptographic hardness for learning intersections of halfspaces. Journal of Computer and System Sciences, 75(1):2-12, 2009.
[14] Y. Li. T. Ma. and H. R. Zhang. Leannig over- over- parametrized two-layer neural networks beyond NTK. Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria). volume 125 Proceedings of Machine Learning Research, pages proceedings... mlr, www.mmrrreeeeeeeee w.w..prees//v1///11011
PMLR, 2020. URL http://
html.
[15] E. Malach and S. Shalev-Shwartz. Computational separation between convolutional and fully-connected networks. arXiv preprint arXiv:2010.01369, 2020.
[16] E. Malach, P. Kamath, E. Abbe, and N. Srebro. Quantifying the benefit of using differentiable learning tangent kernels. arXiv, abs/2103.01210, 2021. URL https: //arxiv. org/abs// abs /21./211111........1.00010

---

[17] M.S. Nacson, N. Srebro, and Soudry. Stochastic gradient descent separahle data: Exact convergence with fixed learning rate. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, volume 89 of Proceedings of Machine Learning Research, pages 3051-3059, PMLR, 2019. URL http::/ mlr. www.mmt....p//.eeee wwwps/eesseeeeeee v89/ 189/nacson199. html.
[18] B. Neyshabur, R. Tomioka, and N. Srebro. In search of the real inductive bias: On the role of implicit regularization deep learning. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Workshop Track Proceedings, 2015. URL httt:://rr//i /ttp:v..v/voo////////// abs/1412 6614.
[19] D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro. The implicit bias of gradient descent separable data. J. Mach. Learn. Res., 19:70:1-70:57, 2018. URL http://jmlr org/ pappppp/eei//////// 18- 188. html.
[20] K. Yang. On learning correlated boolean functions using statistical queries. In Algorithmic Learn- ing Theory, 12th International Conference, ALT 2001, Washington, DC, USA, November 25-28, 2001, Proceedings, volume 2225 of Lecture Notes in Computer Science, pages 59-76. Springer, 2001. doi: 00.100773-540045583-33 URL htt.ha://bbi..rr////.0. 0tteg/1..10073--550 -000100000----45550000 055440-4558337...
[21] Yang. New lower bounds for statistical query Icamming. J. Comput. Syst. Sci. 70(4)485 509, 2005. doi: 10. jo.s 2004..000. URL https: /ttii//o.ooo/// org. wttg//..116//333 1. 2004 10.003.
[22] G. Yehudai and O. Shamir. On the power and limitations of random features for understand- ing neural networks. In Advances in Neural Information Processing Systems 32: Anmual
Conference Neural Information Processing Systems 2019, NeurIPS 2019. 8-14 December
2019, Vancouver, BC, Canada, pages 6594 6604, 2019. URL http::/papers http://ppaprrs...s...p nips cc/ ce/paper/ 8886- on- wwe-oo--tteeeeeee Sche-powe--eeee and limitations--oi - random- features- for for underssttngngn menttttanninnn-nnaaalaa neural seural-netsorks.
12


Reviews:
[{"review_id": "_pVo8Bf6K3F", "reviewer": "Reviewer_Pvqb", "summary": "The paper studies the power of differentiable learning. Previous work of Abbe and Sandon has showed that any learning algorithm can be simulated using SGD with on a network that with a certain structure and certain initialization; furthermore, batch gradient descent was shown to be less powerful (less powerful than the statistical query model).\n\nThe current paper aims at extending this analysis to the case of batch gradient descent. It is assumed that the samples are encoded with a few bits (so not really continuous). The main result of the paper is that for small enough batches (and good precision on the batch-gradient) we can still simulate any algorithm [while this is not the case for larger batches].", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "+ The authors use the term PAC learning but what they really mean is any algorithm that takes as input a training set and outputs a predictor. I don't think PAC is a good choice of terminology for this context. If I understand correctly the result suggest that any learning rule can be simulated.\n\n+ The authors assume that the input samples are represented by a few bits (so not continuous). This should be made more clear throughout the paper.\n\n+ An important part of the paper is to show that batch-statistical query model is as powerful as PAC. For this, the authors show how to extract samples using bSQ queries (but allowing multiple queries from the same batch). As part of Algorithm 1, we read \"perform the batch statistical queries ... on an independently sampled batch...\". This sounds like we generate different batches while we loop. However, I think all the queries in the loop should be performed on the same batch. Can the authors clarify if I am right? Otherwise I don't think the algorithm makes sense.\n\n+ In case I was right about the above point, it means that the in the bSQ model we are not only allowed to ask multiple queries about the same batch, but also we can ask these queries adaptively. Does this affect your proof that bSGD is at least as powerful that bSQ (in the certain regime of b and rho)?\n\n+ Although the authors talk about the work of Abbe and Sandon, they do not specifically say what is different in terms of the techniques used (I see that your results are new, but how is the proof techniques different?)\n\n+ The model is somewhat peculiar since we create a huge network that looks really nothing like usual networks but when you perform bSGD on it, it emulates the desired algorithm. \n\n-----------------------------------\nMy main questions has been answered by the authors in the rebuttal and I am increasing my score from 6 to 7.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't see any direct impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "ZhbvubqPO8v", "reviewer": "Reviewer_Gdae", "summary": "The authors characterize the power of minibatch SGD on differentiable models in comparison to SQ and \"PAC\" (learners with access to samples) models.  They build upon previous work of Abbe & Sandon who had shown that online SGD on neural networks (batch size = 1) is 'universal' in the sense that if some function can be learned using samples in poly time, it can be learned using online SGD over some appropriate neural network with all relevant parameters polynomial, and further that this does not hold with full-batch GD.  The authors sharpen these results to precisely characterize the relationship between batch size/gradient noise using SGD on differentiable models and the competitiveness of this with (a) the class of \"PAC\" algorithms and (b) the class of SQ algorithms.  To do so they introduce the notion of batch SQ algorithms and analyze when inclusions between the different classes are strict or are equalities. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nThe results presented are interesting: understanding separations between SGD on differentiable models on the one hand, and SQ algorithms on the other, is an important topic.  A handful of recent works over the past two years have demonstrated separations between SGD and full-batch GD, leading to the reasonable conjecture that there is some threshold of \"small batch\" such that sufficient randomness (small batch) can enable universality while too much averaging (large batch) can lead to equivalencies with SQ.  (The authors should comment on the recent work [1'] below which also touches on this topic.)  The authors' results are a timely work in the context of the previous work, and develops a novel resolution of these conjectures that are either implicit or explicit in previous work.\n\nThe work is mostly clear, but there are some clarifications that I did not understand on my first and second reads, and given the tight turnaround time for reviews did not have time to examine them more carefully (nor to carefully read proofs in appendix).\n\n(1) The authors' results are for binary input and binary output, suggesting classification problems, yet the loss considered is the squared loss.  Can they comment on this?  Is it possible to extend results to other loss functions?  Presumably not the 0-1 loss?\n\n(2) In Theorem 1, it appears the time T' needed to run SGD on NNs does not depend on the time \"TIME\" needed for a PAC learner, neither on rho -- only the size of the network depends on TIME and rho.  Is this correct? Can you give intuition for this?\n\n(3) The paper would be improved with a paragraph or two dedicated to clearly explaining the difference between rho approximate gradients, the typical tau used in SQ models, and the batch size used to estimate the gradients.  There are implicit equivalences given in e.g. Theorems 1 and 2, but having a paragraph where these settings are explicitly discussed would allow for readers more familiar with the standard concepts of batch size/concentration and the threshold in SQ algorithms to have a more intuitive grasp of this.\n\n\n_Minor points of clarification._\n\n(m1) Line 74 it is implied that \"computationally unbounded SQ\" is limited only by the number of statistical queries, but wouldn't it instead be bounded by the threshold tau / precision of the estimates?  \n\n(m2) in line 144 you mention 'r bits of randomness', in the context of X\\in {0,1}^n should r refer to n+1 then?  Why the usage of r here?\n\n(m3) line 323-324 \"as to what makes a learning problem are learnable\"\n\n[1'] The Connection Between Approximation, Depth Separation and Learnability in Neural Networks. Eran Malach, Gilad Yehudai, Shai Shale-Shwartz, Ohad Shamir\n\n\n** Post rebuttal **\n\nI've read the author response and heartily recommend acceptance. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, they adequately discussed limitations", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Ue7C8Ief_N8", "reviewer": "Reviewer_uqhv", "summary": "This work studies the power of stochastic gradient descent with mini-batch (bSGD). The authors prove that bSGD is as power as SQ learning for all the batch size. Furthermore, they prove that there is a threshold $b'$ relative to the precision, such that if the batch size is less than $b'$ then bSGD is as powerful as PAC learning. Previous work i.e., [1] have studied the case of SGD. The authors define a new model bSQ and prove its computational power and then prove that bSGD is as powerful as bSQ.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. Well-written and organized.\n2. This work establishes some fundamental results in PAC learning and SQ learning as well as on the power of bSGD algorithms.\n3. Introduces a new model bSQ which can be of independent interest.\n4. They show the computational time of the reduction is polynomial, i.e., it does not need a network of exponential size if the PAC learning algorithm has poly-time.\n\nOverall, I think this is a good paper and I recommend acceptance.\n\n#Other comments:\n- $\\mathcal{D}^b$ isn't defined anywhere or $S_t$ uniform over samples.\n- Line 232: \"Lemmas\" to \"theorems\"\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As a theory paper, it doesn't have any negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3-4"}, "extra_text": {}}, {"review_id": "OhMTrRjRZNq", "reviewer": "Reviewer_Sk3C", "summary": "The authors show that how the power of SGD on differential models or neural networks with arbitrary initialization is affected by the relationship between mini-batch size and gradient estimate precision. Abbe and Sandon had already shown that SGD with mini-batch size 1 can simulate any poly-time learning algorithm, but that gradient descent is not more powerful than statistical query learning algorithms. This work gives a finer-grained dichotomy: that when gradient estimates have enough precision relative to batch size, then any learning algorithm can be simulated with a polynomially related number of samples, but for moderately lower precision gradient descent is equivalent in power to statistical query learning algorithms. For poly-time learning/SQ algorithms, the equivalences are shown for poly-size neural networks rather than general differential models.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Recent results by Abbe and Sandon, showing that SGD with batch size 1 on neural networks can simulate any PAC learning algorithm, have made it formally even more obvious than before that theoretical work on the capabilities and limitations of deep learning methods ought not to apply to all possible architectures and initializations, since the freedom to choose architecture and initialization arbitrarily is evidently so powerful. Their results also showed an intriguing gap between SGD and GD, GD being only as powerful as the weaker SQ learning. This paper paints a fuller picture, showing how the capabilities of SGD (on arbitrary network/model architectures with arbitrary initialization, both unrealistic) vary between PAC and SQ learning as batch size and gradient precision change. It is presented in an organized, readable way. The paper has no *practical* significance, as the authors readily admit, but rather helps clarify the landscape of SGD on unrestricted models/initialization in a way that might be useful for showing for which design choices future lower bounds ought not to apply.\n\nI have not read the proofs carefully, nor have I read in depth the relevant works by Abbe and Sandon, so I am recommending acceptance with low confidence.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors provide an adequate discussion of the limitations of their work, especially in section 6, \"summary and discussion\".", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This presents interesting results regarding the power of mini-batch SGD. All reviewers and the AC like the paper and the AC recommend acceptance.
Decision: Accept (Spotlight)