Title: STOCHASTIC MIRROR DESCENT ON OVERPARAME-TERIZED NONLINEAR MODELS

Abstract: Most modern learning problems are highly overparameterized, meaning that the model has many more parameters than the number of training data points, and as a result, the training loss may have infinitely many global minima (in fact, a manifold of parameter vectors that perfectly interpolates the training data). Therefore, it is important to understand which interpolating solutions we converge to, how they depend on the initialization point and the learning algorithm, and whether they lead to different generalization performances. In this paper, we study these questions for the family of stochastic mirror descent (SMD) algorithms, of which the popular stochastic gradient descent (SGD) is a special case. Recently it has been shown that, for overparameterized linear models, SMD converges to the global minimum that is "closest" (in terms of the Bregman divergence of the mirror used) to the initialization point, a phenomenon referred to as implicit regularization. Our contributions in this paper are both theoretical and experimental. On the theory side, we show that in the overparameterized nonlinear setting, if the initialization is close enough to the manifold of global optima, SMD with sufficiently small step size converges to a global minimum that is approximately the closest global minimum in Bregman divergence, thus attaining approximate implicit regularization. For highly overparametrized models, this closeness comes for free: the manifold of global optima is so high dimensional that with high probability an arbitrarily chosen initialization will be close to the manifold. On the experimental side, our extensive experiments on the MNIST and CIFAR-10 datasets, using various initializations, various mirror descents, and various Bregman divergences, consistently confirms that this phenomenon indeed happens in deep learning: SMD converges to the closest global optimum to the initialization point in the Bregman divergence of the mirror used. Our experiments further indicate that there is a clear difference in the generalization performance of the solutions obtained from different SMD algorithms. Experimenting on the CIFAR-10 dataset with different regularizers, 1 to encourage sparsity, 2 (yielding SGD) to encourage small Euclidean norm, and 10 to discourage large components in the parameter vector, consistently and definitively shows that, for small initialization vectors, 10 -SMD has better generalization performance than SGD, which in turn has better generalization performance than 1 -SMD. This surprising, and perhaps counter-intuitive, result strongly suggests the importance of a comprehensive study of the role of regularization, and the choice of the best regularizer, to improve the generalization performance of deep networks.
Which global minima do these algorithms converge to? And what properties do they have?
In this paper, we answer this question for the SGD algorithm, and more generally, for the family of stochastic mirror descent (SMD) algorithms, which includes SGD as a special case. For any choice of potential function, there is a corresponding mirror descent algorithm. We show that, for overparameterized nonlinear models, if one initializes close enough to the manifold of parameter vectors that interpolates the data, then the SMD algorithm for any particular potential converges to a global minimum that is approximately the closest one to the initialization, in Bregman divergence corresponding to the potential. In highly overparameterized models, this closeness of the initialization comes for free, something that is occasionally referred to as "the blessing of dimensionality." For the special case of SGD, this means that it converges to a global minimum which is approximately the closest one to the initialization in the usual Euclidean sense.
We perform extensive systematic experiments with various initial points and various mirror descent algorithms for the MNIST and CIFAR-10 datasets using standard off-the-shelf deep neural network architectures for these datasets with standard random initialization, and we measure all the resulting pairwise Bregman divergences. We found that every single result is exactly consistent with the above theory. Indeed, in all our experiments, the global minimum achieved by any particular mirror descent algorithm is the closest, among all other global minima obtained by other mirrors and other initializations, to its initialization in the corresponding Bregman divergence. In particular, the global minimum obtained by SGD from any particular initialization is closest to the initialization in Euclidean sense, both among the global minima obtained by different mirrors and among the global minima obtained by different initializations. This result, proven theoretically and backed up by extensive experiments, further implies that, even in the absence of any explicit regularization, these algorithms perform an implicit regularization. In particular, it implies that, when initialized around zero, SGD acts as an 2 regularizer. Similarly, by choosing other mirrors, one obtains different forms of implicit regularization (such as 1 or ∞ ), which may have different performances on test data. This raises the question How well do different mirrors perform in practice?
Perhaps, one might expect an 1 regularizer to perform better, due to the fact that it promotes sparsity, and "pruning" in neural networks is believed to be helpful for generalization. On the other hand, one may expect SGD ( 2 regularizer) to work best among different mirrors, because typical architectures have been tuned for and tailored to SGD. We run experiments with four different mirror descents, i.e., 1 (sparse), 2 (SGD), 3 , and 10 (as a surrogate for ∞ ), on a standard off-the-shelf deep neural network architecture for CIFAR-10, namely ResNet-18. Somewhat counter-intuitively, our results for test errors of different mirrors consistently and definitively show that the 10 regularizer performs better than the other mirrors including SGD, while 1 consistently performs worse. This flies in the face of the conventional wisdom that sparser weights (which are obtained by an 1 regularizer) generalize better, and suggests that ∞ , which roughly speaking penalizes all the weights uniformly, may be a better regularizer for deep neural networks.

1. INTRODUCTION:

Deep learning has demonstrably enjoyed a great deal of success in a wide variety of tasks (Amodei et al., 2016; Graves et al., 2013; Krizhevsky et al., 2012; Mnih et al., 2015; Silver et al., 2016; Wu et al., 2016; LeCun et al., 2015) . Despite its tremendous success, the reasons behind the good performance of these methods on unseen data is not fully understood (and, arguably, remains somewhat of a mystery). While the special deep architecture of these models seems to be important to the success of deep learning, the architecture is only part of the story, and it has been now widely recognized that the optimization algorithms used to train these models, typically stochastic gradient descent (SGD) and its variants, play a key role in learning parameters that generalize well.

Since these deep models are highly overparameterized, they have a lot of capacity, and can fit to virtually any (even random) set of data points (Zhang et al., 2016) . In other words, these highly overparameterized models can "interpolate" the training data, so much so that this regime has been called the "interpolating regime" (Ma et al., 2018b) . In fact, on a given dataset, the loss function typically has (infinitely) many global minima, which however can have drastically different generalization properties (many of them perform very poorly on the test set). Which minimum among all the possible minima we converge to in practice is determined by the initialization and the optimization algorithm that we use for training the model.

Since the loss functions of deep neural networks are non-convex-sometimes even non-smooth-in theory, one may expect the optimization algorithms to get stuck in local minima or saddle points. In practice, however, such simple stochastic descent algorithms almost always reach zero training error, i.e., a global minimum of the training loss (Zhang et al., 2016; Lee et al., 2016) . More remarkably, even in the absence of any explicit regularization, dropout, or early stopping (Zhang et al., 2016) , the global minima obtained by these algorithms seem to generalize quite well (contrary to some other global minima). It has been also observed that even among different optimization algorithms, i.e., SGD and its variants, there is a discrepancy in the solutions achieved by different algorithms and how they generalize (Wilson et al., 2017) . Therefore, it is important to ask

1.1. RELATED WORK:

There have been many efforts in the past few years to study deep learning from an optimization perspective, e.g., (Achille & Soatto, 2017; Chaudhari & Soatto, 2018; Shwartz-Ziv & Tishby, 2017; Allen-Zhu et al., 2019; Oymak & Soltanolkotabi, 2019; Azizan & Hassibi, 2019; Ma et al., 2018b; Du et al., 2018; Li & Liang, 2018; Cao & Gu, 2019 ). While it is not possible to review all the contributions here, we comment on the ones that are most closely related to ours and highlight the distinctions between our results and those.

Many recent papers have studied the convergence of the (S)GD algorithm in the so-called "overparameterized" setting (or "interpolating" regime), which is common in deep learning (Oymak & Soltanolkotabi, 2019; Allen-Zhu et al., 2019; Soltanolkotabi et al., 2017; Ma et al., 2018b) . All these works, similar to ours, assume that the initialization is close to the solution space (of global minima), which is a reasonable assumption in highly overparameterized models, as we argue in Section A.4 of the supplementary material. However, our results are more general because they extend to SMD. Furthermore, even for the case of SGD, our results are stronger than those in the literature, in the sense that not only do we show convergence to a global minimum, but we also show that the weight vector we converge to, w ∞ , say, is close to the interpolating weight vector closest to the initialization, w * , say. Denoting the initialization by w 0 , Oymak & Soltanolkotabi (2019) showed that for SGD, w ∞ -w 0 is bounded by a constant factor of w * -w 0 . Our Theorem 4 shows the much stronger statement that w ∞ -w 0 = w * -w 0 + o( w * -w 0 ). We further show that w ∞ and w * are very close to one another, viz. w ∞ -w * 2 = o( w * -w 0 )), something that could not be inferred from the previous work.

