SGD Through the Lens of Kolmogorov Complexity
Authors: Gregory Schwartzman
Venue: Submitted to ICLR 2023 (2023)

Abstract: We initiate a thorough study of the dynamics of stochastic gradient descent (SGD) under minimal assumptions using the tools of entropy compression. Specifically, we characterize a quantity of interest which we refer to as the \emph{accuracy discrepancy}. Roughly speaking, this measures the average discrepancy between the model accuracy on batches and large subsets of the entire dataset. We show that if this quantity is sufficiently large, then SGD finds a model which achieves perfect accuracy on the data in $O(1)$ epochs. On the contrary, if the model cannot perfectly fit the data, this quantity must remain below a \emph{global} threshold, which only depends on the size of the dataset and batch.

We use the above framework to lower bound the amount of randomness required to allow (non stochastic) gradient descent to escape from local minimas using perturbations. We show that even if the model is \emph{extremely overparameterized}, at least a linear (in the size of the dataset) number of random bits are required to guarantee that GD escapes local minimas in polynomial time.

Under review as a conference paper at ICLR 2023
SGD THROUGH THE LENS OF KOLMOGOROV COM- PLEXITY
Anonymous authors Paper under double-blind review
ABSTRACT
We initiate thorough study of the dynamics of stochastic gradient descent (SGD) under minimal assumptions using the tools of entropy compression. Specifically, we characterize a quantity of interest which we refer to as the accuracy discrepancy. Roughly speaking, this measures the average discrepancy between the model accuracy on batches and large subsets of the entire dataset. We show that if this quantity is sufficiently large, then SGD finds model which achieves perfect accuracy on the data in ((1) epochs. On the contrary, if the model cannot perfectly fit the data, this quantity must remain below global threshold, which only depends on the size of the dataset and batch.
We use the above framework to lower bound the amount of randomness required allow (non-stochastic) gradient descent to escape from local minima using perturbations. We show that even if the model is extremely overparameterized, least a linear (in the size of the dataset) number of random bits are required guarantee that GD escapes local minima in subexponential time.
INTRODUCTION
Stochastic gradient descent (SGD) is at the heart of modern machine learning. However, we are still lacking a theoretical framework that explains its performance for general, non-convex functions. Cur- rent results make significant assumptions regarding the model. Global convergence guarantees only hold under specific architectures, activation units, and when models are extremely overparameterized (Du et al. 2019 Allen-Zhu et al. 2019 Zou al., 2018 Zou and Gu 2019). In this paper, take step back and explore what can be said about SGD under the most minimal assumptions. We only assume that the loss function is differentiable and L-smooth, the learning rate is sufficiently small and that models are initialized randomly. Clearly, we cannot prove general convergence to global minimum under these assumptions. However, we can try and understand the dynamics of SGD what types of execution patterns can and cannot happen.
Motivating example: Suppose hypothetically, that for every batch, the accuracy of the model after the Gradient Descent (GD) step on the batch is 100%. However, its accuracy on the set of previously seen batches (including the current batch) remains at 80%. Can this process go on forever? At first glance, this might seem like possible scenario. However, we show that this cannot be the case. That is, if the above scenario repeats sufficiently often the model must eventually achieve 100% accuracy on the entire dataset.
To show the above, we identify a quantity of interest which we call the accuracy discrepancy (formally defined in Section Roughly speaking, this is how much the model accuracy batch differs from the model accuracy on all previous batches in the epoch. We show that when this quantity (averaged over epochs) is higher than certain threshold, we can guarantee that SGD convergence to 100% accuracy on the dataset within O(1) epochs w.h.f We note that this threshold is global, that is, only depends on the size of the dataset and the size of the batch. In doing so, provide sufficient condition for SGD convergence.
The above result is especially interesting when applied weak models that cannot achieve perfect accuracy on the data. Imagine a dataset of size n with random labels, a model with 0.99 parameters, and batch of size log n. The above implies that the accuracy discrepancy must eventually go below
With high probability means a probability of least 1/n, where n the size of the datasct.

---

Under review as a conference paper at ICLR 2023
the global threshold. In other words, the model cannot consistently make significant progress on batches. This is surprising because even though the model is underparameterized with respect to the entire dataset, it is extremely overparameterized with respect to the batch. We verify this observation experimentally (Appendix (B). This holds for a single GD step, but what if we were to allow many GD steps per batch, would this mean that we still cannot make significant progress the batch? This leads us to consider the role of randomness in (non-stochastic) gradient descent.
It is well known that overparameterized models trained using SGD can perfectly fit datasets with ran- dom labels (Zhang et al. 2017). It is also known that when models are sufficiently overparameterized (and wide) GD with random initialization convergences to a near global minimum (Du et al., 2019). This leads to an interesting question: how much randomness does GD require to escape local minima efficiently (in polynomial time)? is obvious that without randomness we could initialize GD next to local minimum, and it will never escape it. However, what about the case where we are provided an adversarial input and we can perturb that input (for example, by adding a random vector to it), how many bits of randomness are required to guarantee that after the perturbation GD achieves good accuracy on the input in polynomial time?
In Section 4 we show that if the amount of randomness is sublinear in the size of the dataset, then for any differentiable and L-smooth model class (e.g.. a neural network architecture), there are datasets that require an exponential running time to achieve any non-trivial accuracy (i.c., better than 1/2 + o(1) for a two-class classification task), even if the model is extremely overparameterized. This result highlights the importance of randomness for the convergence of gradient methods. Specifically, it provides an indication of why SGD converges in certain situations and GD does not. We hope this result opens the door the design of randomness in other versions of GD.
Outline of our techniques We consider batch SGD, where the dataset is shuffled once at the beginning of each epoch and then divided into batches. We do not deal with the generalization abilities of the model. Thus, the dataset is always the training set. In each epoch, the algorithm goes over the batches one by one, and performs gradient descent update the model. This is the "vanilla" version of SGD, without any acceleration or regularization (for formal definition, see Section 2} For the sake of analysis, we add termination condition after every GD step: if the accuracy on the entire dataset is 100% we terminate. Thus, in our case, termination implies 100% accuracy.
To achieve our results, we make use of entropy compression, first considered by Moser and Tardos (2010) to prove constructive version of the Lovász local lemma. Roughly speaking, the entropy compression argument allows one to bound the running time of a randomized algorithnrPby leveraging the fact that random string of bits (the randomness used by the algorithm) is computationally incompressible (has high Kolmogoroy complexity) w.h.p. If one can show that throughout the execution of the algorithm, it (implicitly) compresses the randomness it uses, then one can bound the number of iterations the algorithm may execute without terminating. To show that the algorithm has such a property, one would usually consider the algorithm after executing i iterations, and would try to show that just by looking at an "execution log" of the algorithm and some set of "hints", whose size together is considerably smaller than the number of random bits used by the algorithm, is possible to reconstruct all of the random bits used by the algorithm.
We apply this approach SGD with an added termination condition when the accuracy over the entire dataset is 100%. Thus, termination in our case guarantees perfect accuracy. The randomness we compress is the bits required to represent the random permutation of the data at every epoch. So indeed the longer SGD executes, the more random bits are generated. We show that under our assumptions is possible to reconstruct these bits efficiently starting from the dataset X and the model after executing epochs. The first step in allowing us to reconstruct the random bits of the permutation in each epoch is to show that under the L-smoothness assumption and a sufficiently small step size, SGD is reversible. That is, if we given a model W++1 and a batch B, such that W4+1 results from taking gradient step with model W, where the loss is calculated with respect to B, then we can uniquely retrieve W. using only B, and W,-1- This means that if we efficiently encode the batches used in every epoch (i.e., using less bits than encoding the entire permutation of the data), we can also retrieve all intermediate models in that epoch (at no additional cost). We prove this claim in Section 2
We require that the number of the random bits used is proportional to the execution time of the algorithm. That is, the algorithm flips coins for every iteration of a loop, rather than just constant number at the beginning of the exccution.
2

---

Under review as a conference paper at ICLR 2023
The crux of this paper is to show that when the accuracy discrepancy is high for certain epoch, the batches can indeed be compressed. To exemplify our techniques let us consider the scenario where, in every epoch. just after single GD step on a batch we consistently achieve perfect accuracy on the batch. Let us consider some epoch of our execution, assume we have access to X, and let Wj be the model at the end of the epoch. If the algorithm did not terminate, then W has accuracy at most on the entire dataset (assume for simplicity that is a constant). Our goal is to retrieve the last batch of the epoch, B3 C X (without knowing the permutation of the data for the epoch). naive approach would be to simply encode the indices in X of the elements in the batch. However, we can use W to achieve a more efficient encoding. Specifically, we know that W achieves 1.0 accuracy on By but only 1 accuracy on X. Thus it is sufficient to encode the elements of B, using smaller subset of X (the elements classified correctly by f. which has size at most (1 - +) [ This allows us to significantly compress By. Next, we can use By and Wy together with the reversibility of SGD to retrieve -- We can now repeat the above argument to compress B and so on, until we are able to reconstruct all of the random bits used to generate the permutation of X in the epoch. This will result in a linear reduction in the number of bits required for the encoding.
In our analysis, we show generalized version of the scenario above. We show that high accuracy discrepancy implies that entropy compression occurs. For our second result, we consider a modified SGD algorithm that instead of performing a single GD step per batch, first perturbs the batch with limited amount of randomness and then performs GD until a desired accuracy on the batch is reached. We assume towards contradiction that GD can always reach the desired accuracy on the batch in subexponential time. This forces the accuracy discrepancy to be high, which guarantees that we always find a model with good accuracy. Applying this reasoning to models of sublinear size and data with random labels we arrive at a contradiction, as such models cannot achieve good accuracy on the data. This implies that when we limit the amount of randomness GD can use for perturbations, there must exist instances where GD requires exponential running time to achieve good accuracy.
Related work There has been a long line of research proving convergence bounds for SGD under various simplifying assumptions such as: linear networks (Arora et al. 2019| 2018)), shallow networks (Sffran and Shamir 2018; Du and Lee 2018 Oymak and Soltanolkotabi 2019), etc. However, the most general results are the ones dealing with deep, overparameterized networks (Du et al. 2019 Allen-Zhu et al. 2019 Zou et al.) 2018 Zou and Gu 2019). All of these works make use of NTK (Neural Tangent Kernel (Jacot al. 2018) and show global convergence guarantees for SGD when the hidden layers have width at least poly(n, L) where n is the size of the dataset and L is the depth of the network. We note that the exponents of the polynomials
quite large.
A recent line of work by ZZhag et al. (2022) notes that in many real world scenarios models do not converge to stationary points. They instead take different approach which, similar us, studies the dynamics of neural networks. They show that under certain assumptions (e.g., considering a fully connected architecture with sub-differentiable and coordinate-wist Lipschitz activations and weights laying on a compact set) the change in training loss gradually converges to O, even if the full gradient norms do not vanish.
In (Du et al. (017)) it was shown that GD can take exponential time to escape saddle points, even under random initialization. They provide a highly engineered instance, while our results hold for many model classes of interest. JTnn et al.] (2017) show that adding perturbations during the executions of GD guarantees that it escapes saddle points. This is done by occasionally perturbing the parameters within a ball of radius where r depends on the properties of the function to be optimized. Therefore, a single perturbation must require an amount of randomness linear in the number of parameters.
2 PRELIMINARIES
We consider the following optimization problem. We are given an input (dataset) of size n. Let us denote X = {ar:) ) (Our inputs contain both data and labels, do not need distinguish them for this work). We also associate every x E X with a unique id of [log n.] bits. We often consider batches of the input B X. The size of the batch is denoted by (all batches have the same size). We have some model whose parameters are denoted by W E Rdd where d is the model dimension. We aim to optimize a goal function of the following type: f(W)= 1 Exex (W"), where the functions fa : d + R are completely determined by x E X. We also define for every set A C X: fW) TAi EzeA fa (W). Note that fx =
n
3

---

Under review as a conference paper at ICLR 2023
We denote by acc(W, A) R& 2 [0. 1] the aceuracy of model W the set A C X (where we use W to classify elements from X). Note that for E X holds that acc(W, value indicating whether is classified correctly not. We require that every fz is differentiable and T-smooth: wW,, 22 E R || fz (W,) - Vf2(W)) S L|IW; W2ll This implies that every fA also differentiable and T-smooth. To this consider the following:
binary
1 [
1
(V ff
(W))
Σ fla
A
SEA
VLL())
V.L(W)) S
(> - Vaa(W2)) & LIJW, - W2ll
A
PEA
PEA
We state another useful property of fa:
Lemma 2.1. Let W1, W2 Rd and < 1/L. For any A S X, if holds that W1 aV.a(WW) W/ a (W22) then W1 W2.
Proof. Rearranging the terms we get that W -,W aV -V/a(W)-- Now ust consider the norm of both sides: ||W WW-WWll Unless W1 = W2. the final strict inequality holds which leads to a contradiction.
Va
W || W2l
The above means that for a sufficiently small gradient step, the gradient descent process is reversible. That is, the batch is fixed. We use the notion of reversibility throughout this paper. However, in practice we only have finite precision, thus instead of R work with the finite set IF R. Furthermore, due numerical stability issues, we do not have access to exact gradients, but only to approximate values fA. For the rest of this paper, assume these values are L-smooth on all elements in Fd That is,
always recover the previous model parameters given the current ones, assuming that
WW,, W2 X, - (W,)) < LI[W; W2ll
This immediately implies that Lemma 2.1 holds even when precision is limited. Let us state the following theorem:
Theorem 2.2. Let W1, W We e Id c Rd, A,, A S X and a < L/L. if holds that
W. = W. V A:-, (W;-1), then given A1, A2, A and We we can retrieve W,.
Proof. Given Wt iterate over all W Fd until find W such that W W a A:-1 (W). Using Lemma 2.1 there is only single element such that this equality holds, and thus W = W We repeat this process until we retrieve W..
SGD
We analyze the classic SGD algorithm presented Algorithm | One difference to note in our algorithm, compared to the standard implementation, is the termination condition when the accuracy on dataset is 100%. practice the termination condition is not used, however, we only use to prove that at some point in time the accuracy of the model is 100%.
Algorithm 1: SGD
i < /// epoch counter
W1,1 is an initial model while True do
Take random permutation of X, divided into batches (Bi pm/ jrom to n/b do if (acc(W, ig. X) then Return Wa W f Wi, - fB. (Wes) W1, +- W,-1.n/0+1
4

---

Under review as a conference paper at ICLR 2023
Kolmogorov complexity The Kolmogorov complexity of a string {0, 1)". denoted by K (x). defined as the size the smallest prefix Turing machine which outputs this string. We note that this definition depends on which encoding of Turing machines use. However, this will only change the Kolmogorov complexity by a constant factor (Li and Vitányi 2019).
can show that
We also use the notion of conditional Kolmogorov complexity, denoted by K(x: y). This is the length of the shortest prefix Turing machine which gets y as an auxiliary input and prints æ. Note that count towards the size of the machine which outputs æ. So can be the case that [x]] < ly] but it holds that K (a y) < K (æ). We can also consider the Kolmogorov complexity of functions. Let g: {0, 1) + {0, 1} then K (g) is the size of the smallest Turing machine which computes the function g.
the length of y does
The following properties Kolmogorov complexity will be of use. Let x, y, be three strings:
* Extra information: (( y. =) x K( =) 0(1 - K(x,y 2) + 0(1)
Subadditivity: K(xy 2) - K (x 2. + K 2) + s K(x 2) + K(y +)()
Random strings have the following useful property (Li and Vitányi 2019::
Theorem 2.3. For an n bit string x chosen uniformly at random, and some string independent of (i.e., y fixed before x is chosen) and any e E N it holds that Pr[K (x v) 2 n c| 2 1/22.
Our proofs make extensive use of binary entropy and KL-divergence. In what follows we define these concepts and provide some useful properties.
Entropy and KL-divergence
Entropy: For p E [0. 1] we denote by h(p) -p logg (1 - p) log(1 p) the entropy of p. Note that ((0 h(1) O.
KL-divergence: For p.q E (0,1) let (KI(p II q) p plog & (1 p) log 1 be the Kullback Leibler divergence (Kl-ddivergence) between two Bernoulli distributions with parameters p.q. We also extend the above for the case where p.p {0. 1 as follows: Dx q) D || q) 0, DEL (p 1) = log(1/p), DxI ip || 0) = log(1/(1- p)). This is just notation that agrees with Lemma 2.4 We also state the following result of Pinsker's inequality applied to Bernoulli random
variables: (K
2 2(p 2)
Let state some useful bounds the Kolmogorov complexity of sets. A more detailed explanation regarding the Kolmogorov complexity of sets and permutations together with the proof to the lemma below appears in Appendix A
Representing sets
Lemma 2.4. Let A C B, [B| = m. |A| = mym, and let B + {o, For any set Y S B let YYl
Y = [x 2 Y, (x) 1} Y. Y Y, and Ky
It holds that TYT
K(A B) s <my(lo((//)) - (KL ll (a)) + (logm)
ACCURACY DISCREPANCY
Plu = aee(Wi
AU X,
K1 = aco(W. xe--
2 ace Wey X XX
Wi:
Wi
Ba
B,2
B23
Bya
R
B
X---1
XXX
Figure 1: A visual summary of our notations.
First, let us define some useful notation (Wa,,, Br,, are formally defined in Algorithm D:
Ary acc(W i. X). This is the accuracy of the model epoch on the entire dataset X, before performing the GD step on batch j.
Pi.j = acc(W.,5 B1j-)). This is the accuracy of the model on the (j - 1)-th batch in the i-th
epoch after performing the GD step the batch.
5

---

Under review as a conference paper at ICLR 2023
X1,, =Ui=1 Bi, (note that Vi, X1, 0, X in// X). This is the set of elements in the first batches of epoch i. Let us also denote nij [Xx,] = jb (Note that Vj, b1, f2, [X = =Xxig.l thus i need not appear in the subseript).
XX {x,,-1), where X1 is the accuracy of the model on the set of all previously seen batch elements, after performing the GD step on the (j - 1) batch and X", is the accuracy of the same model, on all remaining elements (j-th batch onward). To avoid computing the accuracy on empty sets, M.₃ is defined for j E [2.n/b + 1] and X" is defined for j E [1, n/b).
Xr,- acc(W Xi,- MM
Pi.j (xI Il (pg)) is the accuracy discrepancy for the j-th batch in iteration i and Pi Enst Pi,j is the accuracy discrepancy at iteration i.
In our analysis, we consider / epochs of the SGD algorithm. Our goal for this section is to derive a connection between E/= and t.
Our goal is to use the entropy compression argument to show that if E Ps is sufficiently large we can bound t. Let us start by formally defining the random bits which the algorithm uses. Let be the string of random bits representing the random permutation of X at epoch i. As we consider t epochs, let r = ...
Bounding t:
Note that the number of bits required to represent arbitrary permutation of [n]] is given by: [log(nl)] = n log n - n log + Olog n) = n log(n/e) + Olog
where in the above we used Stirling's approximation. Thus, it holds that |r| = t(n log(n/e) + (log r.) and according to Theorem 2.3 with probability at least 1 - 1/n² it holds that K(r)= 2 tn log(n/e) O(log n).
In the following lemma we show how to use the model at every iteration to efficiently reconstruct the batch at that iteration, where the efficiency of reconstruction is expressed via pi. Lemma 3.1. holds w.h.p that Vi e [t] that: K(r; W++111 X) S n e bp: + 3 -0OOlog n)
n
Proof. Recall that BLg is the j-th batch in the i-th epoch, and let Pi,j be permutation of B such that the order of the elements Br, under Pt, the same as under r3. Note that given X, if we know the partition into batches and all permutations, we can reconstruct rú. According to Theorem 2.2. given Wiy and B1 we can compute W Let us denote by Y the encoding of this procedure. To implement Y we need to iterate over all possible vectors Fdd and over batch elements to compute the gradients. To express this program we require auxiliary variables of size at most Ollog min (d, b)) = ( n). Thus it holds that K(Y) = O(logn). Let us abbreviate B Br,,,.., .... Brj as (Br,)) We write the following.
K(r; X, W1+1,1) S (r;,, Y X, W(+11) (11 S K(ri) X, W.L11, K(Y X, 11111) + O(logn) n) + K(BBi,, P1 X, W:+1,,Y
< 0(logn) n) + K((B,,,) n/bb
X, WAL.I, Y) + (((P,,) w0/6 X, WiHL,,
n/b
< Ologn) K((B,,)) ///b X, 41.1 W Y)+ Σ K(P.))
Let us bound (((B,,) k=1 n/b
X, W1+111, 1.,,Y Y) by repeatedly using the subadditivity and extra informa- tion properties of Kolmogorov complexity.
K((Br,)RH X, W,H,)) S K(Ba,n/b X, Wo+11) + K((BA) |X,Y, W BEn()) + 0(1)
< K(Binn/b X, Wx+11) + K((B,,) / X,Y, W Wn/bbr Bimn/)) + O())
K K(Ban// X, Ws+1,) + K(B X, Win//b B
+ K((Br.)) a/b-2
Y, Win/b-1, Bin Binn/b1) + 0(1)
n/bb
n/b
S.. 50. mh + Σ
K(Bi5 X, West,, (Bix)) S 00())
+ Σ j=1
K K(Bis Xis, Wast))

---

Under review as a conference paper at ICLR 2023
where in the transitions used the fact that given Wa, Br,--1 and Y we can retrieve W; i That is, we can always bound (... Y, W. B........) by ((.. Y. W. + O(1).
To encode the order Pt, inside each batch, blog(6/e) + (log bits sufficient. Finally get that: (rrs X, W1+111 - ( + / E ((B,,, Xt.j, W W2,+1) + blog(b/e) + Ollog b)].
Let us now bound j x
W Knowing jjj we know that B - x Thus
we need use W compress B Applying Lemma 2.4 with parameters A = B,
1 b/ng-1, = Pigj KB = Xa. and g(x) = acc| W Wi)jz).. x). We get the following:
Wi,) _ bllog( e. - X 5
Pt.j) + Ollg nj-1)
b
Adding blo(bb/)) + Ollog b) to the above, we get the following bound on every element in the sum: bllog( e. n Pt.)) + (b/e) + Ollog b) + Ollogny-1 S log n bps.j O(log ny-1)
b
Note that the most important term in the sum is -ps..- That is, the more the accuracy of Wt, on the batch, B differs from the accuracy of Wi, on the set of elements containing the batch, Xis-1, can represent the batch more efficiently. Let now bound the sum: Σドー 1//2++ fij1 bpi.j
Olog r)--)]] Let us first bound the sum over b blog n3-1:
n/b+1
n/hb
n/b
blog R1--1 = Σ blog.jb jbb = Σ Σ
6log b + log.j)
2
==1
==1
log b b log(n/b)) log + n log
O(log n) = n log
+ O(log n)
b.c
Finally, we can write that:
n/b+1
K(r: X, W.+11) s o(+)+ +
Σ
boo Boog -bpay + O(log n)] $ n log
bp:
n
O(log n)
b
L
Using the above we know that when the value pæ is sufficiently high, the random permutation of the epoch can be compressed. We use the fact that random strings are incompressible to bound - Pt.
Theorem 3.2. If the algorithm does not terminate by the t-th iteration, then it holds w.h.p that Vt, Ei S 0("h
log
82
Proof. Using arguments similar to Lemma 3.1
we can show that K Krr; Wi,1 |X) S K(W++1.1
O(t)+ ((t)+E= K(rx) X, 1&111) (formally proved in Lemma A.3) Combining this with Lemma 3.1 we get that ((r, W1,1 X) & K(W, (W,++1.1 + ([<(og(nn/e) + x Ologg) -bp + O(logn))
b
Our proof implies that we can reconstruct not only r, but also Wi, using X, W, W1+11-- Due to the incompressibilityy of random strings, get that w.h.p K ((r, W1.1 X) 2 d+ log (ng(ne)) -
- Olog n).
Combining the lower and upper bound for K(r, WI.1 X) we can get the following inequality:
+ in log(n/e) O(logn) n) s f/m(log(nn/)) n O
+ (llog))]
bp:
n (logn) n)
Ologn)
Ollog n) n
no n 62
62
bt
B(nb))
Let ((n,b) b) be the exact value the asymptotic expression in Inequality 1 Theorem 3.2 says that as long SGD does not terminate the average accuracy discrepeancy cannot be too high. Using the contra-positive we get the following useful corollary (proof is deferred to Appendix A.3
Corollary 3.3. Vf, & Σ P; > 3(n, + 7, for 7 = 12(b llonn, n). then w.h.p SGD terminates within O(1) epochs.
7

---

Under review as a conference paper at ICLR 2023
The case for weak models Using the above can also derive some interesting negative results when the model is not expressive enough to get perfect accuracy on the data. It must be the case that the average accuracy discrepancy tends below (n, b) over time. We verify this experimentally the MNIST dataset (Appendix [B), showing that the average accuracy indeed drops over time when the model is weak compared to the dataset. We also confirm that the dependence of the threshold in b is indeed inversely quadratic.
4 THE ROLE OF RANDOMNESS IN GD INITIALIZATION
Our goal for this section is to show that when the amount of randomness in the perturbation is too small, for any model architecture which is differentiable and L-smooth there are imputs for which Algorithm requires exponential time to terminate, even for extremely overparameterized models.
Perturbation families Let us consider a family of 2 functions indexed by length real valued vectors V f+b=) zERr. Recall that throughout this paper assume finite precision, thus every can be represented using OEE) bits. We say that v is reversible perturbation family if it holds that V2 E IR 4/ is one-to-one. We often use the notation WW(W), which means pick E B uniformly at random, and apply (W"). We often refer to V simply perturbation.
We note that the above captures a wide range of natural perturbations. For example 1 (W) = W + W where W_ [i] zli mod f). Clearly v. (W) is reversible.
Gradient descent
The GD algorithm we analyze is formally given in Algorithm 2
Algorithm 2: GD(W,, 8) Input: initial model W, dataset Y, desired accuracy
i == ",T'= 1,T'= + poly(d)
W = =Ve(W)
while (o,( Y) < and < T do
W + W a fr (W)
iiit1
Return W
Let us denote by m the number of elements in Y. We make the following 2 assumptions for the rest of this section: (1) l = o(m). (2) There exists T =(2*) + poly(d) and a perturbation family V such that for every input W, Y within T iterations GD terminates and returns a solution that has at least ó accuracy on Y with constant probability. We show that the above two assumptions cannot hold together. That is, if the amount randomness is sublinear in m, there must be instances with exponential running time, even when d >
To show the above, we define a variant of SGD, which uses GD as a sub procedure (Algorithm 3) Assume that our data set is binary classification task (it is easy to generalize results any number of classes), and that elements in are assigned random labels. Furthermore, let us assume that d o(n), e.g., d 0.99 It holds that w.h.p cannot train model with parameters that achieves any accuracy better than 1/2 + o(1) on X (Lemma A.4p. Let us take to be small constant, We show that if assumptions and 2 hold, then Algorithm must terminate and return model with 1/2 + (11) accuracy on X, leading to a contradiction. Our analysis follows the same line as the previous section, and uses the same notation.
Reversibility First, we must show that Algorithm 3 is still reversible. Note that we can take the same approach as before, where the only difference is that in order to get Wi, from Wt,441 we must get all the intermediate values from the call to GD. As the GD steps applied to the same batch, this amounts to applying Lemma 2.T several times instead of once per iteration. More specifically, we must encode for every batch number Tıj = o(2") + poly(d) o(2") + poly(n) (recall that d = o(n)) and apply Lemma 2.1 2. times.
This results in r (: If know z, V then can retrieve vh and efficiently retrieve W., using only d) = Ologn) additional bits (by iterating over all values in Fd). Therefore, in every
8

---

Under review as a conference paper at ICLR 2023
Algorithm 3: SGD"
i < // epoch counter
Wi.1 is an initial model
while True do
Take random permutation of X, divided into batches {Br, nn/b
1-
for j from to n/b do if acc(W L.j. X) 2 1/2(1 e) then Return Wi W Woy-1 t GD(,,,, B, 2(122))
i W + W11.m/6t11
iteration have the following additional terms: log Ollog n)) + over n/b iterations we get o(n) per epoch. We state the following Lemma analogous to Lemma 3.1 Lemma 4.1. For Algorithum 3 it holds w.h.p that Vi E [t] that: ((;,) Wi+1,1, X, Me log 2
+ (log n). Summing
bp; + ((n, b) + o(n).
We show that under our assumptions, Algorithm 3 must terminate, leading to a contradiction.
Lemma 4.2. Algorithm 3 with S2(log n.) terminates within OTT) iterations w.h.p.
Proof. Our goal is to lower bound p: = 1=
Dn/b+1 (x || Pi.)). Let us first upper bound X1.-
Using the fact that X1, S mAi.j as the algorithm does not terminate, get that Vj [2, n/b
T-1)8 (Lemma A.5 combined with the fact that A S 1/22(1 t) as long
it holds that X. S 2(1-c)(0-1))
Using the above we conclude that as long as we do not terminate it must hold that X1 S 2(1-e)= whenever E T = [1 een/b 1,n/b + 1]. That is, X.,, must be close Aτ,5 towards the end of the epoch, and therefore must be sufficiently small. Note that |/| en/b.
We know that as long as the algorithm does not terminate it holds that Fij > 1/2(1 2e) with some constant probability. Furthermore, this probability is taken over the randomness used in the call to GD (the randomness of the perturbation). This fact allows us to use Hoeffding-ryy variables. If yp.. > 1/2(1 2e) we say that it is good. Therefore expectation a constant fraction of "Pi.j.j j E I are good. Applying a Hoeffding type bound we get that w.h.p a constant fraction of Pi.j. are good. Denote these good indices by Ig S I. We are now ready bound P:-
bounds for the Pi
n/b+1
A:
Σ
DK ll ((,)
2 Σ DX ((,))
DKL
1
2(1 2 e)2 2(1 - 22)
j=2
jET,
jEL,
2 0 n (
n 2
1
n
21 - 2c) 2(1
c)2
Where in the transitions we used the fact that divergeee negaattaeive, and Pinsker's inequality. Finally, requiring that = 2(llgg n)) we get that bp: - 3(n, b) - (nn) O(n) - O ( log
log" - o(n) =
((n). Following the same calculation as Corollary 3.3 this guarantees termination within O log epochs, O(T E/ log (T)) iterations (gradient descent steps).
The above leads to contradiction. It is critical to note that the above does hold if T 2 26 or if = Onn), as both would imply that the o(n) term becomes (n)) We state our main theorem: Theorem 4.3. For any differentiable and L-smooth model class with d parameters and a perturbation class V such that é = o(m) there exist an input data set Y of size m such that GD requires 2(22m) iterations to achieve 8 accuracy on Y, even if 1/2 + (1)) and >> M.
REFERENCES
Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In ICML, volume 97 of Proceedings of Machine Learning Research, pages 1675-1685. PMLR, 2019.

