Mirror Descent Maximizes Generalized Margin and Can Be Implemented Efficiently
Authors: Haoyuan Sun
Kwangjun Ahn
Christos Thrampoulidis
Navid Azizan
Venue: NeurIPS 2022 Accept (2022)
Keywords: mirror descent
gradient descent
overparameterization
implicit regularization

Abstract: Driven by the empirical success and wide use of deep neural networks, understanding the generalization performance of overparameterized models has become an increasingly popular question. To this end, there has been substantial effort to characterize the implicit bias of the optimization algorithms used, such as gradient descent (GD), and the structural properties of their preferred solutions. This paper answers an open question in this literature: For the classification setting, what solution does mirror descent (MD) converge to? Specifically, motivated by its efficient implementation, we consider the family of mirror descent algorithms with  potential function chosen as the $p$-th power of the $\ell_p$-norm, which is an important generalization of GD. We call this algorithm $p$-$\textsf{GD}$. For this family, we characterize the solutions it obtains and show that it converges in direction to a generalized maximum-margin solution with respect to the $\ell_p$-norm for linearly separable classification. While the MD update rule is in general expensive to compute and not suitable for deep learning, $p$-$\textsf{GD}$ is fully parallelizable in the same manner as SGD and can be used to train deep neural networks with virtually no additional computational overhead. Using comprehensive experiments with both linear and deep neural network models, we demonstrate that $p$-$\textsf{GD}$ can noticeably affect the structure and the generalization performance of the learned models.

Mirror Descent Maximizes Generalized Margin and Can Be Implemented Efficiently
Haoyuan Sun MIT haoyuans@mit.c edu
Kwangjun Ahn MIT xjahn@mit edu
Christos Thrampoulidis
Navid Azizan MIT azizanemit, edu
UBC
cthrampo@ece. ubc.ca
Abstract
Driven by the empirical success and wide of deep neural networks, understand- ing the generalization performance of overparameterized models has become an increasingly popular question. To this end. there has been substantial effort characterize the implicit bias of the optimization algorithms used, such as gradient descent (GD), and the structural properties of their preferred solutions. This paper answers an open question in this literature: For the classification setting, what Specifically, motivated by its efficient implementation, we consider the family of mirror descent algorithms with potential function chosen as the p-th power of the f,-norm, which an important generalization of GD. We call this algorithm p-GD. For this family, we characterize the solutions it obtains and show that converges in direction to a generalized maximum margin solution with respect to the n,-nrrm for linearly separable classi- fication. While the MD update rule is in general expensive to compute and perhaps not suitable for deep learning, p-GD is fully parallelizable in the same manner SGD and can be used to train deep neural networks with virtually no additional computational overhead. Using comprehensive experiments with both linear and deep neural network models, we demonstrate that p-GD can noticeably affect the structure and the generalization performance of the learned models.
solution does mirror descent (MD) converge
Introduction
Overparameterized deep neural networks have enjoyed a tremendous amount of success in wide range of machine learning applications [Brown et al., 2020, Dosovitskiy et al., 2020, Ramesh et al., 2021, Schritwieser et al., 2020]. However, these highly expressive models have the capacity have multiple solutions that interpolate training data, and not all these solutions perform well on test data, it is important to characterize which of these interpolating solutions the optimization algorithms converge to. Such characterization is important as it helps understand the generalization performance of these models, which is one of the most fundamental questions in machine learning.
Notably, it has been observed that even in the absence of any explicit regularization, the interpolating solutions obtained by the standard gradient- based optimization algorithms, such as (stochastic) gradient descent, tend to generalize well. Recent research has highlighted that such algorithms favor particular types of solutions, i.c., they implicitly regularize the learned models. Importantly, such implicit biases are shown to play crucial role in determining generalization performance, e.g..
(Donhauser al., 2022, Neyshabur et al., 2014, Wilson et al., 2017, Zhang et al., 2021].
In the literature, the implicit bias of first-order methods first studied in linear settings since the analysis is more tractable, and also, there have been several theoretical and empirical evidence that certain insights from línear models translate to deep learning, e.g. [Allen-Zhu et al., 2019, Bartlett et al., 2017, Belkin et al., 2019, Jacot et al., 2018, Lyu and Li. 2019, Nakkiran al., 2021]. In the linear setting, is easier to establish implicit bias for regression tasks, where square loss typically
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: Conceptual summary of our results. In the case of linear regression, the implicit regular- ization results are complete; it is shown that mirror descent converges to the interpolating solution that is closest to the initialization. However, such characterization in the classification setting is missing in the literature and this is precisely the goal of this work. In particular, motivated by its practical application, consider the potential function (b)) p Il- and extend the result of the gradient descent such mirror descents.
Regression
Classification
argmin,,. ||w - Wollz s.t. w fits all data [Engl et al., 1996, Thm 6.1]
argmin,, ||
Gradient Descent (+b(-) 2 11-112
s.t. w classifies all data
Soudry al. [2018]
Ji and Telgarsky [2019]
argmin ||w - wollp
argmin,, l|=l
Mirror Descent
s.t. fits all data Gunasekar et al. [2018] Azizan and Hassibi [2019a]
s.t. classifies all data
(e.g. v)(+) = p I1-1))
This work
used and it attains its minimum at a finite value. For example, the implicit bias of gradient descent (GD) for square loss goes back to Engl et al. [1996]. Beyond GD, analysis of other popular algorithms such as the family of mirror descent (MD). which is an important generalization of GD, more involved and established only recently by [Azizan and Hassibi, 2019a, Gunasekar et al., 2018]. Specifically, those works showed that mirror descent converges to the interpolating solution that closest to the initialization in terms of Bregman divergence. Thus, the implicit bias in linear regression relatively well-understood by now.
On the other hand, in the classification setting, the implicit bias analysis becomes significantly more challenging, and several questions remain open despite significant progress in the past few years. A key differentiating factor in the classification setting is that the loss function does not attain its minimum at a finite value, and the weights have to grow to infinity. It has been shown that for the logistics loss, the gradient descent iterates converge to the l ma-mmxim margin SVM solution in direction [Ji and Telgarsky, 2019, Soudry et al., 2018]. However, such characterizations for mirror descent are missing in the literature. Because it is possible for optimization algorithms exhibit implicit bias in regression but not classification (and vice versa) [Gunasekar et al., 2018), resolving this gap of knowledge warrants careful analysis. See Table for summary.
In this paper, we advance the understanding of the implicit regularization of mirror descent in the classification setting. In particular, inspired by their practicality, we focus on mirror descents with potential function (-) = 11-11p for p 1. More specifically, such choice potential results in an update rule that can be applied coordinate
in the sense that updating the value at one coordinate does not depend on the values other coordinates. Thanks this property, this subelass of mirror descent can be implemented with no additional computational overhead, making it much more practical than other algorithms in the literature; see Remark 10 for more details.
Our contributions. In this paper, we make the following contributions:
We study mirror descent with potential Il-II, for > 1, which will call p-norm GD, and abbreviated p-GD, practical and efficient generalization of the popular gradient descent.
We show that for separable linear classification with logistics loss, p-GD exhibits implicit regular- ization by converging in direction to a "generalized" maximum-margin solution with respect to the 4, norm. More generally, we show that, for monotonically decreasing loss functions, p-GD follows the so-called regularization path, which is defined in Section 2.
We investigate the implications of our theoretical findings with two sets of experiments: Our experiments involving linear models corroborate our theoretical results, and real-world experi- ments with deep neural networks and popular datasets suggest that our findings carry over to such

---

nonlinear settings. Our deep learning experiments further show that p-GD with different lead to significantly different generalization performance.
Additional related work. We remark that recent works also attempt to accelerate the convergence of gradient descent to its implicit regularization, either by using aggressive step size schedule [Ji and Telgarsky, 2021, Nacson et al., 2019] or with momentum [Ji et al., 2021]. Further, there have been several results for other optimization methods, including steepest descent, AdaBoost, and various adaptive methods such as RMSProp and Adam [Gunasekar et al., 2018, Min et al., 2022, Rosset et al., 2004, Telgarsky, 2013, Wang et al., 2021]. A miiror-desscettbasee algorithm for explicit regularization was recently proposed by Azizan et al. [2021a]. Comparatively, there has been very little progress on mirror descent the classification setting. Li al. [2021] consider mirror descent, but their assumptions are not applicable beyond the E2 geometry. To the best of our knowledge, there is no result for more general mirror descent algorithms in the classification setting.
2 Background and Problem Setting
We are interested in the well-known classification setting. Consider a collection of input-label pairs y:) C Rd x {=1} and classifier (x), where E W. For some loss function R x {+1} + I. our goal is to minimize the empirical loss:
1 Σ C(ys fu (xx)). n
L(w)
Throughout the paper, we assume that the classification loss function é is decreasing, convex and does not attain its minimum, as in most common loss functions in practice (e.g., logistics loss and exponential loss). Without loss of generality, we assume that inf E(-) 0.
For our theoretical analysis, we consider linear model, where the models can be expressed by fw (x) = w x and w E Rd. We also make the following assumptions about the data. First, since are mainly interested in the pver-parameterized setting where d n, we assume that the data is linearly separable, i.e., there exists w² E RR s.t. sign((w", xz)) = y: for all i E [ni]. We also assume that the inputs v;'s 's bounded. More specifically, for later purpose,
assume that for > 0, there exists some constant C so that max, ||<]]] ll, < C, where 1/q + 1/p 1
Preliminaries on mirror descent. The key component of mirror descent a potential function. In this work, we will focus on differentiable and strictly convex potentials defined on the entire domain ?
2 We call V the corresponding mirror map. Given a potential, the natural notion of "distance" associated with the potential t is given by the Bregman divergence.
Definition (Bregman divergence [Bregman, 1967]). For a mirror map sb. the Bregman divergence
Dø (-)-) associated to vp is defined as
De (x. v) = (xx) (v)) (V x z-9)-
g). Vx, E R"
An important case is the potential & 11-11" where ||-|| denotes the Euclidean norm. Then, the Breg-
man divergence becomes (x y) = 2 || - ./12. For more background on Bregman divergence and its properties, see, e.g., [Bauschke et al., 2017, Section 2.2] and [Azizan and Hassibi, 201 2019b), 9b).
Mirror descent (MD) with respect to the mirror map v is a generalization of gradient descent where we use Bregman divergence as measure of distance:
Wh++1 = argmin
Do (w, we) + (VL(w)) w)
(MD)
10
17
Equivalently, MD can be written as (+b(w+1)) Vv(w)) 7 (wt). We refer readers to [Bubeck,
2015, Figure 4.1] for nice illustration of mirror descent. Also, see [Juditsky et al., 2011, Section 5.7] for various examples of potentials depending on applications.
One property we will repeatedly use is the following [Azizan and Hassibi, 2019a]:
'To precise, they assume that the Bregman divergence lower and upper bounded by a constant factor of the squared Fuclidean distance, e.g., as the case of squared Mahalanobis distance. In general, the mirror map is convex function of Legendre type (see, e.g., [Rockafellar, 1970, Section 26]).
3

---

Lemma 2 (MD identity). For any w IR", the following identities hold MD:
(w wa) = Do(10 1 + De-nL(WU++) w/) + +rDDL(w we) nI(w) + (I[(w++)))))) (la)
Dw(w, W2+1) (o--)((We11 wx) 7) (VI(m)) w m.. -)T((1))))) + (1(+11)) (Ib)
Using Lemma 2, we make several new observations and prove the following useful statements. Lemma 3. For sufficiently small step size il such that vo - L, is convex, the loss is monotonically decreasing after each iteration of MD, i.e., L(we+1) S L(w.).
Lemma 4, In a separable linear classification problem, in is chosen sufficiently small s.t. 1b I sc. Hence, lim l|well = 30 for any norm I1-Il-
convex, then we have L(wa) ->
The formal proofs of these lemmas can be found in Appendix A.
Remark 5. We can relax the condition in Lemma 3 and 4 such that for a sufficiently small step size 77 10 n2 only locally convex at the iterates wt. The relaxed condition allows us analyze losses such as the exponential loss (see, e.g. Footnote 2 of Soudry et al. [2018]). This condition can be considered the mirror descent counterpart to the standard smoothness assumption in the analysis of gradient descent (see Lu et al. [2018]).
Preliminaries on the convergence of linear classifier. As we discussed above, the weights vector wy diverges for mirror descent. Here the main theoretical question is:
What direction does MD diverge to? In other words, can we characterize wx/ ||,,]] as ( + oo?
To answer this question, we define two special directions whose importance will be illustrated later. Definition 6. The regularization path with respect to the f--norm is defined as
Wp ()
argmin (w)
|=
And if the limit fim--so W. (B)BB exists, we call it the regularized direction and denote it by ulp Definition 7. The margin of the linear classifier w is defined as ((w) = min;=1 ...m Vi (ri, w) The max-margin direction with respect to the e--norm is defined as:
2 = argmax
min yi (24,, w)
(3)
[|ll|
S1
i=......
And let 9p be the optimal value to the equation above.
Note that um is parallel the hard-margin SVM solution w.r.t. Ly-norm: argmin,,((lulpp >ww) 1}. Also note that the superscripts in uf and un are not variables and we only use this notation to differentiate the two definitions. Prior results had shown that, in linear classification, gradient descent converges in direction.
Theorem 8 (Soudry et al. [2018]). For separable linear classification with logistics loss, the gradient wy
descent iterates with sufficienlly small step size converge in direction to u2 i.e., lim Twall u
Theorem (Ji et [2020]). If the regularized direction up, with respect to the ty-norm exists, then the gradient descent iterates with sufficiently small step size converge to the regularized direction uz. uhy.
i.e. litm
Mis
we
3 Mirror Descent with the p-th Power of 4--norm
In this section, we investigate theoretical properties of the main algorithm of interest, namely mirror descent with vb-)) 1
p I1-1, and for > 1.3 We shall call this algorithm p-norm GD because it naturally generalizes gradient descent to f, geometry, and for conciseness, will refer to this algorithm by the shorthand G-G.. As noticed by Azizan et al. [2021b], this choice of mirror potential
Because the potential function must be strictly convex for Bregman divergence to be well-defined, the value of cannot be exactly 1.

---

is particularly of practical interest because the mirror map V v updates becomes separable in coordinates and thus can implemented coordinate-wise independent of other coordinates:
W0++ [j] + [ bاll sign (wt [il
Vj [d].
(p-GD)
wi [i] == (inb)>)l-ssgn((:////
7 (w))bi
Furthermore, we can extend upon the observation of Azizan et al. [2021b] and derive these identities that allow us to better manipulate p-GD:
(Vi(w)) w) sign(ws)run |wa 1a-1 +... sign(wa))ws" |ma|m-1 = ||0l| De (cw, cw") D (w, (w,w') Ve R.
(4a)
(4b)
Remark 10. Note that the coordinate-wiss separability property is not shared among other related
algorithms in the literature. For instance, the choice và 3 11-11g for 1/p+ + //q 1, which is referred to as the p-norm algorithm [Gentile, 2003, Grove et al., 2001] is not fully coordinate-wist separable since it requires computing I|wzel,p at each step (see, e.g.. [Gentile, 2003, eq. (1)]). Another related
algorithm is steepest descent, where the Bregman divergence in MD is replaced with ||-11 for general norm ||-||_ However, for similar reasons, the update rule is not fully separable.
3.1 Main theoretical results
We extend Theorems 8 and 9 to the setting of p-GD. We will resolve two major obstacles in the analysis of implicit regularization in linear classification:
Our analysis approaches the classification setting a limit of the regression implicit bias. This argument gives stronger theoretical justification for utilizing the regularized direction (as employed by Ji et al. [2020]) and partially addresses the concern from Gunasekar al. [2018] that the implicit bias of regression and classification problems are "fundamentally different."
On more technical note, analyzing the implicit bias requires handling the cross terms of the form (V)(ww), w'), which lack direct geometric interpretations. We demonstrate that for our potential functions of interest, these terms can be nicely written and can be handled in the analysis.
We begin with the motivation behind the regularized direction, and consider the regression setting in which there exists some weight vector such that L(w) = O. Then, we can apply Lemma 2 to get
(w, we) = D w(+1) + Dw-aL (W++1, wy) + DDDLWw we) + n([(we+1) L(w))
Since we assumed L(w)= O, the equation above implies that (w w:)) 2 (w W for sufficiently small step-size 1). This can be interpreted as MD having decreasing "potential" of the from Do (w,,) during each step. Using this property, Azizan and Hassibi [2019a] establishes the implicit bias results of mirror descent in the regression setting.
However, such weight vector w does not exist in the classification setting. One natural workaround would then be to choose vector w so that L(w) < L(w,) for all S T. The following result, which generalization of [Ji al., 2020, Lemma 9], shows that one in fact choose the reference vector w as scalar multiple of the regularized direction.
Lemma 11. If the regularized direction up exists, then Va > 0, there exists Ta such that for any w with [ 1| > Tec. we have L((1 + a) ||m|||p ((,))) < L(w).
However, this does not resolve the issue altogether. Recall from Lemma that the loss approaches and therefore one cannot choose fixed reference vector in the limit as T >> oc. But due the homogeneity of Bregman divergence (4b), we can scale uf, by a constant factor during each iteration, and, by doing so, we choose the reference vector to be "moving target." In other words, the idea behind our analysis is that the classification problem is chasing after a regression one and would behave similar to it in the limit. Let formalize this idea. We begin with the following inequality:
De (colly wx41) < D& (ceul, we) mL((w++) + (L()))
'It is also worth noting that steepest descent is not an instance of mirror descent since ||-11 is not Bregman divergence for general norm ||-||.
5

---

where e is taken to be = |
Now we modify (5) so that it can telescope over different iterations. One way is to add De (c++1 Wx+) on both sides of (5) and move Do (cru,, W++1) to the right-hand side follows:
Dy (c W++1)
I Dy (crtfp w:) (1((1++1) + ([(()) + Do (ce+ werl) Du (eug,,
Do (crogg wx) - ()((1)++1)) + (wx)) + (((4411))) - (((cu())) (VD(wr+1); (ct-1 (0)-1-couul cr)ub)
Summing over t = 0p...,I gives us
Du (crug wr) s Di (coule wo) - ([(wr + n(((T) + ((rru))) ((94))
(6)
(Vo(wr+)) (0+11-0))0 - cr)ulp)
The rest of the argument deals with simplifying quantities that do not cancel under telescoping sum. For instance, in order to deal with (Vr((ue+1), uby), we invoke the MD update rule as follows
(Vo(w(+)) - Ve(w)), u/,) = (-n)) up) ス (-n))((w), wi).
where the last inequality follows from the intuition that ui is the direction along which the loss achieves the smallest value and hence ((w,) must point away from uiy- i.e., it must be that (VL(ws), u/)) S (VL(we), u) for any direction u. The following result formalizes this intuition. Corollary 12. For w so that ||ll|p
we have (VL(w), w) 2 (1+ a) Iwl (VL(w), uf))
Proof. This follows from the convexity of L and Lemma 11: (VL(w), w - | up)) N L(w) - L((1 + a) ||w||| up)) O.
Now we are left with the terms LLm)) wt). For general potential sb the quantity (-n)L((w))) wx) = (Ve(w++1) - (we)), we) cannot be simplified. On the other hand, due to our choice of potential, one can invoke Lemma 2 to lower bound these quantities in terms of ||ws+2llp and l|weelpp and this step is detailed in Lemma 18 in Appendix B.2. Once we have es- tablished a lower bound on (Ve(wrr1), u()). we can turn (6) entirely into a telescoping sum and
unwind the above process to show that Dy (up. we/ ([wellp) must converge to zero in the limit as t - co. Putting this all together, we obtain the following result.
Theorem 13. For separable linear classification problem, if the regularized direction vi exists, then with sufficiently small step size, the iterates of p-GD converge to ul in direction:
We weellp
lim 1-000
A formal proof of this theorem can be found in Appendix B.3, We note that our proof further simplifies derivations using the separability of the mirror map. The final missing piece would be the existence of the regularized direction. In general, finding the limit direction u', would be difficult. Fortunately, we can sometimes appeal to the max-mare max-margin direction that is much easier to compute. The following result is generalization of [Ji et al., 2020, Proposition 10] and shows that for common losses in classification, the regularized direction and the max- mar-mn direction are the same, hence proving the existence of the former.
Proposition 14. If we have loss with exponential tail, e.g. lim {())e = b, then the regular- ized direction exists and it is equal to the max-margin direction up.
The proof of this result can be found in Appendix B.5. Note that many commonly used losses in classification, e.g., logistic loss, have exponential tail.
"To he more precise, we want e = (1 + a) | p and reason behind this choice self-evident after we present Corollary 12.

---

1.0
0.08
15
p
Coovergtzee (DA))
0.06
p
10
0.0
0.01
p
-0.5
0,02
= 2
p
1.0
-0.5
0.0
0.5
1.0
10
10a Heration
10F
10
10
102
Iteration
Figure 1: An example of p-GD on randomly generated data with exponential loss and p 1.5, 2, (1) The left plot is scatter plot of the data: x and e's denote the two different labels (y: = = The dotted line is the lg max-margin classifier. For clarity, other Ep max-margin elassifiers are omitted from the plot. (2) The middle plot shows the rate which the quantity D& (ul, w// ||wy]l, [ll)) converges to O. (3) The right plot shows how fast the p-norm of growths. We can observe that the asymptotic behaviors of these plots are consistent with Corollary 17.
3.2 Asymptotic convergence rate
In this section, we characterize the rate of convergence in Theorem 13. Following the proof of Theorem 13, one can show the following result in the case of linearly separable data.
Corollary 15. The following rate of convergence holds:
||wlll O (IIval1(0011
We
D&
Upp
In order to fully understand the convergence rate, we need to characterize the asymptotic behavior of ||wellp- The next result precisely does that. Recall that assumed the dataset is bounded that max, I1, I C for 1/p + 1/q = 1, and the max mar-mn direction up satisfies (Ii, up) 2 fp Vi e [n). Then, we have the following bound on welllp.
Lemma 16. For exponential loss E(2) exp(-2), the asymptotic growth of Iwwll is contained in O(log (). In particular, we have
lim inf [eell 2 ج (logt - plog log + (()) and lim sup Iwl ll, S 15500
59p
logt.
(-+00
p
The proof this lemma can be found in Appendix Similar conelusions can be reached for other losses with exponential tail. Therefore, in such cases, p-GD has poly-logarithmic rate of convergence. Corollary 17. For exponential loss, we have convergence rate
Wt
DΦ
upp
|wrll,
log (t)
Experiments
In this section, investigate the behavior and performance of p-GD for various values of p. We naturally pick p = 2 that corresponds to gradient descent, Because p-GD does not directly support p 1 and co, choose p 1.1 surrogate for f, and p 10 surrogate for foo. We also consider p 1.5, 3, 6 to interpolate these points. This section will present summary of our results; the complete experimental setup and full results can be found Appendices and F.
4.1 Linear classification
Visualization the convergence of GDGD. visualize the results of Theorem 13 and Corollary 17, randomly generated linearly separable set of 15 points in I We then employed GDGD on this

---

dataset with exponential loss {(2) = exp(-2) and fixed step size 17 10 We ran this experiment for p = 1.5, 2, 3 and for 10 iterations.
In the illustrations of Figure 1, the mirror descent iterates wi have unbounded norm and converge in direction up. These results are consistent with Lemma 4 and with Theorem 13. Moreover, as predicted by Corollary 17, the exact rate of convergence for Dy (up: ws/ [[well)) is poly-logarithmic with respect to the number of iterations. Corollary 17 also indicates that the convergence rate would be faster for larger due to the larger exponent, and this is consistent with our observation in the second plot of Figure 1. Finally, in the third plot of Figure 1, the norm of the iterates wy grows at logarithmic rate, which is the same as the prediction by Lemma 16.
Implicit bias of pDGD in linear classification. We now verify the conclusions of Theorem 13. To this end, we recall that up is parallel to the SVM solution argmin [|]w||, >>w) > 1}. Hence, can exploit the linearity and rescale any classifier so that its margin is equal to 1. If the prediction of Theorem 13 holds, then for each fixed value of p. the classifier generated by p-GD should have the smallest E--norm after rescaling.
To ensure that up are sufficiently different for different values of p. we simulate an over-parameterized setting by randomly select 15 points in 10,00, We used fixed step size of 10-4 and ran 250 thousand iterations for different p's.
Table shows the results for p = 1,3, and 10; under each norm, we highlight the smallest classifier in boldface. Among the four classifiers we presented, p-GD with p - 1.1 has the smallest foomm And similar conclusions hold for p = 2.3, 10. Although p-GD converges to up at very slow rate, we are able to observe a very strong implicit bias of p-GD classifiers toward their respective l, geometry
highly verrpaaameeterized setting. This suggests we should be able to take advantage of the implicit regularization in practice and at a moderate computational cost. Due to space constraints, we defer a more complete result with additional values of p to Appendix F.1.
Table 2:
Size of the linear classifiers generated by p-GD (after rescaling) in f1.1 f2, fa and f norms.
4.2
Deep neural networks
f111
82
fs
f10
Going beyond linear models, we now investigate p-GD in deep-learning settings in its impact on the structure of the learned model and potential implications on the generalization performance. As we had discussed in Section 3, the imple- mentation of p-GD is straightforward; to il-
p= 1.1
5.670
1.659
1.100
0.698
p= 2
6.447
1.273
0.710
0.393
p= =
7.618
1.345
0.691
0.318
p= 10
9.086
1.520
0.742
0.281
lustrate simplicity of implementation, we provide code snippets in Appendix D. Thus, are able to effectively experiment with the behaviors p-GD in neural network training. Specifically, we perform set of experiments on the CIFAR- 10 dataset [Krizhevsky et al., 2009]. We use the stochastic version of p-GD with different values of p. We choose a variety of networks: VGG [Simonyan and Zisserman, 2014), RESNET [He et al., 2016], MOBILENET [Sandler et al., 2018] and REGNET [Radosavovic et al., 2020].
Implicit bias of p-GD in deep neural networks. Since the notion of margin is not well-defined in this highly nonlinear setting, we instead visualize the impacts of D-GD's implicit regularization the histogram of weights (in absolute value) in the trained model.
In Figure 2, we report the weight histograms of RESNET- 18 models trained under p-GD with p 1,1,2,3 3 and 10. Depending on p. we observe interesting differences between the histograms. Note that the deep network is most sparse when p = 1.1 as most weights clustered around O. Moreover, comparing the maximum weights, one can see that the case of p = 10 achieves the smallest value. Another observation is that the network becomes denser as p increases; for instance, there are more weights away from zero for the cases p = 3, 10. These overall tendencies are also observed for other deep neural networks; see Appendix F.2.
Generalization performance. We next investigate the generalization performance of networks trained with different p's. To this end, we adopt a fixed selection of train four deep neural network models to 100% training accuracy with p-GD with different p's. As
and then
8

---

500000
11
300000
p
400000
5.126
1.333
200000
200000
100000
100000
8.00
0.01
0.02
0.03
0:04
0.06
0.00
0,01
0,02
0.03
0.01
0.05
300000
3000000
3
P
1.083
mixx
1.062
Pesquezyy
200000
2000000
100000-
100000
0.00
0.02
0.04
0.06
0.08
0.10
0.12
0.2
0.3
0.4
0.5
Absolute Value Weights
Absolute Value Weights
Figure 2: The histogram of weights in RESNET-18 18 models trained with p-GD for the CIFAR-I 10 dataset. For clarity, we cropped out the tails and each plot has 100 bins after cropping. The trends of these histograms reflect the implicit biases of p-GD: the distribution of p = 1.1 has the most number of weights around zero; and the maximum weight is smallest when p = 10.
Table 3: CIFAR-10 test accuracy (%) of p-GD various deep neural networks. For each deep network and value of p, the average + std. dev. over 5 trials are reported. And the best performing value(s) of p for each individual deep network is highlighted in boldface.
VGG-11
RESNET-18 18
MOBILENET-V2
REGNETX-200X2
p 1.1
88.19 117
92.63 .12
91.16 .09
91.21 .18
P 2 (SGD)
90.15
+ .16
93.90
..14
91.97 4.10
92.75 + 113
p 3
90.85 .15
94.01 +.13
93.23 +: .66
94.07 +12
p 10
88.78 + 37
93.55 +.2
92.60 + .22
92.97 + .16
Table 3 shows, interestingly the networks trained by p-GD with p3 consistently outperform other choices of p's notably, for MOBILENET and REGNET, the case of p 3 outperforms the others by more than 1%. Somewhat counter-intuitively. the sparser network trained by p-GD with = 1.1 does not exhibit better generalization performance, but rather shows worse generalization than other values of p. Although these observations are not directly predicted by our theoretical results, we believe that they nevertheless establish an important step toward understanding generalization of overparameterized models. Due to space limit, we defer other experimental results to Appendix F.3.
IMAGENET experiments. We also perform similar set of experiments the IMAGENET dataset [Russakovsky et al., 2015], and these results can be found in Appendix F.4.
Conclusion and Future Work
In this paper, we establish an important step towards better understanding implicit bias in the classification setting, by showing that p-GD converges in direction the generalized regularized/max margin directions. We also run several experiments to corroborate our main findings along with the practicality of G-GD. The experiments and high dimensions, (ii) real-world data with highly over-parameterized nonlinear models.
conducted in various settings: (i) linear models in both low
We conclude this paper with several important future directions:

---

Our analysis holds for (+)) = I-I where we argued that this choice is key practical interest due to its efficient algorithmic implementations. It is mathematically interesting to generalize our analysis other potential functions regardless of practical interest.
As discussed in Section 4.2, different choices of p's for our p-GD algorithm result in different generalization performance. would be interesting to investigate this phenomenon and to develop theory that explains why certain values of lead better generalization performance.
Another interesting question is to further investigate how practical techniques used in training neural networks (such as weight decay and adaptive learning rate) can affect the implicit bias and generalization properties of p-GD.
Acknowledgement
The authors thank MIT UROP students Tiffany Huang and Haimoshri Das for contributing to the experiments in Section 4.2. The authors acknowledge the MIT SuperCloud and Lincoln Laboratory Supercomputing Center for providing computing resources that have contributed to the results reported within this paper. This work was supported in part by MathWorks and the MIT-IBM Watson AI Lab. K.A. acknowledges support through graduate assistantship in part from the NSF grant 1846088, the ONR grant N00014-20-1 4-00---24,,,4 and the VBFF. N.A. also acknowledges support from the Edgerton Career Development Professorship.
References
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pages 242-252, PMLR, 2019.
Navid Azizan and Babak Hassibi. Stochastic gradient/mirror descent: Minimax optimality and implicit regularization. International Conference on Learning Representations, 2019a.
Navid Azizan and Babak Hassibi. A stochastic interpretation of stochastic mirror descent: Risk- sensitive optimality, In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 3960-3965. IEEE, 2019b.
Navid Azizan, Sahin Lale, and Babak Hassibi. Beyond implicit regularization: Avoiding overfitting via regularizer mirror descent. In International Conference Machine Learning, Workshop Overparameterization: Pitfalls Opportumities, 2021a.
Navid Azizan, Sahin Lale, and Babak Hassibi. Stochastic mirror descent on overparameterized nonlinear models. IEEE Transactions on Neural Networks and Learning Systems, 2021b.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally normalized margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
Heinz H Bauschke, Jérôme Bolte, and Marc Teboulle. A descent lemma beyond lipschitz gradient continuity: first-order methods revisited and applications. Mathematics of Operations Research, 42(2):330-348, 2017.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias variance trade-off. Proceedings of the National Academy of Sciences, (16(32):15849-15888 2019.
Lev M. Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics, 73))200-217, 1967.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal,
Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Sébastien Bubeck, Convex optimization: algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4)2231-35 2015.
10

---

Konstantin Donhauser, Nicolo Ruggeri, Stefan Stojanovic, and Fanny Yang. Fast rates for noisy interpolation require rethinking the effects of inductive bias. arXiv preprint w2Xi::2003.03977 2022.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition scale. arXiv preprint arXiv:2010. 11992999,. 2020.
Heinz Werner Engl, Martin Hanke, and Andreas Neubauer. Regularization of inverse problems, volume 375. Springer Science & Business Media, 1996.
Claudio Gentile. The robustness of the p-norm algorithms. Machine Learning, 53(3):265 2e0-22665-999 2003.
Adam J Grove, Nick Littlestone, and Dale Schuurmans. General convergence results for linear discriminant updates. Machine Learning, 43(3):173-210, 2001.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pages 1832-1841, PMLR, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In
Conference on Learning Theory, pages 1772-1798. PMLR, 2019.
Ziwei Ji and Matus Telgarsky. Characterizing the implicit bias via primal-dual analysis. In Algorithmic Learning Theory, pages 772-804. PMLR, 2021.
Ziwei Ji, Miroslav Dudík, Robert E Schapire, and Matus Telgarsky. Gradient descent follows the regularization path for general losses. Conference on Learning Theory, pages 2109-2136. PMLR, 2020.
Ziwei Ji, Nathan Srebro, and Matus Telgarsky. Fast margin maximization via dual acceleration. In International Conference on Machine Learning, pages 4860-4869. PMLR, 2021.
Anatoli Juditsky, Arkadi Nemirovski, al. First order methods for nonsmooth convex large-scale optimization, i: general purpose methods. Optimization for Machine Learning, 30(9):121-148, 2011.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yan Li, Caleb Ju, Ethan X Fang, and Tuo Zhao. Implicit regularization of bregman proximal point algorithm and mirror descent on separable data. arXiv preprint arXiv:2 08.0888 2021.
Haihao Lu, Robert M Freund, and Yurii Nesterov. Relatively smooth convex optimization by first-order methods, and applications. SIAM Journal on Optimization, 28(1):333-355 2018.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations, 2019.
Youngjae Min, Kwangjun Ahn, and Navid Azizan. One One-pass learning via bridging orthogonal gradient descent and recursive least-squares. In 2022 IEEE 61st Conference on Decision and Control (CDC). IEEE, 2022.
Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent on separable data. The 22nd International Conference Artificial Intelligence and Statistics, pages 3420-3428, PMLR, 2019.
11

---

Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and llya Sutskever, Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, (12:(12)124000, 2021.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv:1412.6614 2014.
Ilija Radosavovic, Raj Prateek Kosaraju, Ross Girshick, Kaiming He, and Piotr Dollár. Designing network design spaces. In Proceedings of the IEEE/CVF Conference Computer Vision and Pultern Recognition, pages 10428-10436, 2020.
Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. In International Conference on Machine Learning, pages 1-2118 PMLR, 2021.
R Tyrrell Rockafellar. Convex analysis. Number 28. Princeton University Press, 1970.
Saharon Rosset, Ji Zhu, and Trevor Hastie. Boosting regularized path maximum margin classifier. The Journal of Machine Learning Research, 5:941-973, 2004.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3):211-253 2015.
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chich Chen. Mo- bilenetv2: Inverted residuals and linear bottlenecks. Proceedings of the IEEE conference on computer vision and pattern recognition, pages 44100-520, 2018.
Julian Schrittwisser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 58877839):004-699, 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint vrxivv/4499 1556, 2014.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent separable data. The Journal of Machine Learning Research, 19(1): 2822-2878, 2018
Matus Telgarsky. Margins, shrinkage, and boosting. In International Conference on Machine Learning, pages 307-315. PMLR, 2013.
Bohan Wang, Qi Meng, Wei Chen, and Tie-Yan Liu. The implicit bias for adaptive optimization algorithms on homogeneous neural networks. In International Conference Machine Learning, pages 11849-10858.. PMLR, 2021.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. Advances neural information processing systems, 30, 2017
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64 2021.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] All of our claims accurately reflect the results in Sections 3 and 4.
(b) Did you describe the limitations of your work? [Yes] In Section 5, we described several directions where we can improve this work.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our paper investigates the foundational properties of mirror descent algorithms in learning; we do not believe there any direct societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section for the assumptions we used and the motivation behind them.
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are included in the Appendix, and we have referenced them as we present our claims.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [Yes] They are included the supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We gave an overview of our training setup in Section 4 and the full details are given in Appendix E.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] We reported the standard deviation whenever multiple trials were performed.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] They are reported Appendix
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A] We only used public datasets.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
We did not curate any new assets.
(d) Did you discuss whether and how consent obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] The datasets we used well-known; so, we
did not feel it was necessary to repeat that they do not contain sensitive information.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] There were no human subjects in our work.
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "rOt8CnU0Klq", "reviewer": "Reviewer_LBAU", "summary": "This paper studies the implicit bias of the solution found by mirror descent in the problem of classification with a linear model.\nSimilar problems have been studied for linear regression and/or gradient descent, but not simultaneously for mirror descent and classification.\nTo be fair, mirror descent is a very general optimization method, but here the paper considers a very specific setting, which they call \"p-GD\".\nThis stands for p-norm gradient descent, since (roughly speaking) the (p-1) power of the weights is used to update them.\nPerhaps unsurprisingly, the main theoretical result is that p-GD finds the max-margin solution with respect to the p-norm, thus generalizing the previous finding that GD finds the max-margin wrt the 2-norm.\nThe results of some experiments are shown in support of the theoretical results.\n", "questions": "Minor:\n- How do we know that the argmin in Eq.2 and the argmax in Eq.3 are unique?\n- Eq.(p-GD), first row, w*sign(w) is just the absolute value of w, which implies that the value of the weight w_{t+1} is always positive. \nDoesn't that limit drastically the solutions that can be possibly found by the optimizer?\n", "limitations": "OK", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strenghts:\n- The paper is very clear and well written.\n- The study of implicit bias of solution found by optimization is an important problem.\n\nWeaknesses:\n- It is unclear to me how much this \"p-GD\" optimizer is relevant for the machine learning community, I don't know of anyone using it. \nSection 4.2 reports an application of p-GD to deep neural networks and image classification but, as acknowledged by the authors, those results are \"out of the scope of our theoretical results\", so it remains a bit unclear what conclusions we are supposed to draw.\n\nOverall my opinion is that the strengths slightly outweight the weaknesses, so I vote for a weak accept. \n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "mxq_CkMBun", "reviewer": "Reviewer_ZhPm", "summary": "This work studies mirror descent in the classification setting with exponential and logistic losses and $p$-norm (to power $p$) potential functions, proving that when data is linearly separable and the step size is sufficiently small, this method converges to the maximum margin direction under the $p$-norm. The authors also describe rates of convergence as a function of iteration. Lastly, the authors perform numerical experiments demonstrating the claims of the theory for toy linear classification problems, as well as application to common deep network models on CIFAR-10, demonstrating the resulting weights have a distribution that reflect the structure imposed by the implicit norm regularization.", "questions": "I have one major question for the authors below. I assume that they will answer it satisfactorily, so I have decided to tentatively give this paper a **weak accept**. Depending on the response, I will increase my score to **accept** or decrease to **reject**.\n\n**Questions:**\n- The authors appear to be somewhat inconsistent regarding which loss function each result applies for. At the start of the paper (line 84), they suggest that most results will apply for exponential loss and logistic loss. However, it appears that the exponential loss cannot satisfy Lemma 2, because $\\psi - \\eta \\exp(\\cdot)$ can never be convex. On the other hand, the results on convergence rate are given only for the exponential loss (with proof for the logistic loss left as an exercise for the reader). Can the authors either 1) fix Lemma 2 so that the exponential loss works, or 2) specialize all results to the logistic loss, and omit the exponential loss in result statements?\n\n**Suggestions:**\n- Point out that when $d > n$, linear separability of the data is trivially satisfied. Additionally, comment more on the importance of the separability assumption (allowing interpolation / the loss to going to zero).\n- Make a note that while the hinge loss does not satisfy the assumptions (it attains its minimum), it gives the same maximum-margin solution.\n- More clearly define $u_p^\\mathsf{m}$ and $u_p^\\mathsf{r}$, and make it clear that the superscripts $\\mathsf{m}$ and $\\mathsf{r}$ are not parameters of the problem such as sample sizes. \n- Explain why the choice of $p = 1$ doesn't work.\n- Add the citation [1] discussed under *Significance* above.\n\n**Formatting/typographical:**\n- Use a unified numbering scheme for theorems/remarks/definitions/etc. With so many, it is difficult to find them.\n- (minor) Tables: use `booktabs` package\n- line 206: \"has exponential tail\" -> \"have exponential tail\"\n- line 251: \"space constraint\" -> \"space constraints\"\n\n***\n\n**Edit after review responses** \n\nThe authors have satisfactorily responded to my main question, so I have increased my score from **weak accept** to **accept**.", "limitations": "As mentioned above, the analysis as-is appears to only apply to the logistic loss, even though it is presented in a generic manner that would appear to be able to accommodate other common losses like exponential and hinge. I found no ethical limitations with this work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality:** \nThis work builds on a rich literature of previous work in theoretical analysis of implicit regularization and mirror descent. The main theoretical contribution appears to be that the authors have extended the analysis of Azizan et al. on mirror descent to the classification case where the loss is minimized only for an infinite-norm solution. While Gunasekar et al. have studied classification previously under exponential loss with steepest descent, this work analyzes mirror descent with separable update rules for the logistic loss, which is a more practically relevant setting. I think this work could do a better job of contrasting itself with previous analysis \n\n**Quality & Clarity:** \nI believe the theoretical results presented to be technically sound. The biggest issue is that there appears to be some inconsistency with respect to the loss function from result to result, which is a bit confusing to draw conclusions from (I elaborate in the *Questions* section). \n\n**Significance:**\nIt is of critical importance that we understand the implicit biases of our optimization algorithms in this era of overparameterized machine learning, and this work makes an important contribution by demonstrating how $p$-norm regularization can be achieved solely via efficient optimization methods in classification problems. In particular, it has been recently shown [1] that fast rates for interpolation in noisy settings require $p < 2$, so it is crucial that we go beyond standard gradient descent, both in theory and in practice. This work is an important step in that direction.\n\n[1] Donhauser et al., \"Fast rates for noisy interpolation require rethinking the effects of inductive bias.\" https://arxiv.org/abs/2203.03597", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ldCobU8Rpm", "reviewer": "Reviewer_UoZK", "summary": "This paper studies theoretical details of convergence point of Mirror Descent algorithm those are having potential function as p-th power of l_p norm. Moreover, in the case of linearly separable classification the convergence has been shown to be in the direction which is called generalized maximum margin.", "questions": "- To me it seems that if we check multiple values of p, one of them likely to overperform p=2 case (SGD), so i was curious if there is way to do this process better. Also, it would be nice to have accuracy studies in experimentation with other Optimization Algorithms.\n\n- Is it possible to understand characteristics of p-GD solutions with more complicated decision boundaries ?\n\n", "limitations": "-", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- Paper is theoretically sound, and investigates theoretical characteristics of MD with more suitable potential function 1/p || . ||_p^{p} which could be applicable to train Deep Learning trainings.\n- The paper studies further characteristics of linearly separable classes which is an important first step question to answer.\n- There has been experiments performed to verify results.\n\n\nWeaknesses:\n\n- This would be interpreted as question as well instead of weakness, how do you choose the best p depending on the problem. Is this a new hyper-parameter to tune or there is a structured method to find the necessary p. I am more pointing this issue in terms of experimentation ?\n-  Studying characteristics of linearly separable problems is interesting, but is there any way that p-GD could be studied more complicated decision boundaries ?\n", "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": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "O9DXIixpyAM", "reviewer": "Reviewer_FypC", "summary": "This paper derives the implicit regularization effect for the mirror descent algorithm for linear classification tasks with the exponential-tailed loss and separable data. Specifically, with the potential function being $\\Vert * \\Vert^p_p$, it is shown that mirror descent converges to the $\\ell^p$ max-margin solution. Experiments over linear models and deep neural networks are conducted to support the theoretical findings. ", "questions": "1. More discussion on the importance of mirror descent in model deep learning is appreciated.\n2. In [Soudry et al., 2017], a synthetic dataset is constructed with its max-margin solution known in prior, and the convergence to max-margin solution can thus be verified directly. It is suggested that the authors apply this methodology to verify the correctness of the theoretical results.\n3. In this paper, special potential functions are considered. What is the difficulty to extend the results to general potential functions? ", "limitations": "Please refer to the \"weakness\".", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper is well-written and I enjoy reading the paper.\n2. The theoretical analysis is solid and explicitly explained (the connection with [Ji et al., 2020] is clearly pointed out). The experiment is detailed.\n\nWeakness:\nThe major weakness lies in the motivation of the paper. The implicit bias of gradient descent (with momentum) and adaptive first-order optimizers over classification problems [Soudry et al., 2017; Qian et al. 2019; Wang et al., 2021] are studied due to their popularity in deep learning's application over classification tasks. However, mirror descent is less employed. Therefore, while it is good to know such a result, this problem has limited importance.\n\nReference:\n1. Ji et al. Gradient descent follows the regularization path for general losses, 2020\n2. Soudry et al. The Implicit Bias of Gradient Descent on Separable Data, 2017\n3. Qian et al. The Implicit Bias of AdaGrad on Separable Data, 2019\n4. Wang et al. Does Momentum Change the Implicit Regularization on Separable Data, 2021", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept