SGD Through the Lens of Kolmogorov Complexity

We consider batch SGD, where the model is initialized randomly and the dataset is shuffled once at the beginning of each epoch and then divided into batches. Note that this paper does 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 to update the model. This is the “vanilla" version of SGD, without any acceleration or regularization (for a formal definition see Section 2). Furthermore, for the sake of analysis, we add a termination condition after every GD step: if the accuracy on the entire dataset is at least $1-\epsilon$ we terminate. Thus in our case termination implies good accuracy.

We show that under reasonable assumptions, local progress of SGD implies global progress. Let $\epsilon\in(0,1)$ be an accuracy parameter of our choice and let $X$ be the dataset (every element in $X$ consists of a data point, a label, and some unique ID), where $\left|X\right|=n$. Let $K(X)$ be the Kolmogorov complexity of $X$ (the shortest Turing machine which outputs $X$). We can also define the Kolmogorov complexity of a function as the shortest Turing machine which computes the function (see Section 2 for a formal definition). The assumptions we make are formally stated at the beginning of Section 3. Below is an intuitive outline:

1. 1.

   After every GD step the batch accuracy is improved by at least an additive $\epsilon\beta^{\prime}$ factor (on average, per epoch), where $\beta^{\prime}$ is a local progress parameter. That is, fix some epoch and let $y_{i}$ be the model accuracy on the $i$-th batch before the GD step and let $y^{\prime}_{i}$ be the model accuracy after the GD step, then we require that $\frac{1}{t}\sum_{i=1}^{t}(y^{\prime}_{i}-y_{i})\geq\epsilon\beta^{\prime}$ where $t$ is the number of batches in an epoch.

2. 2.

   The Kolmogorov complexity of the function computed by the model is at most $(\epsilon\beta^{\prime})^{3}n/512$. In other words, either the model is underparameterized, or the function computed by the model is sufficiently simple.

3. 3.

   The loss function is differentiable and $L$-smooth. This must also hold when taking numerical stability into account.

4. 4.

   The batch size is $\Omega((\beta^{\prime}\epsilon)^{-2}\log^{2}(n/(\beta^{\prime}\epsilon)))$. Note, the dependence on $n$ is only polylogarithmic.

5. 5.

   The size of every element in $X$ is at most polynomial in $n$. For example, if $X$ contains images, they are not excessively large compared to $n$. Furthermore, the number of model parameters is at most polynomial in $n$ (this is not implied by Assumption 2, as the model can be huge but still compute a simple function).

Roughly speaking, we show that if $n$ is sufficiently large and assumptions 3 to 5 always hold and assumptions 1,2 only hold for a $\gamma$-fraction of the epochs ($\gamma\in(0,1]$ need not be a constant), then SGD must achieve an accuracy of at least $(1-\epsilon)$ on the entire dataset within $O(\frac{K(X)}{\gamma(\beta^{\prime}\epsilon)^{3}n})$ epochs with high probability (w.h.p)¹¹1This is usually taken to be $1-1/n^{c}$ for some constant $c>1$. For our case, it holds that $c\in(1,2)$, however, this can be amplified arbitrarily by increasing the batch size by a multiplicative constant.. Note that the number of epochs does not depend on the size of the model. Finally, note that when the accuracy is too high the local progress assumption cannot hold anymore (we discuss this further in Section 3.1), and we cannot guarantee progress past this point.

Let us briefly discuss our assumptions. As for Assumption 1, it is quite natural as the GD step attempts to minimize the loss function which acts as a proxy for the accuracy on the data. However, Assumption 2 seems at odds with the fact that we assume the model to be initialized randomly. Intuitively, one might believe that a random initialization surely implies that Assumption 2 does not hold. While it is indeed the case that the model has high Kolmogorov complexity in this case, this is not necessarily the case for the function computed by the model. Recent literature suggests that randomly initialized models are biased towards simple functions rather than complicated ones (see Section 7.3 in [7] for a survey of recent work) and that the function learned by the network has low Kolmogorov complexity [8]. Furthermore, our results also generalize if we allow lossy compression. There is a vast literature on model compression (see [9] for a survey of recent literature), where the size of the model can be significantly compressed while preserving its accuracy. This also serves as a strengthening argument towards this assumption.

Note that assumptions (3)-(5) are rather mild. Assumption 3 (or some variation of it) is standard in the literature [3; 4; 5; 6], and discussions regarding numerical stability are generally omitted. Due to our use of Kolmogorov complexity we need to explicitly state that the L-smoothness assumption holds even when we consider some subset of the real numbers (i.e., floats). We discuss this in more detail in Section 2. In Assumption 4 we only require a polylogarithmic dependence on $n$, which is on par with batch sizes used in practice. Furthermore, it is well observed that when the batch size is too small SGD suffers from instability [10]. Finally, Assumption 5 is extremely mild, as our dependence on the size of the elements / model is only logarithmic when we apply this assumption. That is, even elements / model as large as $n^{1000}$ leave our analysis unchanged asymptotically.

To achieve our results we make use of entropy compression, first considered by Moser and Tardos [1; 2] to prove a constructive version of the Lovász local lemma (the name “entropy compression" was coined by Terrence Tao [11]). Roughly speaking, the entropy compression argument allows one to bound the running time of a randomized algorithm²²2We 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 a constant number at the beginning of the execution. by leveraging the fact that a random string of bits (the randomness used by the algorithm) is computationally incompressible (has high Kolmogorov 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 $t$ 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, it is possible to reconstruct all of the random bits used by the algorithm. We highly encourage readers unfamiliar with this argument to take a quick look at [12], which provides an excellent 1-page example.

We apply this approach to SGD with an added termination condition when the accuracy over the entire dataset is sufficiently high, thus termination in our case guarantees good accuracy. The randomness we compress are 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 it is possible to reconstruct these bits efficiently starting from the dataset $X$ and the model after executing $t$ epochs. The first step in allowing us to reconstruct the random bits of the permutation in each epoch is to show that under our L-smoothness assumption and a sufficiently small GD step, SGD is reversible. That is, if we are given a model $W_{i+1}$ and a batch $B_{i}$ such that $W_{i+1}$ results from taking a gradient step with model $W_{i}$ where the loss is calculated with respect to $B_{i}$, then we can uniquely retrieve $W_{i}$ using only $B_{i}$ and $W_{i+1}$. This means that if we can 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.

The crux of this paper is to show that our assumptions imply that at every epoch the batches can indeed be compressed. Let us consider two toy examples that provide intuition for our analysis. First, consider the scenario where, for every epoch, exactly in the “middle" of the epoch (after considering half of the batches for the epoch), our model achieves 100% accuracy on the set of all elements already considered so far during the epoch (elements on the “left") and 0% accuracy for the remaining elements (elements on the “right"). Let us consider a single epoch of this execution. We can express the permutation of the dataset by encoding two sets (for elements on the left and right), and two permutations for these sets. Given the dataset $X$ and the function computed by the model at the middle of the epoch, we immediately know which elements are on the left and which are on the right by seeing if they are classified correctly or not by the model (recall that $X$ contains data points and labels and that elements have unique IDs). Thus it is sufficient to encode only two permutations, each over $n/2$ elements. While naively encoding the permutation for the entire epoch requires $\lceil\log(n!)\rceil$ bits, we manage to make do with $2\lceil\log(n/2)!\rceil$. Using Stirling’s approximation ($\log(n!)=n\log(n/e)+O(\log n)$) and omitting logarithmic factors, we get that $\log(n!)-2\log((n/2)!)\approx n\log(n/e)-n\log(n/2e)=n$. Thus, we can save a linear number of bits using this encoding. To achieve the above encoding, we need the function computed by the model in the middle of the epoch. Assumption 2 guarantees that we can efficiently encode this function.

Second, let us consider the scenario where, in every epoch, just after a single GD step on a batch we consistently achieve 100% accuracy on the batch. Furthermore, we terminate our algorithm when we achieve 90% accuracy on the entire dataset. Let us consider some epoch of our execution, assume we have access to $X$, and let $W_{f}$ be the model at the end of the epoch. Our goal is to retrieve the last batch of the epoch, $B_{f}\subset X$ (without knowing the permutation of the data for the epoch). A naive approach would be to simply encode the indices in $X$ of the elements in the batch (we can sort $X$ by IDs). However, we can use $W_{f}$ to achieve a more efficient encoding. Specifically, we know that $W_{f}$ achieves 100% accuracy on $B_{f}$ but only 90% accuracy on $X$. Thus it is sufficient to encode the elements of $B_{f}$ using a smaller subset of $X$ (the elements classified correctly by $W_{f}$, which has size at most $0.9\left|X\right|$). This allows us to significantly compress $B_{f}$. Next, we can use $B_{f}$ and $W_{f}$ together with the reversibility of SGD to retrieve $W_{f-1}$. We can now repeat the above argument to compress $B_{f-1}$ 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 again result in a linear reduction in the number of bits required for the encoding.

In our analysis, we show generalized versions of the two scenarios above. First, we show that if at any epoch the accuracy of the model on the left and right elements differs significantly (we need not split the data down the middle anymore), we manage to achieve a meaningful compression of the randomness. Next, we show that if this scenario does not happen, then together with our local progress assumption, we manage to achieve slightly better accuracy on the batch we are trying to retrieve (compared to the set of available elements). This results in a compression similar to the second scenario. Either way, we manage to save a significant (linear in $n$) number of bits for every epoch, which allows us to use the entropy compression argument to bound our running time.

An excellent survey of recent work is given in [13], which we follow below. There has been a long line of research proving convergence bounds for SGD under various simplifying assumptions such as: linear networks [14; 15], shallow networks [16; 17; 18], etc. However, the most relevant results for this paper are the ones dealing with deep, overparameterized networks [3; 4; 5; 6]. All of these works make use of NTK (Neural Tangent Kernel)[19] and show 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 are quite large. For example, assuming a random weight initialization, [4] require width at least $n^{24}L^{12}$ and converges to a model with an $\epsilon$ error in $O(n^{6}L^{2}\log(1/\epsilon))$ steps w.h.p. The current best parameters are due to [6], which under random weight initialization, require width at least $n^{8}L^{12}$ and converge to a model with an $\epsilon$ error in $O(n^{2}L^{2}\log(1/\epsilon))$ steps w.h.p. Recent works [20; 21; 13] achieve a much improved width dependence (linear / quadratic) and running times, however, they require additional assumptions which make their results incomparable with the above. Specifically, in [20; 21] a special (non-standard) weight initialization is required, and in [13] convergence is shown for a non-standard activation unit.

Our results are not directly comparable with the above, mainly due to assumptions 1 and 2. However, if one accepts our assumptions, our analysis has the benefit of not requiring any specific network architecture. The convergences times are also essentially incomparable due to the dependence on $K(X)$. That is, $K(X)$ can be very small if the elements of $X$ are small and similar to each other, or very large if they are very large and contain noise (e.g., high definition images with noise). To the best of our knowledge, this is the first (conditional) global convergence guarantee for SGD for general, non-convex underparameterized models.

We first present some preliminary definitions in Section 2 followed by our main results in Section 3.

We analyze the classic SGD algorithm presented in Algorithm 1. One difference to note in our algorithm, compared to the standard implementation, is the termination condition when the accuracy on the dataset is sufficiently high. In practice the termination condition is not used, however, we only use it to prove that at some point in time the accuracy of the model is indeed sufficiently large. It is also possible to check this condition on a sample of a logarithmic number of elements of $X$ and achieve a good approximation to the accuracy w.h.p.

The Kolmogorov complexity of a string $x\in\{0,1\}^{*}$, denoted by $K(x)$, is defined as the size of the smallest prefix Turing machine which outputs this string. We note that this definition depends on which encoding of Turing machines we use. However, one can show that this will only change the Kolmogorov complexity by a constant factor [22]. Random strings have the following useful property [22]:

We also use the notion of conditional Kolmogorov complexity, denoted by $K(x\mid y)$. This is the length of the shortest prefix Turing machine which gets $y$ as an auxiliary input and prints $x$. Note that the length of $y$ does not count towards the size of the machine which outputs $x$. So it can be the case that $\left|x\right|\ll\left|y\right|$ but it holds that $K(x\mid y)<K(x)$. We can also consider the Kolmogorov complexity of functions. Let $g:\left\{0,1\right\}^{*}\rightarrow\left\{0,1\right\}^{*}$ then $K(g)$ is the size of the smallest Turing machine which computes the function $g$.

The following properties of Kolmogorov complexity will be of use [22]. Let $x,y,z$ be three strings:

• •

  Extra information: $K(x\mid y,z)\leq K(x\mid z)+O(1)\leq K(x,y\mid z)+O(1)$

• •

  Subadditivity: $K(xy\mid z)\leq K(x\mid z,y)+K(y\mid z)+O(1)\leq K(x\mid z)+K(y\mid z)+O(1)$

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\mid B)$ such that $A\subseteq B$, it holds that $K(A\mid B)\leq\lceil\log\binom{\left|B\right|}{\left|A\right|}\rceil+O(\log\left|B\right|)$. To see why, consider Algorithm 2.

In the algorithm $i_{A}$ is the index of $A$ when considering some ordering of all subsets of $B$ of size $\left|A\right|$. Thus $\lceil\log\binom{\left|B\right|}{\left|A\right|}\rceil$ bits are sufficient to represent $i_{A}$. The remaining variables $i,m_{A},m_{B}$ and any additional variables required to construct the set $C$ are all of size at most $O(\log\left|B\right|)$ and there is at most a constant number of them.

During our analysis, we often bound the Kolmogorov complexity of tuples of objects. For example, $K(A,P\mid B)$ where $A\subseteq B$ is a set and $P:A\rightarrow[\left|A\right|]$ is a permutation of $A$ (note that $A,P$ together form an ordered tuple of the elements of $A$). Instead of explicitly presenting a program such as Algorithm 2, we say that if $K(A\mid B)\leq c_{1}$ and $c_{2}$ bits are sufficient to represent $P$, thus $K(A,P\mid B)\leq c_{1}+c_{2}+O(1)$. 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 a permutation to Algorithm 2 and output an ordered tuple of elements rather than a set. Note that when representing a permutation of $A,\left|A\right|=k$, instead of using functions, we can just talk about values in $\lceil\log k!\rceil$. That is, we can decide on some predetermined ordering of all permutations of $k$ elements, and represent a permutation as its number in this ordering.

Our proofs make extensive use of binary entropy and KL-divergence. In what follows we define these concepts and provide some useful properties.

Entropy: For $p\in[0,1]$ we denote by $h(p)=-p\log p-(1-p)\log(1-p)$ the entropy of $p$. Note that $h(0)=h(1)=0$.

KL-divergence: For $p,q\in[0,1]$ let $D_{KL}(p\;\|\;q)=p\log\frac{p}{q}+(1-p)\log\frac{1-p}{1-q}$ be the Kullback Leibler divergence (KL-divergence) between two Bernoulli distributions with parameters $p,q$. We also state the following useful private case of Pinsker’s inequality: $D_{KL}(p\;\|\;q)\geq 2(p-q)^{2}$.

Let us state some useful bounds on the Kolmogorov complexity of sets.

We state the following Hoeffding bound for sampling without replacement.

One important thing to note is that if we have access to $\chi$ as a shuffled tuple (or shuffled array), then taking any subset of $k$ indices, is a random sample of size $k$ drawn from $\chi$ without repetitions. Furthermore, if we take some sample $Y$ from the shuffled population $\chi$ and then take a second sample $Z$ (already knowing $Y$) from the remaining set $\chi\setminus Y$, then $Z$ is sampled without repetitions from $\chi\setminus Y$.

First let us define some useful notations:

• •

  $\lambda_{i,j}=acc(W_{i,j},X)$. This is the accuracy of the model in epoch $i$ on the entire dataset $X$, before performing the GD step on batch $j$.

• •

  $\varphi_{i,j}=acc(W_{i,j},B_{i,j-1})$. This is the accuracy of the model on the $(j-1)$-th batch in the $i$-th epoch after performing the GD step on the batch.

• •

  $X_{i,j}=\bigcup_{k=1}^{j}B_{i,k}$ (note that $\forall i,X_{i,0}=\emptyset,X_{i,n/b}=X$). This is the set of elements in the first $j$ batches of epoch $i$. Let us also denote $n_{j}=\left|X_{i,j}\right|=jb$ (Note that $\forall j,i_{1},i_{2},\left|X_{i_{1},j}\right|=\left|X_{i_{2},j}\right|$, thus $i$ need not appear in the subscript).

• •

  $\lambda^{\prime}_{i,j}=acc(W_{i,j},X_{i,j-1}),\lambda^{\prime\prime}_{i,j}=acc(W_{i,j},X\setminus X_{i,j-1})$, where $\lambda^{\prime}_{i,j}$ is the accuracy of the model on the set of all previously seen batch elements, after performing the GD step on the $(j-1)$-th batch and $\lambda^{\prime\prime}_{i,j}$ is the accuracy of the same model, on all remaining elements ($j$-th batch onward). To avoid computing the accuracy on empty sets, $\lambda^{\prime}_{i,j}$ is defined for $j\in[2,n/b+1]$ and $\lambda^{\prime\prime}_{i,j}$ is defined for $j\in[1,n/b]$.

In our analysis we consider $t$ epochs of the SGD algorithm, where we bound $t$ later. Let us state the assumptions we make (later we discuss ways to further alleviate these assumptions).

1. 1.

   Local progress: There exists some constant $\beta^{\prime}$ such that $\forall i\in[t],\frac{b}{n}\sum_{j=2}^{n/b+1}(\varphi_{i,j}-acc(W_{i,j-1},B_{i,j-1}))>\beta^{\prime}\epsilon$. That is, we assume that in every epoch, the accuracy of the model on the batch after the GD step increases by an additive $\beta^{\prime}\epsilon$ factor on average. Let us denote $\beta=\beta^{\prime}\epsilon$ (we explain the reason for this parameterization in Section 3.1).

2. 2.

   Models compute simple functions: $\forall i\in[t],j\in[n/b],K(acc(W_{i,j},\bullet)\mid X)\leq\frac{n\beta^{3}}{512}$ (where $acc(W_{i,j},\bullet)$ is the accuracy function of the model with parameters $W_{i,j}$). This is actually a slightly weaker condition than bounding the Kolmogorov complexity of the function computed by the model. That is, given $X$ and the function computed by the model we can compute $acc(W_{i,j},\bullet)$, but not the other way around. For simplicity of notation, we assume that $W_{i,j}$ contains not only the model parameters, but also the architecture of the model and the indices $i,j$.

3. 3.

   $b\geq 8\beta^{-2}\ln^{2}(tn^{3})$. That is, the batch must be sufficiently large. After we bound $t$, we get that $b=\Theta(\beta^{-2}\log^{2}(n/\beta))$ is sufficient.

4. 4.

   $\forall x\in X,f_{x}$ is differentiable and L-smooth, even when taking numerical stability into account.

5. 5.

   $K(X)=n^{O(1)},d=n^{O(1)}$. That is, the size of the model and the size of every data point is at most polynomial in $n$. We note that the exponent can be extremely large, say $1000$, and this will only change our bounds by a constant.

Our goal is to use the entropy compression argument to bound the running time of the algorithm. That is, we show that if our assumptions hold for a consecutive number of $t$ epochs, if $t$ is sufficiently large then our algorithm must terminate. Let $r_{i}$ be the string of random bits representing the random permutation of $X$ at epoch $i$. As we consider $t$ epochs, let $r=r_{1}r_{2}\dots r_{t}$. Note that the number of bits required to represent an arbitrary permutation of $[n]$ is given by: $\lceil\log(n!)\rceil=n\log n-n\log e+O(\log n)=n\log(n/e)+O(\log n)$. Where in the above we used Stirling’s approximation. Thus, it holds that $|r|=t(n\log(n/e)+O(\log n))$ and according to Theorem 2.3, with probability at least $1-1/n^{2}$ it holds that $K(r)\geq tn\log(n/e)-O(\log n)$.

Our goal for the rest of the section is to show that if our assumptions hold, then in every epoch we manage to compress $r_{i}$, which in turn results in a compression of $r$, leading to an upper bound on $t$ due to the incompressibility of $r$. For the rest of the section, we assume that all of our assumptions hold and that the algorithm does not terminate within the first $t$ epochs. As discussed in the introduction, our proof consists of two cases. For the first case, we show that if at some point during the epoch $|\lambda^{\prime}_{i,j}-\lambda^{\prime\prime}_{i,j}|$ is sufficiently large, then $r_{i}$ can be compressed. For the second case, if $|\lambda^{\prime}_{i,j}-\lambda^{\prime\prime}_{i,j}|$ is small throughout the epoch and show that $r_{i}$ can be compressed by encoding every batch individually.

In the introduction, we considered the case where during the epoch the model achieves 100% accuracy on half the elements and 0% on the other half. Let us show a generalized version of this statement, where instead of considering the model during the middle of the epoch, we consider the model after seeing a $\eta$-fraction of the data. The statement below holds for an arbitrary difference in the accuracies of the model. Instead of considering $|\lambda^{\prime}_{i,j}-\lambda^{\prime\prime}_{i,j}|$ directly, we first show an auxiliary compression claim involving $|\lambda^{\prime}_{i,j}-\lambda_{i,j}|$ and $|\lambda^{\prime\prime}_{i,j}-\lambda_{i,j}|$. This will immediately allow us to derive the desired result for $|\lambda^{\prime}_{i,j}-\lambda^{\prime\prime}_{i,j}|$, and will also be useful later on. Let us state the following claim.

Note that in the above if $\eta=(j-1)b/n$ is too small or too large, we are unable to get a meaningful compression. Let us focus our attention on a sub-interval of $j\in[2,n/b-1]$ where we get a meaningful bound. Let us denote by $j_{s}=\lceil\beta n/8b\rceil+1,j_{f}=\lfloor(1-\beta/8)n/b\rfloor+1$ the start and finish indices for this interval. We state the following Corollary which completes the proof of the first case.