There exist a number of results that characterize the implicit regularization properties of different algorithms in different contexts (Neyshabur et al., 2017; Ma et al., 2018a; Gunasekar et al., 2017; 2018a; Soudry et al., 2017; Gunasekar et al., 2018b; Azizan & Hassibi, 2019; Mianjy et al., 2018) . The closest ones to our results, since they concern mirror descent, are the works of (Gunasekar et al., 2018a; Azizan & Hassibi, 2019) . The authors in (Gunasekar et al., 2018a) consider linear overparameterized models, and show that if SMD happens to converge to a global minimum, then that global minimum will be the one that is closest in Bregman divergence to the initialization, a result they obtain by examining the KKT conditions. However, they do not provide any conditions for convergence and whether SMD converges with a fixed step size or not. Azizan & Hassibi (2019) also study linear models, but derive conditions on the step size for which SMD converges to the aforementioned global minimum. Our results extend the aforementioned to nonlinear overparametrized models, and show that, for small enough fixed step size, and for initializations close enough to the space of interpolating solutions, SMD converges to a global minimum, something which had not been shown in any of the previous work. Assuming every data point is revisited often enough, the convergence we establish is deterministic. Finally, we show that the solution we converge to exhibits approximate implicit regularization, something that was not not known for nonlinear models.

The remander of the paper is organized as follows. In Section 2, we review the family of mirror descent algorithms and briefly revisit the linear overparameterized case. Section 3 provides our main theoretical results, which are (1) convergence of SMD to a global minimum, and (2) proximity of the obtained global minimum to the closest one from the initialization in Bregman divergence. Our proofs are remarkably simple and are based on a powerful fundamental identity that holds for all SMD algorithms in a general setting. In Section 4, we provide our experimental results, which consists of two parts, (1) testing the theoretical claims about the distances for different mirrors and different initializations, and (2) assessing the generalization properties of different mirrors. The proofs of the theoretical results and more details on the experiments are relegated to the supplementary material.

2. BACKGROUND AND WARM-UP:

Let us denote the training dataset by {(x i , y i ) : i = 1, . . . , n}, where x i ∈ R d are the inputs, and y i ∈ R are the labels. The model (which can be, e.g., linear, a deep neural network, etc.) is defined by the general function f (x i , w) = f i (w) with some parameter vector w ∈ R p . Since typical deep models have a lot of capacity and are highly overparameterized, we are particularly interested in the overparameterized (or so-called interpolating) regime, where p > n (often p n). In this case, there are many parameter vectors w that are consistent with the training data points. We denote the set of these parameter vectors by

EQUATION

This a high-dimensional set (e.g. a (p -n)-dimensional manifold) in R p and depends only on the training data {(x i , y i ) : i = 1, . . . , n} and the model f (•, •).

The total loss on the training set (empirical risk) can be expressed as

L(w) = n i=1 L i (w), where L i (•) = (y i , f (x i , w))

is the loss on the individual data point i, and (•, •) is a differentiable non-negative function, with the property that (y i , f (x i , w)) = 0 iff y i = f (x i , w). Often (y i , f (x i , w)) = (y i -f (x i , w)), with (•) convex and having a global minimum at zero (such as square loss, Huber loss, etc.). In this case, L(w)

= n i=1 (y i -f (x i , w)).

W is the set of global minima, and every parameter vector w in W renders the loss on each data point zero, i.e., L i (w) = 0 ∀i. The loss function is often attempted to be minimized by stochastic gradient descent (SGD):

w i = w i-1 -η∇L i (w i-1 ), i ≥ 1

(2) assuming the data is indexed randomly. We use one index i for both the loss and the parameter vector at step i (for i > n, one can cycle through the data, or select them at random, etc.).

2.1. STOCHASTIC MIRROR DESCENT:

Mirror descent, first introduced by Nemirovski & Yudin (1983) , is one of the most widely used families of algorithms for optimization (Beck & Teboulle, 2003; Cesa-Bianchi et al., 2012; Zhou et al., 2017) , which includes the popular gradient descent as a special case. Consider a strictly convex differentiable function ψ(•), called the potential function. Then updates for stochastic mirror descent (SMD) are defined as ∇ψ(w i ) = ∇ψ(w i-1 ) -η∇L i (w i-1 ).

(3)

Note that, due to the strict convexity of ψ(•), the gradient ∇ψ(•) defines an invertible map, so the recursion in (3) yields a unique w i at each iteration, and thus is a well-defined update, i.e., w i = ∇ψ -1 (∇ψ(w i-1 ) -η∇L i (w i-1 )) . Compared to classical SGD, rather than update the weight vector along the direction of the negative gradient, the update is done in the "mirrored" domain determined by the invertible transformation ∇ψ(•). Mirror descent was originally conceived to exploit the geometrical structure of the problem by choosing an appropriate potential. Note that SMD reduces to SGD when ψ(w) = 1 2 w 2 , since the gradient ∇ψ(•) is simply the identity map. Alternatively, the update rule (3) can be expressed as

EQUATION

where D ψ (w, w i-1 ) := ψ(w) -ψ(w i-1 ) -∇ψ(w i-1 ) T (w -w i-1 ) (5) is the Bregman divergence with respect to the potential function ψ(•). Note that D ψ (•, •) is nonnegative, convex in its first argument, and that, due to strict convexity, D ψ (w, w ) = 0 iff w = w . Different choices of the potential function ψ(•) yield different optimization algorithms, which will potentially have different implicit biases. A few examples follow.

Gradient Descent. For the potential function ψ(w) = 1 2 w 2 , the Bregman divergence is D ψ (w, w ) = 1 2 w -w 2 , and the update rule reduces to that of SGD. Exponentiated Gradient Descent. For ψ(w) = j w j log w j , the Bregman divergence becomes the unnormalized relative entropy (Kullback-Leibler divergence) D ψ (w, w ) = j w j log wj w j j w j + j w j , which corresponds to the exponentiated gradient descent (aka the exponential weights) algorithm (Kivinen & Warmuth, 1997) .

p-norms Algorithm. For any q-norm squared potential function ψ(w) = 1 2 w 2 q , with 1 p + 1 q = 1, the algorithm will reduce to the so-called p-norms algorithm (Grove et al., 2001; Gentile, 2003) .

Sparse Mirror Descent. For ψ(w) = w 1+ 1+ , the algorithm reduces to sparse mirror descent, which is used in compressed sensing (Azizan & Hassibi, 2019) .

2.2. OVERPARAMETERIZED LINEAR MODELS:

Overparameterized (or underdetermined) linear models have been recently studied in many papers due to their simplicity, and the fact that there are interesting insights than one can obtain from them. In this case, the model is f (x i , w) = x T i w, the set of global minima is W = w | y i = x T i w, i = 1, . . . , n , and the loss is L i (w) = (y i -x T i w). The following result characterizes the solution that SMD converges to (Azizan & Hassibi, 2019; Gunasekar et al., 2018a) . Proposition 1. Consider a linear overparameterized model. For sufficiently small step size, i.e., for any η > 0 for which ψ(•) -ηL i (•) is convex, and for any initialization w 0 , the SMD iterates converge to w ∞ = arg min w∈W D ψ (w, w 0 ).

Note that the step size condition, i.e., the convexity of ψ(•) -ηL i (•), depends on both the loss and the potential function. For the case of SGD, ψ(w) = 1 2 w 2 , and

(y i -x T i w) = 1 2 (y i -x T i w) 2

, so the condition reduces to the well-known η ≤ 1 xi 2 . In this case, D ψ (w, w 0 ) is simply 1 2 w -w 0 2 .

Corollary 2. In particular, for the initialization w 0 = arg min w∈R p ψ(w), under the conditions of Proposition 1, the SMD iterates converge to

EQUATION

)

This means that running SMD for a linear model with the aforementioned w 0 , without any explicit regularization, results in a solution that has the smallest potential ψ(•) among all solutions, i.e., SMD implicitly regularizes the solution with ψ(•). In particular, this means that SGD initialized around zero acts an an 2 -norm regularizer. In this paper, we show that these results continue to hold for highly overparameterized nonlinear models in an approximate sense.

3. THEORETICAL RESULTS:

In this section, we provide our main theoretical results. In particular, we show that for highly overparameterized models (1) SMD converges to a global minimum, (2) the global minimum obtained by SMD is approximately the closest one to the initialization in Bregman divergence corresponding to the potential.

Figure 1 : An illustration of the parameter space. W represents the set of global minima, w 0 is the initialization, B is the local neighborhood, w * and the closest global minimum to w 0 (in Bregman divergence), and w ∞ is the minimum that SMD converges to.

3.1. CONVERGENCE OF STOCHASTIC MIRROR DESCENT:

Let us define D Li (w, w ) := L i (w) -L i (w ) -∇L i (w ) T (w -w ), (7) which is defined in a similar way to a Bregman divergence for the loss function. The difference though is that, unlike the potential function of the Bregman divergence, the loss function L i (•) = (y i -f (x i , •)) need not be convex (even when (•) is) due to the nonlinearity of f (•, •).

It has been argued in several recent papers that in highly overparameterized neural networks, any random initialization w 0 is close to W, with high probability (Li & Liang, 2018; Du et al., 2018; Azizan & Hassibi, 2019; Allen-Zhu et al., 2019; Cao & Gu, 2019) (see also the discussion in Section A.4 of the supplementary material). Therefore, it is reasonable to make the following assumption about the initialization. Assumption 1. Denote the initial point by w 0 . There exists w ∈ W and a region B = {w ∈ R p | D ψ (w, w ) ≤ } containing w 0 , such that D Li (w, w ) ≥ 0, i = 1, . . . , n, for all w ∈ B.

It is important to understand what this assumption means. Since L i (•) is not necessarily convex, it is certainly not the case that D Li (w, w ) ≥ 0 for all w . However, since w is a minimizer of L i (•), there will be a neighborhood around it such that for all w in this neighborhood D Li (w, w ) ≥ 0 (see Fig. 2 for an illustration). What we are requiring is that the initialization w 0 be inside the intersection of all such neighborhoods for i = 1, 2, . . . , n. In other words, we require a w 0 close enough to W. 

≤ λ min (H fi (w )) ≤ λ max (H fi (w )) ≤ β, i = 1, . . . , n, for all w ∈ conv B.

This is again a mild assumption, which is assumed in other related work such as (Oymak & Soltanolkotabi, 2019) as well. Note that we do not require α to be positive (just its boundedness). The following theorem states that under Assumption 1, SMD converges to a global minimum. Theorem 3. Consider the set of interpolating parameters W = {w ∈ R p | f (x i , w) = y i , i = 1, . . . , n}, and the SMD iterates given in (3), where every data point is revisited after some steps. Under Assumption 1, for sufficiently small step size, i.e., for any η > 0 for which ψ(•) -ηL i (•) is strictly convex on B for all i, the following holds.

1.. All the iterates {w:

i } remain in B.

2. The iterates converge (to w ∞ ).

3.. w ∞ ∈ W.:

Note that, while convergence (to some point) with decaying step size is almost trivial, this result establishes convergence to the solution set with a fixed step size. Furthermore, the convergence is deterministic, and is not in expectation or with high probability. For example, this result also applies to the case where we cycle through the data deterministically.

We should also remark that the choice of distance in the definition of the "ball" B was important to be the Bregman divergence with respect to ψ(•) and in that particular order. In fact, one cannot guarantee that the SMD iterates get closer to an interpolating w at every step in the usual Euclidean sense. However, once can establish that it gets closer in D ψ (w, •). Finally, it is important to note that we need the step size to be small enough to guarantee the strict convexity of ψ(•) -ηL i (•) in B, not globally.

Denote the global minimum that is closest to the initialization in Bregman divergence by w * , i.e., w * = arg min

EQUATION

Recall that in the linear case, this was what SMD converges to. We show that in the nonlinear case, under Assumptions 1 and 2, SMD converges to a point w ∞ which is "very close" to w * .

Theorem 4. Define w * = arg min w∈W D ψ (w, w 0 ). Under the conditions of Theorem 3, and Assumption 2, the following holds

1. D ψ (w ∞ , w 0 ) = D ψ (w * , w 0 ) + o( ) 2. D ψ (w * , w ∞ ) = o( )

In other words, if we start with an initialization that is O( ) away from W (in Bregman divergence), we converge to a point w ∞ ∈ W that is o( ) away from w * . The Bregman divergence of this point is o( ) from the minimum value it can take.

Corollary 5. For the initialization w 0 = arg min w∈R p ψ(w), under the conditions of Theorem 4, w * = arg min w∈W ψ(w) and the following holds.

1. ψ(w ∞ ) = ψ(w * ) + o( ) 2. D ψ (w * , w ∞ ) = o( )

3.2. PROOF TECHNIQUE: FUNDAMENTAL IDENTITY OF SMD:

The main tool used for the proofs is a fundamental identity that holds for SMD.

Lemma 6. For any model f (•, •), any differentiable loss (•), any parameter w ∈ W, and any step size η > 0, the following relation holds for the SMD iterates

EQUATION

for all i ≥ 1.

This identity allows one to prove the results in a remarkably simple and direct way. Due to space limitations, the proofs are relegated to the supplementary material.

The ideas behind this identity are related to H ∞ estimation theory (Hassibi et al., 1999; Simon, 2006) , which was originally developed in the 1990's in the context of robust control theory. In fact, it has connections to the minimax optimality of SGD, which was shown by (Hassibi et al., 1994) for linear models, and recently extended to nonlinear models and general mirrors by (Azizan & Hassibi, 2019) .

4. EXPERIMENTAL RESULTS:

In this section, we provide our experimental results, which consist of two main parts. In the first part, we evaluate the theoretical claims by running systematic experiments for different initializations and different mirrors, and evaluating the distances between the global minima achieved and the initializations, in different Bregman divergences. In the second part, we assess the generalization error of different mirrors, which correspond to different regularizers, in order to understand which regularizer performs better. 6 × 10 2 2.9 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 Initial 2 2.8 × 10 3 6.1 × 10 2 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 Initial 3 2.8 × 10 3 2.9 × 10 3 5.6 × 10 2 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 Initial 4 2.8 × 10 3 2.9 × 10 3 2.8 × 10 3 5.9 × 10 2 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 Initial 5 2.8 × 10 3 2.9 × 10 3 2.8 × 10 3 2.8 × 10 3 5.7 × 10 2 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 Initial 6 2.8 × 10 3 2.9 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 5.6 × 10 2 2.8 × 10 3 2.8 × 10 3 Initial 7 2.8 × 10 3 2.9 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 6 × 10 2 2.8 × 10 3 Initial 8 2.8 × 10 3 2.9 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 5.8 × 10 2

Table 2: Fixed Mirror: SGD. Pairwise distances between different initial points and the final points obtained from them by SGD (Fig. 4 ). Row i: The closest final point to the initial point i, among all the eight final points, is exactly the one obtained by the algorithm from initialization i. We measure the distances between the initializations and the global minima obtained from different mirrors and different initializations, in different Bregman divergences. Table 1 , and Table 2 show some examples among different mirrors and different initializations, respectively. Fig. 5 shows the distances between a particular initial point and all the final points obtained from different initializations and different mirrors (the distances are often orders of magnitude different, so we show them in logarithmic scale). The global minimum achieved by any mirror from any initialization is the closest in the correct Bregman divergence, among all mirrors, among all initializations, and among both. This trend is very consistent among all our experiments, which can be found in Supplementary Material B.

MNIST. SGD Starting from Initial 4 CIFAR-10. SGD Starting from Initial 2

Figure 5 : Distances between a particular initial point and all the final points obtained by both different initializations and different mirrors. The smallest distance, among all initializations and all mirrors, corresponds exactly to the final point obtained from that initial point by SGD. This trend is observed consistently for all other mirror descents and all initializations (see the results in Tables 8 and 9 in the appendix).

4.2. DISTRIBUTION OF THE WEIGHTS OF THE NETWORK:

One may be curious to see how the final weights obtained by these different mirrors look like, and whether, for example, mirror descent corresponding to the 1 -norm potential induces sparsity. Fig. 6 shows the histogram of the absolute value of the weights for different SMDs, when initialized by the same set of close to zero weights. The histograms of the final weights look substantially different and, since they all started from the same initial weights, this difference is fully attributable to the different mirrors used. The histogram of the 1 -SMD has more weights at and close to zero, which confirms that it induces sparsity. The histogram of the 2 -SMD (SGD) looks almost perfectly Gaussian, whereas the 3 and 10 histograms are shifted to the right, so much so that almost all weights in the 10 solution are non-zero. See Appendix B for more details.

4.3. GENERALIZATION ERRORS OF DIFFERENT MIRRORS:

We compare the performance of the SMD algorithms discussed before on the test set. For MNIST, perhaps not surprisingly, all the four SMD algorithms achieve around 99% or higher accuracy.

For CIFAR-10, however, there is a significant difference between the test errors of different mirrors/regularizers on the same ResNet-18 architecture. Fig. 7 shows the test accuracies of different algorithms with eight random initializations around zero, as discussed before. Counter-intuitively, 10 performs consistently best, while 1 performs consistently worse. This result suggests the importance of a comprehensive study of the role of regularization, and the choice of the best regularizer, to improve the generalization performance of deep neural networks.

Figure 6 : Histogram of the absolute value of the final weights in the network for different SMD algorithm with different potentials. Note that each of the four histograms corresponds to an 11×10 6dimensional weight vector that perfectly interpolates the data. Even though the weights remain quite small, the histograms are drastically different. 1 -SMD induces sparsity on the weights, as expected. SGD appears to be produce a Gaussian distribution on the weights. 3 -SMD starts to reduce the sparsity, and 10 shifts the distribution of the weights significantly, so much so that almost all the weights are non-zero.

Figure 7 : Generalization performance of different SMD algorithms on the CIFAR-10 dataset using ResNet-18. 10 performs consistently better, while 1 performs consistently worse. Assumption 1. Denote the initial point by w 0 . There exists w ∈ W and a region B = {w ∈ R p | D ψ (w, w ) ≤ } containing w 0 , such that D Li (w, w ) ≥ 0, i = 1, . . . , n, for all w ∈ B. Theorem 3. Consider the set of interpolating parameters W = {w ∈ R p | f (x i , w) = y i , i = 1, . . . , n}, and the SMD iterates given in (3), where every data point is revisited after some steps.

Under Assumption 1, for sufficiently small step size, i.e., for any η > 0 for which ψ(•) -ηL i (•) is strictly convex for all i, the following holds.

1. All the iterates {w i } remain in B.

2. The iterates converge (to w ∞ ).

3. w ∞ ∈ W.

Proof of Theorem 3. First we show that all the iterates wil remain in B. Recall the identity of SMD from Lemma 6:

EQUATION

which holds for all w ∈ W. If w i-1 is in the region B, we know that the last term D Li (w, w i-1 ) is non-negative. Furthermore, if the step size is small enough that ψ(•) -ηL i (•) is strictly convex, the second term D ψ-ηLi (w i , w i-1 ) is a Bregman divergence and is non-negative. Since the loss is non-negative, ηL i (w i ) is always non-negative. As a result, we have

EQUATION

This implies that D ψ (w, w i ) ≤ , which means w i is in B too. Since w 0 is in B, w 1 will be in B, and therefore, w 2 will be in B, and similarly all the iterates will remain in B.

Next, we prove that the iterates converge and w ∞ ∈ W. If we sum up identity (9) for all i = 1, . . . , T , the first terms on the right-and left-hand side cancel each other telescopically, and we have

EQUATION

Since D ψ (w, w T ) ≥ 0, we have

EQUATION

)

Since the step size is small enough that ψ(•) -ηL i (•) is strictly convex for all i, the first term D ψ-ηLi (w i , w i-1 ) is non-negative. The second term ηL i (w i ) is non-negative because of the nonnegativity of the loss. Finally, the last term D Li (w, w i-1 ) is non-negative because w i-1 ∈ B for all i. Hence, all the three terms in the summand are non-negative, and because the sum is bounded, they should go to zero as i → ∞. In particular,

D ψ-ηLi (w i , w i-1 ) → 0 (22)

implies w i → w i-1 , i.e., convergence (w i → w ∞ ) (Note that the functions ψ -ηL i do not go to zero, as there is a fixed number, i.e., n, of them). Further,

EQUATION

)

This implies that all the individual losses are going to zero, and since every data point is being revisited after some steps, all the data points are being fit. Therefore, w ∞ ∈ W.

A.3 CLOSENESS OF THE FINAL POINT TO THE REGULARIZED SOLUTION:

In this section, we show that with the additional Assumption 2 (which is equivalent to f i (•) having bounded Hessian in B), not only do the iterates remain in B and converge to the set W, but also they converge to a point which is very close to w * (the closest solution to the initial point, in Bregman divergence). The proof is again based on our fundamental identity for SMD. Assumption 2. Consider the region B in Assumption 1. f i (•) have bounded gradient and Hessian on the convex hull of B, i.e., ∇f i (w ) ≤ γ, and α ≤ λ min (H fi (w )) ≤ λ max (H fi (w )) ≤ β, i = 1, . . . , n, for all w ∈ conv B. Theorem 4. Define w * = arg min w∈W D ψ (w, w 0 ). Under the assumptions of Theorem 3, and Assumption 2, the following holds.

1. D ψ (w ∞ , w 0 ) = D ψ (w * , w 0 ) + o( ) 2. D ψ (w * , w ∞ ) = o( )

Proof of Theorem 4. Recall the identity of SMD from Lemma 6:

EQUATION

which holds for all w ∈ W. Summing the identity for all i ≥ 1, we have

EQUATION

for all w ∈ W. Note that the only terms in the right-hand side which depend on w are the first one D ψ (w, w ∞ ) and the last one η

∞ i=1 D Li (w, w i-1 ).

In what follows, We will argue that, within B, the dependence on w in the last term is weak and therefore w ∞ is close to w * .

To further spell out the dependence on w in the last term, let us expand D Li (w, w i-1 )

EQUATION

for all w ∈ W, where the first equality comes from the definition of D Li (•, •) and the fact that L i (w) = 0 for w ∈ W. The second equality is from taking the derivative of L i (•) = (y i -f i (•)) and evaluating it at w i-1 .

By Taylor expansion of f i (w) around w i-1 and using Taylor's theorem (Lagrange's mean-value form), we have

EQUATION

for some ŵi in the convex hull of w and w i-1 . Since f i (w) = y i for all w ∈ W, it follows that

EQUATION

for all w ∈ W. Plugging this into (26), we have

EQUATION

) for all w ∈ W. Finally, by plugging this back into the identity (24), we have

EQUATION

)

for all w ∈ W. Note that this can be expressed as

EQUATION

for all w ∈ W, where C does not depend on w:

C = ∞ i=1 [D ψ-ηLi (w i , w i-1 ) + ηL i (w i ) -ηL i (w i-1 ) + η (y i -f i (w i-1 ))(y i -f i (w i-1 ))] .

From Theorem 3, we know that w ∞ ∈ W. Therefore, by plugging it into equation ( 31), and using the fact that D ψ (w ∞ , w ∞ ) = 0, we have

EQUATION

where w i is a point in the convex hull of w ∞ and w i-1 (and therefore also in conv B), for all i.

Similarly, by plugging w * , which is also in W, into (31), we have

EQUATION

) where w i is a point in the convex hull of w * and w i-1 (and therefore also in conv B), for all i. Subtracting the last two equations from each other yields

EQUATION

)

Note that since all w i and w i are in conv B, by Assumption 2, we have

EQUATION

and

EQUATION

)

Further, again since all the iterates {w i } are in B, it follows that w ∞ -w i-1 2 = O( ) and w * -w i-1 2 = O( ). As a result the difference of the two terms, i.e., (w * -w i-1 ) T H fi (w i )(w *w i-1 ) -(w ∞ -w i-1 ) T H fi (w i )(w ∞ -w i-1 ) , is also O( ), and we have

EQUATION

) Now note that (y i -f i (w i-1 )) = (f i (w) -f i (w i-1 )) = (∇f i ( wi ) T (w -w i-1

)) for some wi ∈ conv B. Since w -w i-1 2 = O( ) for all i, and since (•) is differentiable and

EQUATION

)

The term in parentheses D ψ (w ∞ , w 0 ) -D ψ (w * , w 0 ) is non-negative by definition of w * . The second term D ψ (w * , w ∞ ) is non-negative by convexity of ψ. Since both terms are non-negative and their sum is o( ), each one of them is at most o( ), i.e.

EQUATION

which concludes the proof.

Corollary 5. For the initialization w 0 = arg min w∈R p ψ(w), under the conditions of Theorem 4, w * = arg min w∈W ψ(w) and the following holds.

1. ψ(w ∞ ) = ψ(w * ) + o( ) 2. D ψ (w * , w ∞ ) = o( )

Proof of Corollary 5. The proof is a straightforward application of Theorem 4. Note that we have

D ψ (w, w 0 ) = ψ(w) -ψ(w 0 ) -∇ψ(w 0 ) T (w -w 0 ) (40)

for all w. When w 0 = arg min w∈R p ψ(w), it follows that ∇ψ(w 0 ) = 0, and

EQUATION

In particular, by plugging in w ∞ and w * , we have D ψ (w ∞ , w 0 ) = ψ(w ∞ ) -ψ(w 0 ) and D ψ (w * , w 0 ) = ψ(w * ) -ψ(w 0 ). Subtracting the two equations from each other yields

EQUATION

which along with the application of Theorem 4 concludes the proof.

A.4 CLOSENESS TO THE INTERPOLATING SET IN HIGHLY OVERPARAMETERIZED MODELS:

As we mentioned earlier, it has been argued in a number of recent papers that for highly overparameterized models, any random initial point is, whp, close to the solution set W (Azizan & Hassibi, 2019; Li & Liang, 2018; Du et al., 2018; Allen-Zhu et al., 2019; Cao & Gu, 2019) . In the highly overparameterized regime, p n, and so the dimension of the manifold W, which is p -n, is very large. For simplicity, we outline an argument for the case of Euclidean distance, bearing in mind that a similar argument can be used for general Bregman divergence. Note that the distance of an arbitrarily chosen w 0 to W is given by

min w w -w 0 2 s.t. y = f (x, w)

where y = vec(y i , i = 1, . . . , n) and f (x, w) = vec(f (x i , w), i = 1, . . . , n). This can be approximated by min

w w -w 0 2 s.t. y ≈ f (x, w 0 ) + ∇f (x, w 0 ) T (w -w 0 )

where ∇f (x, w 0 ) T = vec(∇f (x i , w) T , i = 1, . . . , n) is the n × p Jacobian matrix. The latter optimization can be solved to yield

EQUATION

Note that ∇f (x, w 0 ) T ∇f (x, w 0 ) is an n×n matrix consisting of the sum of p outer products. When the x i are sufficiently random, and p n, it is not unreasonable to assume that whp

λ min ∇f (x, w 0 ) T ∇f (x, w 0 ) = Ω(p),

from which we conclude

EQUATION

) since y -f (x, w 0 ) is n-dimensional.

The above implies that w 0 is close to w * and hence W.

B MORE DETAILS ON THE EXPERIMENTAL RESULTS:

In order to evaluate the claim, we run systematic experiments on some standard deep learning problems.

Datasets. We use the standard MNIST (LeCun et al., 1998) and CIFAR-10 (Krizhevsky & Hinton, 2009) datasets.

Architectures. For MNIST, we use a 4-layer convolutional neural network (CNN) with 2 convolution layers and 2 fully connected layers. The convolutional layers and the fully connected layers are picked wide enough to obtain 2 × 10 6 trainable parameters. Since MNIST dataset has 60,000 training samples, the number of parameters is significantly larger than the number of training data points, and the problem is highly overparameterized. For the CIFAR-10 dataset, we use the standard ResNet-18 (He et al., 2016) architecture without any modifications. CIFAR-10 has 50,000 training samples and with the total number of 11 × 10 6 parameters in ResNet-18, the problem is again highly overparameterized.

Loss Function. We use the cross-entropy loss as the loss function in our training. We train the models from different initializations, and with different mirror descents from each particular initialization, until we reach 100% training accuracy, i.e., until we hit W.

Initialization. We randomly initialize the parameters of the networks around zero (N (0, 0.0001)).

We choose 6 independent initializations for the CNN, and 8 for ResNet-18, and for each initialization, we run the following 4 different SMD algorithms.

Algorithms. We use the mirror descent algorithms defined by the norm potential ψ(w) = 1 q w q q for the following four different norms: (a) 1 norm, i.e., q = 1 + , (b) 2 norm, i.e., q = 2 (which is SGD), (c) 3 norm, i.e., q = 3, (d) 10 norm, i.e., q = 10 (as a surrogate for ∞ norm). The update rule can be expressed as follows.

EQUATION

where w i-1,j denotes the j-th element of the w i-1 vector.

We use a fixed step size η. The step size is chosen to obtain convergence to global minima.

B.1 MNIST EXPERIMENTS:



B.1.1 CLOSEST MINIMUM FOR DIFFERENT MIRROR DESCENTS WITH FIXED INITIALIZATION:

We provide the distances from final points (global minima) obtained by different algorithms from the same initialization, measured in different Bregman divergences for MNIST classification task using a standard CNN. Note that in all tables the smallest element in each row is on the diagonal, which means the point achieved by each mirror has the smallest Bregman divergence to the initialization corresponding to that mirror, among all mirrors. Tables 3, 4 , 5, 6, 7, 8 depict these results for 6 different initializations. The rows are the distance metrics used as the Bregman Divergences with specified potentials. The columns are the global minima obtained using specified SMD algorithms. We provide the pairwise distances between different initial points and the final points (global minima) obtained by using fixed SMD algorithms in MNIST dataset using a standard CNN. Note that the smallest element in each row is on the diagonal, which means the closest final point to each initialization, among all the final points, is the one corresponding to that point. Tables 9, 10 , 11 and 12 depict these results for 4 different SMD algorithms. The rows are the initial points and the columns are the final points corresponding to each initialization.

B.1.3 CLOSEST MINIMUM FOR DIFFERENT INITILIZATIONS AND DIFFERENT MIRRORS:

Now we assess the pairwise distances between different initial points and final points (global minima) obtained by all different initilizations and all different mirrors (Table 8 ). The smallest element in each row is exactly the final point obtained by that mirror from that initialization, among all the mirrors and all the initial points. .507 11.578 32.256 32.325 32.225 32.46 Initial Point 3 31.594 34.643 7.8239 32.521 31.58 32.519 Initial Point 4 32.303 34.811 32.937 7.5589 32.617 32.284 Initial Point 5 32.673 34.678 32.071 32.738 7.5188 31.558 Initial Point 6 32.116 34.731 32.376 32.431 31.699 7.4593 We provide the distances from final points (global minima) obtained by different algorithms from the same initialization, measured in different Bregman divergences for CIFAR-10 classification task using ResNet-18. Note that in all tables the smallest element in each row is on the diagonal, which means the point achieved by each mirror has the smallest Bregman divergence to the initialization corresponding to that mirror, among all mirrors. Tables 13, 14, 15, 16, 17, 18, 19, 20 depict these results for 8 different initializations. The rows are the distance metrics used as the Bregman Divergences with specified potentials. The columns are the global minima obtained using specified SMD algorithms. We provide the pairwise distances between different initial points and the final points (global minima) obtained by using fixed SMD algorithms in CIFAR-10 dataset using ResNet-18. Note that the smallest element in each row is on the diagonal, which means the closest final point to each initialization, among all the final points, is the one corresponding to that point. Tables 21, 22 , 23, 24 depict these results for 4 different SMD algorithms. The rows are the initial points and the columns are the final points corresponding to each initialization. 8 ). The smallest element in each row is exactly the final point obtained by that mirror from that initialization, among all the mirrors and all the initial points.

Figure 9 : Different Bregman divergences between all the final points and all the initial points for different mirrors in CIFAR-10 dataset using ResNet-18. Note that the smallest element in every single row is on the diagonal, which confirms the theoretical results. We then measured all the pairwise distances from different w ∞ to different w 0 , in different Bregman divergences. The closest point (among all initializations and all mirrors) to any particular initialization w 0 in Bregman divergence with potential ψ(•) = • q q is exactly the point obtained by running SMD with potential • q q from w 0 .

B.3 DISTRIBUTION OF THE FINAL WEIGHTS OF THE NETWORK:

One may be curious to see how the final weights obtained by these different mirrors look like, and whether, for example, mirror descent corresponding to the 1 -norm potential induces sparsity.

We examine the distribution of the weights in the network for these algorithms starting from the same initialization. 

B.4 GENERALIZATION ERRORS OF DIFFERENT MIRRORS/REGULARIZERS:

In this section, we compare the performance of the SMD algorithms discussed before on the test set. This is important for understanding the effect of different regularizers on the generalization of deep networks.

For MNIST, perhaps not surprisingly, all the four SMD algorithms achieve around 99% or higher accuracy. For CIFAR-10, however, there is a significant difference between the test errors of different mirrors/regularizers on the same architecture. Fig. 13 shows the test accuracies of different algorithms with eight random initializations around zero, as discussed before. Counter-intuitively, 10 performs consistently best, while 1 performs consistently worse. We should reiterate that the loss function is exactly the same in all these experiments, and all of them have been trained to fit the training set perfectly (zero training error). Therefore, the difference in generalization errors is purely the effect of implicit regularization by different algorithms. This result suggests the importance of a comprehensive study of the role of regularization, and the choice of the best regularizer, to improve the generalization performance of deep neural networks.

Figure 13 : Generalization performance of different SMD algorithms on the CIFAR-10 dataset using ResNet-18. 10 performs consistently better, while 1 performs consistently worse.

:



Figures and Tables:

Figure 2: An illustration of D Li (w, w ) ≥ 0 in a local region in Assumption 1. Our second assumption states that in this local region, the first and second derivatives of the model are bounded. Assumption 2. Consider the region B in Assumption 1. f i (•) have bounded gradient and Hessian on the convex hull of B, i.e., ∇f i (w ) ≤ γ, and α ≤ λ min (H fi (w )) ≤ λ max (H fi (w )) ≤ β, i = 1, . . . , n, for all w ∈ conv B.

Figure 3: An illustration of the experiments in Table 1

Figure 4: An illustration of the experiments in Table 2

Figure 10: An illustration of the experimental results. For each initialization w 0 , we ran different SMD algorithms until convergence to a point on the set W (zero training error). We then measured all the pairwise distances from different w ∞ to different w 0 , in different Bregman divergences. The closest point (among all initializations and all mirrors) to any particular initialization w 0 in Bregman divergence with potential ψ(•) = • qq is exactly the point obtained by running SMD with potential • q q from w 0 .

Fig. 11  shows the histogram of the initial weights, which follows a half-normal distribution. Figs. 12 (a), (b), (c), (d) show the histogram of the weights for 1 -SMD, 2 -SMD (SGD), 3 -SMD, and 10 -SMD, respectively. Note that each of the four histograms corresponds to an 11 × 10 6 -dimensional weight vector that perfectly interpolates the data. Even though, perhaps as expected, the weights remain quite small, the histograms are drastically different. The histogram of the 1 -SMD has more weights at and close to zero, which again confirms that it induces sparsity. However, as will be shown in the next section, this is not necessarily good for generalization (in fact, it turns out that 10 -SMD has a much better generalization). The histogram of the 2 -SMD (SGD) looks almost identical to the histogram of the initialization, whereas the 3 and 10 histograms are shifted to the right, so much so that almost all weights in the 10 solution are non-zero and in the range of 0.005 to 0.04. For comparison, all the distributions are shown together in Fig.12(e).

Figure 11: Histogram of the absolute value of the initial weights in the network (half-normal distribution)



Table content: <table><tr><td/><td colspan="4">1-norm SMD 2-norm (SGD) SMD 3-norm SMD 10-norm</td></tr><tr><td>1-norm BD</td><td>141</td><td>9.19 × 10 3</td><td>4.1 × 10 4</td><td>2.34 × 10 5</td></tr><tr><td>2-norm BD</td><td>3.15 × 10 3</td><td>562</td><td>1.24 × 10 3</td><td>6.89 × 10 3</td></tr><tr><td>3-norm BD</td><td>4.31 × 10 4</td><td>107</td><td>53.5</td><td>1.85 × 10 2</td></tr><tr><td colspan="2">10-norm BD 6.83 × 10 13</td><td>972</td><td>7.91 × 10 -5</td><td>2.72 × 10 -8</td></tr></table>

Fixed Initialization. Distances from final points (global minima) obtained by different algorithms (columns) from the same initialization (Fig.3), measured in different Bregman divergences (rows). First Row: The closest point to w 0 in 1 Bregman divergence, among the four final points, is exactly the one obtained by SMD with 1-norm potential. Second Row: The closest point to w 0 in 2 Bregman divergence (Euclidean distance), among the four final points, is exactly the one obtained by SGD. Third Row: The closest point to w 0 in 3 Bregman divergence, among the four final points, is exactly the one obtained by SMD with 3-norm potential. Fourth Row: The closest point to w 0 in 10 Bregman divergence, among the four final points, is exactly the one obtained by SMD with 10-norm potential.

Table content: <table/>

Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems, pp. 4151-4161, 2017. Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. Google's neural machine translation system: Bridging the gap between human and machine translation. arXiv preprint arXiv:1609.08144, 2016. Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530, 2016. Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Stephen Boyd, and Peter W Glynn. Stochastic mirror descent in variationally coherent optimization problems. In Advances in Neural Information Processing Systems, pp. 7043-7052, 2017. A.2 CONVERGENCE OF SMD TO THE INTERPOLATING SET Now that we have proved Lemma 6, we can use it to prove our main results, in a remarkably simple fashion. Let us first prove the convergence of SMD to the set of solutions.

Table content: <table/>



Table content: <table><tr><td/><td/><td colspan="2">: MNIST Initial Point 1</td><td/></tr><tr><td/><td colspan="4">SMD 1-norm SMD 2-norm (SGD) SMD 3-norm SMD 10-norm</td></tr><tr><td>1-norm BD</td><td>2.767</td><td>937.8</td><td>1.05 × 10 4</td><td>1.882 × 10 5</td></tr><tr><td>2-norm BD</td><td>301.6</td><td>58.61</td><td>261.3</td><td>2.118 × 10 4</td></tr><tr><td>3-norm BD</td><td>1720</td><td>37.45</td><td>7.143</td><td>2518</td></tr><tr><td colspan="2">10-norm BD 7.453 × 10 8</td><td>773.4</td><td>0.2939</td><td>0.003545</td></tr></table>



Table content: <table><tr><td colspan="2">: MNIST 3-norm Bregman Divergence Between the Initial Points and the Final Points</td></tr><tr><td>obtained by SMD 3-norm</td><td/></tr><tr><td colspan="2">Final 1 Final 2 Final 3 Final 4 Final 5 Final 6</td></tr><tr><td>Initial Point 1 7.143</td><td>35.302 32.077 32.659 32.648 32.309</td></tr><tr><td>Initial Point 2 32</td><td/></tr></table>

MNIST 10-norm Bregman Divergence Between the Initial Points and the Final Points Different Bregman divergences between all the final points and all the initial points for different mirrors in MNIST dataset using a standard CNN. Note that the smallest element in every single row is on the diagonal, which confirms the theoretical results.

Table content: <table><tr><td>obtained by SMD 10-norm</td><td/><td/><td/><td/><td/><td/></tr><tr><td colspan="2">Final 1</td><td>Final 2</td><td>Final 3</td><td>Final 4</td><td>Final 5</td><td>Final 6</td></tr><tr><td colspan="2">Initial Point 1 0.00354</td><td>0.37</td><td>0.403</td><td>0.286</td><td>0.421</td><td>0.408</td></tr><tr><td>Initial Point 2</td><td>0.33</td><td>0.00321</td><td>0.369</td><td>0.383</td><td>0.415</td><td>0.422</td></tr><tr><td>Initial Point 3</td><td>0.347</td><td>0.318</td><td>0.00318</td><td>0.401</td><td>0.312</td><td>0.406</td></tr><tr><td>Initial Point 4</td><td>0.282</td><td>0.38</td><td>0.458</td><td>0.00296</td><td>0.491</td><td>0.376</td></tr><tr><td>Initial Point 5</td><td>0.405</td><td>0.418</td><td>0.354</td><td>0.484</td><td>0.00309</td><td>0.48</td></tr><tr><td>Initial Point 6</td><td>0.403</td><td>0.353</td><td>0.422</td><td>0.331</td><td>0.503</td><td>0.00295</td></tr></table>



Table content: <table><tr><td/><td/><td colspan="2">: CIFAR-10 Initial Point 1</td><td/></tr><tr><td/><td colspan="4">SMD 1-norm SMD 2-norm (SGD) SMD 3-norm SMD 10-norm</td></tr><tr><td>1-norm BD</td><td>189</td><td>9.58 × 10 3</td><td>4.19 × 10 4</td><td>2.34 × 10 5</td></tr><tr><td>2-norm BD</td><td>3.12 × 10 3</td><td>597</td><td>1.28 × 10 3</td><td>6.92 × 10 3</td></tr><tr><td>3-norm BD</td><td>4.31 × 10 4</td><td>119</td><td>55.8</td><td>1.87 × 10 2</td></tr><tr><td colspan="2">10-norm BD 1.35 × 10 14</td><td>869</td><td>6.34 × 10 -5</td><td>2.64 × 10 -8</td></tr></table>



Table content: <table><tr><td/><td/><td colspan="2">: CIFAR-10 Initial Point 2</td><td/></tr><tr><td/><td colspan="4">SMD 1-norm SMD 2-norm (SGD) SMD 3-norm SMD 10-norm</td></tr><tr><td>1-norm BD</td><td>275</td><td>9.86 × 10 3</td><td>4.09 × 10 4</td><td>2.38 × 10 5</td></tr><tr><td>2-norm BD</td><td>4.89 × 10 3</td><td>607</td><td>1.23 × 10 3</td><td>7.03 × 10 3</td></tr><tr><td>3-norm BD</td><td>9.21 × 10 4</td><td>104</td><td>53.5</td><td>1.88 × 10 2</td></tr><tr><td colspan="2">10-norm BD 1.17 × 10 15</td><td>225</td><td>0.000102</td><td>2.65 × 10 -8</td></tr></table>



Table content: <table><tr><td/><td/><td colspan="2">: CIFAR-10 Initial Point 3</td><td/></tr><tr><td/><td colspan="4">SMD 1-norm SMD 2-norm (SGD) SMD 3-norm SMD 10-norm</td></tr><tr><td>1-norm BD</td><td>141</td><td>9.19 × 10 3</td><td>4.1 × 10 4</td><td>2.34 × 10 5</td></tr><tr><td>2-norm BD</td><td>3.15 × 10 3</td><td>562</td><td>1.24 × 10 3</td><td>6.89 × 10 3</td></tr><tr><td>3-norm BD</td><td>4.31 × 10 4</td><td>107</td><td>53.5</td><td>1.85 × 10 2</td></tr><tr><td colspan="2">10-norm BD 6.83 × 10 13</td><td>972</td><td>7.91 × 10 -5</td><td>2.72 × 10 -8</td></tr></table>



Table content: <table><tr><td/><td/><td colspan="2">: CIFAR-10 Initial Point 4</td><td/></tr><tr><td/><td colspan="4">SMD 1-norm SMD 2-norm (SGD) SMD 3-norm SMD 10-norm</td></tr><tr><td>1-norm BD</td><td>255</td><td>9.77 × 10 3</td><td>4.18 × 10 4</td><td>2.36 × 10 5</td></tr><tr><td>2-norm BD</td><td>3.64 × 10 3</td><td>594</td><td>1.26 × 10 3</td><td>6.96 × 10 3</td></tr><tr><td>3-norm BD</td><td>5.5 × 10 4</td><td>116</td><td>54</td><td>1.87 × 10 2</td></tr><tr><td colspan="2">10-norm BD 3.74 × 10 14</td><td>640</td><td>5.33 × 10 -5</td><td>2.67 × 10 -8</td></tr></table>



Table content: <table><tr><td/><td/><td colspan="2">: CIFAR-10 Initial Point 5</td><td/></tr><tr><td/><td colspan="4">SMD 1-norm SMD 2-norm (SGD) SMD 3-norm SMD 10-norm</td></tr><tr><td>1-norm BD</td><td>113</td><td>9.48 × 10 3</td><td>4.15 × 10 4</td><td>2.32 × 10 5</td></tr><tr><td>2-norm BD</td><td>2.95 × 10 3</td><td>572</td><td>1.27 × 10 3</td><td>6.85 × 10 3</td></tr><tr><td>3-norm BD</td><td>3.68 × 10 4</td><td>109</td><td>56.2</td><td>1.84 × 10 2</td></tr><tr><td colspan="2">10-norm BD 2.97 × 10 13</td><td>151</td><td>5.74 × 10 -5</td><td>2.61 × 10 -8</td></tr></table>



Table content: <table><tr><td/><td/><td colspan="2">: CIFAR-10 Initial Point 6</td><td/></tr><tr><td/><td colspan="4">SMD 1-norm SMD 2-norm (SGD) SMD 3-norm SMD 10-norm</td></tr><tr><td>1-norm BD</td><td>128</td><td>9.25 × 10 3</td><td>4.25 × 10 4</td><td>2.34 × 10 5</td></tr><tr><td>2-norm BD</td><td>2.71 × 10 3</td><td>558</td><td>1.29 × 10 3</td><td>6.89 × 10 3</td></tr><tr><td>3-norm BD</td><td>3.34 × 10 4</td><td>104</td><td>55.3</td><td>1.85 × 10 2</td></tr><tr><td colspan="2">10-norm BD 2.61 × 10 13</td><td>612</td><td>4.74 × 10 -5</td><td>2.62 × 10 -8</td></tr><tr><td/><td colspan="3">Table 19: CIFAR-10 Initial Point 7</td><td/></tr><tr><td/><td colspan="4">SMD 1-norm SMD 2-norm (SGD) SMD 3-norm SMD 10-norm</td></tr><tr><td>1-norm BD</td><td>223</td><td>9.76 × 10 3</td><td>4.38 × 10 4</td><td>2.27 × 10 5</td></tr><tr><td>2-norm BD</td><td>2.41 × 10 3</td><td>599</td><td>1.37 × 10 3</td><td>6.65 × 10 3</td></tr><tr><td>3-norm BD</td><td>2.3 × 10 4</td><td>116</td><td>61</td><td>1.78 × 10 2</td></tr><tr><td colspan="2">10-norm BD 4.22 × 10 12</td><td>679</td><td>6.42 × 10 -5</td><td>2.55 × 10 -8</td></tr></table>



Table content: <table><tr><td/><td/><td colspan="2">: CIFAR-10 Initial Point 8</td><td/></tr><tr><td/><td colspan="4">SMD 1-norm SMD 2-norm (SGD) SMD 3-norm SMD 10-norm</td></tr><tr><td>1-norm BD</td><td>145</td><td>9.37 × 10 3</td><td>4.17 × 10 4</td><td>2.36 × 10 5</td></tr><tr><td>2-norm BD</td><td>2.48 × 10 3</td><td>576</td><td>1.26 × 10 3</td><td>6.99 × 10 3</td></tr><tr><td>3-norm BD</td><td>2.85 × 10 4</td><td>108</td><td>54.5</td><td>1.89 × 10 2</td></tr><tr><td colspan="2">10-norm BD 1.81 × 10 13</td><td>1.22 × 10 3</td><td>5.2 × 10 -5</td><td>2.64 × 10 -8</td></tr><tr><td colspan="5">B.2.2 CLOSEST MINIMUM FOR DIFFERENT INITILIZATIONS WITH FIXED MIRROR</td></tr></table>

CIFAR-10 1-norm Bregman Divergence Between the Initial Points and the Final Points obtained by SMD 1-norm