---

Under review as a conference paper at ICLR 2023
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via parameterization, In ICML, volume 97 of Proceedings of Machine Learning Research, pages 242-252. PMLR, 2019.
Difan Zou, Yuan Cao. Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes wverpparameterized deep relu networks. CoRR, abs/181 18.0188, 2018.
Difan Zou and Quanquan Gu. An improved analysis of training ever-parameterized deep neural networks. In NeurlPS. pages 2053-2062, 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In ICLR. OpenReview.net, 2017.
Robin Moser and Gábor Tardos. constructive proof of the general lovász local lemma. ACM, 17(2)11:1-11:15, 2010.
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient descent for deep linear neural networks. In ICLR (Poster). OpenReview.net, 2019.
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameeerizzaion. In /CML, volume 80 of Proceedings of Machine Learning Research, pages 244 253. PMLR, 2018.
Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. In ICML, volume 80 of Proceedings of Machine Learning Research, pages 4430-4438. PMLR, 2018.
Simon S. Du and Jason D. Lee. On the power of over- paemmttramttinntionnnn in neural networks with quadratic activation. In ICML, volume 80 of Proceedings of Machine Learning Research, pages PMLR, 2018.
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparametterizatio:: global conver- gence guarantees for training shallow neural networks. CoRR, abs/1902.046744 2019.
Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernel: Convergence and generalization in neural networks. In NeurlPS, pages 8580-8589, 2018.
Jingzhao Zhang, Haochuan Li, Suvrit Sra, and Ali Jadbabaie. Neural network weights do not converge to stationary points: An invariant measure perspective. In ICML, volume 162 of Proceedings of Machine Learning Research, pages 26330-26346, PMLR, 2022.
Simon S. Du, Chi Jin, Jason D. Lee, Michael I. Jordan, Aarti Singh, and Barnabás Póczos. Gradient descent can take exponential time to escape saddle points. In NIPS, pages 1067-1077, 2017.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, and Michael I. Jordan. How escape saddle points efficiently. In ICML, volume 70 Proceedings of Machine Learning Research, pages 1724-1732, PMLR, 2017.
Ming Li and Paul M. B. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications, 4th Edition. Texts in Computer Science. Springer, 2019.
A OMITTED PROOFS AND EXPLENATIONS
A.1 REPRESENTING SETS AND PERMUTATIONS
Throughout this paper, we often consider the value K ((A) where A is a set. Here the program computing A need only output the elements of A (in any order). When considering K [A B) such that C B, it holds that ((A) B) S [log ((x)) + Ollog Bl). ). To see why, consider Algorithm In the algorithm LA is the index of A when considering some ordering of all subsets of B of size [A]. Thus log (18) bits are sufficient represent i.A. The remaining variables m. mg and any
10

