Title: ON THE TRAJECTORY OF STOCHASTIC GRADIENT DE-SCENT LEARNING IN THE INFORMATION PLANE

Abstract: Studying the evolution of information theoretic quantities during Stochastic Gradient Descent (SGD) learning of Artificial Neural Networks (ANNs) has gained popularity in recent years. Nevertheless, these type of experiments require estimating mutual information and entropy which becomes intractable for moderately large problems. In this work we propose a framework for understanding SGD learning in the information plane which consists of observing entropy and conditional entropy of the output labels of ANNs. Through experimental results and theoretical justifications it is shown that, under some assumptions, the SGD learning trajectories appear to be similar for different ANN architectures. First, the SGD learning is modeled as a Hidden Markov Process (HMP) whose entropy tends to increase to the maximum. Then, it is shown that the SGD learning trajectory appears to move close to the shortest path between the initial and final joint distributions in the space of probability measures equipped with the total variation metric. Furthermore, it is shown that the trajectory of learning in the information plane can provide an alternative for observing the learning process, with potentially richer information about the learning than the trajectories in training and test error.

1. INTRODUCTION:

How do information theoretic quantities behave during the training of ANNs? This question was addressed by Shwartz-Ziv & Tishby (2017) in an attempt to explain the learning through the lens of the information bottleneck method (Tishby et al., 1999) . In that work, the layers of an ANNs are considered random variables forming a Markov chain. The authors constructed a 2D information plane by estimating the mutual information values between hidden layers, inputs, and outputs of ANNs. Using this approach it was observed that the information bottleneck method provides an approximate explanation for SGD learning. In addition, their experiments showed the role of compression in learning. That initial paper motivated further work on this line of research (Saxe et al., 2018; Gabrié et al., 2018) . The main practical limitation of that type of experiments is that it requires estimating mutual information between high dimensional continuous random variables. This becomes prohibitive as soon we move to moderately large problems, such as the CIFAR-100 dataset, where the large ANNs are employed. Other works dealing with information theoretic quantities tend to have these experimental limitations. For instance, Russo & Zou (2015) ; Xu & Raginsky (2017) ; Asadi et al. (2018) used generic chaining techniques to show that generalization error can be upper bounded by the mutual information between the training dataset and output of the learning algorithm. Nevertheless, estimating that mutual information to verify those results experimentally becomes intractable. Furthermore, in our previous work (Anonymous, 2018) we defined a novel 2D information plane that only requires to estimate information theoretic quantities between the correct and estimated labels. Since these random variables are discrete and one-dimensional, this framework can be used to study learning in large recognition problems as well. Moreover, that work provides a preliminary empirical study on the behavior of those information theoretic quantities during learning along with some connections between error and conditional entropy.

In this work, we extend the experiments from Anonymous (2018) to more general scenarios and aim to characterize the observed behavior of SGD. Our main contributions are as follows:

• We define a 2D-information plane, inspired by the works of Shwartz-Ziv & Tishby (2017) , and use it to study the behavior of ANNs during SGD learning. The main quantities are entropy of the output labels and its conditional entropy given true labels.

• It is shown that if the learning is done perfectly and under some other mild assumptions, the entropy tends to increase to its maximum.

• It is additionally shown that SGD learning trajectory follows approximately the shortest path in the space of probability measures equipped with the total variation metric. The shortest path is characterized well by a Markov chain defined on probabilities of estimate labels conditioned on true labels. To that end we provide theoretical and experimental justifications for constructing a simple Markovian model for learning, and compare it with SGD through experiments. These experiments are conducted using various datasets such as MNIST (LeCun et al., 1998) , CIFAR-10/ CIFAR-100, spirals (Anonymous, 2018) , as well as different ANN architectures like Fully Connected Neural Networks (FCNNs), LeNet-5 (LeCun et al., 1999) , and DenseNet (Huang et al., 2017) .

• The trajectory, however, is not universal. Through a set of experiments, it is shown that SGD learning trajectory differs significantly for different learning strategies, noisy labels, overfitting, and underfitting. We show examples where this type of trajectories provide a richer view of the learning process than conventional training and test error, which allows us to spot undesired effects such as overfitting and underfitting.

The paper is organized as follows: Section 2 introduces the notation as well as elementary notions from information theory. Section 3 formulates learning as a trajectory on the space of probability measures, defines the notion of shortest learning path, and provides a connection to Markov chains. Section 4 constructs a simple Markov chain model for gradient based learning that moves along the shortest learning path. Finally, Section 5 performs an empirical evaluation of the proposed model.

2. SYSTEM MODEL:

Let x ∈ X be a random vector belonging to some set X of possible inputs. We assume that there exists a function, known as "oracle", that maps x to one of K ∈ N classes. Formally, there exists a deterministic mapping c : X → Y where Y = {0, . . . , K -1} is the set of possible classes. Then, let ỹ ∈ Y denote the random variable ỹ = c(x). One common assumption, that is present in popular datasets such as MNIST, CIFAR-10, CIFAR-100, and Imagenet, is that ỹ is uniformly distributed.