Table content: <table><tr><td>Final 1</td><td>Final 2</td><td>Final 3</td><td>Final 4</td><td>Final 5</td><td>Final 6</td><td>Final 7</td><td>Final 8</td></tr><tr><td colspan="3">Initial 1 1.9 × 10 2 8.1 × 10 4 8.1 × 10 4</td><td>8.4 × 10 4</td><td>8 × 10 4</td><td colspan="3">8.2 × 10 4 7.8 × 10 4 7.8 × 10 4</td></tr><tr><td colspan="3">Initial 2 8.1 × 10 4 2.7 × 10 2 8.1 × 10 4</td><td>8.3 × 10 4</td><td>8 × 10 4</td><td colspan="3">8.2 × 10 4 7.8 × 10 4 7.9 × 10 4</td></tr><tr><td colspan="2">Initial 3 8.1 × 10 4 8.1 × 10 4</td><td colspan="2">1.4 × 10 2 8.4 × 10 4</td><td>8 × 10 4</td><td colspan="3">8.1 × 10 4 7.8 × 10 4 7.8 × 10 4</td></tr><tr><td colspan="3">Initial 4 8.1 × 10 4 8.1 × 10 4 8.1 × 10 4</td><td>2.5 × 10 2</td><td>8 × 10 4</td><td colspan="3">8.2 × 10 4 7.8 × 10 4 7.9 × 10 4</td></tr><tr><td colspan="3">Initial 5 8.1 × 10 4 8.1 × 10 4 8.1 × 10 4</td><td>8.3 × 10 4</td><td colspan="4">1.1 × 10 2 8.1 × 10 4 7.8 × 10 4 7.8 × 10 4</td></tr><tr><td colspan="3">Initial 6 8.1 × 10 4 8.1 × 10 4 8.1 × 10 4</td><td>8.4 × 10 4</td><td>8 × 10 4</td><td colspan="3">1.3 × 10 2 7.8 × 10 4 7.8 × 10 4</td></tr><tr><td colspan="3">Initial 7 8.1 × 10 4 8.1 × 10 4 8.1 × 10 4</td><td>8.4 × 10 4</td><td>8 × 10 4</td><td>8.1 × 10 4</td><td colspan="2">2.2 × 10 2 7.8 × 10 4</td></tr><tr><td colspan="3">Initial 8 8.1 × 10 4 8.1 × 10 4 8.1 × 10 4</td><td colspan="2">8.4 × 10 4 7.9 × 10 4</td><td colspan="2">8.1 × 10 4 7.8 × 10 4</td><td>1.5 × 10 2</td></tr></table>

CIFAR-10 2-norm Bregman Divergence Between the Initial Points and the Final Points obtained by SMD 2-norm (SGD) × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 Initial 2 2.8 × 10 3 6.1 × 10 2 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 Initial 3 2.8 × 10 3 2.9 × 10 3 5.6 × 10 2 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 Initial 4 2.8 × 10 3 2.9 × 10 3 2.8 × 10 3 5.9 × 10 2 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 Initial 5 2.8 × 10 3 2.9 × 10 3 2.8 × 10 3 2.8 × 10 3 5.7 × 10 2 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 Initial 6 2.8 × 10 3 2.9 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 5.6 × 10 2 2.8 × 10 3 2.8 × 10 3 Initial 7 2.8 × 10 3 2.9 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 6 × 10 2 2.8 × 10 3 Initial 8 2.8 × 10 3 2.9 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 2.8 × 10 3 5.8 × 10 2

Table content: <table><tr><td/><td>Final 1</td><td>Final 2</td><td>Final 3</td><td>Final 4</td><td>Final 5</td><td>Final 6</td><td>Final 7</td><td>Final 8</td></tr><tr><td>Initial 1</td><td>6 × 10 2</td><td colspan="2">2.9 × 10 3 2.8 × 10 3</td><td>2.8</td><td/><td/><td/></tr></table>

CIFAR-10 3-norm Bregman Divergence Between the Initial Points and the Final Points

Table content: <table><tr><td colspan="2">obtained by SMD 3-norm</td><td/><td/><td/><td/></tr><tr><td colspan="7">Final 1 Final 2 Final 3 Final 4 Final 5 Final 6 Final 7 Final 8</td></tr><tr><td colspan="4">Initial 1 55.844 103.47 103.61 104.05</td><td>106.2</td><td colspan="2">105.32 110.88 104.56</td></tr><tr><td>Initial 2 105.87</td><td colspan="6">53.455 103.68 104.04 106.31 105.34 110.93 104.58</td></tr><tr><td colspan="2">Initial 3 105.89 103.59</td><td colspan="5">53.527 104.09 106.29 105.35 110.99 104.55</td></tr><tr><td colspan="3">Initial 4 105.83 103.54 103.64</td><td colspan="2">53.978 106.23</td><td>105.3</td><td>110.87 104.54</td></tr><tr><td colspan="3">Initial 5 105.82 103.55 103.64</td><td>104</td><td colspan="3">56.161 105.34 110.88 104.55</td></tr><tr><td>Initial 6 105.91</td><td>103.6</td><td>103.66</td><td>104.1</td><td>106.28</td><td colspan="2">55.316 110.94 104.55</td></tr><tr><td colspan="6">Initial 7 105.87 103.51 103.67 103.98 106.26 105.25</td><td>61.045</td><td>104.5</td></tr><tr><td colspan="7">Initial 8 105.77 103.54 103.59 104.04 106.25 105.28 110.88</td><td>54.509</td></tr></table>

CIFAR-10 10-norm Bregman Divergence Between the Initial Points and the Final Points obtained by SMD 10-norm Initial 1 2.64 × 10 -8 2.89 × 10 -8 2.99 × 10 -8 2.81 × 10 -8 2.85 × 10 -8 2.82 × 10 -8 2.66 × 10 -8 2.82 × 10 -8 Initial 2 2.79 × 10 -8 2.65 × 10 -8 2.83 × 10 -8 2.83 × 10 -8 2.71 × 10 -8 2.74 × 10 -8 2.69 × 10 -8 2.88 × 10 -8 Initial 3 2.89 × 10 -8 2.87 × 10 -8 2.72 × 10 -8 2.94 × 10 -8 2.84 × 10 -8 2.89 × 10 -8 2.78 × 10 -8 2.94 × 10 -8 Initial 4 2.79 × 10 -8 2.86 × 10 -8 2.92 × 10 -8 2.67 × 10 -8 2.84 × 10 -8 2.81 × 10 -8 2.69 × 10 -8 2.85 × 10 -8 Initial 5 2.76 × 10 -8 2.88 × 10 -8 2.95 × 10 -8 2.93 × 10 -8 2.61 × 10 -8 2.73 × 10 -8 2.66 × 10 -8 2.83 × 10 -8 Initial 6 2.80 × 10 -8 2.76 × 10 -8 2.93 × 10 -8 2.79 × 10 -8 2.76 × 10 -8 2.62 × 10 -8 2.71 × 10 -8 2.85 × 10 -8 Initial 7 2.73 × 10 -8 2.76 × 10 -8 2.82 × 10 -8 2.79 × 10 -8 2.71 × 10 -8 2.77 × 10 -8 2.55 × 10 -8 2.83 × 10 -8 Initial 8 2.73 × 10 -8 2.79 × 10 -8 2.85 × 10 -8 2.78 × 10 -8 2.75 × 10 -8 2.74 × 10 -8 2.73 × 10 -8 2.64 × 10 -8 B.2.3 CLOSEST MINIMUM FOR DIFFERENT INITILIZATIONS AND DIFFERENT MIRRORS Now we assess the pairwise distances between different initial points and final points (global minima) obtained by all different initilizations and all different mirrors (Table

Table content: <table><tr><td>Final 1</td><td>Final 2</td><td>Final 3</td><td>Final 4</td><td>Final 5</td><td>Final 6</td><td>Final 7</td><td>Final 8</td></tr></table>

Peer review (iclr2020):
This paper studies the optimization behaviour of stochastic mirror descent (SMD) on over-parametrized nonlinear models. It shows, rigorously and empirically, that SMD finds global minimizer that is approximately the closet global minimizer to the initial point, under the same Bregman divergence. The paper is well written and easy to follow. Pros: 1. The main contribution of this paper is extending the previous results on linear case into nonlinear setting, which is much more general. The results are non-trivial and interesting. 2. The empirical studies in the paper is clean and significant. It also supports the developed theory. The main concern I have is about assumption 1 in the paper. While in the paper the authors tend to claim that it is reasonable/mild, it is not obvious to me. a. Many factors are actually involved in this assumption: smoothness of psi, smoothness of L_i and f_i, number of parameters etc.. I am not sure if it is still a high probability, when eps needs to be small enough so that the intuition behind Figure 2 still holds. b. Is this assumption also made in the referred papers on the top of page 6? Could the authors develop a concrete result, given smoothness coefficients of psi and L_i, for this assumption? c. Without a proper justification of assumption 1, the significance of this paper seems much weaker. For example, one can also assume the PL inequality locally true for over-parametrized function, and develop a convergence result.