Bias of Homotopic Gradient Descent for the Hinge Loss
Denali Molitor Deanna Needell Rachel Ward
stat.ML cs.LG






1]Denali Molitor
1]Deanna Needell
2]Rachel Ward
[1]Department of Mathematics, University of California at Los Angeles, Los Angeles, California, USA
[2]Department of Mathematics, University of Texas at Austin, Austin, Texas, USA


Bias of Homotopic Gradient Descent for the Hinge Loss
    [
    Received: date / Accepted: date
=====================================================



0.3in

Gradient descent is a simple and widely used optimization method for machine learning. For homogeneous linear classifiers applied to separable data, gradient descent has been shown to converge to the maximal margin (or equivalently, the minimal norm) solution for various smooth loss functions.  The previous theory does not, however, apply to non-smooth functions such as the hinge loss which is widely used in practice. Here, we study the convergence of a homotopic variant of gradient descent applied to the hinge loss and provide explicit convergence rates to the max-margin solution for linearly separable data. 





§ INTRODUCTION


Several recent works suggest that the optimization methods used in training models affect the models ability to generalize through implicit biases to certain solutions <cit.>. 
 In order to understand the effects of optimization methods in more complex and often non-convex settings such as for neural networks, it is natural to first understand their behavior in simpler settings, such as for least squares regression, logistic regression, and support vector machines (SVM) <cit.>. In particular, gradient descent and its many variants, including the subgradient method, are popular choices for optimizing machine learning models and thus warrant careful study. 

It was recently shown that gradient descent applied to the (unregularized) logistic regression problem for linearly separable data converges to the solution with maximal margin, while other choices of optimization method converge to different solutions <cit.>. Convergence to the maximal-margin solution is desirable, as the margin is an important quantity for deriving generalization guarantees <cit.>. The analysis of Soudry et al <cit.> extends to additional loss functions, but requires particular properties, including  smoothness and monotonicity. These assumptions do not hold, however, for non-differentiable functions such as the hinge loss objective, which is the loss function used in training SVM <cit.>. 

Here, we analyze the convergence to the maximal margin solution of a homotopic subgradient method applied to the non-smooth hinge loss. In particular we consider a method in which a number of subgradient updates are applied to the hinge loss with decreasing regularization. Although it is well known that the exact solutions of the regularized hinge loss converge to the hard-margin SVM solution as the regularization decreases to zero in the linearly separable case <cit.>, we are unaware of results that provide explicit convergence rates for an iterative optimization algorithm, such as the subgradient method, that converges to the hard-margin SVM solution in a single pass of the regularization parameter λ. We provide such an analysis here, and demonstrate that the iterates of an averaged subgradient method applied to the regularized SVM loss with shrinking regularization parameters converge to the max-margin solution at a rate of O(k^-1/6+δ) for linearly separable data, where δ is any small positive constant. 

For linearly separable data there exists λ' >0 be such that the solution  to the hinge loss with regularization parameter λ is equal to the true,  hard-margin solution ^* for all λ≤λ' <cit.>. While λ is constant for a fixed problem, knowing its value in advance is typically unrealistic. Additionally, if the data is not well separated, λ can be very small. The homotopic subgradient method analyzed here depends on the value of λ and converges at a rate of O((λ)^-2 k^-1/6+δ).
If one were to know the appropriate regularization parameter λ in advance, the averaged subgradient method with appropriate fixed step sizes would converge in L_2 error at a rate of O((λ')^-1k^-1/4). This rate can be improved to O((λ')^-1k^-1/2) by using weighted step sizes that depend on λ <cit.>. Thus, we pay a small price for the shrinking regularization routine and for not knowing the value of λ in advance. We additionally provide faster convergence guarantees and improved convergence results for the proposed method on small datasets as compared to gradient descent applied to the logistic loss with fixed step sizes <cit.>.




 §.§ Contributions
 
While several works analyze the convergence of various optimization methods to the maximal-margin solution for separable data <cit.>, we are unaware of any works that provide explicit convergence rates for the fundamental subgradient descent method. Convergence of the subgradient method and stochastic subgradient method have been analyzed for non-smooth convex functions, however these works only provide convergence guarantees in the loss-function values and not the iterates, as, for general convex functions, the minimizer may not be finite and may not be unique <cit.>. In the context of solving the hard-margin SVM, the restriction to linearly separable data guarantees the existence of a minimizer and considering the maximal margin solution ensures uniqueness. Moreover, in the context of general convex functions, previous works often use the projected subgradient method and require knowledge of a bounded domain in which a minimizer exists <cit.>. For solving the hard-margin SVM via gradient descent, we show that such a projection is unnecessary.

Here, we provide explicit convergence guarantees for a homotopic subgradient method for optimizing the non-smooth SVM hinge loss. The proposed method uses decreasing regularization parameters and leads to the hard-margin SVM solution. We study the effects of optimization via this method on the generalization ability of the learned solutions through proved convergence rates to the hard-margin SVM solution in terms of L_2 error as well as difference in angle and margin from the true solution. We additionally show that these convergence rates to the hard-margin SVM solution outpace recent results such as gradient descent with fixed step sizes applied to the logistic loss <cit.>. We demonstrate the convergence of the proposed method on a synthetic dataset.




 §.§ Organization

In <Ref>, we introduce the specific problem setting, the notation that will be used throughout, and the proposed optimization scheme, <Ref>. <Ref> provides the main convergence results for <Ref>. An outline for the proof of the main convergence theorem, <Ref>, is provided in <Ref>, with additional details in <Ref>.  We test convergence properties of <Ref> for a simple synthetic dataset in <Ref>. <Ref> provides additional implementation details for <Ref> as well as possible modifications and extensions.



§ PROBLEM SETUP




We consider the binary classification problem with data {(_j, y_j) : j=1,…,n}, where _j∈^d are the data points and y_j∈{-1, 1} their labels. We aim to classify the data via a homogeneous linear SVM. Specifically, we wish to identify a weight vector ^* that satisfies 

    ^* = _   subject to    y_j _j^⊤≥ 1  ∀  j.

Throughout, we write ·=·_2. 
We can equivalently find

    ^* = _ subject to ℒ() = 0,

where 

    ℒ() :=1/n∑_j=1^n h(y_j_j^⊤)   and   h(u) := max(0, 1-u).

The function h(u) is commonly referred to as the hinge loss. We assume throughout that the data is linearly separable, i.e. there exists a vector  satisfying ℒ() = 0 as is done in <cit.>. This assumption is common and necessary in order to discuss the margin of the approximated solutions. Minimizing the norm of the solution  to ℒ()=0 corresponds to maximizing the margin, that is maximizing the minimal distance between any data point and the separating hyperplane determined by . In this setting, the solution to <Ref>, ^*, is often referred to as the hard-margin SVM solution.

The constrained optimization problem in <Ref> is the primal formulation of an SVM. While solving or approximating the corresponding dual SVM formulation is popular in practice, there are advantages to approximating the primal problem directly <cit.>. Of particular interest for this work, considering the primal formulation allows for straightforward analysis of the effect of the optimization error on the margin and hyperplane angle.

As an alternative to solving <Ref> directly, one often looks for a solution to an unconstrained, regularized version. Define the functional:

    F_λ() := λ/2^2 + 1/n∑_j=1^n h(y_j_j^⊤) .
 
For λ > 0,  is strongly convex with strong convexity parameter λ. We will use ∂ F to denote the subgradient of F. The gradient of F_λ() exists as long as y_j_j^⊤≠ 1 for all j and is given by

    ∂ F_λ() = λ - 1/n∑_j: y_j _j^⊤ < 1 y_j _j.

When y_j_j^⊤ = 1 for some j, the subgradient set ∂ F_λ() contains the point 

    λ - 1/n∑_j: y_j _j^⊤ < 1 y_j _j ∈∂ F_λ() .

When the gradient does not exist, we will abuse notation and use <Ref> in the subgradient method update of <Ref>. 

Let 

    := _().

We will refer to  as the solution to the regularized subproblem of minimizing <Ref>. A larger regularization parameter λ encourages a solution  with smaller norm at the cost of having some points lie within the margin. For linearly separable data and as λ approaches 0, the regularized solutions  converge to the unregularized solution, ^*. Let λ' >0 be such that = ^* for all λ≤λ'. Such a λ' is guaranteed to exist for linearly separable data <cit.>. This fact suggests solving <Ref> by using the subgradient method for a sufficiently small value of λ. Of course, the value of λ' will typically be unknown. 

We use the following assumption and definition of λ throughout.

The data _1, …, _n∈ℝ^d with labels y_1,…, y_n∈{-1,1} are linearly separable, i.e. there exists  such that for all i, y_i ^⊤_i >0. Let ^* be the hard-margin SVM (i.e. ^* solves <Ref>) and λ' be such that for all λ≤λ', =
 = ^*.



While in practice, one may be satisfied with the solution  for λ sufficiently small, we are interested in the convergence to the true hard-margin SVM given by ^*. Thus, we instead propose to use a “homotopic" variant of the subgradient method that iteratively approximates the solution to  <Ref> while the regularization parameter λ and accompanying step size η of the subgradient method in <Ref> decay at prescribed rates. Incorporating a piecewise constant decaying step size is commonly used for large-scale minimization problems, especially when using stochastic gradient descent variants <cit.>.

Recall the subgradient method given by the updates:

    _k+1 = _k - η_k∂(_k),

where _k is the approximate solution at iteration k and η_k is a step size. 
For some number of outer iterations s = 1, …, S, we choose a regularization parameter λ_s > 0, a step size η_s > 0 and a number of inner iterations t_s. The regularization parameter λ_s and step size η_s are selected such that they decrease to 0 as s increases. Let _s-1 be the current estimate of ^*. We then perform t_s subgradient updates applied to the loss function  with initial iterate _s-1 and step size η_s. The next estimate, , is given by the average of the t_s subgradient iterates. This process is detailed in <Ref>. For specific choices of λ_s, η_s and t_s, <Ref> converges to the hard-margin SVM solution ^*. Convergence guarantees are detailed in <Ref>. 




While the strongly convex functions  are not globally Lipschitz, they are Lipschitz functions on bounded domains. Using a projected subgradient method in which iterates are projected onto a bounded domain is a natural strategy for restricting the domain of the iterates. A projection is unnecessary in this setting, however, as the regularization parameter λ > 0 naturally promotes solutions of smaller norm. 
In fact, the iterates produced by the subgradient method in <Ref> remain bounded in norm with a bound that depends on the current regularization parameter λ. 


Fix a regularization parameter λ > 0 and step size η > 0 such that ηλ < 1. Define 

    B_λ := ∑_j=1^n_j /λ n.

If the initial iterate _0 is such that _0≤ B_λ, then each iterate _k produced by the subgradient method of <Ref> applied to the function  of <Ref> has _k≤ B_λ. Additionally, ^*≤ B_λ.

 In summary, if the initial iterate _0 is such that _0≤ B_λ, then the iterates produced by the subgradient method applied to  will also have norm less than or equal to B_λ. 



Using <Ref>, one can show that the functionals  are Lipschitz over the domain of iterates produced by <Ref>. Specifically, the constant 

    L :=  2/n∑_j=1^n_j

bounds the Lipschitz constants of each function  restricted to the ball centered at the origin with radius B_λ. <Ref> guarantees that the iterates produced when applying the subgradient method to  and for sufficiently small initial iterate remain with this domain. Note that the bound on the Lipschitz constants L is independent of the regularization parameter λ.






§ MAIN RESULTS



We now provide explicit rates of convergence to the hard-margin SVM solution for <Ref>. We provide convergence rates in terms of the L_2 error, difference in angle, and difference in margin between the approximation _S and the true hard-margin solution. 
The convergence results are stated in terms of k, the total number of subgradient updates required. Recall that the approximations  are only updated at increments of t_s subgradient updates. Let _k =, so that _k is the approximation after k = ∑_i=1^s t_i subgradient calculations.

<Ref> provides a convergence guarantee for the L_2 error of the iterates produced by <Ref>. This result will be used to additionally derive convergence guarantees for the angle and margin of the solution in <Ref>. The parameter p determines the rate of decay of the regularization λ_s and the parameter r determines the number of steps t_s used at each fixed level of regularization. The constant L is as defined in <Ref> and is an upper bound on the Lipschitz constants of the functions  restricted to the domain of the iterates produced by the subgradient method applied to  (<Ref>).
 

 
Consider <Ref> with parameters r and p such that 0<p<1 and r>2p. Choose an initial number of inner iterations s_0^r ∈ℕ with s_0>2. 
Let L = 2∑_j=1^n _j/n as defined in <Ref>. 
Define

    C = max{4, 12 s_0^p(s_0-1)^α}  and  α = min(r-2p/2(1+ϵ_0), 1 - p  ) ,

with 
ϵ_0 = log(s_0 ) - log(s_0 -1)/log(s_0).
Let _k be the average of the t_s subgradient descent updates calculated to minimize the function  with step size η_s = C(s_0+s-1)^-α/√(t_s), where k is the total number of subgradient descent updates calculated. 
Then for data and λ satisfying <Ref>, 

    _k - ^*≤ CL ((r+1)k)^-α(1-ϵ_0)/r+1 
    +  L  /2(λ)^2((r+1)k)^-p/r+1.

Let c = min(α(1-ϵ_0)/r+1, p/r+1). Then 

    _k - ^*   ≤(C + 1  /2(λ)^2) L (r+1)^-ck^-c.



An outline for a proof of <Ref> can be found in <Ref> with additional details in <Ref>. Note that, for small ϵ_0, the two terms in the bound of <Ref> will decrease at approximately the same rate if r=2 and p=1/2. 
<Ref> gives a simpler, explicit rate of convergence by making this specification and setting s_0 = 10.
 

Consider <Ref> with parameters r=2, p=1/2 and an initial number of inner iterations s_0^r = s_0^2 ∈ℕ with s_0>2. 
Let L = 2 ∑_j=1^n _j/n.
Define

    C = max{4, 12 s_0^p(s_0-1)^α}  and  α = min(r-2p/2(1+ϵ_0), 1 - p  ) ,

with 
ϵ_0 = log(s_0 ) - log(s_0 -1)/log(s_0).
Let _k be the average of the t_s subgradient descent updates calculated for  with step size η_s = C(s_0+s-1)^-α/√(t_s), where k is the total number of subgradient descent updates calculated. 
Then for data and λ satisfying <Ref>, 

    _k - ^*   ≤ CL (3k)^-1/6(1-ϵ_0)/(1+ϵ_0) 
    +  L (3k)^-1/6/2(λ)^2.


Choosing s_0=10, we have ϵ_0 < 0.046, C < 4.9 and arrive at the convergence rate

    _k - ^*≤   4.17 L k^-0.913/6 
    +  0.42L k^-1/6/(λ)^2.

At least theoretically, sending s_0→∞ leads to the best convergence rate guarantee. In fact, the convergence rate provided by <Ref> can be made arbitrarily close to O(k^-1/6) by choosing r=2, p=1/2, and s_0 sufficiently large. As we will see in <Ref>, using s_0 extremely large becomes impractical as the number of iterations for each fixed-λ subproblem becomes extremely large. 

For strongly-convex, Lipschitz functions with strong-convexity parameter λ, one can achieve convergence in -^* at a rate of O(λ^-1 k^-1/4), using projected averaged gradient descent with fixed step sizes (Theorem 3.2 <cit.>). Using weighted step sizes, and knowledge of the strong convexity parameter, this rate can be improved to O(λ^-1 k^-1/2) (Theorem 3.9 <cit.>, originally from <cit.>). A challenge of solving for the hard-margin SVM is that we do not optimize a strongly convex function. While one could fix a regularization parameter λ leading to a strongly convex function, there is no guarantee that the minimizer of this function  will correspond to the true solution ^*. Since the convergence rate of <Ref> can be made arbitrarily close to O( (λ')^-2k^-1/6) we lose very little, only a factor of O( (λ')^-1k^1/12+δ) compared to the convergence rate of projected averaged gradient descent with fixed step sizes, for not knowing λ' in advance and instead incorporating decreasing explicit regularization. 

Additionally, in designing <Ref>, we aimed for a simple algorithm as opposed to optimizing all possible parameters. One could possibly improve on the rates given here by further optimizing these parameters.




 §.§ Convergence rates for angle and margin gaps


The convergence rate in <Ref> can be used to derive rates of convergence to the angle and margin of the optimal separating hyperplane ^*.  

For the hard margin SVM solution ^* and a vector , define 

    angle gap :=  1 - ^⊤^*/^*

and 

    margin gap := 1/^* - min_i y_i_i^⊤/.



While it is natural to consider the L_2 error of the derived solution, the angle between the true and derived solutions as well as the difference in the size of the margins give a more intuitive interpretation of the effect of that error. For example, an approximate solution  that is off by a constant factor, that is = c^*, will have an angle gap of zero and non-zero margin gap if c 1. If an approximate solution  has a nonzero angle gap, but negligible margin gap, this suggests that the derived solution  still separates the data reasonably well. 

Convergence rates of <Ref> in terms of the angle and margin gaps are stated in <Ref> and compared to other recently obtained convergence rates in <Ref>. The rates of convergence in these metrics can be derived from <Ref>. These arguments are included in <Ref>.



Let 

    c =  min((r-2p)(1-ϵ_0)/2(r+1)(1+ϵ_0), (1 - p)(1+ϵ_0)/r+1 , p/r+1),

where p, r, s_0, and ϵ_0 are as given in <Ref>
 so that c is the exponent in the convergence rate of <Ref>. Let δ be such that c = 1/6 - δ. The value of δ is positive and can be made arbitrarily close to 0 by choosing s_0 sufficiently large and setting p=1/2 and r = 2. Then for the angle gap,

    1 - _k^⊤^*/_k^* = O(k^-1/3 +2δ).

For the margin gap,

    1/^*  - min_i y_i _i^⊤_k/_k  = O(k^-1/6+δ).
 


The convergence guarantees for the angle and margin gaps for <Ref> are significantly faster than 
those given in Soudry et al <cit.> for gradient descent with fixed step sizes applied to the logistic loss (see <Ref>). 
Nacson et al <cit.> demonstrate that using aggressive adaptive step sizes for gradient descent applied to the logistic loss  leads to 
a faster convergence rate of O(log(t)/√(t)). While the convergence guarantees for <Ref> are slower, as c≤ 1/6, in this paper, we are interested in analyzing convergence guarantees for gradient descent applied to the non-smooth hinge loss.











§ PROOF OF <REF>



We prove <Ref> through a series of lemmas, which are stated in <Ref> and whose proofs are contained in <Ref>. The proof of <Ref> is contained in <Ref>.

We briefly summarize each of the lemmas for convenience. 
<Ref> provides a modified convergence guarantee for the averaged subgradient method applied to the functions . <Ref> bounds the distance between minimizers of  for different regularization parameters λ. This result allows for the incorporation of the decreasing regularization in <Ref>. <Ref> makes use of <Ref> and <Ref> to bound the initial error - of each regularized subproblem as given in <Ref>.




 §.§ Useful lemmas


<Ref> is a modified version of a standard convergence analysis of the averaged subgradient method for convex Lipschitz functions (Theorem 3.2 of <cit.>). This result bounds the distance between the average of the subgradient descent iterates  and the minimizer  of the functional  for a fixed regularization parameter λ. 



Let 

    () = λ/2^2 + 1/n∑_j=1^n max(0,1-y_j_j^⊤)
 
and L = 2 ∑_j=1^n _j/n.
 Let the initial iterate _0 be such that _0≤L/2λ and let  minimize . Suppose _0 - ≤ R, so that  is contained in a ball of radius R and center _0. Let = 1/t∑_s=1^t _s be the average of t subgradient method iterates with initial iterate _0 and step size η = R/L√(t). Then 

    0≤ F_λ () - F_λ (_λ^*) ≤RL /√(t) - λ/2 - ^2.



Note that <Ref> also guarantees that 

    - ^2 ≤2RL /λ√(t) .


The next lemma bounds the distance between the minimizers  and _λ^* of the functions  and F_λ and shows that distance from  to the true hard-margin solution ^*, - ^*, is proportional to the regularization parameter λ.


Let  minimize  as given in <Ref> and let ^* solve <Ref>. Let λ' >0 be such that = ^* for all λ≤λ' and L = 2 ∑_j=1^n _j/n. For λ,λ≥ 0 and data satisfying <Ref>, we have 

    - _λ^*≤L/2|1/λ - 1/λ̃|

and 

    - ^*≤L λ/2(λ')^2  .



The final lemma bounds the initial error at each fixed level of regularization for the subgradient updates produced when minimizing . In particular, it specifies a bound shrinking in s on the distance between the initial iterate  and the minimizer  of the function . The fact that the initial error for each regularized subproblem goes to zero is crucial for proving the convergence of <Ref> to the hard margin SVM solution.



 Let L = 2∑_j=1^n _j/n and R_0 = L/2λ_0. For s_0 ∈ℕ with s_0>2, p∈ (0,1), and r >2p, let λ_s = (s_0+s)^-p and t_s = (s_0+s)^r. Let 

    R_s = CL(s_0+s-1)^-α      0≤α≤min(r-2p/2(1+ϵ_0), 1 - p  ),

with 

    C = max{4, 1/2λ_0 (s_0-1)^α} and ϵ_0 = log(s_0 ) - log(s_0 -1)/log(s_0).
 
Let η_s = R_s/L√(t_s). 
Then for the averaged subgradient iterates  of <Ref>,

    - ≤ R_s .



Based on <Ref>, for r>2p and p<1 the radii R_s shrink to 0 as s increases.



 §.§ Proof of <Ref>.

We now prove <Ref> using the above lemmas.

We use the triangle inequality to bound the error as

    - ^*≤ -  +  - ^* .

We then bound the terms - and - ^* using the lemmas of <Ref>.

Let L = 2 ∑_j=1^n _j/n and choose s_0∈ℕ with s_0>2. Let λ_s = (s_0+s)^-p and t_s = (s_0+s)^r. Let 

    R_s = CL(s_0+s-1)^-α ,
     for α = min(r-2p/2(1+ϵ_0), 1 - p  ) ,

with 

    C = max{4, 12s_0^p(s_0-1)^α} and ϵ_0 = log(s_0 ) - log(s_0 -1)/log(s_0).
 
Let η_s = R_s/L√(t_s). By <Ref>, considering the first term in the bound of <Ref>,

    - ≤ R_s = CL(s_0+s-1)^-α.

Changing the base,

    - ≤ CL(s_0+s)^-α(1-ϵ_0).

We now bound the second term of the bound in <Ref>. 
Let λ' >0 be such that = ^* for all λ≤λ'. By <Ref>,

    - ^*≤L λ_s/2(λ)^2 = L (s_0+s)^-p/2(λ)^2 .


The total number of updates, k, used to calculate  is bounded by 

    k = ∑_i=0^s-1 t_i = ∑_i=s_0^s_0+s-1 i^r ≤∫_s_0+1^s+s_0 i^r = (s+s_0)^r+1/r+1 .

Rearranging,

    ((r+1)k)^1/r+1≤ s_0 + s.

Writing the bounds in terms of the total number of updates, k,

    - ≤ CL(s_0+s)^-α(1-ϵ_0)≤ CL ((r+1)k)^-α(1-ϵ_0)/r+1

and 

    - ^*≤L ((r+1)k)^-p/r+1/2(λ)^2 .

Combining these,

    - ^*≤ -  +  - ^*
       ≤ CL ((r+1)k)^-α(1-ϵ)/r+1 
    +  L ((r+1)k)^-p/r+1/2(λ)^2.




In order to optimize the convergence rate given in <Ref>, we aim to choose parameters p and r such that 

    p,q = _p,qmin{(r-2p)(1-ϵ_0)/2(1+ϵ_0), (1 - p)(1-ϵ_0), p }.

For ϵ_0 small, p=1/2 and r=2 lead to a nearly optimal converge rate of 

    - ^*   ≤ 4L ((r+1)k)^-(1-ϵ)/6(1+ϵ) 
    +  L ((r+1)k)^-1/6/2(λ)^2.

The choices p=12 and r=2 are considered in <Ref> and an explicit convergence rate is given under these conditions. 




§ EXPERIMENTAL RESULTS


We demonstrate the convergence of <Ref> through several experiments on a simple synthetic dataset that is shown in <Ref>. The experiments aim to explore the differences between convergence in theory versus practice and are not intended to be exhaustive or demonstrate superior performance over existing methods. 
The data includes four support vectors which occur at ± (0.5,1.5) and ± (1.5,0.5). The hard-margin SVM solution is given by ^* = (0.5,0.5). The maximal regularization parameter λ such that = ^* for all λ≤λ' is λ' = 0.5. We fix the parameters p=1/2 and r=2 as are considered in <Ref> and initialize _0 = 0. 


We measure convergence in terms of the L_2 error as well as the angle and margin gaps of <Ref>. 
Convergence results for <Ref> with p = 1/2, r=2 and varying s_0 are shown in <Ref>.  
In terms of the L_2 error, for a fixed number of iterations, there appears to be an optimal choice for the parameter s_0, as choosing s_0= 10 performs better than s_0=3,5 or 20. 







We additionally compare the convergence of <Ref> in terms of the angle gap and margin gap to gradient descent using fixed step sizes applied to the logistic loss. We use step sizes η = 1/σ_max(), where σ_max() is the largest singular value of the data matrix . As can be seen in <Ref>, we find significantly faster convergence via <Ref> as compared to minimization of the logistic loss via gradient descent with fixed step sizes as considered in <cit.>. This result is unsurprising, as <Ref> arrives at the SVM solution via controlled explicit regularization as opposed to only implicit regularization via gradient descent.



We additionally consider the performance of <Ref> applied to the data of <Ref> with the y-values of the data multiplied by 20. This leads to a slightly more challenging problem with less symmetric data. The results are shown in <Ref>. We find that the convergence of <Ref> is slightly slower in terms of L_2 error. The logistic loss converges significantly slower in terms of both the angle and margin gaps, whereas the effect on the convergence of <Ref> appears to be minimal.









§ IMPLEMENTATION REMARKS

As presented, <Ref> is highly adaptable for different loss functions and settings in which one would like to consider a range of regularization parameters or variable regularization. In this section, we present several potential modifications of interest, including adaptive or gradient based step sizes, amenability to using stochastic subgradients, and alternative updates.




 §.§ Adaptive step sizes
 
When the regularization parameter, λ, or the norm of  are small and close to optimal, if an iterate violates one of the hinge loss constraints, this can increase the magnitude of the gradient of the loss  significantly, leading to a relatively large jump in the next iterate followed by many smaller steps back toward the optimal solution of smaller norm. 
Using gradient descent with adaptive or loss-dependent step sizes can minimize the effects of these cycles. For example, we could adjust <Ref> to use step sizes that are normalized by the magnitude of the subgradient,

    _k+1 = _k - η_k∇(_k)/∇(_k).

With this choice, the magnitude of the update is always η_k and is independent of the magnitude of the gradient of . 
Cursory experimental results suggest that using adaptive step sizes as in <Ref>, leads to slower convergence to the true solution initially and does not lead to improved convergence overall. 

One could also potentially increase the convergence rate guarantees for <Ref> by incorporating aggressive loss-dependent step sizes. In <cit.>, the authors show that when using <Ref> with step sizes η_k = 1/L(_k), gradient descent applied to the logistic loss converges at the nearly optimal rate of O(t^-1/2log t). While this strategy provides a faster convergence rate, loss-dependent step sizes are less commonly used in practice as, in the stochastic setting, updating the loss at each iteration is often too expensive. The stochastic setting is discussed further in <Ref>.







 §.§ Regularization decay rate

In <Ref>, we consider regularization parameters that decay at a rate of λ_s = O(s^-p) for a constant p>0. 
One might consider other choices for the decay rate of the regularization parameter λ. For example λ_s = O(1log(s)) or λ_s = O(c^s) for c∈(0,1). 
Recall that in bounding the error - ^* we use the decomposition

    - ^*≤ -  +  - ^*.

The first term converges more quickly when λ is large while the second term converges more quickly when λ is small. 
The decay rate of λ_s = O(s^-p) was chosen to balance the convergence of these terms.





 §.§ Stochastic subgradients

 <Ref> can be naturally extended to the stochastic subgradient setting, in which one performs updates based on the subgradient of the loss with respect to only a subset of the data points. This is often necessary for large-scale optimization problems. Additionally, although piecewise-constant decaying step sizes are incorporated into <Ref> to account for the introduced regularization, it is also often used in stochastic gradient descent in order to mitigate the effect of noise in the gradient approximation of each update <cit.>. This commonality suggests that <Ref> may be particularly suited for the stochastic setting.



 §.§ Alternative updates

<Ref> is the only result that depends on the update given by the fixed-λ subproblem and, in particular, <Ref> applies to any update that satisfies - ≤ R_s for each s = 1,…, S. Thus, as opposed to using the average of the iterates from each fixed λ subproblem, one could use alternative updates, such as

    _s = _i=1,…, t_s (_i),

or the iterate that leads to the minimal loss for that subproblem. We refer to this update choice as the best-iterate update and investigate the effects of this choice in <Ref>.


 We find that the best-iterate update typically leads to significantly faster convergence in terms of the L_2 error. Specifically, choosing the best iterate can alleviate the slow convergence caused by the slow decrease in step size. The convergence of the two strategies, using the averaged iterate and the best iterate, perform comparably in terms of the angle gap. Using the best iterate converges somewhat slower in terms of the margin gap.






 §.§ Incorporating a bias term

As in <cit.>, we consider the case in which the maximal-margin separating hyperplane intersects the origin. One can allow for more general hyperplanes by learning a bias term b for the separating hyperplane. We propose the following method for approximating the bias term b

    b = -(min_i:y_i=1_i^⊤ + max_i:y_i=-1_i^⊤)/2,

 which is guaranteed to be close to the true max-margin bias b^* when -^* is small. Specifically, one can verify that for the bias b as calculated in <Ref> and b^* the true bias, we have 

    |b-b^*|≤max_i _i-^*.

Initial experiments with a non-trivial bias demonstrate convergence similar to the zero-bias case.




§ CONCLUSION

We have shown that, for linearly separable data, the subgradient method converges to the max-margin SVM solution when minimizing the unconstrained regularized SVM, <Ref>, with decreasing regularization parameters, λ. Under the conditions given in <Ref>, this convergence can be guaranteed to be O(k^-1/6 + δ) for any δ >0. We compare convergence rates in several metrics to those provided in <cit.>. In particular, the convergence rate guarantees for <Ref> are faster than those of <cit.> for gradient descent with fixed step sizes. This restriction to fixed or piecewise constant step sizes is a practical choice, especial when working with large-scale optimization problems. We additionally demonstrate the convergence of <Ref> on a simple synthetic dataset.


Although we specifically consider the hinge loss and SVMs, the results and analysis presented here could be extended to more general settings. For example, one could more generally consider settings in which one aims to solve

    ^* = lim_λ→ 0^+_λ/2 g() + f(),

where g is strongly convex and Lipschitz over bounded domains, f is convex and Lipschitz, and the regularization path, 

    = λ/2 g() + f(),
 
is Lipschitz in λ.


D. Molitor and D. Needell are grateful to and were partially supported by NSF CAREER DMS #1348721 and
NSF BIGDATA DMS #1740325. R. Ward was supported in part by AFOSR MURI Award N00014-17-S-F006.

myalpha









§ LEMMA PROOFS

We now present proofs for the lemmas of <Ref>.

We first prove <Ref>, which gives a bound on the norm of the iterates produced by the subgradient method applied to <Ref>.

Proof of <Ref>
 
Consider the subgradient update for minimizing the function  of <Ref> 

    = (1-λη)  + η/n∑_j : y_j_j^⊤≤ 1 y_j_j

with ηλ < 1. Suppose that the iterate  satisfies ≤1/λ n∑_j=1^n_j. We aim to show that  given by the subgradient update also satisfies ≤1/λ n∑_j=1^n_j. Taking the norm on both sides of <Ref>,

    = (1-ηλ) + η/n∑_j : y_j_j^⊤≤ 1 y_j_j 
       ≤ (1-ηλ) + η/n∑_j : y_j_j^⊤≤ 1 y_j_j 
       ≤ (1-ηλ)1/λ n∑_j=1^n_j + η/n∑_j=1^n _j
       = 1/λ n∑_j=1^n_j -η/ n∑_j=1^n_j + η/n∑_j=1^n _j
       = 1/λ n∑_j=1^n_j .

Thus the norms of all iterates of the subgradient method applied to the function  remain bounded by 1/λ n∑_j=1^n_j if the initial iterate has norm at most 1/λ n∑_j=1^n_j. 
The norm of the minimizer  of  must also satisfy the bound
≤1/λ n∑_j _j 
as 0∈∂() and so

    λ≤1/n||∑_j : y_j_j^⊤≤ 1 y_j_j||.




Proof of <Ref>

<Ref> uses <Ref> to derive bounds for the angle and margin gaps.

To derive a convergence rate for the angle gap, we use the decomposition

    _k - ^*^2    = _k^2 + ^*^2 - 2_k^⊤^*
       =  (_k - ^*)^2 +2_k^* - 2_k^⊤^*.

Dividing by 2_k^*,

    1 -  _k^⊤^*/_k^*   = _k - ^*^2 - (_k - ^*)^2 /2_k^*
       ≤_k - ^*^2  /2_k^*
    .


Since ^* is necessarily bounded away from 0 since y_i_i^⊤^*≥ 1 for all i. We can bound _k away from 0 for t large using the convergence of _k to ^* guaranteed by <Ref>. 
Let 

    c =  min((r-2p)(1-ϵ_0)/2(r+1)(1+ϵ_0), (1 - p)(1+ϵ_0)/r+1 , p/r+1),

be the exponent in the convergence rate of -^* and p,r, and ϵ_0 be defined as in <Ref>. 
Since 

    (_k - ^*)^2 ≤_k - ^*^2 ≤ Ak^-2c

for constants A, c >0 by <Ref>, then 
_k≥^* - Ak^-c. Thus for k sufficiently large, we can bound  away from 0 and have 

    1 - _k^⊤^*/_k^* = O(k^-2c).


We now consider the margin bound.  Let j = _i=1,… ny_i _i^⊤_k/_k. Since y_i _i^⊤^*≥ 1 for all i = 1,…, n, we have that 

    0   ≤1/^*  - y_j _j^⊤_k/_k≤y_j _j^⊤^*/^*  - y_j _j^⊤_k/_k
       =y_j _j^⊤(^*/^*  - _k/_k)
    ≤_j^*/^*  - _k/_k .

Note that 

    ^*/^*  - _k/_k^2 = 2 (1 - _k^⊤^*/_k^*).

Assuming the data is finite and linearly separable, by <Ref> we then have 

    1/^*  - min_i y_i _i^⊤_k/_k  = O(k^-c).






Proof of <Ref>

 <Ref> provides a modified convergence guarantee for the averaged subgradient method applied to the functions  <cit.>.

Let  be a strongly convex function with strong convexity parameter λ
and Lipschitz constant L on the bounded domain considered. Let _0 be an initial iterate and  be the minimizer of . Suppose _0 - ≤ R, so that  is contained in a ball of radius R and center _0. Let = 1/t∑_i=1^t _i be the average of t subgradient descent iterates with initial iterate _0 and step size η = R/L√(t). We aim to show that 

    0≤ F_λ () - F_λ (_λ^*) ≤R L/√(t) - λ/2 - ^2.

The following proof relies heavily on Theorem 3.2 of <cit.> (See also <cit.>). 

Since  is the minimizer of , the inequality 

    F_λ () - F_λ (_λ^*)≥ 0
 is immediate. 
Let g() = () - λ/2||||^2. 
Since g() is convex,

    g()  ≤1/t∑_i=1^t g(_i)

and thus

    () - λ/2||||^2 ≤1/t∑_i=1^t ( (_i)  -λ/2||_i||^2).

Reorganizing and subtracting (),  

    ()-()  
       ≤1/t∑_i=1^t ( (_i) - () -λ/2(||_i||^2 -||||^2) ).

Using the strong convexity of  and the proof of Theorem 3.2 of <cit.>,

    (_i)-() 
       ≤∂(_i)^⊤ (_i - ) - λ/2_i - ^2
       = 1/2η(_i - ^*^2 - _i+1-^*^2) + η/2∂(_i)^2- λ/2_i - ^2
       ≤1/2η(_i - ^*^2 - _i+1-^*^2) + η L^2/2- λ/2_i - ^2.

Making this substitution into <Ref>,

    ()-() 
       ≤1/2 tη(_1 - ^*^2 - _t+1-^*^2) + η L^2/2
          - λ/2t∑_i=1^t(_i - ^2 + ||_i||^2-||||^2 )
       ≤R^2/2 tη + η L^2/2 - λ/2t∑_i=1^t(_i - ^2 + ||_i||^2-||||^2 )
       ≤RL/√(t) - λ/2t∑_i=1^t(||_i||^2-||||^2 + _i - ^2).

Decomposing the sum,

    1/t∑_i=1^t   _i - ^2 = 1/t∑_i=1^t ( ||_i||^2 - 2 _i^⊤ + ||||^2)
       = 1/t∑_i=1^t  (||_i||^2)   - 2 ^⊤ + ||||^2
       = 1/t∑_i=1^t (||_i||^2)  -||||^2 +||||^2  - 2 ^⊤ + ||||^2
       = 1/t∑_i=1^t ( ||_i||^2 -||||^2)  +||-||^2.

Making this substitution,

    ()-() 
       ≤RL/√(t) - λ/t∑(||_i||^2-||||^2 ) - λ/2||-||^2.

Since ||||^2 is convex, λ/t∑(||_i||^2-||||^2 ) ≥0 and 

    ()-() 
       ≤RL/√(t) - λ/2||-||^2

as desired. 



Proof of <Ref>

We now prove <Ref>, which bounds the distance between minimizers of  for different regularization parameters λ. 

Let  minimize  as given in <Ref>. Let λ' >0 be such that = ^* for all λ≤λ'. For λ,λ≥ 0 and data satisfying <Ref>, we aim to show that

    - _λ^*≤L/2|1/λ - 1/λ̃|

and 

    - _λ^*≤max_j_j/(λ')^2 |λ - λ|.


The proof of <Ref> makes use of Lemma 8 of <cit.>, which is also stated below.

(Perturbation of strongly convex functions I <cit.>). Let f() be a non-negative,
α^2-strongly convex function. Let g() be a L-Lipschitz non-negative convex function. For
any β≥0, let [β] be the minimizer of f() + β g(), then we have,

    d[β]/dβ≤L/α^2.


Let f()= ^2 and g()=1/n∑_j=1^n max{0, 1 - y_j _j^⊤}. Then f is strongly convex with strong convexity parameter 2 and g is Lipschitz with a Lipschitz constant bounded by 1n∑_j=1^n_j. 
Note that 

    F_λ()    = λ/2 f() +  g() = λ/2[ f() + 2/λg() ]
       = λ/2[ f() + β(λ)g() ]

for β(λ) = 2/λ.
Applying Lemma 8 of <cit.>,

    d[λ]/dλ   
    = d[λ]/dβ(λ)·dβ(λ)/dλ
       ≤1/2n∑_j=1^n_j· |β'(λ)| 
    = 1n∑_j=1^n_j/λ^2.


Integrating, for any λ̃≥λ̂>0, we have  

    _λ̃^* - _λ̂^*   = ∫_λ̂^λ̃d[λ]/dλ dλ
       ≤∫_λ̂^λ̃d[λ]/dλ dλ
       ≤∫_λ̂^λ̃1n∑_j_j/λ^2 dλ
       
     = 1n∑_j_j |1/λ̃ - 1/λ̂|.


As the regularization parameter λ approaches zero, we will use the following bound. Since for all λ < λ', [λ] = [λ'] = ^*, then for λ < λ', d[λ]/dλ =0. Thus

    d[λ]/dλ≤max_j_j/(λ')^2  ∀ λ> 0.

This gives the second bound,

    _λ^*- _λ̂^*≤∫_λ̂^λ̃1n∑_j_j/λ^2 dλ≤∫_λ̂^λ̃1n∑_j_j/λ^2 dλ≤max_j_j/(λ')^2 | λ-λ̂|.




Proof of <Ref>
We finally prove <Ref>, which makes use of <Ref> and <Ref> to bound the initial error - of each regularized subproblem given in <Ref>.

We aim to show - ≤ R_s with R_s defined below and proceed by induction. For s_0 ∈ℕ with s_0>2, p∈ (0,1), and r >2p, let λ_s = (s_0+s)^-p, t_s = (s_0+s)^r. Recall that L = 2n∑_j=1^n_j.
For some parameter α > 0, let

    R_s = CL(s_0+s-1)^-α with C = max{4, 1/2λ_0 (s_0-1)^α}.

 By <Ref>, and since _0 = 0, we have 
_0 - _λ_0^*≤L/2λ_0. Note that R_0 ≥L/2λ_0 and thus the base case, 
_0 - _λ_0^*≤ R_0
 is satisfied.

Suppose that - ≤ R_s.  By the triangle inequality,

    - ≤ - _λ_s-1^* +_λ_s-1^*- .

For  generated as in <Ref>, <Ref> along with the inductive assumption gives that 

    - _λ_s-1^*≤(2 R_s-1 L/λ_s-1√(t_s-1))^1/2 
    =√(2C) L (s_0+s-2)^-α/2/(s_0+s-1)^r/4-p/2.

From <Ref> of <Ref>,

    _λ_s-1^*-   ≤L2(1λ_s-1λ_s-1)
       =L2((s_0+s)^p - (s_0+s-1)^p )
       ≤Lp2(s_0+s-1)^p-1.

Combining these

    -    ≤√(2C)  L (s_0+s-2)^-α/2/(s_0+s-1)^r/4-p/2  + L/2p(s_0+s-1)^p-1.


Applying a change of base via ϵ≥log(s_0 + s -1 ) - log(s_0 + s-2)/log(s_0+s - 1),

    -    ≤√(2C) L(s_0+s-1)^p/2-α/2(1-ϵ)-r/4 + Lp/2(s_0+s-1)^p-1.

To simplify the analysis and remove the dependence of ϵ on the iteration number s, we use ϵ_0 = log(s_0 ) - log(s_0 -1)/log(s_0).
Now, for 

    0≤α≤min(r-2p/2(1+ϵ_0), 1 - p  )

and p<1, we have 

    - ≤ L(√(2C) +p/2)(s_0+s-1)^-α≤ CL(s_0+s-1)^-α 
    = R_s.
 
Note that allowing the first term in the upper bound on α to increase with s leads to smaller bounds R_s. This choice, however, complicates the analysis. 





