Venue: ICLR 2023 Conference

Reviews:

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

strength_and_weaknesses: I have the following concerns about the paper:

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

However, 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.

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

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


clarity,_quality,_novelty_and_reproducibility: Minor issues:
-- Theorem 4.3: I don’t understand what ½ + θ(1) means
-- Instead of $\tilde{\nabla f_{A}}$ (and others), I would write $\tilde{\nabla f}_{A}$. The long tilde looks really weird
-- I think “w.h.p.” is commonly defined as 1 - n^-c for an arbitrary large c
-- Page 6:” Where in the above we used Stirling’s approximation” and “Where the efficiency of reconstruction is expressed via ρ_i”: should start commas (instead of being new sentences).
-- I think the relation between f and acc was never mentioned

summary_of_the_review: Solid paper, accept.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
strength_and_weaknesses: Overall, the paper is interesting but suffers from clarity issues.

Strengths of the paper:
- The paper discusses SGD, which is an important and relevant topic for the learning community. 
- The paper gives many examples for the introduction / motivation
- The usage of Kolmogorov complexity in the analysis of SGD is interesting

Some comments on weaknesses include:
a. 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?
b. 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.
c. 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?
d. 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.
e. 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.
f. The experiment results were not discussed in detail.
g. 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?
clarity,_quality,_novelty_and_reproducibility: Overall, there is room for clarity and quality. Please refer to the section above for comments on clarity and quality. In terms of originality, the paper provides some discussion of SGD and prior literature but does not provide many comparisons against prior work or prior techniques. Some additional discussion / comments in the paper regarding novelty of techniques would be helpful.
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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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. 

The paper provides two results. 

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

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

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

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

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

Finally, the experiments appear somewhat limited, conducted only on shallow neural networks trained with MNIST dataset. 
  
Minor comments
---
1. 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.”
2. Page 1: “, however” -> “. However”
3. Page 2: “perturbe” -> “perturb”
4. 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?
5. Page 2: “ a sufficiently small GD step” -> “sufficiently small step size”
6. Page 3: “we can sort X by IDs”--- I am not sure this is necessary to say?
7. Page 3: “pertrubes” -> “perturbs”
8. 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 
9. Section 3: W_ij should be defined explicitly. (I understand it’s clear from the picture.)
10. Section 4: I think it’s better to state the goal of this section at its beginning

clarity,_quality,_novelty_and_reproducibility: At a technical level, the main theoretical claims of the paper appear sound. As I discussed, though, they either are under restricted assumptions or appear insufficiently motivated in ML practice.

I have a few suggests regarding writing presentation (see above).
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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.

I 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.
clarity,_quality,_novelty_and_reproducibility: The paper is very novel and generally of good quality. However, the clarity of the paper could be improved by discussing the implications more explicitly. I also point out some typos:
- Throughout the paper: “minimas” should be “minima”
- Pg. 1 footnote, “mean” -> “means”
- Pg. 2: “perturbe”
- Pg. 2, “The randomness we compress are the bits” -> “The randomness we compress is the bits”
- Pg. 3, “Showing that indeed…” is a sentence fragment
- Pg. 3, “pertrubes”
- Pg. 3, by R[0,1] do you mean [0, 1]?
- Pg. 5, “private case of Pinsker’s inequality” what does this mean?
- Pg. 6, “Where in the above…” the word “Where” should not be capitalized; similarly in the paragraph below
- Pg. 8, “Even for extremely…” is a sentence fragment
- Pg. 8, “there must be instances with exponential running time” This is not clear from the paragraph; just because something is not polynomial does not necessarily mean it is exponential.
- Thm. 4.3, “Even if…” is a sentence fragment
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper is about analyzing the behavior of stochastic gradient descent (SGD) using Kolmogorov complexity.  
The 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. 
The 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.“ 
For 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.
For 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.

 

strength_and_weaknesses: Strengths:
- 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. 
- It is shown that this technique can be used both for positive and negative results. 

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


Minor comments:
- Page 5, second bullet: there is a comma missing in the lhs.
- 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. 

clarity,_quality,_novelty_and_reproducibility: The main ideas are quite novel end clearly explained. However, the presentation in the technical parts should be improved. 
summary_of_the_review: I believe the paper makes a solid conceptual contribution and deserves to be accepted if the writing is improved.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strength:

The idea of using entropy compression to analyze SGD is novel and interesting.

Weaknesses:

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

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

Corollary 3.3 uses a stronger assumption than what's actually needed: it seems to be this only needs to hold on average.

The 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.
clarity,_quality,_novelty_and_reproducibility: Writing of this paper needs improvement. Many mathematical statements seem casual and the structure of paper isn't clear (for example, should there be a formal statement of main theorem in section 3?), let alone typos. The presentation of this paper isn't up to the standards a ML audience expects for this conference.
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.

First, 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. 

Then, 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.

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

Finally, 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).
strength_and_weaknesses: **Strengths**

* The results in this paper are architecture-independent. \
This 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.

* 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. \
I believe that it could be beneficial for the article to stress this fact since the importance of this result seems overshadowed by Section 3.

**Weaknesses**

* 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. \
This 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. \
However, 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.
  
  * 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. \
  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. 

* The paper is hard to read and sometimes leaves some useful information unwritten.

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

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

  * How does one go from the first to the second line of equations in the proof of Lemma 3.1?

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

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

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

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

  * 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$ 

* 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.
clarity,_quality,_novelty_and_reproducibility: * **Clarity**: As mentioned in the weaknesses above, the paper is not very clear and is hard to read. \
However, there is time for a careful revision of the manuscript to improve these issues.

* **Quality**: The quality of the paper is good. The ideas are interesting and well-executed.

* **Novelty**: As far as I know, employing Kolmogorov complexity (or similar compression arguments) to show the convergence of SGD or other algorithms is novel. This could spark new analyses of different algorithms.

* **Reproducibility**: \
*Theory*: I reproduced all the proofs except for the questions that I placed the authors in the weaknesses. I believe that after they answer them and clarify those in the manuscript every theoretical aspect should be reproducible. \
Some further notes in this regard are:
  * In the paragraph *Bounding $t$*: is not the probability $1 - 1/n^t$. Of course, this also implies a probability of at least $1 - 1/n^2$, but I believe that that is what one obtains after applying Theorem 2.3.
  * I could not find an open-access resource for the Kolmogorov complexity property $K(x|z) + \mathcal{O}(1) \leq K(x,y|z) + \mathcal{O}(1)$ for any three strings $x,y,z$. Therefore, I trusted this inequality as an axiom to reproduce their results. Could the authors link to an open-access source for this result?

  *Experiments*: There is no code to reproduce the experiments. They are easy to replicate due to the small size of the datasets and the simplicity of the experiment. Nonetheless, it would be helpful to include this resource.
summary_of_the_review: This studies and gives insights in two important phenomena in the convergence of gradient-based algorithms:

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

To obtain these results the paper employs Kolmogorov complexity, which is a novel technique in convergence analysis as far as I know.

The paper is not very clear and has some claims that need further support, as I mention in the weaknesses section of the review.

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

**Minor comments and nitpicks that did not impact the score of the review**

* 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$.
* 7th line, page 2: (and wide) ~~the~~ GD.
* Shouldn't it be $acc(W,A): \mathbb{R}^d \times 2^X \to[0,1]$?
* Before Lemma 4.1, in the parenthesis shouldn't it be "(by iterating over all values of $\mathbb{F}^d$)"? 
* In the proof of Lemma 4.2, it should be $D_{\text{KL}}(\lambda_{i,j}' \lVert \varphi_{i,j})$.
* Figures 4 and 5 are hard to see for a colorblind person. Could you change the colors, please?
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Summary
---
This paper studies the convergence property of stochastic gradient descent (SGD) using tools from Kolmogorov complexity. The authors define a quantity called the "accuracy discrepancy," which is the gap between the model accuracy on a training batch versus the rest of the dataset. They show that if the accuracy discrepancy is consistently beyond a certain threshold, then training will converge to full accuracy in a constant number of epochs. They also consider the use of randomly perturbed inputs to allow SGD to terminate with high accuracy, and show that SGD may take exponential time unless the amount of randomness used in the perturbations is sufficiently high. The authors use these results to provide a lower bound on the amount of randomness needed for SGD to escape local minima using perturbations. Overall, the paper aims to provide insights into the behavior of SGD and its convergence properties using the theory of Kolmogorov complexity.

Strengths:
---
- The paper provides some interesting ideas for studying SGD convergence, which is an important and relevant topic for the learning community.
- The paper provides examples for the introduction/motivation, and uses tools from Kolmogorov complexity to study SGD.

Weaknesses
---
- The main statement of the convergence of SGD in the paper provides a sufficient metric to determine when the algorithm will converge, but it does not give a convergence result for SGD itself. To determine when SGD will converge, one must run the algorithm and calculate the accuracy discrepancies. Therefore it would be helpful if the paper acknowledged this and positioned its contribution as a finding of a sufficient condition for SGD convergence, rather than a direct convergence result for SGD.
- Multiple reviewers complained about the presentation of this paper. 


justification_for_why_not_higher_score: There are two major reasons that I recommend rejection:

- The main result relates the convergence of SGD to the accuracy discrepancy, which, in turn, relies on the optimization process, as discussed by Reviewer w9AC,  Reviewer xLLJ and Reviewer T4KT. It establishes the connection between the convergence of SGD and the accuracy discrepancy which we may not have a good understanding of, rather than something that we have a good understanding of. The main result does not solve the problem that it claims to solve. Given the assumption about the accuracy discrepancy, the proof is straightforward and thus lacks novelty. 
- The presentation of this paper needs improvement.
Decision: Reject