---

Under review as a conference paper at ICLR 2023
Algorithm 4: Compute A given B as input
MA + | m. + | , 6 0, i. is a target index
for every subser C B [C] mA (in predetermined order) do
i = i then Print C i+itl
additional variables required construct the set C' are all of size at most Ollog B)) and there is at most a constant number of them.
During analysis, often bound the Kolmogorov complexity of tuples of objects. For example, ((A, P B) where A C B is a set and P A - [|A] is a permutation of A (note that A, P together form an ordered tuple of the elements of A). Instead of explicitly presenting program such as Algorithm 4 we say that if ({A B) S с₁ and c2 bits are sufficient to represent P, thus (AA, B) S C1 c2 O()). This just means that we directly have a variable encoding P into the program that computes A given B and uses it in the code. For example, we can add permutation to Algorithm 4 and output an ordered tuple of elements rather than set. Note that when representing permutation of A, |A| k, instead of using functions, we can just talk about values in flog k!]. That is, we can decide on some predetermined ordering of all permutations of elements, and represent permutation as its number in this ordering.
A.2 OMITTED PROOFS FOR SECTION
Lemma A.1. For p E [0, 1] it holds that h(p) S p plog(e/p).
Proof. Let write our lemma as:
hpp) = -plogp - (1-p) log(1 p) s plog(e/p)
Rearranging we get:
(1 p) log(1 p) < plogp plog(1/1 + ploge
= -(1 p) log(1 p) S ploge
Inn1 p) [1 (1-P) p)
p
Note that 1n(1 - p) = (1=z) dx S P (1-p)- Where the final transition we use the fact that is monotonically increasing [0, 1). This completes the proof.
Lemma A.2. For g.ge [0, where q, p)r S (1 it holds that
gh( P. + (1 - 4)hl (1- p)y (1 q)
s h(7) - Dx
11

---

Under review as a conference paper at ICLR 2023
Proof. Let expand the left hand side using the definition of entropy:
qh(
17
+ (1
9)h(
p)r
9
(1
g)
PY
P7
--q(
log
+ (1
log 1
(1 - phy
(1 p)y
(1-p)7
log(1 (1 (1-1)7)
(1 - x)(
log
+ (1
(1
(1 q)
(1 q)
(1 9))
PY + (g pn) log
9- --PY
-ppy log
q
9
(1 - p)
(1- q) (1 - ply
((1 p/y log
+ + - g) (1 p)y) log
(1 q)
1 q
= =-y logo - >DKL(P g)
-a- 9 - - ((1 (1) - (1 p) log
9) (1 p)y
1 9
Where the last equality we simply sum the first terms on both lines. To complete the proof we use the log-sum inequality for the last expression. The log-sum inequality states that: Let {ax {= {6x m
be non-negative numbers and let a = Σx= dk b = Σk= bR. then > as log as
b, 2 a log 8. We
apply the log-sum inequality with m = 2, bj q. b2
q py, a2 = (1 - 9) - (1 p)y, = 1 - 7 and
q, b 1, getting that:
( (1) - p2) pー) + ((1 - g) - (1 - (1)) log
(1 q) - (1 -1--p)7 2 (1 - 7) log(1 - 7)
1 1-9
Putting everything together we get that
7 - <loog ? - >Dx (p q)
(q - (log q - - ((1 9) (1- p)7) log (1- q) (1 (1- p\T
1-
S -ylogg - (1 7) log(1 7) >D |l q) = =b(7)= - DDxLL(P) 91
Lemma 2.4. Let A C B. = m, |A| -m, and let g : B + {0,1). For any set Y C B let [r,] Y = f gzz) = =1,,Y Y Yi and Ky = TYT It holds that
K(A B.g) S mm((oo(e/))-Dxxx -
|| KA)) + O(log
Proof. The algorithm is very similar to Algorithm 4 the main difference that we must first compute B1, By from B using g. and select A1, Ao from B1, Bo, respectively, using two indices iA, A Finally we print A A₁ U Ag- We can now bound the number of bits required to represent i : Ao Note that |B]| m Bol = (1 Kg)m. Note that for A₁ we pick a elements from Kmm elements and for An we pick 7(1 - KA) elements from (1 - KB m elements. The number of bits required to represent this selection is:
[log
KBm
) [log (1 kA)m)
(1 kg)m) ) knmh( YRA (1 (1--kig -K-))mmm 2 KA), KB
(1 1B))
< mm((r) DKELKE kA)) S my(log(e/n) - DKL (NB KA))
Where in the first inequality we used the fact that v0 < k: S log (+) I nh(kkn)). Lemma A.2 in the second transition, and Lemma [. in the third transition. Note that when KA 0, We only have one term of the initial sum. For example, for KA- = we get:
Kgmm
(KBM)
?'
[log
[log
1 KBmh(
KB < my log(enn/7) = m - loo (1/11/// 1/kn))
(KAM
ym
kn))) And similar computation yields my(log(e/7) - log (1g(1111-kx)) for K = 0. Finally, the additional Olog m) factor is due to various counters and variables, similarly to Algorithm
n
12

---

Under review as a conference paper at ICLR 2023
A.3 OMITTED PROOFS FOR SECTION
Lemma A.3. It holds that (r, W1,1 (X) I ((WW+11)++0 + Ex= K(ra X, W6+111)
Proof. Similarly to the definition of Y in Lemma 3.1 let y" be the program which receives X, W1+111 input and repeatedly applies Theorem 2.2 to retrieve Wa11 As y' just needs to reconstruct all batches from X, and call Y for n/b times, it holds that K(Y") = Ollog n). Using the subadditivity and extra information properties of ((, together with the fact that W1,1 can be reconstructed given X, W41111 Y', we write the following:
K(r X) < (r, W1,,, Y", W1+1, X) + 0(1) & (W,,, W4L1, Y' (X) K(r x,Y, W4+11) + +01 & (( () + (rr X, We+11) + O(logn)
First, we note that: Vi E [t - 1], K(;; | X,Y', WHz2,, & K(r; X,Y', W1+11) + O(1).
Where in the last inequality simply execute Y' on X, W14,,,,,1H4 get W1-1,1, Let us write:
K(rir2... Tr X,,Y, W4411) K(r, X,Y", Y', W4+1,) (rin2 .1.12...f:]) X, Y', (z) 0(1)
K(r,) X,W++1. + K(ring... X,Y', (,,1 +0())((1))
K(r, X, (,,,1),) + K(r-1 X, Wi,1 ((1122... X,Y W.111) 0(1)
... (()) + Σ K(r X, 1.
Combining everything together we get that:
K(r |X)= < ((W++11) + O(t) + Σ
K(ra W.1.1
k=1
Corollary 3.3. If, k Et= > B(n,b) + for 'logn), n). then w.h.p SGD terminates within (1) epochs.
Proof. Let us simplify Inequality
I
d + tn logg////e) Ollogn) < d t[n(log(n/e) + n O(logn)
Ologn)) - Σ bp
1=1
Ologgn) < =11 n Ollogn)
Ollgn]]]
Σ bp:
i=1
p.) t3(n, 6) < Ologn))/
Our condition implies that Ei=1 Pi > ((3((,, 6) + 7). This allows to rewrite the above inequality
as:
ty < (logg)) = ==== +1)
A.4 OMITTED PROOFS FOR SECTION 4
Lemma A.4. Let X be some set of size and let f X + (0,1)) be random binary function. It holds whhp that there exists no function g X + {0,1) such that K(g X) = o(n) and g agrees with f on n11 12-2 @(1)) elements in X.
13

---

Under review as a conference paper at ICLR 2023
Proof. Let us assume that 9 agrees with on all except elements in X and bound Using Theorem 2.3 it holds w.h.p that [f X) > n - O(logn), We show that e is sufficiently far from 1/2, use compress below its Kolmogorov complexity, arriving
contradiction.
We can construct f using g and the set of values on which they do not agree, which we denote by D. This set is of size en and therefore can be encoded using log (m)) I nn((c) bits (recall that vO < k A n, log (+) < nh(kk/n) given X (i.e., (DD X) I nn((e).. To compute f(x) using D,g simply check if x: D and output g(x) 1 - -g(x)) accordingly. The total numher of bits required for the above is K (g. D XX) < o(n) + +n((e) (where auxiliary variables are subsumed in the o(n) term). We conclude that (( X) S o(n) + nh(e). Combining the upper and lower bounds on Kf X), it must hold that o(n) + nh(e) 2 n Ollogn) = h(e) 2 - o(1). This incquality
only holds when c = 1/2 + o(1).
Lemma A.5. It holds that 1 m(1->ig) G1-
S X.j S
nAis
(j-1jh-
Proof. We can write the following for j E 12, n/b + 1]:
mdi Σ
acc (o
Σ
acc(We,,a)) +
Σ
acc(W
=EX
xEX,5-1
X
= (j - 1)b21 . + +nn - [j - 1))))")>
nZis - (n (j - 1
X1.5
(j 1j-1)b 1)6
Setting Nr we get
X1. ndi
(n (j - 1)6)
ndj.j
- (j 1)b
(j 1)b
And setting X" = 1 we get
ndS. (n (j 1)6)>
21 n11 - Aia))
X
1)b
(j - 1)6
B EXPERIMENTS
Experimental setup We perform experiments on MNIST dataset and the same data set with random labels (MNIST-RAND). We use SGD) with learning rate 0.01 without momentum or regularization. We use a simple fully connected architecture with a single hidden layer, GELU activation units (a differentiable alternative ReLU) and cross entropy loss. We run experiments with hidden layer of size 2,3 5, 10. We consider batches of size 50, 100, 200. For each of the datasets we run experiments for all configurations of architecture sizes and batch sizes for 300 epochs.
Results Figure 2 and Figure 3 show the accuracy discrepancy and accuracy over epochs for all configurations for MNIST and MNIST-RAND respectively. Figure and Figure show for every batch size the accuracy discrepancy of all three model sizes on the same plot. All of the values displayed are averaged over epochs, i.e., the value for epoch t is E Zz.
First, indeed observe that the scale of the accuracy discrepancy is inversely quadratic in the batch size, as our analysis suggests. Second, for MNIST-RAND we can clearly see that the average accuracy discrepancy tends below certain threshold over time, where the threshold appears to be independent of the number of model parameters. We see similar results for MNIST when the model is small, but not when it is large. This is because the model does reach its capacity within the timeframe of our experiment.
14

---

Under review as a conference paper at ICLR 2023
barch 56, rum hadden
zatra nur t:lden
ANOoge octeectyy decrosecyy
bete So, rum
D. 30
g
2002
65
000
Avercc
byoch 1atch con 100 haddan
batch 100 Fadden:
batch 100, hiddee:
B. (es)
8
6
21
10
25
100
204
1.0
120
Accunay
12
Ln3
2ooch
Figure 2: Full results for the MNIST dataset.
bstrft sumihinden
bohrh mam hadden
Accrage extrner doenppory
30 30
11a
X33
Nerrac
301
1000
300
tpoch
spacs
batth
batch rum kidde
banch
11/2
optra mouney eooneyy drunawyyy
45-
X22
Ovarage accommn descrppancy
15.1
1112
8
A65
230
126
26
254
30
16
25
20
300
30
150
20
254
206
100
-3.15
10.5
30.2
10.0
1004
1110
Figure 3: Full results for the MNIST-RAND dataset.
15

---

Under review as a conference paper at ICLR 2023
baich
batch
batth
123
322
150
36
250
35
305
150
300
250
300
32C
123
750
750
Lpanch
Lpoch
Figure 4: We plot for every batch size the accuracy discrepancies of the different models. Results for MNIST.
Batch size:
batch Size: 102
batch site 200
Prgtipo scourcy decrsonnc
100
100
150
100
Dpach
Figure 5: We plot for every batch size the accuracy discrepancies of the 3 different models. Results for MNIST-RAND.
16


Reviews:
[{"review_id": "yP5C0U-GbA", "reviewer": "Reviewer_dQLw", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "", "summary_of_the_paper": "The paper considers studies dynamics of mini-batch SGD using Kolmogorov complexity. They define a notion of accuracy discrepancy as a KL-divergence between accuracy of the model on previous batches in the current epoch and on the last batch. Using the fact that the random strings used for generating the epoch’s permutation are incompressible, they bound the accuracy discrepancy throughout the algorithm execution.\n", "summary_of_the_review": "Solid paper, accept.", "strength_and_weaknesses": "I have the following concerns about the paper:\n\n-- As I understand, the discussion near Theorem 2.2 is really important, since it shows that the provess is invertible. Moreover, the algorithm actually relies on the fact that the set of possible values is finite, to find the original point in finite time.\n\nHowever, the conditions in Theorem 2.2 don’t necessarily hold in practice. To give an example, for f(x)=x^2 / 2, with the step size 1e-16, for the double type, the gradient step starting from points 1e16 + 2 and 1e16 produce the same result.\n\nWhile I understand that the example is artificial, it suffices to show that the process is, in general, not invertible (when working in doubles). I’m not sure, but it might be important for the rest of the paper, since you do rely on the invertibility. I think that it should be clarified why the conditions of Theorem 2.2 actually hold.\n\n-- “It is clear that w.h.p we cannot train a model with d parameters that achieves any accuracy better than 1/2 + o(1) on X” - I’m not sure this statement is true. You probably should use non-random labels and counting argument.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "pSpL_eLMc9Y", "reviewer": "Reviewer_GiuD", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper studies batch SGD using the theory of Kolmogorov complexity to deduce novel observations about the behavior of SGD. For instance, the paper shows that certain patterns of classification accuracy obtained on the batches would allow the randomness of the batches (the permutation used to select the batches) to be compressed, and this implies a bound on the number of iterations SGD requires before achieving 100% test accuracy on the entire training data set. The paper also considers a lower bound on the amount of randomness needed to escape local minima.", "summary_of_the_review": "Despite the lack of concrete implications, I like the novelty and I recommend the paper for acceptance. I hope that it will generate interesting follow-up work.", "strength_and_weaknesses": "I found the paper to be very interesting and refreshing, as it adopts a perspective on SGD that I had not considered before. I also appreciate the focus on minimal assumptions, as it seems important to understand the general behavior of SGD.\n\nI believe that the main weakness of the paper is that it is quite abstract, and it is not clear to what extent the findings are applicable to real-world situations. To this extent, more concrete examples in the main text would be appreciated (e.g., are there concrete learning tasks for which the results of the paper are easily illustrated?). Also, it is worth noting that the setting may be too general, and the results of the paper may not be typical for situations encountered in practice.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "jIOBaEBnx7", "reviewer": "Reviewer_5jcV", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The paper considers dynamics of stochastic gradient descent (SGD) and relates accuracy with a notion of \"accuracy discrepancy\". The paper shows that if the \"accuracy discrepancy\" is large enough, then SGD can find a model with perfect accuracy, while on the other hand if the \"accuracy discrepancy\" is small, there exists inputs for which a specific gradient descent component within an SGD algorithm terminates in exponential time.", "summary_of_the_review": "The paper is interesting but has several concerns including those listed in the sections above. Revisions on the paper would help with its clarity and quality.", "strength_and_weaknesses": "Overall, the paper is interesting but suffers from clarity issues.\n\nStrengths of the paper:\n- The paper discusses SGD, which is an important and relevant topic for the learning community. \n- The paper gives many examples for the introduction / motivation\n- The usage of Kolmogorov complexity in the analysis of SGD is interesting\n\nSome comments on weaknesses include:\na. It appears that the \"reversibility\" of Lemma 2.1 and other usages in the paper requires that the smoothness constant L satisfy L>1, but it was not clearly mentioned in the paper. Are there any comments on this and how it affects or puts limitations on the main result?\nb. There are parts in the paper that leave a confusing impression. For example, in page 2 \"Outline of our techniques\" it is stated that \"if the accuracy on the entire dataset is 100% we terminate\" but immediately at the top of page 3 the paper asks the reader to consider a scenario where \"we terminate our algorithm when we achieve 90% accuracy on the entire dataset\". This, being in the introduction section, may cause confusion for readers.\nc. Following the above point on confusion, there are also other sentences that may require revision. For example, on page 5, what does \"private case of Pinsker's inequality\" mean? And in the \"Representing sets\" section, it is said that \"some useful bounds\" are to be stated there, but there is only one bound Lemma 2.4., is something missing here?\nd. Does the result only hold for specific scenarios of SGD? For example, does the results of Section 4 only hold when we need convergence/termination in Alg. 2? What about the scenario when SGD only has one step of GD (such as similar to Algorithm 1)? This seems to show that the results are fairly limited and only suitable for specific scenarios.\ne. The main results and flow of the discussion is not very clear and concise. This is also shown through the fact that there are a lot of Lemmas but there is no main Theorem in Section 3 and only one main Theorem at the very end of page 9 in Section 4. The clarity of the paper would be greatly improved with more discussions on the flow of proofs and more interpretations of lemmas.\nf. The experiment results were not discussed in detail.\ng. Some comments on typos: There are several occurrences in the paper where \"perturb\" is spelled wrong. Another point is: Is the description of Algorithm 3 missing?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "fDJNIrxQ60V", "reviewer": "Reviewer_w9AC", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "", "summary_of_the_paper": "The paper studies the convergence property of SGD using tools from Kolmogorov Complexity.  A key quantity considered here is the accuracy discrepancy---the gap between the model accuracy on a training batch vs the rest of the data set. \n\nThe paper provides two results. \n\n* Section 3 shows that during training if the accuracy discrepancy is consistently beyond a global threshold $\\beta(n,b)$, depending only on batch size $b$ and data size $n$, then training will converge to full accuracy in constant epochs (namely, after constant cycles over the dataset). \n* Section 4 considers randomly perturbing the inputs to allow SGD to terminate with high accuracy. It's shown that SGD may take exponential time unless the amount of randomness used in the perturbations is sufficiently high. ", "summary_of_the_review": "Overall I think the paper has some interesting ideas. However, I am not convinced about the applicability of the claims. The paper can also be improved in terms of clarity and scope of experiments. ", "strength_and_weaknesses": "The paper provides some interesting ideas for studying SGD convergence. To the best of my knowledge, the argument in Section 3 is novel. I think the result is intuitive. That is, if any model training can consistently improve the accuracy on the current batch during SGD, relative to the full dataset, then it is capable of fitting all data. I appreciate the technical part where this idea is formalized. \n\nWhile the theoretical claim of section 3 is interesting, I have concerns about the setting and motivation. First, the argument hinges upon the assumption that the SGD/GD is run with a sufficiently small step size below $1/L$.  I am not convinced that this holds in practice. In particular, modern neural networks are typically trained with large step sizes at a initial stage, higher than what's suggested by optimization theory, then later annealed as training loss improves. See the literature on \"learning rate decay\" and \"learning rate schedule\". This may break the reversibility lemma in section 2 and affect the main claim of section 3. \n\nFor section 4, as the author(s) suggested, one motivation is to study whether SGD can escape local minima. It's unclear this is an interesting question (either in theory or practice). In practice, large networks are highly parametrized and capable of fitting the entire train set. And it's observed that standard optimization techniques (SGD and its variants, such as Adam) can converge. \nThe claim of section 4 seems to be that we need to perturb the input points to avoid getting stuck at a highly sub-optimal local min (with 1/2+$\\epsilon$ accuracy). I encourage the author(s) to expand on the conceptual  message here, since as far as I know, this is not required in practical settings.\n\nThe main result in sec 3 applies to reshuffling SGD where each epoch uses a fresh random permutation. It's also common in practice that there's a single random permutation (sampled upfront) used by all epochs. (This is called single shuffle SGD; see e.g. Can Single-Shuffle SGD be Better than Reshuffling SGD and GD? by Chulhee Yun, Suvrit Sra, Ali Jadbabaie.) Could the author(s) comment on this setting?\n\nSome parts of the paper can be better written.  In the introduction (especially in the “outline of our techniques” section), it should be clarified what are the random bits that the reversal procedure tries to reconstruct. From early discussion (top of page 2), there are random bits in the initialization of the network, random bits for drawing SGD samples per step, and random perturbations added to the input points. The author(s) should specify what the main target here is. \n\nFinally, the experiments appear somewhat limited, conducted only on shallow neural networks trained with MNIST dataset. \n  \nMinor comments\n---\n1. Page 1: “For every batch, the accuracy of the model after the Gradient Descent (GD) step on the batch is 100%.” When I read it first, it wasn’t clear if this is a claim or a thought experiment. Maybe add: “Suppose hypothetically.”\n2. Page 1: “, however” -> “. However”\n3. Page 2: “perturbe” -> “perturb”\n4. Page 2: The precise termination condition seems confusing here. In one paragraph, it is written that “thus, in our case, termination implies 100% accuracy”. In a later paragraph: “We apply this approach to SGD with an added termination condition when the accuracy over the entire dataset is beyond some threshold. Thus, termination in our case guarantees good accuracy”. Which one is actually applied here?\n5. Page 2: “ a sufficiently small GD step” -> “sufficiently small step size”\n6. Page 3: “we can sort X by IDs”--- I am not sure this is necessary to say?\n7. Page 3: “pertrubes” -> “perturbs”\n8. Page 3: “Applying this reasoning to data with random labels we arrive at a contradiction” — I don’t understand this point: what’s the contradiction \n9. Section 3: W_ij should be defined explicitly. (I understand it’s clear from the picture.)\n10. Section 4: I think it’s better to state the goal of this section at its beginning\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "IyzEN6Xa0xX", "reviewer": "Reviewer_EpmW", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper is about analyzing the behavior of stochastic gradient descent (SGD) using Kolmogorov complexity.  \nThe authors are using an “entropy compression argument” to prove the termination (and convergence) of SGD under weaker assumptions as well as provide a lower bound on the amount of randomness needed for SGD to escape local minima using perturbations. \nThe main argument originates from a constructive proof of the Lovasz Local Lemma by Moser, and the idea is that: “Suppose that by looking at the execution of a randomized algorithm, one is able to produce a string shorter than the string of random bits that the algorithm used, albeit it is possible to use that shorter string in order to reconstruct the input random string, then the algorithm should terminate as soon as that happens since it is not possible to compress a string of i.i.d random bits.“ \nFor the first result, the data is split in batches and the algorithm terminates when the accuracy reaches some value<1 (e.g 90%), while for each batch the accuracy is 100%. This allows a more efficient “encoding” of the batch samples since only the subset of correctly classified data could be used. This enables the entropy compression argument to go through and prove termination of the SGD algorithm.\nFor the second result, it is assumed that the algorithm used $\\ell$ uniformly random bits to choose among $2^\\ell$ different perturbations. The authors use a similar argument or random string reconstruction and show that a using a sublinear in the size of the dataset number of random bits, it is not possible for SGD to terminate in polynomial time and non-trivial accuracy.\n\n \n", "summary_of_the_review": "I believe the paper makes a solid conceptual contribution and deserves to be accepted if the writing is improved.  ", "strength_and_weaknesses": "Strengths:\n- The paper proposes a novel use of a powerful idea, which even though it comes from a different area, it is demonstrated to potentially have interesting applications in optimization and machine learning. \n- It is shown that this technique can be used both for positive and negative results. \n\nWeaknesses\n- The presentation of the paper could be improved. For example, the results need to be more clearly stated in the introduction and I would also suggest that the main results are stated earlier in each of the sections. \n\n\nMinor comments:\n- Page 5, second bullet: there is a comma missing in the lhs.\n- In section 4: I am a bit confused with the use of $m$ and $n$. It seems that they should both mean the size of the dataset. So, the notation needs to be merged. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "FBkz6Roi1u", "reviewer": "Reviewer_xLLJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper proves that SGD fits the training data whenever the average accuracy discrepancy over epoches, defined as the sum of accuracy improvement over batches, is large enough. Using a similar idea, this paper also proves GD needs a certain amount of randomness to escape local minimas efficiently.", "summary_of_the_review": "The idea of this paper is very novel and has the potential to be make impacts. However the assumption and result need more clarification/justification and the writing can be improved.", "strength_and_weaknesses": "Strength:\n\nThe idea of using entropy compression to analyze SGD is novel and interesting.\n\nWeaknesses:\n\nThe assumption of accuracy discrepancy isn't natural: unlike other \"prior\" assumptions, this assumption involves the process of optimization. The assumption is felt to be designed especially for using the entropy compression tool.\n\nThe bound $O(\\frac{n \\log n}{b^2})$ implies $b=\\Omega(\\sqrt{n})$ because $\\rho_i$ is bounded by a constant, likely $\\log 2$ in practice for this binary classification problem. I wonder whether a batch size as large as $\\Omega(\\sqrt{n})$ is practical, or already implies good convergence results itself.\n\nCorollary 3.3 uses a stronger assumption than what's actually needed: it seems to be this only needs to hold on average.\n\nThe setting of section 4 seems artificial and I don't see any close relationship to the theme of section 3, except the common tool they use.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "8S9LF0n1W_", "reviewer": "Reviewer_T4KT", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This paper analyzes the convergence of stochastic gradient descent (SGD). It also concerns the study of the minimum amount of randomness that needs to be added to non-stochastic gradient descent (GD) so that it can converge.\n\nFirst, it defines the *accuracy discrepancy* as the cumulative difference (measured with the relative entropy)  between the accuracy of the model in the batches seen until iteration $j$ and the accuracy of the model at iteration $j$ of a certain epoch. \n\nThen, it shows that if the average of accuracy discrepancies over the last $t$ epochs is over a certain threshold, then SGD converges to 100\\% accuracy with high probability (w.h.p.) within $\\mathcal{O}(1)$ epochs. This result is architecture-independent, in contrast with the current literature.\n\n* An extra contribution of this result is its analysis, since it is uncommon in this area. It relies on Kolmogorov complexity, which is a measure of compression. The idea is to consider the randomness used to select the permutation of the batches in SGD. Pure randomness cannot be compressed, thus giving a lower bound on the Kolmogorov complexity. After observing the model at a certain iteration and the data, such randomness can be compressed and the paper shows an upper bound that depends on the accuracy discrepancy. Combining those they show that w.h.p. if at epoch $t$ the algorithm did not terminate then the accuracy discrepancy is smaller than a certain threshold. Hence, if the accuracy discrepancy is larger than such a threshold, it must terminate. \n\nFinally, they argue that GD does not converge if the amount of randomness included can be represented with $o(n)$ bits and the amount of epochs is $\\text{poly}(d,n)$, where $d$ is the parameters' dimension and $n$ is the number of data samples. That is, if the randomness is sublinear with $n$, there is a dataset for which the amount of epochs needed for convergence is superpolynomial (e.g. exponential).", "summary_of_the_review": "This studies and gives insights in two important phenomena in the convergence of gradient-based algorithms:\n\n* If finds a sufficient condition for the convergence of SGD. As long as the accuracy discrepancy (introduced in this paper) is larger than a certain threshold the algorithm terminates within $\\mathcal{O}(1)$ epochs. Hence, understanding when such a quantity crosses the threshold is enough to understand when SGD will converge. This can serve to derive new theory to characterize the convergence of SGD.\n* It shows that a necessary condition to ensure GD convergence is to have some randomness with a superlinear Kolmogorov complexity with respect to the number of samples. This is an insighful result that can serve to better understand and design current algorithms and to develop new ones.\n\nTo obtain these results the paper employs Kolmogorov complexity, which is a novel technique in convergence analysis as far as I know.\n\nThe paper is not very clear and has some claims that need further support, as I mention in the weaknesses section of the review.\n\nDue to the lack of clarity, I must lean to rejection at the moment. The reason is that unless some of my questions and concerns are addressed, I cannot verify that the proofs are correct. Nonetheless, I am open to changing my rating to accept once they are successfully answered. This is because even though the convergence analysis is not direct, I believe that the paper contributes to a better understanding of the convergence of gradient-based methods and introduces an interesting proof technique that can be used in further work. \n\n**Minor comments and nitpicks that did not impact the score of the review**\n\n* Usually, with high probability (w.h.p.) always means that the probability tends to 1. I am not so sure the footnote is needed, then. Also, in your case, you prove a stronger convergence rate than $1 - 1/n$.\n* 7th line, page 2: (and wide) ~~the~~ GD.\n* Shouldn't it be $acc(W,A): \\mathbb{R}^d \\times 2^X \\to[0,1]$?\n* Before Lemma 4.1, in the parenthesis shouldn't it be \"(by iterating over all values of $\\mathbb{F}^d$)\"? \n* In the proof of Lemma 4.2, it should be $D_{\\text{KL}}(\\lambda_{i,j}' \\lVert \\varphi_{i,j})$.\n* Figures 4 and 5 are hard to see for a colorblind person. Could you change the colors, please?", "strength_and_weaknesses": "**Strengths**\n\n* The results in this paper are architecture-independent. \\\nThis is good since the current understanding of the global convergence of SGD is for specific models that usually require over-parameterization. The only requirements for this theory are that the loss is differentiable, $L$-smooth, and that the step size is smaller than $1/L$, all of which are reasonable.\n\n* The result of the necessity of superlinear randomness with respect to the number of samples for the convergence of GD is insightful. It opens a bridge between why SGD generalizes and GD does not in certain situations and opens the door to the design of the randomness in other versions of GD where the randomization is included differently such as stochastic gradient Langevin dynamics, or even the design of new GD-based stochastic algorithms. \\\nI believe that it could be beneficial for the article to stress this fact since the importance of this result seems overshadowed by Section 3.\n\n**Weaknesses**\n\n* The main statement of the convergence of SGD says that if the average accuracy discrepancies until epoch $t$ is larger than a certain threshold, then the algorithm converges within $\\mathcal{O}(1)$ epochs. \\\nThis statement is interesting on its own in the sense that it gives a sufficient metric to determine the convergence of SGD. That is, if one can see when the average accuracy discrepancy will exceed the threshold, then one knows when SGD will converge. \\\nHowever, it still does not give any convergence result for SGD, since it is still needed to run the algorithm to be able to calculate the accuracy discrepancies. That is, to determine the quantity that tells if SGD converges, one needs to run SGD until convergence.\n  \n  * The paper may be improved with an acknowledgement of this fact and placing the contribution in a different fashion: that is, as a finding of a sufficient condition for SGD convergence. \\\n  Otherwise, and more strongly, the paper would benefit from an analysis of the accuracy discrepancy and when it exceeds said threshold. Though I understand this may be the work of a future follow-up project. \n\n* The paper is hard to read and sometimes leaves some useful information unwritten.\n\n  * In the related work section it mentions the work from *Zhang et al. (2022)* requires *certain assumptions*. It would be helpful to state such conditions. Similarly, when discussing *Jin et al. (2022)* it is said that the randomness required for the perturbations on this work is beyond the considered threshold. This claim is not recovered in Section 4, so we are to believe such a statement.\n\n  * Theorem 2.3 deals with the conditional Kolmogorov complexity $K(x|y)$ before it is introduced int eh following paragraphs. It would be useful to describe this property of random strings right after the general properties of the Kolmogorov complexity.\n\n  * How does one go from the first to the second line of equations in the proof of Lemma 3.1?\n\n  * Also in the proof of Lema 3.1, the papepr goes back and forth with the notation $B_{i,j}$ knowing $X_{i,j}$ and $B_{i,j-1}$ knowing $X_{i,j-1}$. Although equivalent, it would aid readability to maintain one indexing. The same happens in the definition of the variables of interest in the beginning of Section 3.\n\n  * In proof of the Corollary 3.3, what is the exact value of $\\beta(n,b)$? Also, what is $\\gamma$? I could not follow the proof without that knowledge.\n\n  * In the proof of Lemma 4.2, how does one go from the first to the second line of equations? I understand that Pinsker's inequality is employed. My question regards the $\\Theta(n/b)$ term, based on the equation it seems it says that $|I_g| = \\epsilon \\Theta(n/b)$. If so, how do we know that? \n\n* The KL divergence (or relative entropy) $D_{\\text{KL}}(p \\lVert q)$ extension is unjustified. The extremes with respect to $p$ are set to zero when there are real finite limiting points, and the extremes with respect to $q$ are set to some finite value when they diverge.\n\n  * A suggestion is to use the standard agreement that $0 \\log 0 = 0$ by continuity and let $D_{\\text{KL}}(1 \\lVert q) = \\log(1/q)$ and $D_{\\text{KL}}(0 \\lVert q) = \\log(1/(1-q))$, and $D_{\\text{KL}}(p \\lVert 0) \\to \\infty$ and $D_{\\text{KL}}(p \\lVert 1) \\to \\infty$. This should not be a problem for your theory since the relative entropy is only employed in the accuracy disagreement and we have that if $\\lambda_{i,j}' \\neq 0,1$ then $\\varphi_{i,j} \\neq 0,1$ \n\n* In the Appendix B, it would be helpful if some of the figures had the y-axis adjusted to have a better visual comparison between them. Without a closer look, in Figure 2 for batch size 200 and 10 hidden units, one may get the opposite idea.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject