Proximal gradient method for huberized support vector machine

Abstract

The support vector machine (SVM) has been used in a wide variety of classification problems. The original SVM uses the hinge loss function, which is non-differentiable and makes the problem difficult to solve in particular for regularized SVMs, such as with $\ell _1$-regularization. This paper considers the Huberized SVM (HSVM), which uses a differentiable approximation of the hinge loss function. We first explore the use of the proximal gradient (PG) method to solving binary-class HSVM (B-HSVM) and then generalize it to multi-class HSVM (M-HSVM). Under strong convexity assumptions, we show that our algorithm converges linearly. In addition, we give a finite convergence result about the support of the solution, based on which we further accelerate the algorithm by a two-stage method. We present extensive numerical experiments on both synthetic and real datasets which demonstrate the superiority of our methods over some state-of-the-art methods for both binary- and multi-class SVMs.

Appendices

Appendix A: Proof of Proposition 1

First, we derive the convexity of each $f_i$ from the composition of the convex function $\phi _H$ and the linear transformation $y_i(b+{\mathbf{x}}_i^\top {\mathbf{w}})$ (e.g., see [4]). Thus, $f$ is also convex since it is the sum of $n$ convex functions. Second, it is easy to verify that

$$\begin{aligned}\phi '_H(t)=\left\{ \begin{array}{ll} 0,&\quad {\text{for}}\;\,t>1;\\ \frac{t-1}{\delta },&\quad {\text{for}}\;\,1-\delta <t\le 1;\\ -1,&\quad {\text {for}}\;\,t\le 1-\delta ; \end{array} \right. \end{aligned}$$

and it is Lipschitz continuous, namely $|\phi '_H(t)-\phi '_H(s)|\le \frac{1}{\delta }|t-s|,$ for any $t,s$.

Using the notations in (7) and by the chain rule, we have $\nabla f_i({\mathbf{u}})=\phi '_H({\mathbf{v}}_i^\top {\mathbf{u}}){\mathbf{v}}_i$, for $i=1,\ldots ,n$ and

$$\begin{aligned} \nabla f({\mathbf{u}})=\frac{1}{n}\sum _{i=1}^n\phi '_H({\mathbf{v}}_i^\top {\mathbf{u}}){\mathbf{v}}_i. \end{aligned}$$

(23)

Hence, for any ${\mathbf{u}},\hat{\mathbf{u}}$, we have

$$\begin{aligned}&\Vert \nabla f({\mathbf{u}})-\nabla f(\hat{\mathbf{u}})\Vert \\&\quad\le \frac{1}{n}\sum _{i=1}^n\left\| \nabla f_i({\mathbf{u}})-\nabla f_i(\hat{\mathbf{u}})\right\| \\&\quad=\frac{1}{n}\sum _{i=1}^n\left\| \left( \phi '({\mathbf{v}}_i^\top {\mathbf{u}})-\phi '({\mathbf{v}}_i^\top \hat{\mathbf{u}})\right) {\mathbf{v}}_i\right\| \\&\quad\le \frac{1}{n\delta }\sum _{i=1}^n|{\mathbf{v}}_i^\top ({\mathbf{u}}-\hat{\mathbf{u}})|\Vert {\mathbf{v}}_i\Vert \\&\quad\le \frac{1}{n\delta }\sum _{i=1}^n \Vert {\mathbf{v}}_i\Vert ^2\Vert {\mathbf{u}}-\hat{\mathbf{u}}\Vert , \end{aligned}$$

which completes the proof.

Appendix B: Proof of Theorem 1

We begin our analysis with the following lemma, which can be shown through essentially the same proof of Lemma 2.3 in [1].

Lemma 2

Let $\{\mathbf{u}^k\}$ be the sequence generated by (5) with $L_k\le L$ such that for all $k\ge 1$,

$$\begin{aligned} \xi _1({\mathbf{u}}^{k})&\le \xi _1(\hat{\mathbf{u}}^{k-1}) +\left\langle \nabla \xi _1(\hat{\mathbf{u}}^{k-1}), {\mathbf{u}}^{k}-\hat{\mathbf{u}}^{k-1}\right\rangle \nonumber \\&\quad +\frac{L_k}{2}\left\| {\mathbf{u}}^{k}-\hat{\mathbf{u}}^{k-1}\right\| ^2. \end{aligned}$$

(24)

Then for all $k\ge 1$, it holds for any ${\mathbf{u}}\in \mathcal {U}$ that

$$\begin{aligned} \xi ({\mathbf{u}})-\xi ({\mathbf{u}}^k)&\ge \frac{L_k}{2}\Vert {\mathbf{u}}^k-\hat{\mathbf{u}}^{k-1}\Vert ^2+\frac{\mu }{2}\Vert {\mathbf{u}}-{\mathbf{u}}^k\Vert ^2\nonumber \\&\quad +L_k\langle \hat{\mathbf{u}}^{k-1}-{\mathbf{u}}, {\mathbf{u}}^k-\hat{\mathbf{u}}^{k-1}\rangle . \end{aligned}$$

(25)

We also need the following lemma, which is the KL property for strongly convex functions:

Lemma 3

Suppose $\xi$ is strongly convex with constant $\mu >0$. Then for any ${\mathbf{u}},{\mathbf{v}}\in \mathrm {dom}(\partial \xi )$ and ${\mathbf{g}}_{\mathbf{u}}\in \partial \xi ({\mathbf{u}})$, we have

$$\begin{aligned} \xi ({\mathbf{u}})-\xi ({\mathbf{v}})\le \frac{1}{\mu }\Vert {\mathbf{g}}_{\mathbf{u}}\Vert ^2. \end{aligned}$$

(26)

Proof

For any ${\mathbf{g}}_{\mathbf{u}}\in \partial \xi ({\mathbf{u}})$, we have from the strong convexity of $\xi$ and the Cauchy-Schwarz inequality that

$$\begin{aligned} \xi ({\mathbf{u}})-\xi ({\mathbf{v}})\le \langle {\mathbf{g}}_{\mathbf{u}},{\mathbf{u}}-{\mathbf{v}}\rangle -\frac{\mu }{2}\Vert {\mathbf{u}}-{\mathbf{v}}\Vert ^2\le \frac{1}{\mu }\Vert {\mathbf{g}}_{\mathbf{u}}\Vert ^2, \end{aligned}$$

which completes the proof. $\square$

Global convergence

We first show ${\mathbf{u}}^k\rightarrow {\mathbf{u}}^*$. Letting ${\mathbf{u}}={\mathbf{u}}^{k-1}$ in (25) gives

$$\begin{aligned} &\xi ({\mathbf{u}}^{k-1})-\xi ({\mathbf{u}}^k)\\&\quad\ge \frac{L_k}{2}\Vert {\mathbf{u}}^k-\hat{\mathbf{u}}^{k-1}\Vert ^2+\frac{\mu }{2}\Vert {\mathbf{u}}^{k-1}-{\mathbf{u}}^k\Vert ^2\nonumber \\&\quad\quad +L_k\langle \hat{\mathbf{u}}^{k-1}-{\mathbf{u}}^{k-1}, {\mathbf{u}}^k-\hat{\mathbf{u}}^{k-1}\rangle \nonumber \\&\quad=\frac{L_k}{2}\Vert {\mathbf{u}}^k-{\mathbf{u}}^{k-1}\Vert ^2+\frac{\mu }{2}\Vert {\mathbf{u}}^k-{\mathbf{u}}^{k-1}\Vert ^2\nonumber \\&\quad\quad -\frac{L_k}{2}\omega _{k-1}^2\Vert {\mathbf{u}}^{k-1}-{\mathbf{u}}^{k-2}\Vert ^2\nonumber \\&\quad\ge \frac{L_k}{2}\Vert {\mathbf{u}}^k-{\mathbf{u}}^{k-1}\Vert ^2+\frac{\mu }{2}\Vert {\mathbf{u}}^k-{\mathbf{u}}^{k-1}\Vert ^2\\&\quad\quad -\frac{L_{k-1}}{2}\Vert {\mathbf{u}}^{k-1}-{\mathbf{u}}^{k-2}\Vert ^2.\nonumber \end{aligned}$$

(27)

Summing up the inequality (27) over $k$, we have

$$\begin{aligned}&\xi ({\mathbf{u}}^0)-\xi ({\mathbf{u}}^K)\\&\quad\ge \frac{\mu }{2}\sum _{k=1}^K\Vert {\mathbf{u}}^{k-1}-{\mathbf{u}}^k\Vert ^2 +\frac{L_K}{2}\Vert {\mathbf{u}}^K-{\mathbf{u}}^{K-1}\Vert ^2, \end{aligned}$$

which implies ${\mathbf{u}}^k-{\mathbf{u}}^{k-1}\rightarrow {\mathbf {0}}$ since $\xi ({\mathbf{u}}^k)$ is lower bounded.

Note that $\{{\mathbf{u}}^k\}$ is bounded since $\xi$ is coercive and $\{\xi ({\mathbf{u}}^k)\}$ is upper bounded by $\xi ({\mathbf{u}}^0)$. Hence, $\{{\mathbf{u}}^k\}$ has a limit point $\bar{\mathbf{u}}$, so there is a subsequence $\{{\mathbf{u}}^{k_j}\}$ converging to $\bar{\mathbf{u}}$. Note ${\mathbf{u}}^{k_j+1}$ also converges to $\bar{\mathbf{u}}$ since ${\mathbf{u}}^k-{\mathbf{u}}^{k-1}\rightarrow {\mathbf {0}}$. Without loss of generality, we assume $L_{k_j+1}\rightarrow \bar{L}$. Otherwise, we can take a convergent subsequence of $\{L_{k_j+1}\}$. By (5), we have

$$\begin{aligned} {\mathbf{u}}^{k_j+1}=&\arg \underset{\mathbf{u}}{\min } \xi _1(\hat{\mathbf{u}}^{k_j})+ \langle \nabla \xi _1(\hat{\mathbf{u}}^{k_j}),{\mathbf{u}}-\hat{\mathbf{u}}^{k_j}\rangle \\&+\frac{L_{k_j+1}}{2}\Vert {\mathbf{u}}-\hat{\mathbf{u}}^{k_j}\Vert ^2+\xi _2({\mathbf{u}}). \end{aligned}$$

Letting $j\rightarrow \infty$ in the above formula and observing $\hat{\mathbf{u}}^{k_j}\rightarrow \bar{\mathbf{u}}$ yield

$$\begin{aligned} \bar{\mathbf{u}}=\arg \underset{\mathbf{u}}{\min }&\xi _1(\bar{\mathbf{u}})+ \langle \nabla \xi _1(\bar{\mathbf{u}}),\mathbf{u}-\bar{\mathbf{u}}\rangle +\frac{\bar{L}}{2}\Vert {\mathbf{u}}-\bar{\mathbf{u}}\Vert ^2+\xi _2(\mathbf{u}), \end{aligned}$$

which indicates $-\nabla \xi _1(\bar{\mathbf{u}})\in \partial \xi _2(\bar{\mathbf{u}})$. Thus $\bar{\mathbf{u}}$ is the minimizer of $\xi$.

Since $\{\xi ({\mathbf{u}}^k)\}$ is nonincreasing and lower bounded, it converges to $\xi (\bar{\mathbf{u}})=\xi (\mathbf{u}^*)$. Noting $\frac{\mu }{2}\Vert {\mathbf{u}}^k-{\mathbf{u}}^*\Vert ^2\le \xi ({\mathbf{u}}^k)-\xi ({\mathbf{u}}^*),$ we have ${\mathbf{u}}^k\rightarrow {\mathbf{u}}^*.$

Convergence rate

Next we go to show (19). Without loss of generality, we assume $\xi ({\mathbf{u}}^*)=0$. Otherwise, we can consider $\xi -\xi ({\mathbf{u}}^*)$ instead of $\xi$. In addition, we assume $\xi ({\mathbf{u}}^k)>\xi ({\mathbf{u}}^*)$ for all $k\ge 0$ because if $\xi ({\mathbf{u}}^{k_0})=\xi ({\mathbf{u}}^*)$ for some $k_0$, then ${\mathbf{u}}^k={\mathbf{u}}^{k_0}={\mathbf{u}}^*$ for all $k\ge k_0$.

For ease of description, we denote $\xi _k=\xi ({\mathbf{u}}^k)$. Letting ${\mathbf{v}}={\mathbf{u}}^*$ in (26), we have

$$\begin{aligned} \sqrt{\xi _k}\le \frac{1}{\sqrt{\mu }}\Vert {\mathbf{g}}_{{\mathbf{u}}^k}\Vert , \quad {\text {for\; all}}\quad{\mathbf{g}}_{{\mathbf{u}}^k}\in \partial \xi ({\mathbf{u}}^k). \end{aligned}$$

(28)

Noting $-\nabla \xi _1(\hat{\mathbf{u}}^{k-1})-L_k({\mathbf{u}}^k-\hat{\mathbf{u}}^{k-1})+\nabla \xi _1({\mathbf{u}}^k)\in \partial \xi ({\mathbf{u}}^k)$ and $L_k\le L$, we have for all $k\ge K$,

$$\begin{aligned} \sqrt{\xi _k}\le \frac{2L}{\sqrt{\mu }}\left( \Vert {\mathbf{u}}^k-{\mathbf{u}}^{k-1}\Vert +\Vert {\mathbf{u}}^{k-1}-{\mathbf{u}}^{k-2}\Vert \right) \end{aligned}$$

(29)

Noting $\sqrt{\xi _k}-\sqrt{\xi _{k+1}}\ge \frac{\xi _k-\xi _{k+1}}{2\sqrt{\xi _k}}$ and using (27) yield

$$\begin{aligned}&(L_{k+1}+\mu )\Vert {\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\Vert ^2\\ &\quad\le L_k\Vert {\mathbf{u}}^{k-1}-{\mathbf{u}}^{k}\Vert ^2+\frac{8L}{\sqrt{\mu }}\left( \sqrt{\xi _k}-\sqrt{\xi _{k+1}}\right) \Vert {\mathbf{u}}^k-{\mathbf{u}}^{k-1}\Vert \\&\qquad+\frac{8L}{\sqrt{\mu }}\left( \sqrt{\xi _k}-\sqrt{\xi _{k+1}}\right) \Vert {\mathbf{u}}^{k-1}-{\mathbf{u}}^{k-2}\Vert , \end{aligned}$$

after rearrangements. Take $0<\delta <\frac{1}{2}(\sqrt{L+\mu }-\sqrt{L})$. Using the inequalities $a^2+b^2\le (a+b)^2$ and $\sqrt{ab}\le ta+\frac{1}{4t}b$ for $a,b,t>0$, we have from the above inequality that

$$\begin{aligned}&\sqrt{L_{k+1}+\mu }\Vert {\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\Vert \\ &\quad\le \sqrt{L_k}\Vert {\mathbf{u}}^{k-1}-{\mathbf{u}}^{k}\Vert +\frac{2L}{\delta \sqrt{\mu }}\left( \sqrt{\xi _k}-\sqrt{\xi _{k+1}}\right) \\&\qquad+\delta \left( \Vert {\mathbf{u}}^k-{\mathbf{u}}^{k-1}\Vert +\Vert {\mathbf{u}}^{k-1}-{\mathbf{u}}^{k-2}\Vert \right) . \end{aligned}$$

Summing up the above inequality over $k$ and noting $\Vert {\mathbf{u}}^k-{\mathbf{u}}^{k+1}\Vert \rightarrow 0, \xi _k\rightarrow 0$ yield

$$\begin{aligned}&\sum _{k=m}^\infty \left( \sqrt{L_{k+1}+\mu }-\sqrt{L_{k+1}}-2\delta \right) \Vert {\mathbf{u}}^k-{\mathbf{u}}^{k+1}\Vert \\ \le&\left( \sqrt{L}+2\delta \right) \Vert {\mathbf{u}}^{m-1}-{\mathbf{u}}^m\Vert +\delta \Vert {\mathbf{u}}^{m-2}-{\mathbf{u}}^{m-1}\Vert +\frac{2L}{\delta \sqrt{\mu }}\sqrt{\xi _m}, \end{aligned}$$

which together with $\sqrt{L+\mu }-\sqrt{L}\le \sqrt{L_k+\mu }-\sqrt{L_k}$ for all $k\ge 0$ implies

$$\begin{aligned}&\sum _{k=m}^\infty \Vert {\mathbf{u}}^k-{\mathbf{u}}^{k+1}\Vert \nonumber \\ \le&C_1 \sqrt{\xi _m}+C_2\left( \Vert {\mathbf{u}}^{m-1}-{\mathbf{u}}^m\Vert +\Vert {\mathbf{u}}^{m-2}-{\mathbf{u}}^{m-1}\Vert \right) , \end{aligned}$$

(30)

where

$$\begin{aligned} C_1=\frac{2L}{\delta \sqrt{\mu }\left( \sqrt{L+\mu }-\sqrt{L}-2\delta \right) },\quad C_2=\frac{\sqrt{L}+2\delta }{\sqrt{L+\mu }-\sqrt{L}-2\delta }. \end{aligned}$$

Denote $S_m=\sum _{k=m}^\infty \Vert {\mathbf{u}}^k-{\mathbf{u}}^{k+1}\Vert$ and write (30) as

$$\begin{aligned} S_m\le C_1 \sqrt{\xi _m}+C_2(S_{m-2}-S_m), \end{aligned}$$

which together with (29) gives

$$\begin{aligned} S_m & \le \left( C_1\frac{2L}{\sqrt{\mu }}+C_2\right) (S_{m-2}-S_m)\\ &= C_3(S_{m-2}-S_m),\text { for\; all }\, m\ge 2. \end{aligned}$$

Let $\tau =\sqrt{\frac{C_3}{1+C_3}}$ and $C=S_0$. Then we have $S_m\le C\tau ^m, \forall m\ge 0.$ Note $\Vert {\mathbf{u}}^m-{\mathbf{u}}^*\Vert \le S_m$, and thus we complete the proof.