Implicit Regularization of Bregman Proximal Point Algorithm and Mirror Descent on Separable Data
Authors: Yan Li
Caleb Ju
Ethan Fang
Tuo Zhao
Venue: ICLR 2022 Submitted (2022)

Abstract: Bregman proximal point algorithm (BPPA), as one of the centerpieces in the optimization toolbox, has been witnessing emerging applications. With a simple and easy-to-implement update rule, the algorithm bears several compelling intuitions for empirical successes, yet rigorous justifications are still largely unexplored. We study the computational properties of BPPA through classification tasks with separable data, and demonstrate provable algorithmic regularization effects associated with BPPA. We show that BPPA attains a non-trivial margin, which closely depends on the condition number of the distance-generating function inducing the Bregman divergence. We further demonstrate that the dependence on the condition number is tight for a class of problems, thus showing the importance of divergence in affecting the quality of the obtained solutions. In addition, we extend our findings to mirror descent (MD), for which we establish similar connections between the margin and Bregman divergence. We demonstrate through a concrete example, and show BPPA/MD converges in direction to the maximal margin solution with respect to the squared Mahalanobis distance. Our theoretical findings are among the first to demonstrate the benign learning properties of BPPA/MD, and also provide strong corroborations 
for a careful choice of divergence in the algorithmic design. 