We assume this to be true throughout this paper. Note that the designer of the dataset has control over the marginal distribution of ỹ.

We model the effect of having error-prone labels, denoted by the random variable y, in the data by introducing discrete independent random noise z ∈ Y to ỹ in the form of modulo addition1 , that is y = ỹ ⊕ z ∈ Y. Let θ ∈ Θ be the vector, possibly random, containing of all tunable parameters in the hypothesis space Θ. Then a classifier is a deterministic function g : Θ × X → Y that aims to approximate c. Further, ŷ = g(θ, x) is defined to be the random variable of the label predicted by the classifier g(θ, •). Using this notation we define the three types of error: the dataset error p = P (y = ỹ), the test error ε = P (ŷ = y), the true error ε = P (ŷ = ỹ). A summary of this system model is provided in Figure 1 . We shortly review some elementary concepts from information theory such as entropy and mutual information. The entropy of a discrete random variable y ∈ Y is defined as2 H(y) = -y∈Y P (y = y) log P (y = y) = -E log P (y) .

The entropy is bounded by 0 ≤ H(y) ≤ log |Y| and it measures the amount uncertainty present in y. Similarly, the conditional entropy between two random variables y and ŷ is

H(y|ŷ) = -E log P (y|ŷ)

and it quantifies the uncertainty about y given that ŷ is known. Finally, the mutual information I(y; ŷ) between y and ŷ measures how much information does one random variable carry about the other. It may be defined in terms of entropies as

I(y; ŷ) = H(y) -H(y|ŷ) = H(ŷ) -H(ŷ|y) .

Moreover, the following proposition is a well-known result from information theory, known as Fano's inequality, that relates test error ε and conditional entropy.

Proposition 1. Fano's Inequality (Csiszàr & Körner (2011) , Lemma 3.8)

The value of H(y|ŷ) and H(ŷ|y) is upper bounded by a function of the expected error as

max{H(y|ŷ), H(ŷ|y)} ≤ Ψ(ε),

where the function Ψ : [0, 1] → R is defined as

Ψ(x) = x log(K -1) + h b (x), x ∈ [0, 1] and h b (x) = -x log(x) -(1 -x) log(1 -x)

is the binary entropy function.

This results provides an upper bound on conditional entropy in terms of ε, that is known to be sharp.

In the works of Feder & Merhav (1994) it has been shown that I(y; ŷ) gives an upper and lower bound on the minimal error3 between y and ŷ. In addition, the minimal error is minimized when I(y; ŷ) reaches its maximum. Therefore, learning can be modeled as finding θ such that I(y; ŷ) is maximized. This can be written in terms of entropies as

EQUATION

As in our previous work (Anonymous, 2018) we are interested on characterizing the trajectory in the 2D information plane, composed by H(ŷ) and H(ŷ|y), during the learning process of artificial neural networks (ANNs). In Figure 2 we observe that learning trajectory for the DenseNet architecture of 100 layers as it learns to classify data from the CIFAR-100 dataset, for p = 0. Intuitively, when solving equation 1, maximizing H(ŷ) is more related with the unsupervised component of learning since it does not depend y. On the other hand, keeping H(ŷ|y) low while H(ŷ) increases can be seen as the supervised component of equation 1. From this point of view it would be interesting to characterize the inflection point from which H(ŷ|y) starts decreasing, since it allows us to observe at which point SGD starts paying more attention to assigning labels correctly than to learn about the distribution of the input. One also may wonder if this increasing-decreasing trajectory is an accidental result for that occurs only on this particular experimental setup, or if it is a fundamental property of SGD. In Anonymous (2018) we showed that this behavior seems to appear regardless of the activation function employed (see Appendix C) on the spirals and MNIST dataset. Moreover, in further sections we provide a justification for this type of trajectory and show that it remains in other datasets. As z is independent, minimizing ε amounts to g(θ, •) learning c(•), regardless of the value of p (Angluin & Laird, 1988) . For more information about error and entropy relations in the presence of noisy labels see Appendix A. 

3. CONNECTION BETWEEN SGD AND MARKOV CHAINS:

In gradient based training of ANNs, the tunable parameters of the networks θ are changed in time by the gradient updates of the loss function, in order to minimize the learning error for a particular problem at hand. Let θ n ∈ Θ denote the tunable parameters of an ANN after n ≥ 1 training steps of SGD. The parameters are initialized as θ 0 , which can be random or deterministic. The set Θ can be seen as a high dimensional Euclidean space with the network parameter θ as its vector.

At the training step n, the outcome of the learning algorithm is captured by the random variable ŷn which is modulated by the network function g(θ n , •) applied to the random input data x, i.e., ŷn = g(θ n , x). Therefore the SGD learning gives rise the following sequence of random variables g(θ 0 , x), . . . , g(θ n , x), . . . .

