Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: 1. Well-written and organized.
2. This work establishes some fundamental results in PAC learning and SQ learning as well as on the power of bSGD algorithms.
3. Introduces a new model bSQ which can be of independent interest.
4. 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.

Overall, I think this is a good paper and I recommend acceptance.

#Other comments:
- $\mathcal{D}^b$ isn't defined anywhere or $S_t$ uniform over samples.
- Line 232: "Lemmas" to "theorems"

limitations_and_societal_impact: As a theory paper, it doesn't have any negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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).

The 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].
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.

+ 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.

+ 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.

+ 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)?

+ 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?)

+ 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. 

-----------------------------------
My main questions has been answered by the authors in the rebuttal and I am increasing my score from 6 to 7.

limitations_and_societal_impact: I don't see any direct impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

I 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.
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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 

main_review: 
The 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.

The 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).

(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?

(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?

(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.


_Minor points of clarification._

(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?  

(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?

(m3) line 323-324 "as to what makes a learning problem are learnable"

[1'] The Connection Between Approximation, Depth Separation and Learnability in Neural Networks. Eran Malach, Gilad Yehudai, Shai Shale-Shwartz, Ohad Shamir


** Post rebuttal **

I've read the author response and heartily recommend acceptance. 

limitations_and_societal_impact: Yes, they adequately discussed limitations
review_title: null

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)