Year: 2021

Abstract:
Bregman proximal point algorithm (BPPA), as one of the centerpieces in the optimization 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 separable data, and demonstrate provable algorithmic regularization effects associated with BPPA. We show that BPPA attains 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 Mahalanobis distance. Our theoretical findings are among the first to demonstrate the benign learning properties BPPA/MD, and also provide strong corroborations for a careful choice of divergence in the algorithmic design.

heading: 1 INTRODUCTION
text: 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 (Kingma and Ba, 2014; Duchi et al., 2011), have received tremendous attention, with detailed investigations dedicated to understanding the effect of batch size (Goyal et al., 2017; Smith et al., 2018; Keskar et 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., 2018), mean-teacher learning paradigm (Tarvainen and Valpola, 2017), few-shot learning (Zhou et al., 2019), policy optimization (Green et al., 2019), and fine-tuning pre-trained models (Jiang et al., 2020), yielding competitive performance compared to 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(·, ·),
θt+1 = argminθ L(θ) + 1/(2ηt)D(θ, θt). (1.1) Popular choices of divergence function used in practice include the squared `2-norm distance DLS(θ, θt) = ED ‖fθ(x)− fθt(x)‖22 (Tarvainen and Valpola, 2017), and Kullback-Leibler based divergence DKL(θ, θt) = EDKL (fθ′(x)‖fθ(x)) (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-shelf 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 a 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 is supported with numerous provable examples: GD/SGD converges to the minimum-norm solution of under-determined linear systems (Gunasekar et al., 2018), converges to the max-margin solution for separable data (Soudry et al., 2018; Nacson et al., 2019), aligns layers of deep linear networks (Ji and Telgarsky, 2018), and converges to a generalizable solution for nonlinear networks (Brutzkus et al., 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 D(·, ·) 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., θt+1) and previous model (i.e., θt) yields the state-of-the-art result (Jiang et al., 2020). 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/designing the suitable divergence for a given task. As an important addition, one may also ask whether the impact of divergence on 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 algorithms)?
In this paper, we initiate our study to address our previously proposed questions. We focus on a non-trivial example of an under-determined system – training linear classifiers using separable data. In particular, for exponential tail losses (e.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 a concrete demonstration, we tailor our main theorem for Mahalanobis distance, and show that BPPA converges in direction to the maximal margin solution. We provide nonasymptotic 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 a 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, we 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 a 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] := {1, . . . , n}; sgn(z) = 1 if z ≥ 0 and −1 elsewhere. We use w.r.t in short for “with respect to”. For any ‖·‖ in Euclidean space Rd, we use ‖·‖∗ = max‖y‖≤1 〈·, y〉 to denote its dual norm. Note that we have (‖·‖∗)∗ = ‖·‖.

heading: 2 PROBLEM SETUP
text: We study the binary classification on linearly separable data. Specifically, the dataset is S = {(xi, yi)}ni=1 ⊂ Rd × {+1,−1}, where xi is the feature vector, and yi is the label. In addition, there exists a linear classifier u ∈ Rd such that yi 〈u, xi〉 > 0 for all i ∈ [n]. That is, the decision rule fu(·) = sgn(〈u, ·〉) achieves the perfect accuracy on the dataset, with yi = fu(xi) for all i ∈ [n]. For each linear classifier fu(·) with perfect accuracy, we define its ‖·‖∗-norm margin as the minimum distance in ‖·‖∗-norm from the feature vectors to the decision boundaryHu = {x : 〈x, u〉 = 0}. It is well known that the ‖·‖∗-norm margin, denoted as γu, only depends on the direction of the classifier and satisfies γu = mini∈[n] 〈 xiyi, u ‖u‖ 〉 , where ‖·‖ is the dual norm of ‖·‖∗. The ‖·‖∗-norm margin measures how well the data is separated by decision rule fu(·), measured in ‖·‖∗-norm, and is an important measure on the generalizability and robustness of the decision rule. Given a norm ‖·‖∗ on Rd, we define the optimal linear classifier with the maximum ‖·‖∗-margin below. Definition 2.1 (Maximum ‖·‖∗-norm Margin Classifier). Given a linearly separable dataset {(xi, yi)}i∈[n], we define the maximum ‖·‖∗-norm margin classifier u‖·‖∗ , and its associated maximum ‖·‖∗-norm margin γ‖·‖∗ as
u‖·‖∗ = argmax‖u‖≤1 min i∈[n] 〈u, yixi〉 , γ‖·‖∗ = max‖u‖≤1 mini∈[n] 〈u, yixi〉 .
For a separable dataset, we consider finding the classifier by minimizing the empirical loss LS(θ) = 1n ∑n i=1 ` (〈θ, yixi〉) . (2.1) Here we focus on the exponential loss `(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 0 but possesses no finite solution that attains the infimum. Thus any optimization algorithm minimizing the loss LS(·) 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 in 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 (Ji et al., 2020). A striking feature behind such phenomena is that there is no explicit regularization in the loss function, and such effects have been termed as the implicit (algorithmic) regularization.
Up to 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., 2020; Furlanello et 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 (2.1) in detail. The BPPA (Algorithm 1) is an adaptation of the vanilla proximal point algorithm (Rockafellar, 1976a;b) to non-euclidean geometry, by using Bregman divergence as the divergence measure in (1.1). Specifically, given a distance generating function w(·) that is convex and differentiable, we define the Bregman divergence Dw(·, ·) associated with w(·) as Dw(θ, θ′) = w(θ)−w(θ′)− 〈∇w(θ′), θ − θ′〉 . Throughout our discussions, we only impose the following mild assumption on Bregman divergence function Dw(·, ·).
Algorithm 1 Bregman Proximal Point Algorithm (BPPA)
Input: Distance generating function w(·), stepsizes {ηt}t≥0, samples {xi, yi}ni=1. Initialize: θ0 ← 0. for t = 0, . . . do
Update θt+1 = argmin θ
LS(θ) + 1
2ηt Dw(θ, θt). (2.2)
end for
Assumption 1. We assume that the distance generating function of Bregman divergence Dw(·, ·) is Lw-smooth and µw-strongly convex w.r.t. ‖·‖-norm. That is,
µw 2 ‖θ − θ′‖2 ≤ w(θ)− w(θ′)− 〈∇w(θ′), θ − θ′〉 ≤ Lw 2 ‖θ − θ′‖2 .

heading: 3 ALGORITHMIC REGULARIZATION OF BPPA
text: We show BPPA achieves a ‖·‖∗-norm margin that is at least √ µw/Lw-fraction of the maximal one. Theorem 3.1 (Constant Stepsize BPPA). Let D‖·‖∗ = maxi∈[n] ‖xi‖∗, where ‖·‖∗ denotes the dual norm of ‖·‖. Then under Assumption 1, for any constant stepsize ηt = η > 0, the following hold. (1) We have limt→∞ LS(θt) = 0. Specifically, we have that LS(θt) diminishes at the following rate,
LS(θt) ≤ 1 γ‖·‖∗ηt + Lw log
2 ( γ‖·‖∗ηt ) 4γ2‖·‖∗ ηt = O ( Lw log 2 ( γ‖·‖∗ηt ) γ2‖·‖∗ ηt ) .
(2) We have that the margin is asymptotically lower bounded by
lim t→∞ min i∈[n] 〈 θt ‖θt‖ , yixi 〉 ≥ √ µw Lw γ‖·‖∗ , (3.1)
where γ‖·‖∗ is defined in Definition 2.1. In addition, for any given > 0, there exists a t0 satisfying t0 := Õ ( max { D2‖·‖∗ 2γ2‖·‖∗ , exp ( D2‖·‖∗ γ2‖·‖∗ 2 √ Lw µw ) 1 γ2‖·‖∗ η }) ,
such that for t ≥ t0 number of iterations, we have〈 θt ‖θt‖ , yixi 〉 ≥ (1− ) √ µw Lw γ‖·‖∗ , ∀i ∈ [n].
We highlight that (1) The choice of Bregman divergence in BPPA is flexible and can 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 5 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 ‖θt‖ → ∞. The optimization problem of our interest does not meet the standard assumptions in 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., 2004), which can be viewed as performing only one proximal step at the origin, with an extremely large stepsize. (4) Finally, our result is a generalization of Telgarsky (2013); Gunasekar et al. (2018) to non-euclidean settings with Bregman divergence. Working with Bregman divergence poses unique challenges, as 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. ‖·‖-norm, then Bregman proximal point algorithm will output a solution with near optimal ‖·‖∗-norm margin. As a concrete realization of Theorem 3.1, we consider the Mahalanobis distance ‖·‖A := √ 〈·, A·〉 induced by a positive definite matrix A. Corollary 3.1. Let ‖·‖ = ‖·‖A for some positive definite matrix A. Under the same conditions as in Theorem 3.1, BPPA with distance generating function w(·) = 〈·, A·〉 converges to the maximum ‖·‖∗-margin solution, where ‖·‖∗ = ‖·‖A−1 . Specifically, we have
LS(θt) ≤ 1 γ‖·‖∗ηt + Lw log
2 ( γ‖·‖∗ηt ) 4γ2‖·‖∗ ηt = O ( Lw log 2 ( γ‖·‖∗ηt ) γ2‖·‖∗ ηt ) .
In addition, we have limt→∞mini∈[n] 〈
θt ‖θt‖ , yixi 〉 = γ‖·‖∗ . Specifically, for any given > 0,
there exists a t0 satisfying t0 := Õ ( max { D2‖·‖∗ 2γ2‖·‖∗ , exp ( D2‖·‖∗ γ2‖·‖∗ 2 ) 1 γ2‖·‖∗ η }) , such that for t ≥ t0
number of iterations, we have〈 θt ‖θt‖ , yixi 〉 ≥ (1− )γ‖·‖∗ , ∀i ∈ [n]. Finally, we have the direction convergence that limt→∞ θt‖θt‖ = u‖·‖∗ .
Note that similar directional convergence results have been shown in Gunasekar et al. (2018) for steepest descent w.r.t. ‖·‖A norm. The directional convergence of BPPA obtained here, however, is not a simple corollary of known results, since existing analyses focus on first-order algorithms in euclidean setting (e.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 w(·) is ill-conditioned w.r.t. ‖·‖-norm (i.e., √ µw/Lw 1), it might be tempting to suggest that the margin lower bound in (3.1) is loose, and what really happens is limt→∞mini∈[n] 〈 θt ‖θt‖ , yixi 〉 = γ‖·‖∗ . 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 a factor of 2), demonstrating that the dependence on condition number of distance generating function w(·) w.r.t. ‖·‖-norm is not a proof artifact. Proposition 3.1 (Tight Dependence on Condition Number). There exists a sequence of problems {P(m)}m≥1, where each P(m) = ( S(m), ‖·‖(m) , w(m) ) denotes the dataset, the norm, and the
distance generating function of the m-th problem. For each m, the distance generating function w(m)(·) is µ(m)w -strongly convex and L(m)w -smooth w.r.t. ‖·‖-norm. Then Bregman proximal point algorithm applied to each problem in {P(m)}m≥1 yields
lim t→∞ min (x,y)∈S(m) 〈 θt ‖θt‖ , yx 〉/ γ‖·‖(m)∗ ≤ 2 √ µ (m) w
L (m) w
, ∀m ≥ 1, (3.2)
In addition, for any m ≥ 4, we have limt→∞min(x,y)∈S(m) 〈 θt ‖θt‖ , yx 〉/ γ‖·‖(m)∗ ≤ 2 √ µ (m) w L (m) w < 1. In fact,
lim t→∞ min (x,y)∈S(m) 〈 θt ‖θt‖ , yx 〉/ γ‖·‖(m)∗ → 0, as m→∞. (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 Dw(·, ·) in BPPA is highly important to the quality of the obtained solution, and advocates a 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 √ µw/Lw-fraction of the maximal one. Meanwhile, our complexity bound in Theorem 3.1 shows that to obtain such a margin lower bound, it might take an exponential number of iterations. We next show by employing a more aggressive stepsize scheme, we can attain the same margin lower bound in a polynomial number of iterations, while speeding up the convergence of the empirical loss {LS(θt)}t≥0 drastically. Theorem 3.2 (Varying Stepsize BPPA). Given any positive sequence {αt}t≥0, letting the stepsizes {ηt}t≥0 be ηt = αtLS(θt) , then the following facts hold.
(1) limt→∞ LS(θt) = 0. Specifically, for any t ≥ 0, we have LS(θt+1) ≤ LS(θt)β(αt), where β(α) = minβ∈(0,1) max { β, exp ( − 2αβ 2γ2‖·‖∗ Lw )} < 1.
(2) Letting αt = 1√t+1 , we have limt→∞mini∈[n] 〈 θt ‖θt‖ , yixi 〉 ≥ √ µw Lw γ‖·‖∗ . In particular, for any
∈ (0, 12 ), there exists a t0 satisfying
t0 = O ( Lw γ‖·‖∗ √ µw )8 , (3.4) such that in t ≥ t0 number of iterations, we have〈
θt ‖θt‖ , yixi
〉 ≥ (1− ) √ Lw µw γ‖·‖∗ , ∀i ∈ [n].
Additionally, the convergence rate of {LS(θt)}t≥0 is given by LS(θt) = O ( exp ( −γ 2 ‖·‖∗ Lw √ t )) .
We remark that (1) We do not optimize for the best polynomial dependence on 1/ in the iteration complexity (3.4), as our main goal is to show the exponential gap between the complexity presented in Theorem 3.1 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 a polynomial number of iterations.
• Inexact Implementation of BPPA. The proximal update (2.2) 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 on the varying stepsize scheme proposed in Theorem 3.2, we discuss the feasibility of a gradient descent based inexact BPPA that: (1) admits a simple implementation and achieves polynomial complexity, (2) retains the margin properties of exact BPPA. Specifically, at the t-th iteration, the gradient descent based inexact BPPA solves the proximal step
θ̂t+1 ≈ argminθ φt(θ) := 1n ∑n i=1 exp (−〈θ, yixi〉) + 12ηtDw(θ, θ̂t) (3.5)
up to a pre-specified accuracy δt with gradient descent. Our key observation comes from the fact that when applying gradient descent to φt(·) with small enough stepsizes, the iterate would stay in a region that has relative smoothness Mt and relative strong convexity µt bounded by
Mt ≤ LS(θ̂t) + 1ηt = LS(θ̂t) ( 1 + 1αt ) , µt ≥ 1ηt = L(θ̂t) αt ,
both measured w.r.t. Bregman divergence Dh(·, ·) (Lu et al., 2018). Note that the first inequality follows by our choice of stepsize ηt in Theorem 3.2. Thus the effective condition number κt := Mt/µt of φt(·) is bounded by κt = 1 + αt = O(1), which implies that the t-th proximal step requires O ( κt log(
1 δt
) ) = O ( log( 1δt ) ) number of gradient descent steps. Summing up across t0 iterations
(3.4), we need up to O (∑t0
t=1 log( 1 δt
) )
gradient descent steps, which depends polynomially on t0 even if we choose an extremely high accuracy δt = O(exp(−t)) for each inexact proximal step (3.5).

heading: 4 ALGORITHMIC REGULARIZATION OF MIRROR DESCENT
text: Inspired by the results in the previous section, we further show that mirror descent (MD, Algorithm 2), as a generalization of gradient descent to non-euclidean geometry, possesses similar connection between the margin and Bregman divergence. We remark that our results are the first to characterize the algorithmic regularization effect of MD for classification tasks, while previous literature exclusively focus on under-determined regression problems (Gunasekar et al., 2018; Azizan and Hassibi, 2019).
Algorithm 2 Mirror Descent Algorithm (MD)
Input: Distance generating function w(·), stepsizes {ηt}t≥0, samples {xi, yi}ni=1. Initialize: θ0 ← 0. for t = 0, . . . do
Compute gradient∇LS(θt) = 1n ∑n i=1 exp (−〈θt, yixi〉) (−yixi).
Update θt+1 = argminθ 〈∇LS(θt), θ − θt〉+ 12ηtDw(θ, θt). end for
Theorem 4.1 (Constant Stepsize MD). Let D‖·‖∗ = maxi∈[n] ‖xi‖∗, where ‖·‖∗ denotes the dual norm of ‖·‖, and D‖·‖2 = maxi∈[n] ‖xi‖2. Under Assumption 1, let µ2 be the strong convexity parameter of w(·) w.r.t. ‖·‖2-norm. Then for any constant stepsize ηt = η ≤ µ22D‖·‖2 , we have that
(1) limt→∞ LS(θt) = 0. Specifically, we have that LS(θt) diminishes at the following rate,
LS(θt) ≤ 1 γ‖·‖∗ηt + Lw log
2 ( γ‖·‖∗ηt ) 4γ2‖·‖∗ ηt = O ( Lw log 2 ( γ‖·‖∗ηt ) γ2‖·‖∗ ηt ) .
(2) We have that the margin is asymptotically lower bounded by
lim t→∞ min i∈[n] 〈 θt ‖θt‖ , yixi 〉 ≥ √ µw Lw γ‖·‖∗ .
In addition, for any > 0, there exists a t0 satisfying
t0 = O exp  D3/2‖·‖∗D‖·‖2Lwη γ2‖·‖∗ µ 1/2 w µ 3/2 2 3/2 log ( 1 ) , (4.1) such that any t ≥ t0, we have 〈
θt ‖θt‖ , yixi
〉 ≥ (1− ) √ µw Lw γ‖·‖∗ ,
Theorem 4.1 shows that mirror descent attains the same ‖·‖∗-norm margin lower bound as BPPA, which is √ µw/Lw-fraction of the maximal margin. Note that µ2 > 0 is a direct consequence of Assumption 1 and the equivalence of norm on finite-dimensional vector space.
Similar to Corollary 3.1, let ‖·‖ = ‖·‖A be the Mahalanobis distance, then MD equipped with distance generating function w(·) = 〈·, A·〉 converges to the maximum ‖·‖∗-norm margin classifier. Corollary 4.1. Let ‖·‖ = ‖·‖A for some positive definite matrixA. Then under the same conditions as in Theorem 4.1, the MD with distance generating function w(·) = 〈·, A·〉 converges to the maximum ‖·‖∗-margin solution, where ‖·‖∗ = ‖·‖A−1 . Specifically, we have LS(θt) = O ( Lw log
2(γ‖·‖∗ηt) γ2‖·‖∗ ηt
) .
In addition, we have limt→∞mini∈[n] 〈
θt ‖θt‖ , yixi 〉 = γ‖·‖∗ . Specifically, for any given > 0,
there exists a t0 with t0 = O ( exp ( D 3/2 ‖·‖∗ D‖·‖2Lwη
γ2‖·‖∗ µ 1/2 w µ 3/2 2
3/2 log ( 1 ))) , such that for t ≥ t0 number of
iterations, we have 〈 θt ‖θt‖ , yixi 〉 ≥ (1− )γ‖·‖∗ , ∀i ∈ [n]. Finally, we have direction convergence that limt→∞ θt‖θt‖ = u‖·‖∗ .
Note that Corollary 4.1 recovers the directional convergence of steepest descent in Gunasekar et al. (2018) w.r.t ‖·‖A, which coincides with MD with distance generating function w(·) = 〈·, A·〉. Theorem 4.1 guarantees the near optimal ‖·‖∗-norm margin when the distance generating function w(·) is well-conditioned w.r.t. ‖·‖-norm. For cases when w(·) is ill-conditioned, we demonstrate that there exists a class of problem for which the margin lower bound is tight. Proposition 4.1. There exists a sequence of problems {P(m)}m≥1 by the same construction as in Proposition 3.1, such that the margin lower bound in Theorem 4.1 is tight up to a non-trivial factor of 2. 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 an exponential number of iterations (4.1) as constant stepsize MD, such a stepsize scheme only needs a polynomial number of iterations, and achieves an almost exponential speedup for the empirical loss {LS(θt)}t≥0. Theorem 4.2 (Varying Stepsize MD). Let the stepsizes {ηt}t≥0 be given by ηt = αtLS(θt) , where αt = min{ µ22D‖·‖2 , 1√ t+1 }. Then under the same conditions as in Theorem 4.1,
(1) We have limt→∞mini∈[n] 〈
θt ‖θt‖ , yixi
〉 ≥ √
µw Lw γ‖·‖∗ . In addition, for any > 0, there exists a t0 satisfying t0 = O ((
D‖·‖2Lw γ‖·‖∗µ2 √ µw )4) , such that for any t ≥ t0, we have〈
θt ‖θt‖ , yixi
〉 ≥ (1− ) √ µw Lw γ‖·‖∗ , ∀i ∈ [n].
(2) We have limt→∞ LS(θt) = 0. In addition, the convergence rate is given by LS(θt) = O ( exp ( − γ2‖·‖∗ Lw √ t )) .

heading: 5 EXPERIMENTS
text: Synthetic Data. We take S = {((−0.5, 1),+1) , ((−0.5,−1),−1) , ((−0.75,−1),−1) , ((2, 1),+1)}. One can readily verify that the maximum ‖·‖2-norm margin classifier is u‖·‖2 = (0, 1). For both BPPA and MD, we take the Bregman divergence as Dw(x, y) = ‖x− y‖22, which corresponds to the vanilla proximal point algorithm and gradient descent algorithm. Note that both algorithms are guaranteed to converge in direction towards u‖·‖2 = (0, 1), following Corollary 3.1 and 4.1.
We take ηt = η = 1 for the constant stepsize BPPA/MD, and ηt = 1L(θt) √ t+1
for the varying stepsize BPPA/MD, following the stepsize choices in Theorem 3.1, 3.2, 4.1 and 4.2. To implement the proximal step in BPPA at the t-th iteration, we take 128 number of gradient descent steps with stepsize 0.2ηt, following our discussion at the end of Section 3. We initialize all algorithms at the origin and run 1200 iterations. From Figure 1, we can clearly observe that both BPPA and MD converge in direction to the maximum ‖·‖2-norm margin classifier u‖·‖2 , which is consistent with our theoretical findings. In addition, by adopting the varying stepsize scheme proposed in Theorem 3.2 and 4.2, both BPPA and MD converge exponentially faster than their constant stepsize counterparts.
Data-dependent Bregman Divergence. We illustrate through an example on how properly chosen data-dependent divergence can lead to much improved separation compared to data-independent divergence, even on simple linear models.
We have n labeled data {(xi, yi)}mi=1 sampled from a mixture of sphere distribution: yi ∼ Bernoulli(1/2), xi ∼ Unif (Syiµ(r)), where Sz(r) denotes the sphere centered at z with radius r in Rd. In addition, we also have m unlabeled data {x̃j}mj=1, following the same distribution as {xi}ni=1, with no labels given. Clearly, the maximum ‖·‖2-margin classifier for the mixture of sphere distribution considered here is given by the linear classifier f∗(·) = sign(〈·, µ〉).
Divergence Alignment D(1)(·, ·) 0.8703 D(2)(·, ·) 0.8175 D(3)(·, ·) 0.9754
Table 1:
〈 θT ‖θT ‖2 , µ 〉
av-
eraged over 8 runs.
We choose n = d = 2,m = 100, r = 0.8, and generate µ ∼ Unif (S0(1)). We compare three types of Bregman divergence, given by D(1)(θ, θ′) = ‖θ − θ′‖22 (vanilla proximal point), D(2)(θ, θ′) = (θ − θ′)>Σ̂(θ − θ′), and D(3)(θ, θ′) = (θ − θ′)>Σ̂−1(θ − θ′), where Σ̂ = 1m ∑m j=1 xjx > j denotes the empirical covariance matrix. Note that D(2) and D(3) 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 1. We make two important remarks on the empirical results:
• Data-dependent divergence D(3) gives the best separation despite limited labeled data (in fact only 2!), much improved over data-independent squared `2-distance D(1). • Not all data-dependent divergence helps, D(2) shows degradation compared to D(1). We further remark that by utilizing Corollary 3.1, one can completely characterize the solution obtained by BPPA for each of the divergence in closed form. Using such a characterization allows one to corroborate the empirical phenomenon with our developed theories, deferred in Appendix A.
CIFAR-100. We demonstrate the potential of extending our theoretical findings for linear models to practical networks, using ResNet-18 (He et al., 2016), ShuffleNetV2 (Ma et al., 2018), MobileNetV2 (Sandler et al., 2018), with CIFAR-100 dataset (Krizhevsky et al., 2009). At each iteration of BPPA, the updated model parameter θt+1 is given by solving the proximal step θt+1 = argminθ 1/n ∑n i=1 `(fθ(xi); yi) + 1/(2ηt)D(θ; θt) for all t ≥ 0, where D denotes divergence function, and θ0 is obtained by standard training with SGD. We consider inexact implementation of the proximal step, discussed in (3.5). Specifically, each proximal step is solved by using SGD, with a batch size of 128, an 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 DLS(θ′, θ) = 1/(2n) ∑n i=1 ‖fθ(xi)− fθ′(xi)‖ 2 2 (Tarvainen and Valpola, 2017),
and DKL(θ, θ′) = 1/(2n) ∑n i=1 KL (fθ′(xi)‖fθ(xi)) (Furlanello et al., 2018). For each of the divergence, we run BPPA with 3 proximal steps, with the proximal stepsize ηt = η = 0.025 for DKL, and ηt = η = 0.2 for DLS (ηt = 0.025 gives significantly worse performance). For standard training with SGD, we use a batch size of 128, an initial learning rate of 0.1 further divided by 5 at the 60th, 120th, and 160th epoch. The results are reported in Figure 3.
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 negligible 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.83% (standard training) to 78.56% after 3 proximal steps – an additional 1.4% improvement over Tf-KDself (see Table 2), which can be viewed as BPPA with 1 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-KDself ) , which is equivalent to BPPA with 1 proximal steps, using DKL(θ, θ′) as the divergence function. Tf-KDself was shown to improve over SGD for various network architectures on CIFAR-100 and Tiny-ImageNet. We include the reported results on CIFAR-100 therein in Table 2 for completeness.

heading: 6 CONCLUSION AND FUTURE DIRECTION
text: To conclude, we have shown that for binary classification task with linearly separable data, the Bregman proximal point algorithm and mirror descent attain a ‖·‖∗-norm margin that is closely related to the condition number of the distance generating function w.r.t. ‖·‖-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 to nonlinear neural networks requires more delicate definitions of margin and divergence. We leave this direction as our long-term investigation plan.

Review summaries:
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.

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  a) 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.  b) 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.  c) It shows that that above results also extend to the dual first order algorithms such as mirror descent.

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.