As n grows large with a successful training, the sequence of random variables converges approximately to the true labels ỹ which itself follows a joint distribution with x. Note that the above random variables are coupled through the common random variable x and the sequence of parameter updates θ n .

If the probability distribution of ŷn is denoted by p n , a first question is to see how SGD methods modify p n on the space of probability measures defined on Y. As a consequence, one can determine the trajectory of H(ŷ n ), which will be plotted later. However it is additionally important in learning that the random variable ŷn approximates the true labels. Therefore, a second question would be how SGD methods change the joint distribution of (ŷ n , ỹn ). The answer could determine instead the trajectory of the conditional entropy H(ŷ n |ỹ n ). We first study the trajectory of H(ŷ n ).

The random variables ŷn are defined as g(θ n , x). Consider the sequence of random variables {θ n }. Let T denote the set of training samples (x, y) that are obtained prior to training and independently.

In addition, let T n be a subset of T that is used at the step n for SGD update. T n is assumed to be independent from (θ 0 , . . . , θ n-1 ) and it is either deterministic and known all n or randomly chosen at each step. These variations correspond to the variants of SGD.

In pure gradient based methods without momentum based techniques, the network parameters obey the following recursive relation

EQUATION

where f denotes the update rule of SGD. The model assumes that the SGD updates only depend on the parameters in the last step and the training set used in the current iteration. We can assume that T n are i. The transition probability of this Markov chain can be obtained only from f and T 1 . In that sense, the random process {θ n } is a homogeneous Markov chain. Throughout this work, it is assumed that the Markov chain {θ n } has a stationary distribution which corresponds to the learned ANN.

This proposition shows that SGD updates induce Markov property for weights of an ANN. The sequence of random variables ŷn = g(θ n , x) however is in general not a Markov chain, particularly because they are coupled through a common random variable x. Since we are interested in H(ŷ n ) and the distribution p n , these random variables can be decoupled by considering the random variables g(θ n , x n ) where x n are i.i.d. random variables with the same distribution as x. Note that the value of the entropy function remains unchanged after decoupling, namely

H(ŷ n ) = H(g(θ n , x n )).

The new sequence is a function of a Markov chain and i.i.d. random variables. The question whether the resulting sequence is a Markov chain has been addressed in Spreij (2001) ; Gurvits & Ledoux (2005) showing that ŷn is not a Markov chain in general unless certain conditions are met by the function g(•). Unfortunately the function g(•) is not injective and a non-injective function of a Markov chain is not Markov chain in general. However the random variable g(θ n , x n ) can be seen as the observation of the Markov process {θ n } through a noisy memoryless channel g(•, x n ). Therefore the random process {g(θ n , x n )} is a HMP. See Ephraim & Merhav (2002) for an information theoretic survey.

If the learning is done perfectly, the HMP {g(θ n , x n )} converges to the uniform distribution of correct labels. Since the random variables are discrete, entropy is a continuous function of the distribution p n . Therefore as the correct labels are uniformly distributed, the entropy H(ŷ n ) approaches its maximum log K. The instantaneous entropy H(ŷ n ) would converge monotonically to the entropy of the stationary distribution log K if the sequence were to be a Markov chain. This could explain the monotonicity of H(ŷ n ) in the experiments. Although the sequence not a Markov chain but it is indeed a HMP, the following proposition shows that the entropy is lower-bounded by an increasing function. Proposition 3. Suppose that the Markov process {θ n } with the probability distribution q n has a stationary distribution q. We have

H(ŷ n ) ≥ log |K| -D(q n q).

The proof follows from data processing inequality for Kullback-Leibler divergence and is found in Appendix B. Note that since {θ n } is a Markov process, D(q n q) is non-increasing.

4. SGD ON JOINT PROBABILITY MEASURES:

In the previous section, the non-decreasing property of H(ŷ n ) was investigated by modeling the network output as an HMP. In the same spirit let us define ỹn = c(x n ) to be i.i.d. realizations of ỹ. In the ideal situation where the network manages to learn successfully the true labels, we can say ŷn converges to ỹn almost surely4 . The joint distribution of (ŷ n , ỹn ) specifies a point on the space of probability measures on Y × Y. The task of learning consists tuning the parameters θ n in a way that the joint distribution approaches the distribution of (ỹ n , ỹn ). Therefore the gradient descent steps corresponds to a sequence of points, that is joint distributions of (ŷ n , ỹn ), on the space of probability measures on Y × Y with the end point ideally being the joint distribution of (ỹ n , ỹn ). In this section, we investigate the gradient descent algorithm by exploring the path it takes on the space of probability measures on Y × Y5 . The trajectory of conditional entropy H(ŷ n |ỹ n ) is determined for the trajectory of probability distributions on the space of joint measures.

