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- prw-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 loss function. Unless noted otherwise, we take the loss function to be the
e: R x ) - R20 squarc-loss laq (ū. = (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 (1:) 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, 1]P 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 {8/( 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-sid (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)" 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 > O. 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 ;; = Es(2
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=f66FFiAAp
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 becceeddnngsneuriippee wwtppppppe///////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--000055888800000
URI.httpa://aoi wtt.:/...rr.r.1.11//0000/222 (0000099888600003333 (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 nwwrggs...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..vvvoo////////// 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-540045583333 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.p nips cc/ ce/paper/ 8886- on- wwe-oo--tteeeeeee Sche-powe--eeee and limitations--oi - random- features- for for -nderrannnntn--n---nnnee menttttanninnn-nuaaalaa neural seural-netsorks.
12


Reviews:
[{"review_id": "s-wqnXsjev_", "reviewer": "Reviewer_wyJF", "summary": "The paper finds some parameters regimes (size of mini-batch, precision of gradient) where the mini-batch stochastic gradient is equivalent with SQ-learning or respectively with PAC learning.", "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": "The paper is well written and pleasing to read. It extends non-trivially the results of [1] when the batch size was $1$. I recommend accepting this paper.\n\nMinor remarks\n- The title is too broad compared to the authors' contributions.\n- Maybe some notions presented in section 2 should be introduced before to make section 1 more readable, e.g., PAC and SQ Learning. Also, in the introduction, the authors could forward reference what is explained later, e.g., Definition 1 as a quantitative definition of a framework \"simulating\" the other. This would help while reading to distinguish the wording that corresponds to a specific quantification from the wording that is looser.\n- Could you comment on the difficulty of obtaining this type of results for other versions of SGD, e.g., with momentum or variance-reduced techniques?\n- Line 38-39: \"All this justifies studying differentiable learning as a different and distinct paradigm from empirical risk minimization.\" The above explanation seems to rather mean that bSGD is a specific instance to ERM that adds implicit constraint. Hence, the characterization \"different and distinct\" seems a bit strange.\n- Line 25: \"and bSGD might not find that global minimizer\": it would seem even more appropriate to be less cautious and say that \"in general bSGD do not find that global minimizer\"?\n\nSome typos\n- Line 79: \"Our analysis relies on introduction of a variant\": the introduction.\n- Line 170: \"That is $C^\\prime \\leq C + \\delta$ means that $C^\\prime$ os at least as powerful as C\": this is the interpretation provided it is true for all $\\delta>0$?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "6hZ2F_lCpQ8", "reviewer": "Reviewer_1153", "summary": "Summary:\nThe main question in the paper is the interplay of what we can learn by mini-batch SGD in the Differentiable Learning paradigm vs. PAC and SQ learning models.\n(This extends a prior work that considered this question with mini-batch of size 1, by Abbe and Sandon - Neurips2020).\nThe parameters that play a role are the mini-batch size and precision of gradient calculations.\nThe authors gave (almost) a full characterization with respect to these parameters. \nAs a byproduct, the authors introduced a variant of SQ learning which seems interesting in other contexts.", "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": "Significance:\nThe paper discusses some fundamental questions in Learning Theory that are of high interest.\nThe results are significant and interesting.\n\nOriginality: \nThe main question is based on the results of Abbe and Sandon (Neurips2020). This paper naturally generalizes their question and their methods seem to be different and novel.\n\nClarity and relation to prior work:\nThe paper is very clear and easy to follow. \nThe authors honestly discuss what are the implications of their results.\nAlso, the literature review is thorough.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "5gJ8obgsAi5", "reviewer": "Reviewer_Gr4i", "summary": "In this work, the authors study the strength of mini-batch stochastic gradient descent (bSGD in their notation), where strength refers to the ability to solve expected loss minimization problems up to a certain precision level, uniform over the choice of underlying data distribution. More concretely, the authors consider a supervised learning task under the squared loss, with bounded inputs and outputs, as well as a differentiable prediction model. Regarding the \"implementation\" of SGD, they consider using not the raw mini-batch average, but rather a clipped version.\n\nThe characteristic feature of this work is that provides new insights into the strength of bSGD under a wide range of mini-batch sizes, characterizing bSGD in terms of the strength relative to PAC-learners and statistical query algorithms. From previous recent work in the literature, SGD using a single example was already known to be at least as strong as PAC (the class of PAC learners), but the authors have shown how this holds as the mini-batch size grows larger than one, and in particular show how the precision level (the error due to clipping) plays an important role. If the precision is too low (i.e., a large value of $\\rho$ in their notation), then in order to bSGD to be at least as strong as PAC, the mini-batch size cannot be too large. These rough statements are made quite precise in the main results of this paper. Furthermore, they explore how computational tractability plays a role in these relative strength assessments.\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": "Overall, I found the paper straightforward to follow, well-written, with lucid descriptions of the main results and discussion of the key take-aways, as well as remaining limitations in our knowledge. I was not familiar with the key related works of this paper prior to reading it, and thus it is difficult for me to comment objectively on the novelty and/or technical merit of the contributions made here, but to the best of my understanding, the results appear to fill a clear gap in the existing literature, and I believe warrants acceptance at NeurIPS.\n\n**Update:**\nI thank the authors for their response. Having read through the other reviews as well as the authors' response, my overall opinion remains unchanged.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The main limitations are of a technical nature an are implicit in the above comments. For example, a lot of important properties of real-world noisy gradients are essentially abstracted out of the analysis by using bounded data. That said, considering the state of the art before the authors set upon this work, these limitations seem perfectly reasonable given the progress made.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the power of learning via mini-batch stochastic gradient descent and shows that SGD can simulate learning with statistical queries.  The paper is well written, clear, and has novel results.  There are some limitations to applications to the real world, but this remains a solid work worthy of acceptance.
Decision: Accept (Spotlight)