Stochastic Mirror Descent on Overparameterized Nonlinear Models
Authors: Navid Azizan
Sahin Lale
Babak Hassibi
Venue:  (2020)
Keywords: deep learning
optimization
overparameterized
stochastic gradient descent
mirror descent

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, l1 to encourage sparsity, l2 (yielding SGD) to encourage small Euclidean norm, and l10 to discourage large components in the parameter vector, consistently and definitively shows that, for small initialization vectors, l10-SMD has better generalization performance than SGD, which in turn has better generalization performance than l1-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.

Under review as a conference paper at ICLR 2020
STOCHASTIC MIRROR DESCENT ON OVERPARAME- TERIZED NONLINEAR MODELS
Anonymous authors Paper under double-blind review
ABSTRACT
Most modern learning problems are highly overparameterizze, meaning that the model has many more parameters than the number of training data points, and as result, the training loss may have infinitely many global minima (in fact, man- ifold of parameter vectors that perfectly interpolates the training data). Therefore, it is important to understand which interpolating solutions converge to, how they depend on the initialization point and the learning algorithm, and whether they lead to different generalization performances. In this paper, study these questions for the family of stochastic mirror descent (SMD) algorithms, of which the popular stochastic gradient descent (SGD) is 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 mir- ror used) to the initialization point, a phenomenon referred to as implicil regular- ization. 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 close enough to the manifold of global optima, SMD with suffi- ciently small step size converges to a global minimum that is approximately the closest global minimum in Bregman divergence, thus attaining approximate im- plicit regularization. For highly overparametrized models, this closeness comes for free: the manifold of global optima 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 Breg- man divergences. consistently confirms that this phenomenon indeed happens deep learning: SMD converges to the closest global optimum to the initializa- tion 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, l to encourage sparsity, & (yielding SGD) to encourage small Euclidean norm, and Eı to discourage large components the parameter vector, consistently and definitively shows that, for small initial- ization vectors, SMD has better generalization performance than SGD, which in turn has better generalization performance than & -SM.. This surprising, and perhaps counter-intuitive, result strongly suggests the importance of a comprehen- sive study of the role of regularization, and the choice of the best regularizer, to improve the generalization performance of deep networks.
INTRODUCTION
Deep learning has demonstrably enjoyed a great deal of success in a wide variety tasks (Amodei
et al. 2016 Graves et al.) 2013 Krizhevsky et al. 2012 Mnih et al., 2015] Silver et al.) [016)] Wu
et al. mance of these methods 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 key role in learning parameters that generalize well.
2016 LeCun et al. 2015). Despite its tremendous success, the reasons behind the good perfor-

---

Under review as a conference paper at ICLR 2020
Since these deep models are highly overparameterized. they have 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 "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 datasct, the loss function typically has (infinitely) many global minima, which however can have drastically different general- ization properties (many of them perform very poorly on the test set). Which minimum among all the possible minima 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.c., 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 a 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
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 special case. For any choice of potential function, there is a corresponding mirror descent algorithm. We show that, for overpa- rameterized 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 to the initialization, in Bregman divergence corre- sponding to the potential. In highly overparameterized models, this closeness of the initialization comes for free, something that is occasionally referred to "the blessing of dimensionality." For the special case of SGD, this means that 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 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 implicit regularization. In particular, it implies that, when initialized around zero, SGD acts as an l2 regularizer. Similarly, by choosing other mirrors, one obtains different forms of implicit regularization (such as E₁ or loo), 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 l 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 (l2 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, standard off-the-shelf deep
ie., l (sparse), lz (SGD), fs. and t1 (as a surrogate for lxc). neural network architecture for CIFAR-10, 10, namely ResNet- Somewhat counter- counter-intuitively, our results for test errors of different mirrors consistently and definitively show that the εn regularizer performs better than the other mirrors including SGD, while l consistently performs worse. This flies in the face of the conventional wisdom that sparser weights (which are obtained by an l regularizer) generalize better, and suggests that foo. which roughly speaking penalizes all the weights uniformly, may be better regularizer for deep neural networks.
2

---

Under review as a conference paper at ICLR 2020
1.1 RELATED WORK
There have been many efforts in the past few years to study deep learning from optimization
perspective, e.g., (Achille & Soatto, 2017: Chaudhari & Soatto| 2018 (Siaarttwrtttts & Tishby 2017)
Allen-Zhu et al.
2019 Oymak & Soltanolkotabi [019 Azizan & Hassibi 2019 Ma al. 201
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 "over- parameterized" setting (or "interpolating" regime), which is common in deep learning (Oymak & Soltanolkotabi] 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 suppiementary 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, When say. is close to the interpolating weight vector closest to the initialization, w", say. Denoting the initialization by Wo. Oymak & Soltanolkotabij (2019) showed that for SGD, ||w - wall bounded by a constant factor of w woll Our @erorem4showwe the much stronger statement that || [oso woll = I= woll + o[]lw* woll). We further show that Wao and w" are very close one another, viz. |w w" 1|2 o[Ilw* woll). (), 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.] 201 8a, Gunasekar et al., 2017]
2018a Soudry 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 overpa- rameterized models, and show that if SMD happens to converge to global minimum, then that global minimum will be the one that is closest in Bregman divergence to the initialization, result they obtain by examining the KKT conditions. However, they do not provide any conditions for con- vergence 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 afore- mentioned 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 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 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 supplemen- tary material.
BACKGROUND AND WARM-UP
n). where 2; Rd are the inputs, and Y: E R are the labels. The model (which can be, e.g., linear, a deep neural network, etc.) is defined by the general function fI,, w) fww with some parameter vector E Rº. 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 > n1). In this case,
Let us denote the training dataset by {(x,, Vi) : = 1,...,n),
3

---

Under review as a conference paper at ICLR 2020
there many parameter vectors that are consistent with the training data points. We denote the set of these parameter vectors by
W = W E RP [ -. i........
(1)
This a high-dimensional set (e.g. a (p n) -imeensioa manifold) in Re and depends only on the training data ((r,, ye) : = 1,..., n and the model [(:--).
The total loss on the training set (empirical risk) can be expressed as I(w) = Ei= I,(w), where I,(+) = f(v:: f(,, w)) is the loss on the individual data point i, and ((.,-) is differen- tiable non-negative function, with the property that E(g,, f w)) = 0 iff y; = f(z,, w). Often Kyyi, f (a,, w)) E(y: f w)), with E(-) convex and having global minimum zero (such as square loss, Huber loss, etc.). In this case, L(w)= = >i=1 f(y; fzz; w))
W is the set of global minima, and every parameter vector w in W renders the loss each data point zero, i.c., (() = O Vi. The loss function is often attempted to be minimized by stochastic gradient descent (SGD):
W; = - - ( i2
(2)
assuming the data is indexed randomly. We use one index i for both the loss and the parameter vector at step i (for > 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 of the most widely used families of algorithms for optimization (Beck & Teboulle 2003
et al,, 2012 Zhou al. 2017), which includes the popular gradient descent as special case. Consider strictly convex differentiable function v-(-), called the functtion descent (SMD) are defined as
function. Then updates for stochastic mirror
Ve(wa)) = Vo((w-11) (T;T1(
Note that, due to the strict convexity of v-)) the gradient V.h(-) defines invertible map, so the recursion in (3) yields a unique W/ at each iteration, and thus is a well-defined update, i.e., Compared to classical SGD, rather than update the
w) = ViL (V - -n weight vector along the direction of the negative gradient, the update is done in the "mirrored" domain determined by the invertible transformation Viv(-). Mirror descent was originally conceived exploit the geometrical structure of the problem by choosing an appropriate potential. Note that SMD reduces to SGD when ((r) = | 2, since the gradient (-b(.) is simply the identity map.
();=))
Alternatively, the update rule 3 can be expressed as
W, = arg min ny" V Li + Dw w;-1),
(4)
where
(5) the Bregman divergence with respect to the potential function (²()). Note that (.. is non- negative, convex in its first argument, and that, due to strict convexity, (sw w') 0 iff w w'.
(ww,, w;-1) = (ww) - (ww--1) V 1) wi-1)
Different choices of the potential function v-() yield different optimization algorithms, which will potentially have different implicit biases. A few examples follow.
Gradient Descent. For the potential function (ww) 1 ||=1 the Bregman divergence is De(w, w') = 1lll - "² and the update rule reduces to that of SGD.
Exponentiated Gradient Descent. For (ww) E3 wj log wj. the Bregman divergence becomes the unnormalized relative entropy (Kullback-Leible divergence) (w, w') = Σ3 wy log #
Wj + +,, w/. which corresponds to the exponentiated gradient descent (aka the exponential weights) algorithm (Kivinen & Warmuth 1997).
E,
p-norms Algorithm. For any q-norm squared potential function (w) = 1 || 12 with = 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+t the algorithm reduces to sparse mirror descent,
which is used in compressed sensing (Azizan & Hassibi 2019).
4

---

Under review as a conference paper at ICLR 2020
2.2 OVERPARAMETERIZED LINEAR MODELS
Overparameterized (or underdetermined) linear models have been recently studied in many pa- pers due their simplicity, and the fact that there interesting insights than one can obtain from them. In this case, the model is [1 w) = x. w. the set of global minima is W {w y = o w, i == I.....77 ni and the loss is (() = fly, x; w). The following result charac- terizes the solution that SMD converges to (Azizan & Hassibi 2019 Gunasekar et al. 2018a).
Proposition 1. Consider linear overparameterized model. For sufficientll small step size, i.e., for any rj > 0 for which 4/(-) nT((+) is convex, and for any initialization wo, the SMD iterates converge to
W
arg min De (w, wo).
wEW
Note that the step size condition, i.e., the convexity of (x)) - (- depends on both the loss and the potential function. For the case of SGD, ((w) //ll and E(y 2 w) ( x ))² so the condition reduces to the well-known
|| In this case, Dw(w, wo) is simply ||w - wo
Corollary 2. In particular, for the initialization wp arg win (/(w,, under the conditions of Proposition 7 the SMD iterates converge to
Woo arg min (w))..
wEW
This means that rumning SMD for linear model with the aforementioned wo, without any explicit regularization, results in a solution that has the smallest potential vi()) among all solutions, i.e., SMD implicitly regularizes the solution with (-)). In particular, this means that SGD initialized around zero acts an an f2-norm regularizer. In this paper, we show that these results continue to hold for highly overparameterizeed nonlinear models in an approximate sense.
THEORETICAL RESULTS
In this section, provide main theoretical results. In particular, show that for highly over- parameterized models (1) SMD converges to a global minimum, (2) the global minimum obtained by SMD is approximately the closest one the initialization in Bregman divergence corresponding to the potential.
B
Woo W
Figure 1: An illustration of the parameter space. W represents the set of global minima, wo the initialization, B is the local neighborhood, w* and the closest global minimum to wo (in Bregman divergence). and Woo the minimum that SMD converges to.
3.1 CONVERGENCE OF STOCHASTIC MIRROR DESCENT
Let us define
Dr, (w. w/) = T.(w) (.(w))-((u')) VI,(w)) (w-))")""ww
which is defined in similar way to Bregman divergence for the loss function. The difference though is that, unlike the potential function of the Bregman divergence, the loss function Lx(.) = fly; f(x,,) need not be convex (even when e(-) is) due to the nonlinearity of f(
5

---

Under review as a conference paper at ICLR 2020
It has been argued in several recent papers that in highly overparameterrzze neural networks, any dom initialization wy is close to W. with high probability (Li & Liang 2018 Du et al. 2018 Azizan
& Hassibi, 2019, Allen-ZZhe 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 wp- There exists w E W and a region B = -ww E (w w') S e} contuining wo, such that Dr,(W, (w, w 2 0, = n, for all w' E B.
RP|
is important to understand what this assumption means. Since L((-) is not necessarily convex, is certainly not the case that Dr. (wo, w') 2 0 for all w'. However, since w is minimizer of Li(.), there will be a neighborhood around it such that for all w' in this neighborhood Dr. (w, w') 2 0 (see Fig. for an illustration). What we are requiring is that the initialization wp be inside the intersection of all such neighborhoods for i ,.,,, n. In other words, require wi close enough to W.
Li
w
(w, w')
w
Figure 2: An illustration of Dr, (w, w') 2 O in local region in Assumption
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 7. J(l)) have bounded gradient and Hessian on the convex hull of B, i.e., fi (w")l S 7 and Amin 5, (w²)) S >maxx (H f, S B, 1,...,n, for all w' E conv B.
This is again mild assumption, which is assumed in other related work such as (Oymak & Soltanolkotabi] (209)) as well. Note that we do not require a to be positive (just its boundedness). The following theorem states that under Assumption [1 SMD converges to global minimum.
Theorem 3. Consider the set of interpolating parameters W {w Rº f(z,, w) yo. i 1,..., n and the SMD iterates given in (3), where every data point is revisited after some steps. Under Assumption for sufficiently small step size, i.e., for any r > 0 for which vi.) n.:(.) is strictly convex on B for all i, the following holds.
1. All the iterates {w;} remain in B.
2. The iterates converge (to woo).
3. Weo E 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 fixixed 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 (b() and in that particular order. In fact, one cannot guarantee that the SMD iterates get closer an interpolating w at every step in the usual Euclidean sense. However, once can establish that it gets closer in (w,,)) -). Finally, it is important to note that we need the step size to be small enough to guarantee the strict convexity of vb()) nL)(-) in B, not globally.
Denote the global minimum that is closest to the initialization in Bregman divergence by w", i.c.. w"
arg min De wo).
wEW
Recall that in the linear case, this was what SMD converges to. We show that in the nonlinear case, under Assumptions and 2 SMD converges to point woo which is "very close" to w...

---

Under review as a conference paper at ICLR 2020
Theorem 4. Define wt arg min wEW (w wo). Under the conditions Theorem and As-
sumption 2 the following holds
1. (W0e, wo) ( + o(c)
2. Ds wx) o(e)
In other words, if start with an initialization that is (c)) away from W (in Bregman divergence), we converge to point Wao E W that is o(c) away from w². The Bregman divergence of this point o(c) from the minimum value it can take.
Corollary 5. For the initialization wo arg win (w)), under the conditions of Theorem w arg wiw (w)) and the following holds.
1. (w)))) = v0(w) o(c)
2. Do("", wx)) o(EE)
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 ). any differentiable loss (()), any parameter W, and any step size 1j > 0, the following relation holds for the SMD iterates {we}
Delw, wi-1) (w w;) + Dw-nn nt. (wi, w 1) + nL:(w;; + nDI, (w, w;-1),
(9)
for all 1.
This identity allows one to prove the results in a remarkably simple and direct way. Due to space limitations, the proofs relegated to the supplementary material.
The ideas behind this identity are related to Hos 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 (Azizan & Hassibi 2019).
EXPERIMENTAL RESULTS
In this section, we provide our experimental results, which consist of two main parts. In the first part, 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, assess the generalization eтror of different mirrors, which correspond to different regularizers, in order to understand which regularizer performs better.
Wh
W
10:30
...D -Q
Cin M/rm
Figure 3: An illustration of the experiments in Table !

---

Under review as a conference paper at ICLR 2020
SMD 1-norm
SMD 2-norm (SGD)
SMD 3-norm
SMD 10-norm
1-norm BD
141
9.19
10ss
4.1
10a
2.34 10
2-norm BD
3.15 X 10
562
1.24 x 10
6.89 X 103
3-norm BD
4.31 X 10*
107
53,5
1.85 x 102
10-norm BD
6.83 10
972
7.91 10-5
2.72 10
Table 1: Fixed Initialization. Distances from final points (global minima) obtained by different algo- rithms (columns) from the same initialization (Fig. B). measured in different Bregman divergences (rows). First Row: The closest point wo in & Bregman divergence, among the four final points, is exactly the one obtained by SMD with I-norm potential. Second Row: The closest point to wo in l Bregman divergence (Euclidean distance), among the four final points, exactly the one ob- tained by SGD. Third Row: The closest point to wi in &a Bregman divergence, among the four final points, is exactly the one obtained by SMD with 3-norm potential. Fourth Row: The closest point to wi in f1o Bregman divergence, among the four final points, is exactly the one obtained by SMI) with 10-norm potential.
4.1 Do SMDs CONVERGE TO THE CLOSEST POINT IN BREGMAN DIVERGENCE?
While accessing all the points on W and finding the closest one is impossible, we design system- atic experiments to test this claim. We run experiments on some standard deep learning problems, namely, a standard CNN on MNIST (LeCun et al., 1998) and the ResNet-18 (He et al. 2016) on CIFAR-10 (Krizhevsky & Hinton, 2009). We train the models from different initializations, and with different mirror descents from each particular initialization, until we reach 100% training accuracy, i.c., point on W. We randomly initialize the parameters of the networks around zero. We choose 6 independent initializations for the CNN, and 8 for ResNet- 18, and for each initialization, we run dif- ferent SMD algorithms with the following four potential functions: (a) E norm, (b) & norm (which SGD), (c) fa norm, (d) 10 norm (as a surrogate for (oo). See Supplementary Material for more details on the experiments.
Final
Final 2
Final
Final 4
Final
Final 6
Final
Final
Initial
6x 10a
2.9 10*
2.8 10
2.8 10a
2.8 x 10
2.8 10
2.8 x 10
2.8
10"
Initial
2.8 10a
x 10a
2.8 x 10
2.8 10a
2.8 10a
x 10a
2.8 x 10
2.8
10
Initial
2.8 10a
2.9 10a
5.6 10a
2.8 10a
2.8 103
2.8 10a
2.8 x 10
2.8 10
Initial
2.8 10
2.9 103
2.8
5.9 10a
2.8 x 10
10
2.8 x 10
2.8 x 10
Initial
2.8 x 10a
2.9 10a
2.8 10a
2.8 x 10a
5.7 10a
2.8 10a
2.8 x 10a
2.8 x 10a
Initial
2.8 10a
2.9 10a
2.8 10a
2.8 10a
2.8 x 10a
5.6 x 10a
2.8 x 10a
2.8 x 10a
Initial 7 2.8 10a
2.9 x 10a
2.8 x 10a
2.8 x 10a
2.8 x 10a
2.8 x 10a
6 X 10
2.8 x 10a
Initial 8
2.8 103
2.9 x 103
2.8
x 10a
2.8
x 10a
2.8 x 10a
2.8 x 10a
2.8 x 103
5.8 x 10a
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, exactly the one obtained by the algorithm from initialization
66)
Initializations:
Final Points:
(2)
(6)
(3)
Figure 4: An illustration of the experiments in Table 2
We measure the distances between the initializations and the global minima obtained from different mirrrs and different initializations, in different Bregman divergences. Table and Table show some examples among different mirrors and different initializations, respectively. Fig. shows the
8

---

Under review as a conference paper at ICLR 2020
distances between particular initial point and all the final points obtained from different initializa- tions and different mirrors (the distances are often orders 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
Logeriin 7attre
Logeebee 35ln00
20
900
IHd 1992
5-22 (990)
1990
isal 00011
tral 4 200010
Foe sunt
Ra Sun1o
th
MNIST. SGD Starting from Initial 4
CIFAR-10. SGD Starting from Initial
Figure 5: Distances between particular initial point and all the final points obtained by both dif- ferent 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 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 f--oorm potential induces sparsity. Fig. 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 & SMD has more weights at and close to zero, which confirms that induces sparsity. The histogram of the SMD (SGD) looks almost perfectly Gaussian, whereas the f and ε1 histograms are shifted to the right, so much so that almost all weights in the L1 solution 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% higher accuracy. For CIFAR-10. however, there is significant difference between the test errors of different mir- rors/regularizers on the same ResNet-18 architecture. Fig. 7 shows the accuracies of different algorithms with cight random initializations around zero, as discussed before. Counter-intuitively 1o performs consistently best, while é performs consistently worse. This result suggests the impor- lance of comprehensive study of the role of regularization, and the choice of the best regularizer, improve the generalization performance deep neural networks.

---

Under review as a conference paper at ICLR 2020
500000
180000
11-norm
12-nrrm
200000
250000
210000
200000
220000
Frequency
40000
50000
0.00
0.01
0.02
0.03
0.84
0.05
0.00
0.01
0.02
0.03
0.04
0.05
Absolute Value Weights
Absolute Value Weights
100000
100000
B.nom
110 norm
160000
250000
140000
120000
200000
Frequency
100000
150000
00000
60000
300000
40000
50000
20000
0.00
0.02
0.05
0.00 9.01
0.04
Weights
Value Weights
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 x 10 dimensional weight vector that perfectly interpolates the data. Even though the weights remain quite small, the histograms are drastically different. f SMD induces sparsity on the weights, as expected. SGD appears to be produce Gaussian distribution the weights. fy-SMD starts reduce the sparsity, and ε1 shifts the distribution of the weights significantly, so much so that almost all the weights are non-zero.
Test Accuracy(9)
SMD 1-nom
500
SMD 3-norm
SMD 10-norm
Figure 7: Generalization performance of different SMD algorithms on the CIFAR-10 dataset using
ResNet- 18. t10 performs consistently better, while performs consistently worse.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Alessandro Achille and Stefano Soatto. On the emergence of invariance and disentangling in deep representations. arXiv preprint arXiv:1706.01/ 01350, 2017.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In Proceedings of the 36th International Conference Machine Learning. PMLR, 2019.
Dario Amodei, Sundaram Ananthanarayanan, Rishita Anubhai, Jingliang Bai, Eric Battenberg, Carl Case, Jared Casper, Bryan Catanzaro, Qiang Cheng, Guoliang Chen, al. Deep speech 2: End- to-end speech recognition in english and mandarin. In International Conference on Machine Learning, pp. 173-182, 2016.
Navid Azizan and Babak Hassibi. Stochastic gradient/mirror descent: Minimax optimality and implicit regularization. In International Conference on Learning Representations (ICLR), 2019.
Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-175, 2003.
Yuan Cao and Quanquan Gu. A generalization theory of gradient descent for learning over- parameterized deep relu networks. arXiv preprint arXiv:1902.011 384, 2019.
Nicolo Bisa-Bianchi, Pierre Gaillard, Gábor Lugosi, and Gilles Stoltz. Mirror descent meets fixed share (and feels no regret). In Advances in Neural Information Processing Systems, pp. 980-988, 2012.
Pratik Chaudhari and Stefano Soatto. Stochastic gradient descent performs variational inference, converges limit cycles for deep networks. In International Conference Learning Represen- tations, 2018
Simon S Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. arXiv preprint arXiv: 1.03844, 2018.
Claudio Gentile. The robustness of the p-norm algorithms. Machine Learning, 53(3):265-22) 2003.
Alex Graves, Abdel-rahman Mohamed, and Geoffrey Hinton. Speech recognition with deep recur- rent neural networks. In 2013 IEEE international conference on acoustics, speech and signal processing, pp. 6645-6649. IEEE, 2013.
Adam J Grove, Nick Littlestone, and Dale Schuurmans. General convergence results for linear discriminant updates. Machine Learning, 43(3):173-210, 2001.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems, pp. 6152-6160, 2017.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pp. 1827- 1836, 2018a.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Implicit bias of gradicnt descent linear convolutional networks. arXiv preprint 1006.0:80000004000 2018b.
Babak Hassibi, Ali H. Sayed, and Thomas Kailath. Hoo optimality criteria for LMS and backprop- agation. In Advances in Neural Information Processing Systems 6, pp. 351-358. 1994.
Babak Hassibi, Ali H Sayed, and Thomas Kailath. Indefinite- Quadrrati Estimation and Control: A Unified Approach H2 and H-infinity Theories, volume 16. SIAM, 1999.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
11

---

Under review as a conference paper at ICLR 2020
Jyrki Kivinen and Manfred K Warmuth. Exponentiated gradient versus gradient descent for linear predictors. Information and Computation, 132(1):1-63, 1997.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Tech- nical report, Citeseer, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks, In Advances in Neural Information Processing Systems, pp. 1097-1105, 2012.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2322 1998.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553):436, 2015.
Jason D Lee, Max Simchowitz, Michael Jordan, and Benjamin Recht. Gradient descent only converges minimizers. In Conference Learning Theory, pp. 1246-1257, 2016.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in Neural Information Processing Systems, pp. 8157- 8166, 2018
Cong Ma. Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in nonconvex sta- tistical estimation: Gradient descent converges linearly for phase retrieval and matrix completion. In International Conference on Machine Learning, pp. 3351-3360, 2018a.
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effec- tiveness of SGD in modern over-parametrized learning. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pp. 3325-3334. PMLR, 2018b.
Poorya Mianjy, Raman Arora, and Rene Vidal. On the implicit bias of dropout. In International Conference Machine Learning, pp. 3537-3545, 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver. Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015.
Arkadii Nemirovski and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Behnam Neyshabur, Ryota Tomioka, Ruslan Salakhutdinov, and Nathan Srebro. Geometry of opti- mization and implicit regularization in deep learning. arXiv preprint arXiv:1005.03071, 2017.
Samet Oymak and Mahdi Soltanolkotabi. Overparameterized nonlinear learning: Gradient descent takes the shortest path? In Proceedings of the 36th International Conference on Machine Learn- ing. PMLR, 2019.
Ravid Shwartz-Zir Ziv and Naftali Tishby. Opening the black box of deep neural networks via informa- tion. arXiv preprint arXiv:1703.0000 000000 2017.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering
the game of go with deep neural networks and tree search. Nature, 529(7587):844
2016.
Dan Simon. Optimal state estimation: Kalman, H infinity, and nonlinear approaches. John Wiley & Sons, 2006.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimiza- tion landscape of over over--vrameen peee-paammterrzeed shallow neural networks. arXiv preprint arXiv: 2017.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data. arXiv preprint 1710.//710. 2017.
12

---

Under review as a conference paper at ICLR 2020
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, Quoe V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. Google's neural machine trans- lation system: Bridging the gap between human and machine translation. arXiv preprint 16X1v:1609008144, 2016.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint urXiv:1611.03533 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.
13

---

Under review as a conference paper at ICLR 2020
Supplementary Material
A PROOFS OF THE THEORETICAL RESULTS
In this section, prove the main theoretical results. The proofs are based fundamental identity about the iterates of SMD, which holds for mirrors and overparametereized (even nonlinear) models ( We first prove this identity, and then use it to prove the convergence and implicit regularization results.
A.1
FUNDAMENTAL IDENTITY OF SMD
Let us prove the fundamental identity.
Lemma 6 For any model f(--),, any differentiable loss f(-), any parameter w E W, and any step size 1j > O, the following relation holds for the SMD iterates {w:}
Dol wx-1) (ww wi) + Do- (wi, w/-1) + (w;) + n (w, w1-1);
for all i 1.
Proof of Lemma 6 nition
Let us start by expanding the Bregman divergence (w ws) based on its defi-
(w ws) (wr) vww)) (w:(w;;) (w ww))
By plugging the SMD update rule Ve((w))) = V V - 17 L, (w:-1) into this, we can write
(w, wx) (bw) (w.)) v 1) (w wi) 1/ Li (w -ow-a ww)- (10)
Using the definition of Bregman divergence for (w, w1-1) and (w,, w/-1), ie., Dw w;-1) = (ww) 1 - Veb(w,,1) (w - w;-1) and Velw;-1) )² (w; - wi-1), we can express this as
= vlww)) - (((0)11)
(ww, wi) = Dolw, w;-1) (w;-1) + Vv((:-1) (w w/-1) (bww))
( (T wi) + L, (w)-1) ) wi) (11)
= -w, w[-1) + (w;=-1) - (ww)) + ( )7 (w; - -w;-1)
+ (w ( (w- 100-wwp w)) (12)
= -Do wi-1) Do 1;-1) + V L, (w:-1) (T (w-w:) w:).
(13)
Expanding the last term using wA (w wi-1) (w, w;-1). and following the definition of DL, (...) from (7) for (w, w;-1) and (w,, w;-1). we have
Do w;) (ww, w0-1) (w0, w1-1) 1/ (,( ( (w
w:-1)
- LV (1; (Tw -w- (14)
Dw, w;-1) - D (wi, w;- + (Li(w) Li(w;-1) Dr, (w. w;-1))
1) (I,(w:) [x(W=-1) DD, (1, w;-1)) (15)
Doow, wi-1) - Do (;- + (T+(w) - Dr,, (w,,ww1))
- (L, DL, (wi, w+-1)
(16)
Note that for all w E W, we have (.ww) = O. Therefore, for all w W
(1o, w:) = (w, w - (wc, w; w;-1) -1 D1, (w, w;-1) nT((w;) + +1 (wi, wi wi-1). (17)
Combining the second and the last terms in the right-hand hand side leads to
(eww, wx) Ds(w, wi-1) De-nL, (wi, w;-1) DD, (w, wi-1) - nLi(wss, for all W. which concludes the proof.
(18)
14

---

Under review as a conference paper at ICLR 2020
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 the set of solutions.
Assumption I Denote the initial point by wp- There exists w E W and a region B = {ul E IRP Dup (w, w S c containing wo, such that Dr, (w, w') 2 0, = 1.... for all w' E B.
Theorem Consider the set of interpolating parameters W = {w E TRP [(x24 w) Vi: i 1,..., n and the SMD iterates given 33) where every data point revisited after some steps. Under Assumption 7 for sufficiently small step size, i.e. for any nj > 0 for which vb(.) nL1(-) is strictly convex for all i, the following holds.
1. All the iterates {wi} remain in B.
2. The iterates converge (to Wooh.
3. Who E W.
Proof of Theorem 3 from Lemma O
First we show that all the iterates wil remain in B. Recall the identity of SMD
Do(w, w;-1) (ww w)) De- (wi, w;-1) + (Tss()s)) + 1,DL, w;-1)
which holds for w E W. If w;-1 in the region B, we know that the last term Dr, ui;-1) is non-negative. Furthermore, if the step size is small enough that vb(-) n.4(-) is strictly convex, the second term Dg-nLL (w;, w;-1) a Bregman divergence and is non-negative. Since the loss is non-negative, (w,)) is always non-negative. As result, we have
Dww w;-1) Do(w,, w:),
(19)
This implies that (w,, wt) S 6, which means wy is in too. Since wp is in B, wi will be in B, and therefore, w2 will be in B, and similarly all the iterates will remain in B.
Next, we prove that the iterates converge and Who E W. If we sum up identity 9 for all
1,..., T, the first terms on the right- and left-hand side cancel each other telescopically, and we have
T
(ww wo) Dio WT)
Σ Dis-nt,(us wi-1) + nLi(w;) + nDD. (w, w;-1)]
(20)
Since Dw WT) 2 0. we have Σ DDa- nt., (w,, w1-1) 1) + nT((wss) + 17 11, (w, (w,,;-1)) wi-1)] Dww,, wo). If we take oc, the sum still has remain bounded, i.c..
(w w1-1) + (,,)) + 1,D (w, ur S (wwwwo))
(21)
Since the step size is small enough that +b.-) n)((()) is strictly convex for all i, the first term De-nL, (W,, w;-1) is nen-negative. The second term nT,(( is non-negative because of the non- negativity of the loss. Finally, the last term DL, (w, w;-1) is non-negative because w E B for all i. Hence, all the three terms in the summand are non-negative and because the sum is bounded, they should go zero as i + In particular,
D De-nta (W), W:-1) -
(22)
implies w; - w;-1, i.e., convergence (w; + wx)) (Note that the functions va - -n,, do not go to zero, as there is a fixed number, i.e., n, of them). Further,
nT((w))) - 0.
(23)
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, woo W.
15

---

Under review as a conference paper at ICLR 2020
A.3 CLOSENESS OF THE FINAL POINT TO THE REGULARIZED SOLUTION
In this section, we show that with the additional Assumption (which is equivalent to fi(+) having bounded Hessian in B), 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 our fundamental identity for SMD.
Assumption 3 Consider the region B in Assumption on the convex hull of B, i.e., (V(((w)) S 7, and Amin 5 S >max (H (w")) S 3, 1,... n. for all w' E conv B.
7 Se(.) have bounded gradient and Hessian
Theorem Define w* arg win D& (w,, wo). Under the assumptions of Theorem and Assumption the following holds.
1. Do wu) Dw wo) + o(c)
2. (w""" w=)) o(()
Proof of Theorem 4 Recall the identity of SMD from Lemma 6
(u w4-1) (w, w.) which holds for all w E W. Summing the identity for all i 2 1, we have
D De-nL, (wy, wx-1) (w,((w,) + L,0, (10,
Dol wo) = Dw woo) + Σ (D nI. (wi, w;-1) 1) + (u::(w;) + DnDr, ws-1)] i=1
(24)
for all w E W. Note that the only terms in the right-hand side which depend on w are the first one (w,, )xo) and the last one 17 اi= DL. (w, w;-1). what follows, We will argue that, within B, the dependence on w in the last term is weak and therefore wo is close to w².
To further spell out the dependence on w in the last term, let us expand Dr, (w, wi-1)
Dr. (w, w;-1) = L.(w:-1) (L: (w w;-1)
(25)
L. + (1:
wi-1)
(26)
for all w E W, where the first equality comes from the definition of (:.) and the fact that (w) = 0 for E W. The second equality is from taking the derivative of T.(+)) E(y f(())
and evaluating it at u1:1-
By Taylor expansion of fi(w) around w;-1 and using Taylor's theorem (Lagrange's mean-value form), we have
1 2/ (ww- w,-1) 1 (1):(( wi-1), (27) fi(w) = fi(w;-1) + Vfi(w; (w- w:-1) +
for some ú; in the convex hull of w and w;-1. Since fi(w) = yi for all w E W, it follows that
V Vi(w;-)) w;-1) ys --(((=-)))) (w wi )²t Hy (w::(w ws-1),
(28)
for all w W. Plugging this into 26). we have
DL. (w, w;-1) -L (y. fi(w;-1) 1 (o-ww-1) H (w:))w-w---))) (w:-w (29)
for all w E W. Finally, by plugging this back into the identity 24 we have
Do(w, wo) (ww Woo) + 20
Σ
DV- (ws, wi-1) - nL,(w:) - -LL(wi-1)
1 + npf (y: (((ws-1)) [1 5 -w:-i H (w:)) w.-)) (30)
for all w E W. Note that this can be expressed as
(w, wp) = (w, W +C Σ
ne fa(w;=1)) w w;-1)" H (w:)(w - -w;-1, (31)
i=1
16

---

Under review as a conference paper at ICLR 2020
for all W, where C' does not depend on
C= Σ DD- (w,, 11 + nL,(wr) (w, + rf (v: fi(w;-1)) f((w;-1))]-
From Theorem we know that Who E W. Therefore, by plugging it into equation and using the fact that D v Woo Wooo] = O, we have
(woo wo) = = Σ
1 nh (1: - fi(w;-1)) - wi-1)" (wo)) w;-1), (32)
2
where w/ is point in the convex hull of woo and w; (and therefore also in conv B), for all i.
Similarly, by plugging w", which is also W, into (31) we have
(w wo) = Dw(w", w + Σ nf ne - -w;-))
w;-1) H (1f)(
w;-1),
(33)
where w." is point in the convex hull of wn and w;-1 (and therefore also in conv B), for all Subtracting the last two equations from each other yields
(W wo) - Dw(w", wa) (D= Woo) ) n (vi fi(w)-1))
[ww* w;-1)" H (ww wi-1) - (wis wi-1) w (w)) - wi-1)] (34)
Note that since all wn and wn¹' are in conv B, by Assumption 2 we have
al|wxx w;-112 < (woe - w,-1)" H1 (w)) w1-1) S B11 wi-1l1?
(35)
and
a all"* wil1ll s (w" w Hy, (u(")(( wi-1) S $11"" 11-1112
(36)
Further, again since all the iterates (w;) are in B, it follows that I|w 11 O(c). As result the difference of the two terms, i.e., wi-1) (woo w H (w wx-1)]. is also O(e), and we have
|| (w=- H (w"
11-11 1| O and
(w wo) (w wo) -Dww", woo) Σ
ne f(w;-1))((())
(37)
Now note that (y fe(w;-1)) ([((w) - s((w;-1)) ((Vs(())) (ww-) for some Wi; E conv B. Since || w;-1|1 = (()) for all i, and since E(.) is differentiable and fa(-) have bounded derivatives, it follows that (11 - fi(w;-1)) = o(c). Furthermore, the sum is bounded. This implies that D wo) (w"" wo) - Dow"", (ss) o(c), or equivalently
(De (Wox: wo) - Dy(w", wo)) Dw ,,,,) = o(e).
(38)
The term in parentheses (woo wp) Do(w", wo) is non-negative by definition of w*. The second term Du Dw("", Woe) is non-negative by convexity of th. Since both terms are non-negative and their sum is o(e), each one of them is at most o(c), i.c.
Du wo) - D& (w",, wo) = o(c) Dolu", Woo) o(e)
(39)
which concludes the proof.
5, For the initialization = arg min vkww), under the conditions of Theorem wn arg mww vb(w) and the following holds.
Corollary
1. (W v(ww)) o(c)
2. (w0"" w00) =(())
17

---

Under review as a conference paper at ICLR 2020
Proof of Corollary
The proof is straightforward application of Theorem Note that have
(a(w, wo) vi(w) (b(w)) Veb(wo) (F wo)
(40)
for all w. When wg arg wER" (w)w,, it follows that Vvb(wo) = O. and
Do (w, wo) = (ww)) - (ww))
(41)
In particular, by plugging in whe and w", we have D3 (w wo) = (wwx)) - (ww)) and Dø(w", wo) ww) ((w") (wo)). Subtracting the two equations from each other yields
De (wee, wo) (w=, wo) (w vb("),
(42)
which along with the application of Theorem concludes the proof.
A.4 CLOSENESS TO THE INTERPOLATING SET IN HIGHLY OVERPARAMETERIZED MODELS
As mentioned earlier, it has been argued in number of recent papers that for highly overparam- eterized 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, > n, and so the dimension of the manifold W, which is n, is very large. For simplicity, we outline that a similar argument can be used for general Bregman divergence. Note that the distance of an arbitrarily chosen wy W is given by
argument for the case of Euclidean distance, bearing in mind
min || woll?
s.t. y f(x, w)
where y vec(y,, 1, I.....n) .)) and f(x, w) veo(f w), I....nn). This can be approxi- mated by
min || woll
woll
y = f(z, wo) + V fz, wo) T ww))
where fx wo) vee Vee(V w) ,.....n) n) the x p Jacobian matrix. The latter optimization can be solved to yield
I|, woll ~ (y - f(a, wo)) (vf(z, wo) 1o) [V, wo)) -1 (y f(x, wo))
(43)
Note that (f ffr wo) is the x; are sufficiently random, and >> n, it not unreasonable to assume that whp
matrix consisting of the of p outer products. When
Amin (Vf(r, w V fzz wo)) = !(p).
from which we conclude
lw. wall || - fxx 12 -1-)
(44)
since y - ff(x, wo) is n-dimensional. The above implies that wg is close w, and hence W.
18

---

Under review as a conference paper at ICLR 2020
B MORE DETAILS ON THE EXPERIMENTAL RESULTS
In order to evaluate the claim, we run systematic experiments on some standard deep learning prob- lems.
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 convo- lution layers and 2 fully connected layers. The convolutional layers and the fully connected layers are picked wide enough to obtain 2 x 10 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 x 10 parameters in ResNet-18, 18, the problem is again highly overparameterized.
Loss Function. We use the cross-entropy loss as the loss function our training. We train the models from different initializations, and with different mirror descents from each particular initial- ization, 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 initializa- tion, we run the following different SMD algorithms.
Algorithms. We use the mirror descent algorithms defined by the norm potential (bw) = w for the following four different norms: (a) & norm, i.e., g = 1 1 c, (b) le norm, i.e., 9 = 2 (which is SGD), (c) & norm, i.e., 3. (d) lı0 norm, i.e., 10 (as surrogate for foo norm). The update rule can be expressed as follows.
wi. = |w:-1s1 1-1 sign(wi-1.) - v Li(Wi-
sign [wx-1,ي 9-1 sign( (1)) - - LV (45)
where Wi-1, denotes the j-th element of the Wi-1 vector.
We fixed step size 17. 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 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 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.
5
S depict these results for
Table 3: MNIST Initial Point
SMD I-norm
SMD 2-norm (SGD)
SMD 3-norm
SMD 10-norm
1-norm BD
2.767
937.8
1.05
10a
1.882 10a
2-norm BD
301.6
58.61
261.3
2.118 x 10a
3-norm BD
1720
37.45
7.143
2518
10-norm BD
7.453 10
773.4
0.2939
0.003545
19

---

Under review as a conference paper at ICLR 2020
Table 4: MNIST Initial Point
SMD I-norm
SMD 2-norm (SGD)
SMD 3-norm
SMD 10-norm
1-norm BD
2.78
945
1.37
10
2.01 10"
2-norm BD
292
59.3
374
2.29 x 104
3-norm BD
1.51 x 103
38.6
11.6
2.71 10
10-norm BD
1.06 x 10
831
0.86
0.00321
Table MNIST Initial Point
SMD I-norm
SMD 2-norm (SGD)
SMD 3-norm
SMD 10-norm
1-norm BD
3.02
968
1.06
10a
1.9 10
2-norm BD
291
60.9
272
2.12 10a
3-norm BD
1.49 x L03
39.1
7.82
2.49 10
10-norm BD
1.1 x 10
900
0.411
0.00318
Table 6: MNIST Initial Point
SMD 1-norm
SMD 2-norm (SGD)
SMD 3-norm
SMD 10-norm
1-norm BD
2.78
1.21 x 10
1.08
10a
1.92 10
2-norm BD
291
77.3
271
2.15 10a
3-norm BD
1.48 x 103
49.7
7.56
2.52 x 10
10-norm BD
9.9 x 10"
1.72 x 10a
0.352
0.00296
Table 7: MNIST Initial Point 5
SMD 1-norm
SMD 2-norm (SGD)
SMD 3-norm
SMD 10-norm
1-norm BD
2.79
958
1.08 x 10a
2 x 10
2-norm BD
292
60.4
271
2.28 10*
3-norm BD
1.49 x 103
39
7.52
2.69 103
10-norm BD
9.09 x 107
846
0.342
0.00309
Table MNIST Initial Point SMD 2-norm (SGD)
SMD 1-norm
SMD 3-norm
SMD 10-norm
1-norm BD
2.96
930
1.08
10a
1.9 x 10
2-norm BD
308
59
271
2.12 x 10*
3-norm BD
1.63 x 103
38.6
7.46
2.47 103
10-norm BD
1.65 x 108
864
0.334
0.00295
B.1.2 CLOSEST MINIMUM FOR DIFFERENT INITILIZATIONS WITH FIXED MIRROR
We provide the pairwise distances between different initial points and the final points (global min- ima) obtained by using fixed SMD algorithms 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, the one corresponding to that point. Tables 9 10 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.
1.1.3 CLOSEST MINIMUM FOR DIFFERENT INITILIZATION AND DIFFERENT MIRRORS
Now we assess the pairwise distances between different initial points and final points (global min- ima) obtained by all different initilizations and all different mirrors (Table 8). The smallest element in each row exactly the final point obtained by that mirror from that initialization, among all the mirrors and all the initial points.
20

---

Under review as a conference paper at ICLR 2020
Table 9: MNIST 1-norm Bregman Divergence Between the Initial Points and the Final Points ob-
tained by SMD 1-norm
Final
Final
Final 3
Final 4
Final 5
Final 6
Initial Point
2.7671
20311
20266
20331
20340
20282
Initial Point
20332
2.7774
20281
20299
20312
20323
Initial Point 3
20319
20312
3.018
20344
20309
20322
Initial Point
20339
20279
20310
2.781
20321
20297
Initial Point 5
20347
20317
20273
20316
2.7902
20311
Initial Point
20344
20323
20340
20318
20321
2.964
Table 10: MNIST 2-norm Bregman Divergence Between the Initial Points and the Final Points obtained by SMD 2-norm (SGD)
Final
Final
Final
Final 4
Final 5
Final 6
Initial Point
58.608
670.75
667.03
684.18
671.36
667.84
Initial Point 2
669.84
59.315
669.16
682.04
669.45
669.98
Initial Point 3
666.35
670.22
60.858
683.44
667.57
669.99
Initial Point
669.71
668.86
671.19
77.275
670.33
669.7
Initial Point 5
671.1
669.12
668.45
683.61
60.39
666.04
Initial Point
669.46
670.92
671.59
684.32
667.37
59.043
Table 11: MNIST 3-norm Bregman Divergence Between the Initial Points and the Final Points obtained by SMD 3-norm
Final
Final
Final
Final 4
Final 5
Final 6
Initial Point
7.143
35.302
32.077
32.659
32.648
32.309
Initial Point 2
32.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
32.116
34.731
32.376
32.431
31.699
7.4593
Table 12: MNIST 10-norm Bregman Divergence Between the Initial Points and the Final Points obtained by SMD 10-norm
Final 1
Final 2
Final 3
Final 4
Final 5
Final 6
Initial Point
0.00354
0.37
0.403
0.286
0.421
0.408
Initial Point 0.33
0.00321
0.369
0.383
0.415
0.422
Initial Point 0.347
0.318
0.00318
0.401
0.312
0.406
Initial Point 0.282
0.38
0.458
0.00296
0.491
0.376
Initial Point 0.405
0.418
0.354
0.484
0,00309
0.48
Initial Point 0.403
0.353
0.422
0.331
0.503
0.00295
21

---

Under review as a conference paper at ICLR 2020
10F5 SNO sd FS 30
119022
189655
11973 7
21:62 22
21555.7
21151.2
211523
S5
21162.3
21153
2470.968
2470
2470.908
24700
24700
218
3477
500
2469
0.408L4
0422372
0.405223
0.376555
200322
20015
5 200
6
2200
22787-1
T3
22N0S
22798
245
2688
2507
7667
2607
A3
2007
0.47442
0415
0.51
D
0503257
Figure 8: 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.
5 1155 30 30 SWIDD 10 2 SWN 1o SWD 10Ft
1929176
7
35765%
S
3 24556
24555
21553
#7
PILSA
2550
2550 SAW
2518
DSYO 173
25
0,25822
O. 0.33366
0.009653
O. 0,3WPSS
1
18S77
1995222 2
19980233
3
21139
211865
2119
2498
476
2409
2489
415
2409 302
PADS OMN
2 ONA
0566577
DOCSER
0.477535
0742790
O.
2007
2009997
201071
200992
200N22
22902
22901
22904
22808
22496-
2706 C1
SSS
2700 491
2706
852
2706
2706 22
O. 0.39977
O 0322543
180211
190679
3677A00
187959
23179
2116A
211653
AO
2517 GLY
107
248
857
511
3470K
28
0.40 334
2517
2517
2517
22900.00
229933
2293.
22938
72
S4
1000E 21
704
4250
705 155
701 3650
32, 3OSSS
32 42.5135
32 2844
3E SSSKA
455226
7.70754
0.7276
0.71877
0.944199
6.78977
0.334
70H
705
32
F5 SMOO
22922-12
22922
22982
43
22900
31
7OL 5516
TOL 1583
270 872
32. 54062
32 S7516
D. CASSSA
6.72732
6.347117
F4 SHO
220823
19726.33
58
22637.
70S 1756
785 SEHB
74S- 7715
ST SOLD
AM07
0.51548A
0.7500M
D. 0,351
AJRYARSA
0.579777
TZ
F3 SMD
2009041
2200
2272344
22733
74
1998
0644
PUA J132
78211T
772767
1
O 02-455
7AN077
701L
272
POLL
F2 SMDD
202986
13730
24200-62
242833
22
24011
73
760-351
2561
6536
757.0133
CRSA
3M GADSS
3A MARSS
S4 7X7
133044
1241466
1,778044
224999
750
750
750
Fl SMND
10500.0
22902
71
22997.06
22910
2332
2023
5777
5977
7.34230
31. 59M47
32 3006
32 5730
32 11641
0.SEES3
0.63365
0.585511
6.801500
7.305566
26
700
705
32
F5 SMID
20455-42
20183
46
20M68
45
20HBA
2714
SCT 3379
CED 9933
6SSA OME
DB S1245
TP 240S
D7 20046
KC SSAW
DO SPAA
854
7:91
86A
U54 2965
930
S7
054
79
20499 88
2049 01
3561
GPT 5665
GO WV-Y
ST SAOIS
DIC WYZZ
BIG 2313
B4G 5443
BAG 6509
20406
S7
SNO
20015
20572 S4
1214
517
69977
THE S531A
4017
1758.22 299
1718-575
1756.57
3718.06
1710
1710-531
7
7X
F3 SMDD
204530
20000
38
9677
20009:
36
2053 DZ
SKT 052E
S0 557O7
SAN 44G
S 737337
54084
57
500 454
500
2781
500
900
524
900 3729
2065
900
ON
994 9926
214577-21
30
2-
S70 2202
BAR SECO
67 STEE
36740
KT 4MA
754
1445
7577
3:33
16-7
1642
F2 SWS
20500105
20401.
2040
2000N
670
67
67
851
830
831
651
851
631
SWO
2012
20W77:15
20476.10
20493 D0
55-50766
65S 2499
67 TOMS
37 45100
RSS 47958
KIS SKAVK
D5 33501
773. LA
7523
772 8A42
773 9967
66
773.
F6 SNO
2001
51
20022
2002220
20229
2594022
SM0 2012
7151
9599 204
18S7 SSS
LASE OB
OR
1.5SE- 40
1.65E-4 155--00
960
USSO
5- SWI F SMND
20002
2
20112
205211
203209
923 9KG
976
438
DAS
2S SSX LOS
SS1 AM
47
9 SE
9 OOT
9,15
2011
202994
20H13
2,7M1
203154
SWS 289
SUMS 359
MAZ 3356
S-L 77
SSSS TD
9 TOT
977
407
DC
9.96
F3 SWD
20006-2
202900
59
78
20108
2OB 2Z
200
SUN
SPN
JSLE 2AS
JONE COC
USL FAN
15 DOR
LIE-OO LE-08
JE OR
1.1E 1.IE-OR
08
1.1F
110-00
56
27777M3
31
O2
SEMO S1S
1544 ANG
1540 935
LOSE OR
Q8
1066 C8
1060-08
2001
20278
LOSE
2-1
SNO
47
20332
22
59
301
5218
538
95%-4615
SNG B459
L710 BRS
7751 S8
1758 31
1751 224
7.45E+08
7.45E OB
7.48E-08
7.45 408
7.55-408
1755
a I-merm 10
80
B 1-norm 80
80
80
is 1-torm BO
DO
BD
BD
B
B
BE
B
B
1-torm
i 1-nom
B 2-torm
Il mmrrm
3-3ormm
B Smorm
3
i Smorm
IS S-torm
10
2 10morm
N 10morm
i 10morm
22

---

Under review as a conference paper at ICLR 2020
B.2
CIFAR-10 EXPERIMENTS
B.2.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 CIFAR- 1-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 T3
19 20 depict these results for 8 different initializations. The rows are the distance metrics used the Bregman Diver- gences with specified potentials. The columns are the global minima obtained using specified SMD) algorithms.
14
T3 16
Table 13:
CIFAR-10 Initial Point 1
SMD 1-norm
SMD 2-norm (SGD)
SMD 3-norm
SMD 10-norm
1-norm BD
189
9.58 x 10
4.19 x 10a
2.34 x 10"
2-norm BD
3.12 x 10a
597
1.28 10a
6.92 10
3-norm BD
4.31 X 104
119
55.8
1.87
10a
10-norm BD
1.35 x 10
869
6.34 x 10-3
2.64 x 10-8
Table 14: CIFAR-10 Initial Point 2
SMD 1-norm
SMD 2-norm (SGD) SMD 3-norm
SMD 10-norm
1-norm BD
275
9.86 x 103
4.09 x 10a
2.38 x 10"
2-norm BD
4.89 x 103
607
1.23 10s
7.03 10
3-norm BD
9.21 X 104
104
53.5
1.88
10
10-norm BD
1.17 x 10
225
0.000102
2.65 x 10-6
Table 15: CIFAR-10 Initial Point 3
SMD 1-norm
SMD 2-norm (SGD) SMD 3-norm
SMD) 10-norm
1-norm BD
141
9.19 x 103
4.1 x 10t
2.34 10a
2-norm BD
3.15 x 103
562
1.24 x 103
6.89 x 103
3-norm BD
4.31 x 10
107
53.5
1.85
102
10-norm BD
6.83 x 1013
972
7.91 10-3
2.72 10-8
Table 16: CIFAR-10 Initial Point 4
SMD 1-norm
2-norm (SGD)
SMD 3-norm
SMD 10-norm
1-norm BD
255
9.77 103
4.18
10a
2.36 10"
2-norm BD
3.64 x 103
594
1.26 10
6.96 x 10
3-norm BD
5.5 x 104
116
54
1.87 102
10-norm BD
3.74 10
640
5.33 10-5
2.67 10-8
Table 17: CIFAR- Initial Point
SMD 1-norm
SMD 2-norm (SGD)
SMD 3-norm
SMD 10-norm
1-norm BD
113
9.48 103
4.15 10a
2.32 10a
2-norm BD
2.95 X 103
572
1.27 10x
6.85 10x
3-norm BD
3.68 x 10*
109
56.2
1.84 x 102
10-norm BD
2.97
10
151
5.74 10 1
2.61 10 10-5
23

---

Under review as a conference paper at ICLR 2020
Table 18: CIFAR-10 Initial Point 6
SMD I-norm
SMD 2-norm (SGD)
SMD 3-norm
SMD 10-norm
1-norm BD
128
9.25
10
4.25 10
2.34 10"
2-norm BD
2.71 x 10s
558
1.29 x 103
6.89 x 103
3-norm BD
3.34 x 10*
104
55.3
1.85 10
10-norm BD
2.61 x 1013
612
4.74 10-3
2.62 x 10-8
Table 19: CIFAR-10 Initial Point 7
SMD 1-norm
SMD 2-norm (SGD)
SMD 3-norm
SMD 10-norm
1-norm BD
223
9.76
10a
4.38
10a
2.27 10"
2-norm BD
2.41 x 103
599
1.37 103
6.65 x 103
3-norm BD
2.3 x 104
116
61
1.78 x 102
10-norm BD
4.22 10
679
6.42 10-3
2.55 10-5
Table 20: CIFAR-10 Initial Point 8
SMD 1-norm
SMD 2-norm (SGD) SMD 3-norm
SMD 10-norm
1-norm BD
145
9.37 x 10
4.17 10a
2.36 10
2-norm BD
2.48 103
576
1.26 10
6.99
103
3-norm BD
2.85 x 104
108
54.5
1.89 x 102
10-norm BD
1.81 x 10
1.22 x 10a
5.2 x 10-5
2.64 x 10-8
B.2.2 CLOSEST MINIMUM FOR DIFFERENT INITILIZATIONS WITH FIXED MIRROR
We provide the pairwise distances between different initial points and the final points (global min- ima) obtained by using fixed SMD algorithms in CIFAR-I0 dataset using ResNet-18. Note that the smallest element each row is on the diagonal, which means the closest final point to each ini- tialization, among all the final points, is the corresponding to that point. Tables 21 23 24 depict these results for 4 different SMD algorithms. The rows are the initial points and the columns are the final points corresponding each initialization.
24

---

Under review as a conference paper at ICLR 2020
Table 21: CIFAR-10 1-norm Bregman Divergence Between the Initial Points and the Final Points
obtained by SMD 1-norm
Final
Final 2
Final 3
Final 4
Final 5
Final
Final 7
Final
Initial
1.9 10
8.1
10
8.1 10"
8.4 10
10"
8.2 10"
10"
7.8
10
Initial
8.1 10*
2.7
10a
10*
8.3 10*
8 10*
8.2 10
7.8
10*
7.9 10
Initial
10*
10
1.4 10
8,4 10
10"
8.1 10"
7.8 10*
7.8 10
Initial
8.1 10a
10a
8.1 10*
2.5 10a
104
8.2 104
7.8 10a
7.9 10
Initial
8.1 10*
10
8.1 10
8.3 x 10*
1.1 10a
8.1
7.8 10a
7.8 10
Initial
8.1 10*
8.1 10
8.4 x 10
x
1.3 10a
7.8 x
7.8 10
Initial 7
8.1 10*
8.1
10
X
8.4 10
8.1 10*
2.2 x 10
7.8 10
Initial 8.1 X 10*
8.1 10
8.1 X
8.4 X 10
7.9 x 104
8.1 x 10*
7.8 10*
1.5 X 10
Table 22: CIFAR-10 2-norm Bregman Divergence Between the Initial Points and the Final Points
obtained by SMD 2-norm (SGD)
Final 2
Final 4
Final
Final
Final
Initial
6 10a
2.9 x 10"
2.8 x 10"
2.8 x 10a
2.8 x 10
2.8 x 10"
2.8 x 10
2.8 x 10
Initial 2.8 10
6.1 x 10a
2.8 x 10
2.8 x 103
2.8 x 10
2.8 x 10a
2.8 x 103
2.8 x 10
Initial
2.8 10
2.9 x 10a
5.6 10
2.8 10a
2.8 10a
2.8 10a
2.8 102
2.8 10
Initial
2.8 10a
2.9 10a
2,8 10a
5.9 x 10a
2.8 10a
2.8 10a
2.8 10a
2.8 10a
Initial
2.8 10a
2.9 10a
2.8
10a
2.8 10a
5.7 10a
2.8 x 10a
2.8 x 10a
2.8 10a
Initial
2.8 10
2.9 10a
2.8 10
2.8 10
2.8 10
5.6 10a
2.8 10a
2.8 x 10a
Initial 7
2.8 10a
2.9 10a
2.8
10a
2.8 10a
2.8 10a
2.8 x 10a
6 102
2.8 10a
Initial
2.8 x 10a
2.9 10a
2.8
10
2.8 10a
2.8 10a
2.8 10
2.8 10a
5.8 10a
Table 23: CIFAR-10 3-norm Bregman Divergence Between the Initial Points and the Final Points
obtained by SMD 3-norm
Final
Final
Final
Final
Final
Final
Final
Final
Initial
55.844
103.47
103.61
104.05
106.2
105.32
110.88
104.56
Initial 2
105.87
53.455
103.68
104.04
106.31
105.34
110.93
104.58
Initial 3
105.89
103.59
53.527
104.09
106.29
105.35
110.99
104.55
Initial 4
105.83
103.54
103.64
53.978
106.23
105.3
110.87
104.54
Initial 5
105.82
103.55
103.64
104
56.161
105.34
110.88
104.55
Initial 6
105.91
103.6
103.66
104.1
106.28
55.316
110.94
104.55
Initial 7
105.87
103.51
103.67
103.98
106.26
105.25
61.045
104.5
Initial 8
105.77
103.54
103.59
104.04
106.25
105.28
110.88
54.509
25

---

Under review as a conference paper at ICLR 2020
Table 24: CIFAR-10 10-norm Bregman Divergence Between the Initial Points and the Final Points
obtained by SMD 10-norm
Final
Final
Final 3
Final
Final 5
Final 6
Final
Final 8
Innal
2.61
2.89
10
2.99 x 10
2.81
2,85
10
2,82 x
2.06
10
2.82
10
Intaal
2.79
10
2.65 10
2.83 x
2.83
10
2.71 10
2.7% x 10
266
10
2.88
10
Iniiial
2.89
2.87
10
2.72
2.94
10
2884 10
2.89 x 10-
2,78
10
2.94
x 10
Initial
2.79
10-4
2.86 10
2.92 10
2.67 10
2.84 10
2.81 10
2.0
10
2.85
10
Initial 5
2.76 x 10-*
2.88 x 10
2,96 x 10-a
2.93
10
2.6 10
2.73 10-
2,06
10
2.8 x 10
Initial
10
10
Initial
2.73 10
2.76
10
2.82 x 10
2.79
10
2.71
2.77 x 10
2.55 x 10
2.83 x 10
2.79 10
2.78
2.75
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 min- ima) obtained by all different initilizations and all different mirrors (Table 8). The smallest element in each row exactly the final point obtained by that mirror from that initialization, among all the mirrors and all the initial points.
26

---

Under Leview as a conffrennce S paper at ICLR 2020
Jruove BiCa SIs uafe swo uo os siee di tesso zirz ane uf ra u
GER SR FOR ses
PORTOO
193.2 T Tet
THE SIR
24
2. TH 2.00 DE 2 DE
2
Z 24
2 ON 2,SSE 28
2.83--2
2
73022
277000
256127
Z 2
ZEI 2
2002
2 2 2 5715 2 2
Figure 9: Different Bregman divergences between all the final points and all the initial points for different mirrors in CIFAR-10 10 dataset using ResNer- 18, Note that the smallest element in every single row is on the diagonal, which confirms the theoretical results.
240735
24005
200090
TOM S0
THE 20
2000 2 ON 2 DAIEON 277
2 OF 2 OE 2 2 RRE
77 2 ON 7 7 175 2
240005
230912
20992
200624
777455
797Z3
155
ISE 19S
CANEON LO0E ON 2 dU THE DANS
241239
24:200
241335
24120
24122
7OLL
722MD
COOL
720030
TAO
TXU
JON 200
28
NO 50
THT MOY
NST WEDE LN NNT SOS
LE LAGE DE 2OE OF LASE
240300
24000
27128
240000
240990
7200
7ER-27
EOOM SIDOR OZWA PIAAD 2A0E
SOSD IN THE DES TAUL 7VM OF TIST
MELDL BORISE DOLAO SON ERERS DASS 2AN LREAN 200 DASS
199 AW
UODRY SOUEH SET MEE TOC 42
243900
747000
2407
2437
WIT DOLON TO SOM INC THC W POER 20 7007
FOREE RASM SRAN 1957
DO NOT TIRON IN IONC IN PRIDS
215733
240790
2407H
2000
2407
LESEST JICKE NOSS JIRLZ HIRE TRESS
1979
2
2
31597
11507
JIST
SURO DHEAK SIN OO
5.25
5.25
S
5.8
5.3-0
mrav0
220004
337099
THASS
SHE
ALANG
12
OF
IESMO S 2350 Ia TAUNO re IE
120070
1
15251
SOOLE
SANCO DRO LONCL
TO ONINN JOL DON 39
DOC
JOS
DOY 771
4
4
A
4
T5
TOCH
SU JICCS
KORAH SEYM
S
17-05
115000
SYN ONED
TOU DOE
FOR MNT
OF
53
5
5.00
13.00
LIASS
COPEE
LEANE
SENLAY
SEPE
SEPLA SYPL
CO SON
HILEN
FOR SON
7-M 05
7 05
7
7
75045
TMPNG
TIMS
ROXL
ROOK
SSAS
TIN
JON
JOS CI
0.000
0O00L
0000L
0200
0200
40755
12549
11500
SIACH
2055
11500
407.24
305-006
AOSUNI
155777
C.
6.
500T
29286-
201
ZHILES 3T.TH TRICTT 200L JUN
DOLL MN SALL DILES 55T PANT ON 20241
PACC SOEE IO SHIES SKICK DRRK DON MOXL
2O SEANE INCLO JMO SWALS
NO LO
NGT LN
1OP 277
12:9 ON
123
12:5
13:000
1950
1H Its SMO JANNO Is 25 FESMex I75003
969922
96077
98447
2758-27
WOLLT
2NO SALA MHOZE 2007 59 2007
SER ZEREZI 2H00 DS JAPL
TOS TON
TON CT
1IS RON
CTP
ON CM
CTE
GYN KIN
GTU ON
GN C3
20012
09013
5099
54
SAREL
DONT
1000
IT
PEO TOSS IN
IN AW
TO MM
JOT
IST MA
CLD. IR
6O SO HELIE ELL
68 HELME CLD 28
PUA 87 P5001 SAREL 95778
WEEN POREE PAISE SELESS
SOZE WONL VOR & WOHEYY 9522
DELT
FOR TEL
SIZOO GELAS SS.ME
GALSS 15.24
60 1SLME
CO 0000 13LMG
100 SHE
FOR AH
JEIO
JOLL DU
SWO S09
TOS SH
IOG MR
HERRS 2E SII OO
BEINS UN WILON
977
SER 250 92 02
472 02
POSS 2011
JOST 30
POL
IRS DOS
IS
19
JOM
TIK
SRRNS 225
SER 220
PAILLS
36399
5A7716
SCHOA
JRAA OF
THE OR
20N3
372 ST2
17.80
BOLNS
7040N
4637.0
NOX
1006
SECD
2010
1881
1890
18543
1840
783622
4400
493--11
1
ROS MIS
2H08
7R0M
ZHR8
22560
4.2
4.8-2
22
436-3
SIDWRS
SISIE
S1086
BIZAKS
4
SOOT TO
FUOSS
HOAT
23866
TRASS
TRUSS
24
285-3
36611
24'1 76
7007444
75584
7508
75SRS
TARIE
PR5ST
S00L 50
SOOR 27
2E 22
COO TN
JAMES
TORE
SARNS
30.3
3013
36-3
5000 7
E54L3
SMILE!
SPALTE
SEEER JESTICA
STMU BIIAA SUYNE SYRCH
STRLON
CHO
SISS S4
SOST
DONZ
4
COCELS
LI SEE 3REU
LEGS SRAS ARRA
37814
SMAND 175014
OF 1744
ESSMO
SI444
BURZA
BUSS
DENEEN SISS II
DNN GH OREE CHCA
BOS END 49
ACD/O
4057
RUSO
40189
4USTA
SUSES
12-25 SERIS
274.557
$5722
OIZELL
SYSEYS
DUSSK
ROTEL
LIVIS
12545
12445
807285
BOTTE
80722
S150,44
STREE
STROZ
SLU O7
4071
42100
41
14
14
2200 30
Jo
27

---

Under review as a conference paper at ICLR 2020
WD
56D
W
Figure 10: An illustration of the experimental results. For each initialization wh. we ran different SMD algorithms until convergence point the set W (zero training error). We then measured all the pairwise distances from different the to different wo, in different Bregman divergences. The closest point (among all initializations and all mirrors) to any particular initialization wo in Bregman divergence with potential vb-) = || ll is exactly the point obtained by running SMD with potential -|- 1-11 from wp-
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 f-orr potential induces sparsity. We examine the distribution of the weights in the network for these algorithms starting from the same initialization. Fig. 11 shows the histogram of the initial weights, which follows half-normal distribution. Figs. T2 (a). (b), (c), (d) show the histogram of the weights for 4-SMD, &2-S (SGD), S3-SMD, and 10 SMD, respectively. Note that each of the four histograms corresponds to an 11 x 103-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 GSMD has more weights at and close to zero, which again confirms that induces sparsity. However, will be shown in the next section, this is not necessarily good for generalization (in fact, turns out that & SMDD has a much better generalization). The histogram of the S2DSMD (SGD) looks almost identical to the histogram of the initialization, whereas the & and f1o histograms 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. [2
200000
Initial
150000
Frequency
50000
0.00
0.01
0.02
0.03
0.04
0.05
Absolute Value of Weights
Figure 11: Histogram of the absolute value of the initial weights in the network (half-norma distri- bution)
28

---

Under review as a conference paper at ICLR 2020
12-norm
250000
Frequency
80000
40000
20000
3.00
0.01
0.02
0.03
0.84
0.05
0.00
9.01
0.02
0.03
0.04
0.05
Absolute value of Weights
Absolute Value Weights
(b)
180000
300000
B-norm
110-norm
160000
250000
140000
120000
200000
100000
Frequency
150000
80000
60000
100000
20000
8.00
0.01
0.02
0.03
0.04
0.05
8.00
0.01
0.02
0.03
0.04
0.05
Weights
Weights
(d)
l1-narm
2.norm
13-norm
200000
110-norm
Frequency
150000
100000
50000
8.00
Absolute Value of Weights
Figure 12: Histogram of the absolute value of the final weights in the network for different SMD algorithms: (a) LI-MD, (b) f2-MM (SGD), (c) fs-SMD, (d) (1-SM.. Note that each of the four histograms corresponds to an 11 x 10 -i-dimensional weight vector that perfectly interpolates the data. Even though the weights remain quite small, the histograms are drastically different. Li-SM induces sparsity on the weights, as expected. SGD does not seem to change the distribution of the weights significantly. fDDSMD starts reduce the sparsity, and t shifts the distribution of the weights significantly, so much so that almost the weights are non-zero.
29

---

Under review as a conference paper at ICLR 2020
B.4 GENERALIZATION ERRORS OF DIFFERENT MIRRORS/REGULARIZER
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 the generalization of deep networks.
For MNIST, perhaps surprisingly, all the four SMD algorithms achieve around 99% higher accuracy. For CIFAR-10, however, there is a significant difference between the test emross dif- ferent mirrors/regularizes
the same architecture. Fig. 13 shows the test accuracies of different algorithms with eight random initializations around zero, as discussed before. Counter-intuitively, f10 performs consistently best, while & 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 comprehensive study of the role of regularization, and the choice of the best regularizer, improve the generalization performance of deep neural networks.
95
94
Test Accuracy( (%)
93
92
91
90
SMD 1-norm
SGD
SMD 3-norm
SMD 10-norm
Figure 13: Generalization performance of different SMD algorithms the CIFAR-10 dataset using
ResNet-18 18. éı performs consistently better, while & performs consistently worse
30


Reviews:
[{"review_id": "ryx4tvdTKB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors study the behavior of stochastic mirror descent on overparameterized nonlinear models. Especially, the authors show that for appropriate initialization, SMO converges to a global minimum with a minimal distance to the initialization. The authors also report some experimental results to verify this theory.\n\nThe implicit regularization of SGD/SMD is widely studied in the literature. Although it is claimed that the paper improved existing results by either considering nonlinear models or identify more precise implication regularization, the contribution is a bit minor. In particular, the fundamental identity in Lemma 6 is exactly a specific case of Lemma 4 in  Azizan & Hassibi (2018) with no noises. Moreover, Azizan & Hassibi (2018) also discussed the implicit regularization of SMD in their Theorem 10 for nonlinear models with some localization arguments. This paper considers similar localization arguments with some different assumptions.\n\nAfter rebuttal:\nI am sorry to select by mistake a N/A for the correctness of experiments.  \nI have read the authors' rebuttal and would not like to change my score. The fundamental identity in Lemma 6 was already derived in Azizan & Hassibi (2018). This paper identifies some assumptions to show the implicit regularization studied in Azizan & Hassibi (2018) with heuristic argument. However, these assumptions are very strong and with the assumptions the argument follows similarly to those in Azizan & Hassibi (2018). Indeed, as stated in Azizan & Hassibi (2018), the convergence in linear case depends on the non-negativity of $D_{L_i}(w,w_{i-1})$. In this paper, the authors just assume that this non-negativity holds locally in Assumption 1. In my opinion, this seems not a rigorous way to formulate assumptions.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJxY1oCnKS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nPros:\n1. 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. \n2. The empirical studies in the paper is clean and significant. It also supports the developed theory.\n\nThe 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. \n    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. \n    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?  \n    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. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1gJmHhziH", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the performance of the mirror gradient method when applied to the overparameterized network. The authors claim that the SMD method could find the regularized global minimize for different potential functions, in terms of minimal Bregman distance. Further experiments are carried out to back up the authors' claim.\n\nHowever, the drawbacks of this paper are listed in these several points:\n\n1) The regularization w.r.t. Bregman distance is quite different from the regularization used in network training: instead of $\\|w - w_0\\|$, we use $\\|w\\|$ more often, therefore, the virtue of sparsity shared by 1-norm is not exploited.\n\n2) The authors' assumption in Assumption 3.1 is too fuzzy: instead of detailed analysis in the papers related to the overparameterized network, the author does not give ANY relationship between the $\\epsilon$ and these three important parameters: a) network width, b) probability introduced by random initialization, c) the number of input data.\n\n3) Therefore, according to the too strong and fuzzy assumption mentioned in the last point, Assumption 3.1 simply makes the network equals to the linear model, which leads to minor contributions according to the study of the overparameterized network.\n\n4) The `over parameterized network' discussed now, including the work of (Li & Liang, 2018; Du et al., 2018; Azizan & Hassibi, 2019; Allen-Zhu et al., 2019; Cao & Gu, 2019), are mainly focused on the `network of infinite width', however, in the authors' experiment, the network architecture, e.g. ResNet18, is more to be a `very deep network' rather than a `very wide network'. Therefore, the authors' theory is built on Assumption 3.1, which is based on `network of infinite width', while the experiment is built on the `very deep network'. The result of the experiments is not enough to support the authors' theorem.\n\nIn conclusion, I am convinced that the authors' work is over-claimed in this paper.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper takes results related to the convergence and implicit regularization of stochastic mirror descent, as previously applied within overparameterized linear models, and extends them to the nonlinear case.  Among other things, conditions are derived for guaranteeing convergence to a global minimizer that is (nearly) closest to the initialization with respect to a divergence that depends upon the mirror potential.  Overall the paper is well-written and likely at least somewhat accessible even for non-experts in this field.

That being said, two reviewers voted to reject while one chose accept; however, during the rebuttal period the accept reviewer expressed a somewhat borderline sentiment.  As for the reviewers that voted to reject, a common criticism was the perceived similarity with reference (Azizan and Hassibi, 2019), as well as unsettled concerns about the reasonableness of the assumptions involved (e.g., Assumption 1).  With respect to the former, among other similarities the proof technique from both papers relies heavily on Lemma 6.  It was then felt that this undercut the novelty somewhat.   

Beyond this though, even the accept reviewer raised an unsettled issue regarding the ease of finding an initialization point close to the manifold that nonetheless satisfies the conditions of Assumption 1.  In other words, as networks become more complex such that points are closer to the manifold of optimal solutions, further non-convexity could be introduced such that the non-negativity of the stated divergence becomes more difficult to achieve.  While the author response to this point is reasonable, it feels a bit like thoughtful speculation forged in the crunch time of a short rebuttal period, and possibly subject to change upon further reflection.  In this regard a less time-constrained revision could be beneficial (including updates to address the other points mentioned above), and I am confident that this work can be positively received at another venue in the near future.
Decision: Reject