However it is in general difficult to precisely characterize this path. Instead, one might ask how the gradient descent trajectory compares with a certain natural path on the space of distributions. A Note that the length is measured in this space using L 1 -norm. The following theorem guarantees that there is a shortest path on this space between probability measures and it can be traveled using a Markov chain.

Theorem 1. The shortest path between two probability measures µ and ν on the space of discrete probability measures P(Y × Y) is given by tµ + (1 -t)ν for t ∈ [0, 1]. Furthermore if the probability measures are represented by row vectors there is a transition matrix Π with the stationary distribution ν such that µ n = µΠ n is on the line segment between µ and ν and lim n→∞ µ n = ν.

Proof. Not that the space of probability distributions here is a bounded compact metric space with each two points connected by a rectifiable curve. The existence of shortest path follows from (Burago et al., 2001, Corollary 2.5.20,Theorem 2.5.23) . The transition matrix in Theorem 1 is given simply by

Π = (1 -α)I + α1 T ν

where 1 = (1, 1, . . . , 1).

To see the implication of previous theorem more precisely, consider conditional distributions P (ŷ n ∈ •|ỹ n = l) and let pl (n) ∈ R K be the following vector for l ∈ Y, that is

pl (n) = (P (ŷ n = 0|ỹ n = l), P (ŷ n = 1|ỹ n = l), • • • , P (ŷ n = K -1|ỹ n = l)) .

We use the compact notation P (n) ∈ R K×K for the matrix with p0 (n), . . . , pK-1 (n) as rows.

Note that, with the assumption that ỹn is uniformly distributed, the joint distribution of (ŷ n , ỹn ) is fully determined by P (n) since P (ŷ, ỹn ) = 1 K P (ŷ|ỹ n ). Suppose that the initialization θ 0 is such that g(θ 0 , •) initially maps all inputs to the same class (the first class is assumed for simplicity). Therefore the initial distribution matrix P (0) assumes no knowledge about the input and is given by

P (0) = 1e T 1 .

Ideally, in a learning algorithm, the matrix P (0) converges to an optimal distribution P * as n → ∞, that is P * = lim n→∞ P (n). If P (ŷ n = ỹn ) = 1, we have

P * = I .

Now that we set the initial distribution and stationary distributions, the following transition matrix provides a way to pass from the initial distribution to the stationary one. Definition 1. α-Simple Markov Learning Chain (α-SMLC) Given 0 < α < 1, the sequence of random pairs

{(ŷ n , ỹn )} is an α-SMLC if pl (n) = pl (n -1)Π l , for every n ≥ 0, l ∈ Y with Π l = 1e T l + α(I -1e T l ) , P (0) = 1e T l .

The above construction provides a different transition matrix for each pl (n) depending on l. The following theorem describes how an α-SMLC moves P (n) in the space of stochastic matrices. It actually shows this construction leads to points on the shortest path between the measures. Theorem 2. If (ŷ n , ỹn ) is the n-th random pair generated of an α-SMLC, then

EQUATION

Proof. c.f. Appendix B This shows that P (n) belongs to the continuous curve from equation 3, regardless of the choice of α. Moreover, let ŷ(t) be a version of ŷn parametrized by t ∈ [0, 1] such that its conditional distribution with ỹn corresponds to P (n) = (1 -t) P (0) + tI. Proposition 4. If {(ŷ n , ỹn )} is an α-SMLC and z follows the distribution

P (z = i) = 1 -p, i = 0 p K-1 , i ∈ {1, . . . , K -1} , then ∂H(ŷ(t)|y) ∂t = 1 K p log(1 -tp) + (1 -K + p) log(1 -t + t p K -1 ) -(K -1)(1 -p) log(t(1 -p)) -(K -1)p log(t p K -1 ) Proof. c.f. Appendix B Corollary 1. In the setting of Proposition 4, if p → 0 then H(ŷ(t)|y) has one maximum at t = 1 2 , H(ŷ( 1 2 )|y) = K-1 K log 2.

This result allows us to characterize the shape of the 2D curves (H(ŷ(t)), H(ŷ(t)|y)) for the above construction.

We now consider the implication of Markov assumption for error. Define ŷl n ∈ Y for all l ∈ Y to be random variables distributed according to the conditional probabilities P (ŷ l n = k) = P (g(θ n , x) = k|ỹ n = l) for all k ∈ Y. Note that, since ỹn is uniformly distributed, one can compute the joint distribution of (ŷ n , ỹn ) from the marginal distributions of ŷ0 n , . . . , ŷK-1 n and vice-versa. The following propositions shows that the Markov trajectory implies the reduction in error as well. Step (%) This last results shows that ε is non-increasing with n (i.e., no over-fitting), which is a desirable property for any learning algorithm. We will show through numerical simulations how a comparable behavior is observed for gradient descent methods.

5. EXPERIMENTS:

In this section we compare gradient based learning to the α-SMLC model through empirical simulations. First, we use the datasets where SGD is extremely successful at the classification task (ε ≈ 0), that is the MNIST dataset and the spirals dataset (Anonymous, 2018). The spirals dataset constitutes a 2D-spiral classification task constructed as

x = ( √ a + b) cos 2πa + 2π K ỹ , ( √ a + b) sin 2πa + 2π K ỹ , where a ∈ [0, 1], b ∈ [0, 0.1]

and ỹ ∈ {0, 1, . . . , K -1} are independent uniformly distributed random variables and K = 3. This dataset is divided into a training set of 50 000 samples and a test set of 2 000. Furthermore, we train the FCNN of Anonymous (2018) for the spirals dataset and use LetNet-5 (LeCun et al., 1999) for MNIST, achieving an average accuracy above 99% in both cases. For the sake of completeness we perform more experiments on the CIFAR-10 and CIFAR-100 datasets using the DenseNet architecture from Huang et al. (2017) with 40 and 100 layers respectively. FCNN and LetNet-5 are trained using Adam's optimizer, while DenseNet is trained with SGD. More detailed explanation about the experimental setup is provided in Appendix C. We estimate use a naive estimator of entropy which consists on computing the empirical distribution of (ŷ, y) and directly calculating entropy afterwards. This method is known to have an approximation error of K 2 /N (Miller, 1955) , which is good enough for our experiments since N is much larger than K 2 in our datasets. For cases with larger K one could use more sophisticated methods, such as Schürmann ( 2004); Archer et al. (2014) . For our experiments we introduce i.i.d. noise to the dataset labels before training according to P (z = 0) = 1 -p and P (z = 0) = p/(K -1). We keep fixed α = 0.85 for all simulations.

In Figure 3 we show the similarity between the α-SMLC model and ANNs on the spirals and MNIST dataset. This figure is obtained by averaging the entropy values over 100 realizations of training. We observe ANNs move along the information plane in a similar way as the α-SMLC model, and converge to the optimal distribution. In addition, we display the inflection point of H(y|ŷ) of the α-SMLC model for different values of p. Interestingly, as labels get noisier the inflection point occurs at a larger H(ŷ) value. This seems to be the case for SGD learning as well. This phenomena suggests that, as labels get noisier, a learning algorithm needs to know more about the input distribution before it can start assigning labels efficiently. Similar conclusions can be drawn form Figure 4 , which is also obtained by averaging over 100 realizations of training. An interesting result is that, regardless of the value of p, a good learning algorithm should converge to a point that lies on the upper bound provided by Fano's inequality. These Figures artificially mitigate the randomness induced by SGD on the trajectory by averaging over several realizations of training6 . How much SGD oscillates seems to depend on the experimental setup, such as the learning rate, dataset, and the structure of the classifier. See Appendix C for examples of highly oscillating trajectories.

Our last experiment consists on investigating how underfitting and overfitting affects the trajectory of SGD. To that end in Figure 5 (a) we include an 1 norm regularization term into the loss function (details in Appendix C) controlled by a parameter λ. As expected for sufficiently small λ the minimum error is attained. Interestingly, as we induce underfitting by increasing this regularization coefficient the obtained models move away from Fano's bound. This naturally leads to increased error values. On the other hand, in Figure 5 (b) we increase the number of parameters of FCNN and reduce the dataset size in order to induce overfitting (details in Appendix C). While overfitting leads to larger error as well as underfitting, it can be distinguished by its trajectory in the entropy-error plane. Underfitting seems to push models away from Fano's bound while overfitting happens when an ANN is at the bound. This experiment shows that the information plane provides a richer view beyond train and test error that allow us to observe effects that were previously hidden. Further understanding about desired trajectories is interesting since it may allow practitioners to monitor models during training, spot undesired behaviors, and possibly tune hyperparameters accordingly.

A COLLECTION OF RESULTS FOR LEARNING WITH RANDOM LABELS:

For ε < 1-1 K , proposition 1 can be written as a lower bound on ε through the following Proposition of Anonymous (2018). Proposition 6. (Anonymous, 2018) 

Φ(H(z)) ≤ ε, where Φ : [0, log |K|] → [0, 1-1 K ] is the inverse function of Ψ in the interval [0, 1 -1 K ].

Proof. For independent noise z, we have

H(y|ŷ) ≥ H(y|ŷ, ỹ) = H(z|ŷ, ỹ) = H(z).

By Proposition 1, it follows that

H(z) ≤ Ψ(ε). Applying the inverse Φ(x), x ∈ [0, 1-1 K ], completes the proof.

In Anonymous (2018) it is shown that this bound is sharp when z is distributed such that Φ(H(z)) = p, thus p ≤ ε. We generalize this result in the following theorem for an arbitrary distribution of z, under some mild conditions, and show that p ≤ ε is in fact a sharp lower bound for arbitrary z. Lemma 1. Let z ∈ Y be a random variable with P (z = 0) = 1 -p, then

H(z) ≤ Ψ(p) .

Proof. Let us define β k P (z = k) and the auxiliary random variable z ∈ {1, . . . , K -1} with

P (z = k) = β k /p for all k = 1, . . . , K -1. H(z) = -(1 -p) log(1 -p) - K-1 k=1 β k log β k = -(1 -p) log(1 -p) -p K-1 k=1 β k p log β k p p = -(1 -p) log(1 -p) -p K-1 k=1 β k p log p -p K-1 k=1 β k p log β k p = -(1 -p) log(1 -p) - K-1 k=1 β k log p + pH(z) = -(1 -p) log(1 -p) -p log p + pH(z) = h b (p) + pH(z) ≤ h b (p) + p log(K -1) = Ψ(p) Theorem 3. If P (z = 0) = 1 -p and P (z = 0) > P (z = k) for all k = 1, . . . , K -1, then p ≤ ε ,

and equality is attained if and only if P (ŷ = ỹ) = 1.

Proof. of Theorem 3 For the sake of notation let us define

δ k P (ŷ = ỹ ⊕ k) β k P (z = k) for all k ∈ {0, . . . , K -1} β max max k=1,...,K-1 β k .

From Proposition 1 we know that ε ≥ Φ(H(z)). Since Ψ is an increasing function in the interval [0, 1 -1 K ] and Φ is its inverse in that interval, we have that Φ is an increasing function as well. From Lemma 1 (c.f. Appendix B) we know that H(z) ≤ Ψ(p), this leads to

Φ(H(z)) ≤ Φ(Ψ(p)) = p .

Then, if the bound from Proposition 1 were to be sharp, ε could reach values strictly lower than p. We will show that this is not possible.

EQUATION

If ε < p we obtain (1 -p) < 1 -ε ≤ (1 -p) which is a contradiction, hence it must hold that ε ≥ p.

Finally, if ε = p then equation 10 yields

1 -p ≤ (1 -p)δ 0 + β max (1 -δ 0 ) .

Since β max < (1 -p), this inequality holds if and only if δ 0 = 1, that is P (ŷ = ỹ) = 1.

This theorem shows that the minimum expected error ε can only be attained if g(θ, •) manages to denoise the labels, hence ε = 0. We extend this result by deriving bounds for ε, given ε and p, in the following theorem. Theorem 4. (Angluin & Laird, 1988) Given ε < 1 -1 K and p < 1 2 , if P (z = 0) = 1 -p, and

P (z = k) < 1 2 for all k = 1, . . . , K -1, then ε is bounded by ε -p 1 -p ≤ ε ≤ ε -p 1 -2p .

Proof. of Theorem 4

EQUATION

) ε ≤ (1 -p) -(1 -ε) (1 -p) -β max ≤ (1 -p) -(1 -ε) (1 -p) -p = ε -p 1 -2p . Applying K-1 k=1 δ k β k ≥ 0 in equation 13 leads to 1 -ε ≥ (1 -p)(1 -ε) thus (1 -p) -(1 -ε) (1 -p) ≤ ε ⇒ ε -p 1 -p ≤ ε,

which completes the proof.

Corollary 3. If p < 1 2 , ε < 1 -1 K , and ε-p 1-2p < 1 -1 K then max{H(ỹ|ŷ), H(ŷ|ỹ)} ≤ Ψ( ε -p 1 -2p ) .

Proof. Since Ψ is an increasing function in the interval [0, 1 -1 K ], the proof follows from applying Theorem 4 on Proposition 1.

In information theory there is a result of this kind, known as Mrs. Gerber's Lemma (MGL), that does not require knowledge about p and ε. MGL provides an upper bound on H(ỹ|ŷ) given H(y|ŷ) for the case of K = 2. This result also states that the minimum H(y|ŷ) is attained when H(ỹ|ŷ) = 0. Since we assumed ỹ to be uniformly distributed, this corresponds to ε = 0, up to permutation ambiguities. Generalizing MGL for arbitrary K is still an open question in information theory. Nevertheless, Jog & Anantharam (2014) successfully proved MGL for the cases where K is a power of 2. We summarize that result in the following proposition. Proposition 7. Generalized Mrs. Gerber's Lemma for We have derived inequalities that relate entropies and error values. Then we showed that in the presence of corrupted labels, the best g(θ, •) can do for minimizing ε is to learn c, regardless of the value of p.

K = 2 n (Jog & Anantharam, 2014) f 2 n (ỹ, z) = min H(ỹ|ŷ)=ỹ,H(z)=z H(ỹ ⊕ z|ŷ) with f 2 n (ỹ, z) = f 2 (ỹ -k log 2, z -k log 2) + k log 2 if k log 2 ≤ ỹ, z ≤ (k + 1) log 2, max(ỹ, z) otherwise where f 2 (x, y) = h(h -1 (x) h -1 (y))

B DEFERRED PROOFS:

Proof of Proposition 3: The proof follows from the following general theorem. Theorem 5. Let {y n } be an HMP defined as the observation of a Markov process {x n } through an arbitrary stationary memoryless channel with values in the state space Y. Suppose that the probability distributions on the respective state spaces of {x n } and {y n } are given by {q n } and {p n } with the stationary distribution q and p. Then D(p n p) ≤ log D(q n q).

Proof. Based on the assumption above, x n and y n are related according to the conditional distribution characterized by the conditional probabilities {r(•|x) : x ∈ X}. Denote the joint distribution of x n and y n by µ n defined on X × Y and given by q n (x) × r(•|x). The stationary joint distribution µ is defined by q × r. Using the chain rule (Cover & Thomas, 2006, Theorem 2.5 .3), we have: D(µ n µ) = D(q n q) + D(r r) = D(q n q). On the other hand, the chain rule and the non-negativity of Kullback-Leibler divergence shows that: D(µ n µ) ≥ D(p n p), which implies the theorem. l = 0, . . . , K -1. Then for uniformly distributed y, and z distributed according to equation 4, we can express this relation in matrix form as

P (t) = ((1 -p - p K -1 )I + p K -1 11 T )

circular convolution matrix of P (z) P (t) .

Therefore, the (i, j)-th element of P (t) is denoted as P i,j (t) and given by P i,j (t) = e T i P (t)e j = (1 -t)e T 1 e j + t(1 -p -p K -1 )e T i e j + t p K -1 .

Differentiating P i,j (t) with respect to t yields

∂P i,j (t) ∂t = -e T 1 e j + (1 -p - p K -1 )e T i e j + p K -1 .

For particular choices of i, j these expressions boil down to

P i,j (t) =          1 -t + t(1 -p), j = 1, i = j 1 -t + t p K-1 , j = 1, i = j t(1 -p), j = 1, i = j t p K-1 , j = 1, i = j and ∂P i,j (t) ∂t =          -p, j = 1, i = j p K-1 -1, j = 1, i = j 1 -p, j = 1, i = j p K-1 , j = 1, i = j .

Finally, we make use of these to derive a closed form expression for H(ŷ(t)|y) ∂t , that is

H(ŷ(t)|y) ∂t = ∂ ∂t   - K j=1 1 K K i=1 P i,j (t) log P i,j (t)   = - 1 K K j=1 K i=1 ∂P i,j (t) ∂t (1 + log P i,j (t)) = - 1 K 1 j=1 i=j ∂P i,j (t) ∂t (1 + log P i,j (t)) - 1 K 1 j=1 i =j ∂P i,j (t) ∂t (1 + log P i,j (t)) - 1 K K j=2 i=j ∂P i,j (t) ∂t (1 + log P i,j (t)) - 1 K K j=2 i =j ∂P i,j (t) ∂t (1 + log P i,j (t)) = 1 K p log(1 -tp) + 1 K (K -1)( p K -1 -1)(1 + log(1 -t + t p K -1 )) - 1 K (K -1)(1 -p)(1 + log(t(1 -p))) - 1 K (K -1)p(1 + log(t p K -1 )) 1 K p -(K -1)( p K -1 -1) -(K -1)(1 -p) -(K -1)p =0 = 1 K p log(1 -tp) + (1 -K + p) log(1 -t + t p K -1 ) -(K -1)(1 -p) log(t(1 -p)) -(K -1)p log(t p K -1

) .

Remark: For p → 0 we now that the maximum the curve is at t = 1 2 since lim p→0 H(ŷ(t)|y) ∂t 

! = 0 ⇒ 1 K [(1 -K) log(1 -t) -(1 -K) log t] = 0 ⇒ log 1 -t t = 0 ⇒ t = 1 2 .

C EXPERIMENTAL DETAILS AND COMPLEMENTARY EXPERIMENTS:

A fully connected ANN with four hidden layers of five neurons each, as FCNN, is trained on the spirals dataset. For the MNIST dataset, the popular convolutional network called LeNet-5 LeCun et al. (1999) is used. To train these networks we let the learning rate γ ∈ R start at a given γ max ∈ R and then decay by 40% per epoch until reaching some given minimum learning rate γ min < γ max , that is γ = max{γ max 0.6 epoch , γ min }. For the CIFAR-10 dataset we train a 100 layer DenseNet architecture as done in Huang et al. (2017) , but we stop the training after 10 epochs instead of the original 300 used by the authors. The different configurations used for these experiments are summarized in Table 1 . For instance, Figure 2 shows 1 realization of SGD training for DenseNet on CIFAR-100. In that figure we observe a rather stable trajectory, with not much oscillation. However, in Figure 8 we average over 2 realizations of SGD learning for DenseNet on CIFAR-10 and obtain highly oscillating trajectories. As expected, both trajectories follow a similar behavior as the α-SMLC model.

In Figure 5 (a) the same model as in Figure 3 is used but an additional regularization term is added to the loss function, that is λ w 1 where w is a vector containing all the weights in the network.

In Figure 5 (b) a FCNN with a single hidden layer of size 100, and tanh activations, is used and the dataset sizes are reduced according to 3. Other parameters are γ max = 10 -1 , γ max = 10 -2 , and the number of epochs is 10 000. 

:

We use ⊕ to denote the modulo K addition.

In this paper we assume log to be the natural logarithm.

The minimal error is the error obtained by a maximum likelihood classifier that predicts y from ŷ.

A weaker notion of convergence can be used although this choice is not crucial for the next results.

The problem of finding the optimal way to change the distribution is connected to the problem of optimal transport. We would like to thank (removed for anonymity) for mentioning this connection.

The realizations that did not converge are discarded.

Figures and Tables:

Figure 1: System model.

Figure 2: Learning trajectory of DenseNet on the CIFAR-100 dataset. The markers in the black dashed lines represent the ideal values of H(y), H(ŷ|y) and ε when ε = 0. (a): The dashed lines correspond to the maximum entropy value. (b): The dashed lines are the upper bound given by Fano's inequality.

Figure 3: Experiments for FCNN and LeNet-5. This figures follow the same format as Figure 2(a). The shape of the makers differentiate between different values of p. For the α-SMLC model the white star shows the inflection point of H(ŷ|y) and α = 0.85.

Figure 4: Experiments for FCNN and LeNet-5. This figures follow the same format as Figure 2(b), with α = 0.85. The shape of the makers differentiate between different values of p.

Figure 5: Experiments for FCNN on the spirals dataset. This figures follow the same format as Figures 3 and 4.

and k is an arbitrary positive integer and a b a(1 -b) + b(1 -a).

Figure 7: Information plane trajectory during the learning process (Anonymous, 2018).

Simulation Parameters for Figure7(Anonymous, 2018). The models with highest accuracy are used in the main paper.

Table content: <table><tr><td colspan="4">Dataset Activation Batch Size γ max</td><td colspan="2">γ min Test Accuracy</td></tr><tr><td/><td>tanh</td><td>128</td><td colspan="2">10 -1 10 -2</td><td>99.7%</td></tr><tr><td>Spirals</td><td>sigmoid</td><td>128</td><td colspan="2">10 -1 10 -5</td><td>99.6%</td></tr><tr><td/><td>ReLU</td><td>700</td><td colspan="2">10 -1 10 -5</td><td>97.8%</td></tr><tr><td/><td>tanh</td><td>128</td><td colspan="2">10 -2 10 -2</td><td>97.1%</td></tr><tr><td>MNIST</td><td>sigmoid</td><td>128</td><td colspan="2">10 -2 10 -4</td><td>96.3%</td></tr><tr><td/><td>ReLU</td><td>128</td><td colspan="2">10 -2 10 -4</td><td>99.1%</td></tr><tr><td colspan="6">Table 2: Simulation Parameters for DenseNet on CIFAR datasets Dataset Activation Batch Size γ max γ min Test Accuracy</td></tr><tr><td>CIFAR-10</td><td>ReLU</td><td>64</td><td colspan="2">10 -1 10 -1</td><td>80.2%</td></tr><tr><td>CIFAR-100</td><td>ReLU</td><td>64</td><td colspan="2">10 -1 10 -1</td><td>80.2%</td></tr></table>

Dataset Sizes for Figure 5(b)

Table content: <table><tr><td>p</td><td>Dataset Size</td></tr><tr><td>0.1</td><td>200</td></tr><tr><td>0.2</td><td>400</td></tr><tr><td>0.4</td><td>1000</td></tr></table>

Peer review (iclr2019):
 In summary, this paper does the following: - The initial problem is to analyze the trajectory of SGD in training ANNs in the space of P of probability measures on Y .times Y. This problem is interesting, but difficult. - the paper constructs a Markov chain that follows a shortest path in TV metric on P (the .alpha SMLC) - through experiments, the paper shows that the trajectories of SGD and .alpha-SMLC have similar conditional entropy. My issues with this paper are: a/ The main result is a simulation. How general is this? Could it depend on the dataset? Could you provide some intuition or prove that for certain dataset, these two trajectories are the same (or very close)? b/ Meaning of this trajectory. This is not the trajectory in P, it is the trajectory of the entropies. In general, is there an intuitive explanation on why these trajectories are similar? And what does it mean -- for example, what would be a possible implication for training SGD? Could it be that all learning methods will have this characteristic parabolic trajectory for entropies? c/ The theoretical contribution is minor: both the techniques and results quoted are known. Overall, I think the paper lacks a take-away. It is an interesting observation that the trajectory of .alpha-SMLC is similar to that of SGD in these plots, but the authors have not made a sufficient effort to interpret this.