IMPLICIT REGULARIZATION OF BREGMAN PROXIMAL POINT ALGORITHM AND MIRROR DESCENT ON SEPA- RABLE DATA
Anonymous authors Paper under double-blind review
ABSTRACT
Bregman proximal point algorithm (BPPA), as one of the centerpieces in the op- timization toolbox, has been witnessing emerging applications. With simple and easy to implement update rule, the algorithm bears several compelling intuitions for empirical successes, yet rigorous justifications are still largely unexplored. We study the computational properties of BPPA through classification tasks with sepa- rable data, and demonstrate provable algorithmic regularization effects associated with BPPA. We show that BPPA attains non-trivial margin, which closely depends the condition number of the distance generating function inducing the Bregman divergence. We further demonstrate that the dependence on the condition number is tight for class of problems, thus showing the importance of divergence in affecting the quality of the obtained solutions. In addition, we extend our findings mirror descent (MD), for which we establish similar connections between the margin and Bregman divergence. We demonstrate through a concrete example, and show BPPA/MD converges in direction the maximal margin solution with respect to the Mabalanobis distance. Our theoretical findings are among the first demonstrate the benign learning properties BPPA/MD, and also provide strong corroborations for a careful choice of divergence in the algorithmic design.
INTRODUCTION
The role of optimization algorithms has become arguably one of the most critical factors in the empirical successes of training deep models. As the go-to choice for modern machine learning. first-order algorithms, including (stochastic) gradient descent and their adaptive counterparts (Kingmal
and Ba 2014, Duchi et al. 2011). have received tremendous attention, with detailed investigations
dedicated to understanding the effect of batch size (Goyal al. 2017 Smith et al.) 2018 Keskar
cet al. 2016), learning rate (Li et al. 2019 He et al. 2019 Lewkowycz et al. 2020), and momentum
(Sutskever et al. 2013 Smith
2018 across a broad spectrum of applications.
Meanwhile, Bregman proximal point algorithm (Eckstein 1993 Kiwiel 1997) has been drawing substantial interests. The resounding successes of this classical algorithm are particularly evident for applications including knowledge distillation (Furlanello et al. (2088), mean-teacher learning paradigm (Tarvainen and Valpola, 2017). few-shot learning (Zhou al. [2019) policy optimization (Green et 2019), and fine-tuning pre-trained models (Jiang et al. (020), yielding competitive performance compared its first-order counterparts. In the general form, Bregman proximal point algorithm updates parameters by minimizing a loss L(-), while regularizing the weighted distance to the previous iterate measured by some divergence function D.,,)),
0.11 argmin, ((0) + 1/22 (D0, 0.).
(1.1)
Popular choices of divergence function used in practice include the squared 4n-nrm distance D1s(O, 0t) = Ep [f((z) So, (rr) 1| (arvainen and Valpola, 2017). and Kullhack-Leibler based divergence (0, 0,) = KL (for [r]]] (Furlanello et al. 2018), where D denotes the data distribution. Such a simple update is of great practical purposes, as it is easy to describe, and admits simple implementation by adopting suitable off-the- black-box optimization algorithms (Solodov and Svaiter, 2000; Monteiro and Svaiter 2010 Zaslavski 2010). The updating form also suggests plausible intuitions for its empirical successes, including iteratively constraining the search space, alleviating aggressive updates, and preventing catastrophic forgetting (Schulman et al. 2015 Li and Hoiem 2017). However, none of the intuitions have been rigorously justified, and

---

theoretical understandings for the empirical successes of Bregman proximal point algorithm remains underexplored.
A first, and natural question is whether Bregman proximal point algorithm benefits from the same kind of mechanism that (stochastic) gradient descent (GD/SGD) enjoys for having the generalization properties. In particular, in many important applications, GD/SGD is widely believed as the "the algorithm that finds the right kind of solutions" for problems with non-unique solutions. Such a claim supported with numerous provable examples: GD/SGD converges to the minimum-norm solution of under-determined linear systems (Gunasekar et al. (018)) converges to the max-margin solution for separable data (Soudry et al.
et al. 2019). aligns layers of deep linear networks (Ji and Telgarsky, 2018), and converges to generalizable solution for nonlinear networks (Brutzkus) ct 2017] Allen-Zhu et al. 2018) in the presence of infinitely many overfitting solutions. Given the emerging successes of Bregman proximal point algorithm, and the aforementioned evidences on its first-order counterparts (e.g. GD/SGD) finding generalizable solutions, one would naturally wonder
Does Bregman proximal point algorithm converge to a solution with favorable qualities?
Another important question with great practical implications for Bregman proximal point algorithm is how the divergence measure -)--) affects the solution. Instead of directly applying the Euclidean distance based divergence, it is widely observed that the successful application of Bregman proximal point algorithm is contingent on the careful design of divergence measure, based on the task at hand (Li and Hoiem 2017 Hinton et al. 2015). Take the example of fine-tuning language model, the symmetrized Kullback Leibler based divergence evaluated on the predictions of the updated model (i.e., le+1) and previous model (i.e., f₂) yields the state-of-the-art result (Jiang et al. (020). Identifying the underlying mechanism for the success or failure of a given divergence choice is not only of theoretical interest, but also can significantly reduce human effort in searching/designingg the suitable divergence for given task. As an important addition, one may also ask whether the impact of divergence the Bregman proximal point algorithm find natural counterparts in commonly adopted first-order algorithms (e.g. mirror descent, (Nemirovski and Yudin, 1983). In such cases, better task-dependent algorithmic designs could be proposed in conjunction with the suitable divergence. To this end, we raise our second question.
How does divergence affect the qualities of the solution obtained by Bregman proximal point algorithm (and other first-order algorithmss?
In this paper, we initiate our study to address our previously proposed questions. We focus on non-trivial example of an under-determined system training linear classifiers using separable data. In particular, for exponential tail losses (c.g.. exponential loss), the empirical loss function has infimum zero that is asymptotically attainable at infinity along infinitely many directions. The natural candidate for measuring the quality of the obtained classifier is its margin, i.e., the minimum distance between the samples and the decision hyperplane. For such a problem, we summarize our theoretical findings below as concrete answers to the previous questions.
We show that Bregman proximal point algorithm (BPPA) obtains a solution with non-trivial margin lower-bound. As concrete demonstration, we tailor our main theorem for Mahalanobis distance, and show that BPPA converges in direction the maximal margin solution. We provide non- asymptotic analyses of the margin and empirical loss for constant stepsize BPPA, and propose a more aggressive stepsize rule for a provable exponential speed-up.
We establish a dependence of such margin lower-bound on the condition number of the distance generating function for defining the divergence. In addition, we provide a class of problems where the margin lower-bound is tight, demonstrating that the Bregman divergence is crucial in affecting the quality of the obtained solution.
We extend our findings to first-order algorithms. Specifically, show that mirror descent (MD) enjoys the same previously mentioned margin properties. We also provide non-asymptotic convergence analyses of the margin and empirical loss for constant stepsize MD, and its exponential speed-up using varying stepsize scheme. Our findings for MD strictly complement prior works on under-determined regression problems (Gunasekar et al. 2018 Azizan and Hassibi 2019).
Notations. We denote [n] == [I,..., nt:: sgn(z) = 1 if = 2 0 and -1 elsewhere. We use w.r.t in short for "with respect to". For any II-II in Euclidean space Rdd, we use ||-11, = max si ( 9) to denote its dual norm. Note that we have (II-11.), =1--11-
2

---

2 PROBLEM SETUP
We study the binary classification on linearly separable data. Specifically, the dataset S {(2,, (t)li IR {+1, -1), where z; is the feature vector, and yi is the label. In addition, there exists linear classifier и E R2 such that y: an)) > 0 for all i E [n]. That is, the decision rule f.(+) = sgu((u, ()) achieves the perfect accuracy on the dataset, with = (x,) for all i [n].
For each linear classifier fu(-) with perfect accuracy, define its |1-ll. margin the minimum distance in Il-Il, -norm from the feature vectors to the decision boundary H., = { : (a, u) = 0}. is well known that the ||-II, -norm margin, denoted Yus only depends the direction of the classifier and satisfies %uu mi)
T where ||-|| is the dual norm of Il-1l.. The ||-Il.-nom margin measures how well the data is separated by decision rule fu(-), measured in I|- and is an important measure on the generalizability and robustness the decision rule. Given a norm II-1l. on Rdd we define the optimal linear classifier with the maximum ml-rl-n below.
(zill::
Definition 2.1 (Maximum Il-ll-nnorm Margin Classifier). Given linearly separable dataset {(r,, 34 9:) he(m) we define the maximum ||-II, -norm margin classifier W||lI,, and its associated maxi- mum Il- -nomm margin 7
MIl arginax min (u, yar)) TH... max min (u, yer.) || /Ein]
w EE(m)
For separable dataset, consider finding the classifier by minimizing the empirical loss Ls( 1 E.= (16, y;zz)).
(2.1)
Here we focus on the exponential loss f(x) = exp(-x), and our analyses can be readily extended to other losses with tight exponential tail (e.g., logistic loss).
Observation. One can readily verify that with a separable dataset S, the empirical loss has infimum but possesses no finite solution that attains the infimum. Thus any optimization algorithm minimizing the loss (-)-) will observe the explosion on the norm of iterate.
It has been shown that various optimization algorithms, including (stochastic) gradient descent and steepest descent, converge in direction to the maximum margin classifier different norms (Soudry et al., 2018 Nacson et al. 2019: Gunasekar et al., 2018 Ji and Telgarsky 2019 2021). Connections between gradient descent and the regularization path of homotopy method have also been established (Ii al. 2020). A striking feature behind such phenomena is that there is explicit regularization in the loss function, and such effects have been termed as the implicit (algorithmic) regularization.
Up date, most of the implicit regularization effects are attributed to (stochastic) gradient descent, given their prevalence in applications. However, as Bregman proximal point algorithm (BPPA) becomes increasingly popular in various domains, there exists considerable lack of understanding on the computational properties of BPPA. In addition, practitioners often find the choice of divergence function crucially important for the performance of BPPA (Jiang et al.) 20200; Fuulancllo al.. 2018). This empirical evidence thus calls for a detailed characterization on the connection between computational properties and the divergence function of BPPA.
In what follows, we study the BPPA for solving problem 1 in detail. The BPPA (Algorithm I is an adaptation of the vanilla proximal point algorithm (Rockafellar 1976a b) non-euclidean geometry, by using Bregman divergence
the divergence measure in I.1p. Specifically, given distance generating function w-)) that is convex and differentiable, we define the Bregman divergence (-.)..)
associated with w(-) (0, 0') w()) w(O') (Vw(('), 0') Throughout our discussions, we only impose the following mild assumption on Bregman divergence function (w
Algorithm 1 Bregman Proximal Point Algorithm (BPPA)
Input: Distance generating function w(-). stepsizes (n' he2o samples {aa, y Initialize: 8 O. for 1. O,... do.do
Update 0.41 argmin Ls(0) + - Dm,(0,
(2.2)
21,.
end for
3

---

Assumption 1. We assume that the distance generating function of Bregman divergence Dw(:,)) is Tmo-tho and po -trongly convex w.r.t ||-|| -normm. That is,
Hh 110 - 112 I w((t) w(6' (6) 8¹) I
Iaw
2 10 8¹11
2
ALGORITHMIC REGULARIZATION OF BPPA
We show BPPA achieves a Il-II, norm margin that is at least / Lw fraction of the maximal one. Theorem 3.1 (Constant Stepsize BPPA). Let PIHII- maxie(n) [m] || ll where II- denotes the dual norm of I|- Then under Assumption for any constant stepsize T)t 1 > the following hold. (1) We have lim, (0,) = O. Specifically, we have that (s((t)) diminishes at the following rate,
1 L log" 2 Cn-n..7)
L log" (111.1. nt)
(O.) -
M1-11_ nt +
4niH1, tyt
M1-11
(2) We have that the margin is asymptotically lower bounded by
O2
Pw 711-11-
lim min where MHI is defined in Definition
0 Metr
Tuo
(3.1)
2.1
In addition, for any given >> O, there exists satisfying
D
Di.
Hw 2imn. 1
Tow 1
IH..
= O
max
exp
M.. 2
such that for t 2 to number of iterations, we have
(1 - VV Hw
Vi [m]]
|10.11
Ln 7HI..
We highlight that (1) The choice of Bregman divergence in BPPA is flexible and be data dependent. Properly chosen data-dependent divergence can adapt to data geometry much better than data-independent divergence, leading to better separation and margin. In Section we demonstrate how BPPA can benefit significantly from such an adaptivity of carefully designed data-dependent divergence. (2) Our analysis on the convergence requires handling non-finite minimizers, which implies divergence of iterate ||0||| > oc. The optimization problem of our interest does not meet the standard assumptions
the classical analysis of BPPA in the literature, and requires a careful choice of reference point in order to derive non-trivial convergence results. (3) Our result is closely related, but should not be confused with the homotopy method in (Rosset et al. 20044), which can be viewed performing only one proximal step the origin, with extremely large stepsize. (4) Finally, our result is a generalization of Telgarsky 2) Gunasekar et al.) (2018) to non-euclidean settings with Bregman divergence. Working with Bregman divergence poses unique challenges, it is previously unclear how to relate the primal margin progress to the per-iteration progress over the dual space.
Theorem 3.1 shows that if the distance generating function w(-)) is well-conditioned w.r.t. Il-|l-norm, then Bregman proximal point algorithm will output a solution with near optimal ||-11, -norm margin.
As concrete realization of Theorem 3.1 we consider the Mahalanobis distance ||+ a A.) induced by a positive definite matrix A.
Corollary 3.1. Let [1-I1
|I-II for some positive definite matrix A. Under the same conditions as Theorem 3./ BPPA with distance generating function w(-) A-) converges to the maximum |l-1l. -arginn solution, where I1-11.
I1. Specifically, we have
Lo log? (n (m-11_.))
Tow log² (11-1_79) 7t)
1
Ls(O.) 5
71-11 9
47,-11 1/
Ti-1_ 9d
In addition, we have lim minge[m)
|
B vewr)
= 71-111-
Specifically, for any given > 0,
there exists to satisfying to = δ max number of iterations, we have
1 exp
D
F.. ) such that for t to
....
21 ))
Vi E [m].
||
Finally, have the direction convergence that lim
[o.I u -1-1
4

---

Note that similar directional convergence results have been shown in Gunasekar al. (2018) for steepest descent w.r.t. ||-1l norm. The directional convergence of BPPA obtained here, however, is not simple corollary of known results, since existing analyses focus on first-order algorithms in euclidean setting (c.g., GD/SGD, steepest descent). Such existing analyses do not simply extend to non-first-order algorithms in non-euclidean setting, such as BPPA.
When the distance generating function wr(:) ill-conditioned w.r.t. Il-ll-norm (i.e., v // Lo & 1), it might be tempting to suggest that the margin lower bound in (3.1) is loose, and what really happens is lim minlg[]]]
T M/.34) = I However, as we show in the following proposition, there exists a class of problems, where the lower bound in (3.1) is in fact a tight upper bound (up to factor of 2), demonstrating that the dependence on condition number of distance generating function w(-) w.r.t. ||-1|- n-ol-norm not a proof artifact.
Proposition 3.1 (Tight Dependence on Condition Number). There exists sequence of problems (p(m))m2 where each p(m) = (s(m), [1-11(m], _m(m) denotes the dataset, the norm, and the distance generating function of the m-th problem. For each m, the distance generating function (.) is plu -strongyy convex and (mm) -smooth w.t.. |l-|-norm. Then Bregman proximal point algorithm applied to each problem in (P(m) Jmzi yields
0₂ |
(m) pa
lim
min (St)))
yr)
/71 S 2
L (m]
Vm 2
(3.2)
In addition, for any m 2 4, we have lime-so min (a.v)ess))
o ToeT y2) vxx
1 /711-11m0
S 2
(mn) 1.
< 1.
In fact.
02 [0.1" y /7m/-1/00 + 0, as m72 - 00.
lim 81000 (s.))
min
(3.3)
Combine Theorem 3.1 Corollary 3.1 and Proposition 3.1 we conclude that the margin of the obtained solution by BPPA has non-trivial dependence on the condition number of the distance generating function w-.). This observation provides a strong evidence that the Bregman divergence (-: in BPPA is highly important to the quality of the obtained solution, and advocates careful design of Bregman divergence when using the BPPA. Our theoretical findings also aligns the empirical evidences on the importance of divergence found in knowledge distillation and model fine-tuning (Jiang et al. 2020 Furlanello et al. 2018).
We have shown that BPPA with constant stepsize achieves a margin that is at least / L Low of the maximal one. Meanwhile, our complexity bound in Theorem 3.T shows that to obtain such margin lower bound, it might take an exponential number of iterations. We next show by employing a more aggressive stepsize scheme, can attain the same margin lower bound in polynomial number of iterations, while speeding up the convergence of the empirical loss (Oss drastically.
Theorem 3.2 (Varying Stepsize BPPA). Given any positive sequence {ar Peo- letting the stepsizes then the following facts hold.
(n be Vtt
are
Le(P,)'
(I) oo Ls( O. Specifically, for any 1 2 O, we have Ls(0 S (s(0))8(as), where
20,3 7i.
3(a) = min max B. exp
<L
L.
(2) Letting a4 = V we have lim4-+00 minie(n)
1
< [10/]] (12i) 2
M1-11- - In particular, for any Ah Iow
(0, 3), there exists to satisfying
(( ( Vinwe
Lew
))
to 0
(TIN Tilll
(3.4)
such that in 1. to number of iterations, we have
0,
Li --ll. Vi E [n].
|10.1| ysar
2 (1 - V)
Pwu
5

---

Additionally, the convergence rate of (Ls(0:))e20 is given by Ls(O,) =0 (expp
1 - Law
eep
vt)
We remark that (1) We do not optimize for the best polynomial dependence 1/c in the iteration complexity (3.4). as our main goal is to show the exponential gap between the complexity presented in Theorem and here. We refer interested readers to Appendix [B] where we show that we can improve the polynomial dependence with more tailored analysis. (2) We also demonstrate that the
empirical loss converges almost exponentially faster with our choice of stepsizes. (3) We reiterate that using the aggressive stepsizes does not change our established margin lower bound, and the exact convergence to the maximum margin solution demonstrated in Corollary 3.1 still holds for this scheme of stepsizes, which can be achieved with polynomial number of iterations.
Inexact Implementation of BPPA. The proximal update 2.2p requires solving a non-trivial
optimization problem, and there has been fruitful results of inexact implementation of BPPA in optimization literature (Rockafellar 1976b Yang and Toh 2021 Solodov and Svaiter 2000; Monteiro
and Svaiter 2010). Here based the varying stepsize scheme proposed in Theorem 3.2 discuss the feasibility of gradient descent based inexact BPPA that: (1) admits a simple implementation and achieves polynomial complexity, (2) retains the margin properties of exact BPPA. Specifically, the 1-th iteration, the gradient descent based inexact BPPA solves the proximal step
De+1 Rs argming (0) - E exp (- (0, yv2))) + J (0,
(3.5)
up to a pre-specified accuracy 5, with gradient descent. Our key observation comes from the fact that when applying gradient descent to (-(-) with small enough stepsizes, the iterate would stay in region that has relative smoothness M, and relative strong convexity μt bounded by
M, Ls (0.) " Ls((t) (1+
1 L(θ.) Oie
14
2018 Note that the first incquality follows by our choice of stepsize f/ in Theorem 3.2 Thus the effective condition number ne == M2/ pe of (-)- is bounded by Re = +1+ a4 = (1), which implies that the t-th proximal step requires
both measured w.r.t Bregman divergence (. (Lu al.
O Ke log( 2))
O (log(t) )) number of gradient descent steps. Summing up across to iterations
gradient descent steps, which depends polynomially to even if we choose an extremely high accuracy 5, ((exp(-1) for each inexact proximal step 335).
3.4 we need up to O Ete log( 1t
4 ALGORITHMIC REGULARIZATION OF MIRROR DESCENT
Inspired by the results in the previous section, we further show that mirror descent (MD, Algorithm 2 as generalization of gradient descent to non-euclidean geometry, possesses similar connection be- tween the margin and Bregman divergence. We remark that our results are the first to characterize the algorithmic regularization effect of MD for classificatinn tasks, while previous literature exclusively focus on under- determindd regression problems (Gunasekar et al. 2018 Azizan and Hassibi 2019).
Algorithm 2 Mirror Descent Algorithm (MD)
Input: Distance generating function w(-), stepsizes (77)e20 samples {ax y V Initialize: 8 O.
for I O,...do do
Compute gradient V (O.)).) = -n exp (- (0:. yrrr)) (-yare)- Update f argming (VLs(0:), 0i) + 24. (n (0,0,) 0c). end for
Theorem 4.1 (Constant Stepsize MD). Let Dp-i_ = max || where |I-I1. denotes the dual
let μ2 be the strong convexity norm of I| and D1-12 = maxse[n] [| 22- Under Assumption [
pz parameter of w(-) w.r. -lolm--norm. Then for any constant stepsize ni S 20 we have that
(1) lim Ls(),) O. Specifically, we have that Ls(O,) diminishes at the following rate,
1 L log2 (n-n.77)) o Lw log? (711-1_7t)
Ls(O)) z
+
71-11 nt 27 nt
n- nt

---

(2) We have that the margin is asymptotically lower bounded by
O2
Pvu Lnp -
lim min +20 xE(n)
z
In addition, for any e > 0, there exists a to satisfying
3/2
11-1. P1- (
to o
exp
log
(4.1)
|/ 1.
112 63/2
23/2
such that any t 2 to we have
pw V
|0.11
2 (1 2
L 7|1-11_
Theorem shows that mirror descent attains the same I1- -nomm margin lower bound as BPPA, which is -rrfctctoonn of the maximal margin. Note that μ22 >> 0 is direct consequence of Assumption and the equivalence of norm on finite-dimensional vector space.
Similar to Corollary 3.1 let |1-11 = 11-11A be the Mahalanobis distance, then MD equipped with distance generating function w(-) A-) converges to the maximum -loll-norrm margin classifier. Corollary 4.1. Lef [I-]1 = I1-Il for some positive definite matrix A. Then under the same conditions as in Theorem 4.1 the MD with distance generating function w(-) {-, A-) converges to the maximum
I1-ll- solution, where I1-11= = 1--1==1-11A--1111 Specifically, we have Ls O log' (71 a. nt)
P. 92
In addition, we have lim minge[n)
O. Toell yizrs
71ll1. Specifically, for any given
log (t) (+)) succ that for 2 to number of 7 nw 12/2
D D D1 Lw
there exists a to with to O exp iterations, we have
Oz
(1 -
Vi E [n].
|[0.1|
Finally, we have direction convergence that limy-+00
6 |
Note that Corollary 4.1 recovers the directional convergence of steepest descent in Gunasekar et al.) (2018) w.r.t Il which coincides with MD with distance generating function w(.) A,
Theorem 4.1 guarantees the near optimal ||-II_ -norm margin when the distance generating function w(-) is well-conditioned w.r.t |]-I| n-rl-norm. For cases when w(-) is ill-conditioned, we demonstrate that there exists class problem for which the margin lower bound is tight.
Proposition 4.1. There exists sequence of problems (P(m) m2 by the same construction in Proposition such that the margin lower bound in Theorem 4.1 is tight to non-trivial factor of Specifically, we have (3.2) and (3.3) also hold for MD.
Finally, we propose a more aggressive stepsize scheme for MD that achieves the same margin lower bound. In addition, instead of requiring exponential number of iterations (4.1) as constant stepsize MD, such a stepsize scheme only needs polynomial number of iterations, and achieves an almost exponential speedup for the empirical loss (Ls (0.)))00
Theorem 4.2 (Varying Stepsize MD). the stepsizes (Ma}1o be given by me Ls(0,)) where V ). Then under the same conditions as in Theorem 4.1
a, min 2D1-12
(1) We have lim minse[n)
Be MH In addition, for any >> 0, there exists V
to satisfying to =0 =
(7I )))
Dj 11-12 T.
such that for any t 2 to. we have
0
2 21-
Pw L
Vi [n].
|10,1|"
M-l..
(2) We have lim, Ls(),) 0. In addition. the convergence rate is given by
Ti-1
Ls().)
eepp
vi

---

5 EXPERIMENTS
Synthetic Data. We take = (((-0.5, +1), ( -1), One can readily verify that the maximum Iloll--norm margin classifier is u||-1: (0. For both BPPA and MD, we take the Bregman divergence as (a, y) = a y1ا which corresponds to the vanilla proximal point algorithm and gradient descent algorithm. Note that both algorithms are guaranteed to converge in direction towards Willlla
-1), -1,, -1),
(0, 1), following Corollary 3.1 and 4.1
1.00
10
1.400
0.975
10
0.96
10
0,950
0.94
0,900
10
Chastal Sigpeia
10
0.850
Comnier dieptte Siepetr
0.90
200 400 600 se0 1000 120
Iterations
Irerations
Iterations
(a) BPPA
(b)
MD
Figure 1: BPPA and MD run on the simple data set S.
for the varying To implement the proximal step in BPPA at the t-th iteration, we take 128 number of gradient descent steps with stepsize 0.2%; following our discussion the end of Section 3
We take
for the constant stepsize BPPA/MD, and тΙ
V18.)
stepsize BPPA/MD, following the stepsize choices in Theorem 3.1 3.2 4.1
and
We initialize all algorithms the origin and run 1200 iterations. From Figure 1 we can clearly observe that both BPPA and MD converge in direction to the maximum [1-Il2-norm margin classifier "I|-Il. which consistent with our theoretical findings. In addition, by adopting the varying stepsize schème proposed in Theorem 3.2 and both BPPA and MD converge exponentially faster than their constant stepsize counterparts.
Data-dependent Bregman Divergence. We illustrate through example on how properly chosen data-dependent divergence can lead to much improved separation compared to inta-independent divergence, even simple linear models.
We have n labeled data {(,, 3)) sampled from a mixture of sphere distribution: ys Bernoulli(1/22) 24 Unif (r),, where (r) denotes the sphere centered with radius in Rd. In addition, also have unlabeled data (= following the same distribution as {z, ). with no labels given. Clearly, the maximum ||-I|,- -malgnn classifier for the mixture of sphere distribution considered here is given by the linear classifier f*(+) sign((
Usabeld
Divergence
Alignment
Negrow
(
0,8703
((2)
0.8175
D19)
0.9754
Figure 2: BPPA with Bregman divergence ((3) (right) significantly improves alignment with optimal classifier μ4, compared to D(1) (left) eraged over 8 runs. and D (middle).
Table 1: < Rr
1, + av-
We choose n = d = 2, m = 100, r0,,== = 0.8, and generate ~ Unif (So(1)). We compare three types of Bregman divergence, given by (0, 0') = 0 0'13 (vanilla proximal point), (0,)0, 81 T 8'), and (33) (0, 8') (0 8') ) T- 6'), where E m プ,и denotes the empirical covariance matrix. Note that (2) and (33) are data-dependent from their construction. For each divergence function, we run BPPA with 8 independent runs, the results are reported in Figure 2 and Table I We make two important remarks on the empirical results:
Data-dependen divergence (3) gives the best separation despite limited labeled data (in fact only 2!), much improved over data-independent squared fz-distance (11)
Not all data-dependent divergence helps, (22) shows degradation compared to D(),
We further remark that by utilizing Corollary 3.1 one completely characterize the solution obtained by BPPA for each of the divergence in closed form. Using such a characterization allows
to corroborate the empirical phenomenon with developed theories, deferred in Appendix A
8

---

CIFAR-100. We demonstrate the potential of extending our theoretical findings for linear models to practical networks, using ResNet-18 (He et al., 2016), ShuffeNett2 (Ma et al.] 2018), Mo- bileNetV2 (Sandler et al. 2018), with CIFAR-TO0 dataset (Krizhevsky et al. 2009). iteration of BPPA, the updated model parameter 0z-1 is given by solving the proximal step 0.+1 = argming 1/n > E {ffo(z)); v.) + ( 0.) for all & 2 O, where D denotes di- vergence function, and Bn is obtained by standard training with SGD. We consider inexact imple- mentation of the proximal step, discussed in (35). Specifically, each proximal step is solved by using SGD, with batch size of 128, initial learning rate of 0.1 which is subsequently divided by 5 at the 60th, 120th, and 160th epoch. We consider two divergence functions widely used in practice, defined by Drs((',, 0) = 12((2) and (f 8¹) = 12(2n) D KL (for (2;))lff(zz)) (Furlanello et al. 2018). For each of the diver- gence, we run BPPA with proximal steps, with the proximal stepsize v 7 0.025 for DRL., and M) = 1 0.2 for DL. (7p- = 0.025 gives significantly worse performance). For standard training with SGD, we use batch size of 128, an initial learning rate of 0.1 further divided by 5 the 60th, 120th, and 160th epoch. The results are reported in Figure 3
each
(T==o))(((x))) (x.))) Tarvainen and Valpola 2017
B8sNet18
StuVt
ResNetl8
75.0
Tho
50.0
5GD
SCD
Prov
Pros
57.5
33
125
Epoch
Spuch
Epech
Epoch
Figure 3: BPPA with divergences DKL and DLS on CIFAR- 100 dataset. KL-Prox-k denotes learning
curve of the k-th proximal step with DKL; LS-Prox-k denotes learning curve of the k-th proximal step with Dis-
One can clearly see from Figure 3 (1) Across different model architectures, BPPA with DKL outperforms standard training with SGD: (2) BPPA with DLS yields negligihle differences compared to SGD, The qualitative difference of DKL and DLs strongly indicates that the divergence function serves an important role in affecting the model performance learned by BPPA, which we view as an important evidence showing broader applicability of our developed divergence-dependent margin theories. In addition, the learned model with DKL improves gradually w.r.t the total number of proximal steps. For ResNet- 18, the accuracy increases from 75.8 75.83% (standard training) 78.56% after 3 proximal steps an additional 1.4% improvement over Tf-KD seif (see Table 2), which can be viewed as BPPA with proximal step. We view such findings as the evidence suggesting the scope of algorithmic regularization associated with BPPA goes beyond simple linear models.
We make further remarks on the previously proposed method in Yuan et al.] (2019), named Teacher-free Knowledge Distillation via self-training (Tf-KD sel)) which is equivalent BPPA with proximal steps, us- ing DKL(0, 8') as the divergence function. Tf-KD.elf was shown to improve over SGD for various network architectures on CIFAR- 100 and Tiny-ImageNet. We include the reported results CIFAR-10M 100 therein in
Model
SGD
Tf-KD self
MobileNetV2
68.38
70.96 (+2.58)
ShuffleNetV2
70.34
72.23 (+1.89)
ResNer18
75.87
77.10 (+1.23)
GoogLeNet
78.72
80.17 (+1.45)
DenseNet121
79.04
80.26 (+1.22)
Table Comparison of Tf-KKDeet sel (2-step
Table 2 for completeness.
BPPA) and SGD on CIFAR-100.
CONCLUSION AND FUTURE DIRECTION
To conclude, we have shown that for binary classification task with linearly separable data, the Bregman proximal point algorithm and mirror descent attain ||-11, -norm margin that is closely related to the condition number of the distance generating function w.r.t. |lolm-norm. We list two directions worthy of future investigations.
(1) Our analyses exploit the fact that the Bregman divergence is defined over the model parameters, while many popular data-dependent divergences are defined over the model output (e.g. prediction confidence). Making this non-trivial extension to data-dependent divergence can also help demystify the mechanism of the data-dependent divergence. (2) Our current analyses focus on linear models, and the extension nonlinear neural networks requires more delicate definitions of margin and divergence. We leave this direction as our long-term investigation plan.

---

REFERENCES
ALLEN-ZHU, Z.,, LI, Y. and LIANG, Y. (2018). Learning and generalization in overparameterizee neural networks, going beyond two layers. arXiv preprint arXiv:181 1.04918.
AZIZAN, N. and HASSIBI, B. (2019). Stochastic gradient/mirror descent: Minimax optimality and implicit regularizatio.. In International Conference on Learning Representations.
BRUTZKUS, A., GLOBERSON, A., MALACH, E. and SHALEV-SHWARE S. (2017). Sgd learns over-parameteriza networks that provably generalize on linearly separable data. arXiv preprint vrxiv:/7100 10174.
DEVLIN, J., CHANG, M.-W., LEE, K. and TOUTANOVA, K. (2018). Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:
DUCHI, J., HAZAN, E. and SINGER, Y. (2011). Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research 12.
ECKSTEIN, (1993). Nonlinear proximal point algorithms using bregman functions, with applica- tions to convex programming. Mathematics of Operations Research 18 202-226.
FRENCH, R. M. (1999). Catastrophic forgetting in connectionist networks. Trends in cognitive
sciences 3 128-135.
FURLANELLO, T., LIPTON, Z., TSCHANNEN, M., ITTI, L. and ANANDKUMAR, A. (2018). Born again neural networks. International Conference on Machine Learming. PMLR.
GOYAL, P., DOLLÁR, P., GIRSHICK, R., NOORDHUIS, P., WESOLOWSKI, L., KYROLA, A.,
TULLOCH, A., JIA, Y. and HE, K. (2017). Accurate, large minibatch sgd: Training imagenet in hour, arXiv preprint arXiv:
GREEN. S., VINEYARD, C. M. and Koç, C. K. (2019). Distillation strategies for proximal policy optimization. arXiv preprint arXiv:1901.0812.
GUNASEKAR, S., LEE, J., SOUDRY, D. and SREBRO, N. (2018). Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning. PMLR.
HE, K., ZHANG, X., REN, S. and SuN, J. (2016). Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition.
HE, T., ZIIANG, Z., ZIIANG, H., ZIIANG, Z., XIE, J. and LI, M. (2019). Bag of tricks for image classification with convolutional neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition.
HINTON, G., VINYALS, O. and DEAN, J. (2015). Distilling the knowledge in neural network. arXiv preprint 1rXiv:150..02531.
J1, Z., DUDIK, M., SCHAPIRE, R. E. and TELGARSKY, M. (2020). Gradient descent follows the regularization path for general losses. In Proceedings of Thirty Third Conference on Learning Theory (J. Abernethy and S. Agarwal, eds.), vol. 125 of Proceedings of Machine Learning Research. PMLR.
J1, Z. and TELGARSKY, M. (2018). Gradient descent aligns the layers of deep linear networks. arXiv preprint arXiv:1810.02032.
J1, Z. and TELGARSKY. M. (2019). The implicit bias of gradient descent on nonseparable data. In Proceedings of the -ecood Conference on Learning Theory (A. Beygelzimer and D. Hsu, eds.), vol. 99 of Proceedings of Machine Learning Research. PMLR, Phoenix, USA.
J1, Z. and TELGARSKY, M. (2021). Characterizing the implicit bias via primal- dual analysis. In Algorithmic Learning Theory. PMLR
10

---

JIANG, H., HE, P., CHEN, W., LIU, X., GAO, and ZHAO, T. (2020). SMART: Robust and efficient fine-tuning for pre-trained natural language models through principled regularized optimization. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguistics, Online.
KAKADE, S.. SHALEV-SSWARTZ S., TEWARI, A. ET AL. (2009), On the duality of strong convexity and strong smoothness: Learning applications and matrix regularization. Unpublished Manuscript, http:/htic. uchicago. eduuhhai/ppperssccaadeellll Tewarri09 pdf 2.
KESKAR, N. S., MUDIGERE, D., NOCEDAL, J., SMELYANSKIY, M. and TANG, P. P. (2016). On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprini 0609,
KINGMA, D. P. and BA, J. (2014), Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.698..
KIRKPATRICK, J.. PASCANU, R., RABINOWITZ, N., VENESS, J., DESIARDINS, G., RUSU, A. A., MILAN, K., QUAN, J., RAMALHO, T., catastrophic forgetting in neural networks. Proceedings of the national academy of sciences 114 3521-3526.
A. ET AL. (2017). Overcoming
KIWIEL, K. C. (1997). Proximal minimization methods with generalized bregman functions. SIAM journal control and optimizaatin 35 1142-1168.
KRIZHEVSKY, A., HINTON, G. ET AL. (2009). Learning multiple layers of features from tiny images
LEWKOWYCZ, A., BAHRI, Y., DYER, E., SOHL-DICKSTEIN, and GUR-ARI, G. (2020). The large learning rate phase of deep learning: the catapult mechanism. arXiv preprint arXiv:2003.02218
LI, Y., WEI, C. and MA, T. (2019). Towards explaining the regularization effect of initial large learning rate in training neural networks. arXiv preprini urXiv:1907004595.
LI, Z. and HOIEM, D. (2017). Learning without forgetting. IEEE transactions pattern analysis and machine intelligence 40 2935-2947.
LU, H., FREUND, R. M. and NESTEROV, Y. (2018). Relatively smooth convex optimization by first-order methods, and applications. SIAM Journal on Optimization 28 333-354.
MA. N., ZHANG, X., ZHENG, H.-T. and SUN, J. (2018). Shufflenct v2: Practical guidelines for efficient architecture design. In Proceedings of the European conference computer vision (ECCV).
McCLOSKEY, M. and COHEN, N. J. (1989). Catastrophic interference in connectionist networks: The sequential learning problem. In Psychology of learning and motivation, vol. 24. Elsevier, 109-165.
MONTEIRO, R. D. and SVAITER, B. (2010). Convergence rate of inexact proximal point methods with relative error criteria for convex optimization. submitted to SIAM Journal on Optimization.
NACSON, M. S., LEE, J.. GUNASEKAR, S., SAVARESE, P. H. P., SREBRO, N. and SOUDRY, D. (2019). Convergence of gradient descent on separable data. In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statisties (K. Chaudhuri and M. Sugiyama, eds.), vol. 89 of Proceedings of Machine Learning Research. PMLR.
NEMIROVSKI, A. S. and YUDIN, D. B. (1983). Problem complexity and method efficiency in optimization.
ROCKAFELLAR, R. T. (1976a). Augmented lagrangians and applications of the proximal point algorithm convex programming. Mathematics of operations research 97-1166.
ROCKAFELLAR, R. T. (1976b). Monotone operators and the proximal point algorithm. SIAM journal control and optimization 14 877-898.

---

ROSSET, S., ZHU, and HASTIE, (2004). Boosting as a regularized path a maximum margin classifier. The Journal of Machine Learning Research 5 941-973.
SANDLER, M., HOWARD, A., ZHU, M., ZHMOGINOV, A. and CHEN, L.-C. (2018). Mobilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE conference computer vision and pattern recognition.
SCHULMAN, J., LEVINE, S., ABBEEL, P., JORDAN, M. and MORITZ, P. (2015). Trust region policy optimization. International conference on machine learning. PMLR.
SMITH, L. N. (2018). A disciplined approach to neural network hyper-parameters: Part 1-learning rate, batch size, momentum, and weight decay. arXiv preprint
SMITH, S. L., KINDERMANS, P.-J. and LE, Q. V. (2018). Don't decay the learning rate, increase the batch size. In International Conference on Learning Representations.
SOLODOV, M. V. and SVAITER, B. F. (2000). Error bounds for proximal point subproblems and associated inexact proximal point algorithms. Mathematical programming 88 371-389.
SOUDRY, D., HOFFER, E. and SREBRO, N. (2018), The implicit bias of gradient descent on separable data. International Conference on Learning Representations.
SUTSKEVER, I., MARTENS, J., DAHL,, G. and HINTON, G. (2013). On the importance of initial- ization and momentum deep learning. In Proceedings of the 30th International Conference on Machine Learning (S. Dasgupta and D. McAllester, eds.), vol. 28 of Proceedings of Machine Learning Research. PMLR, Atlanta, Georgia, USA.
TARVAINEN, A. and VALPOLA, H. (2017). Mean teachers are better role models: Weight- averaged consistency targets improve semi-supervised deep learning results. arXiv preprint 17xiv:1703.0/880.
TELGARSKY, M. (2013). Margins, shrinkage, and boosting. In International Conference on Machine Learning. PMLR.
YANG, L. and TOH. K.-C. (2021). Bregman proximal point algorithm revisited: new inexact version and its variant. arXiv preprint arXiv:2105.10370.
YUAN, L.. TAY, F. E., L1, G., WANG, T. and FENG, (2019). Revisit knowledge distillation: free framework.
ZASLAVSKI, A. J. (2010). Convergence of proximal point method the presence of computational eттогs in hilbert spaces. SIAM Journal on Optimization 20 2413-2421.
ZHANG, T., WU, F., KATIYAR, A., WEINBERGER, K. Q. and ARTZI, Y. (2021). Revisiting few-sample (bert] fine-tuning, In International Conference on Learning Representations.
ZHOU, P., YUAN, X., XU, H., YAN, S. and FENG, J. (2019). Efficient meta learning via mini- batch proximal update. In Advances in Neural Information Processing Systems (H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bon Buc, E. Fox and R. Garnett, eds.), vol. 32. Curran Associates, Inc.
12


Reviews:
[{"review_id": "vL0sD_c8Rgb", "reviewer": "Reviewer_nntq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "## Strengths\n\nThis paper provides a framework to study theoretical guarantees of BPPA. It provides both a lower bound and an upper bound on the margin obtained by BPPA, both depending on the condition number of the distance generating function of Bregman divergence. It is a step-stone for further studies about BPPA and relevant algorithms.\n\n## Weakness\n\n1. The setting is restricted to binary classification on linearly separable data. I'd want to know how the results generalize to other settings, like regression and multi-classification. \n2. No comparison with the convergence rate of SGD. Since SGD is the more popular alternative of BPPA, it would be helpful to state the convergence property of SGD and make a comparison with BPPA. There are some comparisons in experiments. But the difference between SGD and BPPA is not very large. It would be interesting to know which one is better in a certain situation. \n3. The comparison between SGD and BPPA in the experiment with CIFAR-100 may not be a fair comparison. Tf-KD\\_self is a more sophisticated method than the one studied in this paper. There are also variants of SGD, e.g. Adam, which are more commonly used and probably more efficient. So comparing vanilla SGD with Tf-KD\\_self does not seem fair.\n", "summary_of_the_paper": "This paper studies theoretical properties of Bregman proximal point algorithm in the linearly separable binary classification problem. The main theorem shows that the margin obtained by BPPA is lower bounded by the maximum margin multiplied by a factor, which depends on the distance generating function of the Bregman divergence. Similar results are extended to mirror descent. The theorems emphasize the importance of the choice of Bregman divergence, which is further demonstrated in several numerical experiments.", "summary_of_the_review": "I recommend accepting the paper. Even though the setting is restricted to binary classification with linearly separable data, it adds some new understandings of the properties of BPPA and gives some suggestions on how to choose the Bregman divergence.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "r0opKKl-hex", "reviewer": "Reviewer_ZTvX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "Strength\n1. Bregman proximal point is gaining interest in applications as mentioned by the authors, and understanding the property of its convergence direction (for a linearly separable data) is of significant interest.\n2. This is a non-trivial extension of Gunasekar et al. (2018) showing that the GD converges in direction to the max margin solution for a linearly separable data.\n\nWeakness\n1. Applications: For a novice like me on the use of Bregman proximal point method in applications like knowledge distillation and mean-teacher learning (listed in page 1), providing such examples explicitly in the beginning with the specific choice of the Bregman distance could have been useful. I believe that this will also better motivate the presented work from the beginning, although some are mentioned later in the experiments section.\n2. Non-trivial margin: It is not clear whether the convergence in direction to \"non-trivial margin\" solution has any important meaning. The GD converging in direction to the max margin solution somewhat suggested that the GD will generalize well, in the literatures. However, I don't see what one can claim from the non-max margin by BPPA/MD that is $\\sqrt{\\frac{\\mu_w}{L_w}}$-times the max margin. The authors claim, after theorem 3.1, that the data-dependent divergence leads to a better separation and margin, but I don't think there is any theoretical justification for this. Let me know if I am missing something here. This also applies to the sentence \"the Bregman divergence in BPPA is highly important to the quality of the obtained solution\". I hope to see a more detailed explanation on the \"quality\" of the solution.\n3. When the distance generating function is chosen to be the Mahalanobis distance, one has the max margin solution. Then, what does this make interesting over the classic GD that also find the max margin solution? The authors are aware of such fact (see the beginning of page 5), but other than this is a non-trivial derivation, I don't see any benefit of using BPPA over GD, which I expected from the abstract of this paper.\n4. Conditions for the distance generating functions: To the best of my knowledge, the KL divergence in page 9 is not smooth. I suggest the authors clarify this.\n5. Experiment on CIFAR-10: The authors claim that BPPA performs better than SGD in early iterations, which is not evident from the figure. In addition, the provided theory is interested in the asymptotic behavior of the methods, and asymptotically SGD and BPPA seem to behave similar in this experiment.\n\nComments\n- page 2: I think (Bregman) proximal point algorithms are considered to be in the class of first-order algorithms.\n- page 4: What is the reference point you are referring to? Could you also explain this and the corresponding non-trivial convergence results in more details?\n- page 8 synthetic data: How about a constant step size that depends on $L(\\theta_t)$? Is either $L(\\theta_t)$ or \\frac{1}{\\sqrt{t+1}}$, or both making the adaptive BPPA/MD better, over the constant step BPPA/MD?\n- page 8 synthetic data: How about considering the non-Euclidean distance here?\n- page 8 mixture of sphere: Are the choices $D^{(2)}$ or $D^{(3)}$ standard? Any references? Are the first and second figures in figure 2 really almost the same? I personally think that the explanation of this section can be largely improved. I was not able to understand many points clearly. \n\n", "summary_of_the_paper": "This paper extends the max margin analysis of the gradient descent (GD) method (using an exponential tail loss with linearly separable data) to its analogous analysis of the Bregman proximal point algorithm (BPPA) and mirror descent (MD). Unlike the GD converging in direction to the max margin solution, the authors show that BPPA/MD converge in direction to a solution with a margin depending on the condition number of the distance generating function.", "summary_of_the_review": "The theory is new, but the theory does not seem to support the authors' claim that BPPA finds a better data-dependent solution. The experiment also do not seem to fully support the author's claim.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "eqwY7LhnT57", "reviewer": "Reviewer_Mehh", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "The typical study of implicit regularisation in the literature looks at how doing plain gradient descent on reparameterized problems lead to bias effects (such as sparsity or low rank). Moreover, these regularisation effects are because gradient dynamics along with reparameterization precisely correspond to mirror flows. I find it slightly odd that you call your setting 'implicit regularisation', because your results are dependent on a norm which is explicitly imposed by the Bregman divergence used. In this sense, I find the results obtained unsurprising. Moreover, many of the citations are related to implicit regularisation, and very few to the study of mirror descent. For example, \nOrabona, Francesco, Koby Crammer, and Nicolo Cesa-Bianchi. \"A generalized online mirror descent with applications to classification and regression.\" Machine Learning 99.3 (2015): 411-435.\nGhai, Udaya, Elad Hazan, and Yoram Singer. \"Exponentiated gradient meets gradient descent.\" Algorithmic Learning Theory. PMLR, 2020.\n\nI think what is missing is a review of the existing theoretical contributions on mirror descent and the authors should clarify their contributions in the context of existing works.", "summary_of_the_paper": "This article provides an analysis of Bregman PPA / mirror descent for classification. This work is largely motivated by the recent works on implicit regularisation (of gradient descent). Their theoretical results show how the recovered margins depend on the Bregman divergence used.", "summary_of_the_review": "In my opinion, linking this to implicit regularisation is an over-sell of the paper. The authors derive some interesting results on margin convergence, but similar results also exist in the literature, and proving convergence results in terms of the norm that you are strongly convex with respect to is not new.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "Apkx_e8XZNA", "reviewer": "Reviewer_yiCx", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "Strength\n\nThe paper is a very well written paper with analysis and shows the properties of the BPPA algorithm and mirror descent algorithms to learn a linear classifier using separable data. To the best of my understanding the analysis seems correct. I have gone through the proofs and they seems fine.  However, I am not sure if there is earlier work with this analysis for the particular problem they deal with.\n\nWeakness\n\nThe main issue or concern is how relevant is the study of these algorithms to find a linear classifiers on separable data. As suggested in future work, even if they had shown empirical results on the non-linear classifiers with some heuristics would have significantly improved the contribution of the paper.\n\nOverall my belief is that the work  has some good results but I am not sure of the relevance of these results in the present day machine learning.", "summary_of_the_paper": "This work studies the use of Bregman Proximal Point Algorithm(BPPA) on training linear classifiers using seperable data. The paper focuses on theoretical findings of the following form\n\na) BPPA obtains a solution with non-trivial margin lower bound. For the mahalanobis distance, they show that the solution is a max-margin solution. They also show non-asymptotic analysis for constant step size and speed it up to exponential step size using a stepsize selection.\n\nb) Show that the max-margin lower bound is dependent on the condition number of generating function for defining the divergence. As a result suggest that the divergence should be chosen based on the underlying space on which the data resides.\n\nc) It shows that that above results also extend to the dual first order algorithms such as mirror descent.", "summary_of_the_review": "The paper addresses the use of BPPA algorithm and the mirror descent algorithm to find the max-margin linear classifier in case of separable data.  My only concern is if there is some other work if this has already been addressed and relevance of the work to present day machine learning.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper extends the analysis of Telgarsky (2013) and Gunasekar et al. (2018) to the Breman proximal point algorithm and to mirror descent. Upper and lower bounds show a dependency on the condition number of the distance generating function used in the Bregman divergence.

The paper received lukewarm reviews, also because the topic does not seem to be a good match for this community. In fact, none of the algorithms analyzed seem to be commonly used as optimization algorithms for deep learning, despite of the applications mentioned by the authors.

So, I didn't take into account the concerns about the relevance of the results for deep learning people, the complains about missing references from the OMD literature, and the supposed restricted setting.

However, even ignoring the above issues, the paper seems to fall squarely on the borderline. Hence, I carefully read it.

It seems to me that the analysis heavily builds on previous work, in particular the seminal paper of Telgarsky (2013) and the Fenchel-Young trick in Ji&Telgarsky (2019). The part on the Bregman divergence is novel, but technically speaking it is also straightforward for people in this sub-community. For example, Lemma B.3 is very well-known to any optimization person. Moreover, the curvature of the Bregman divergence is exactly the term one would expect to appear. So, the upper bound seems to be incremental compared to past work and it does not really add much to our understanding of this problem.
The matching lower bound is probably the only truly interesting result. However, it still does not exclude the possibility to achieve a better margin when measuring it in a different way. Indeed, measuring the margin according to the (dual) norm appearing in the strong convexity definition of Bregman divergence is not completely justified, but rather it seems a way to make the analysis work coherently.

Overall, given the overall lukewarm reviews and my evaluation of the limited novelty of the theoretical results, I recommend rejecting this paper.
Decision: Reject