2.1 Basic definitons and setups

• $D>0$,
  • we use this symbol for the upper bound of the
• $G>0$,
  • we use this symbol for the constant of Lipschitz function
• $\mathcal{K}\subseteq {\mathbb{R}}^d$,
  • diameter is bounded by $D$
  • convex
  • compact

Definition

• $f:\mathcal{K}\to \mathbb{R}$,
  • convex
• $G>0$,

$f$ is said to be $G$-bounded if

$$\Vert {\partial }_{x}f\Vert \le G$$

where ${\partial }_{x}f$ is subgradient of $f$ at $x$.

■

Definition positive definite

• $A$,
  • $n\times n$-matrix
• $B$,
  • $n\times n$-matrix

We write $A\preccurlyeq B$ if $B-A$ is positive semidefinite.

■

Proposition property of positive definite

• $A$,
  • $n\times n$-matrix
• $B$,
  • $n\times n$-matrix
• $\alpha >0$,

(1) If $\alpha A\preccurlyeq B$ and $A$ is nonnegative definite, then for all $\beta <\alpha$,

$$\beta A\preccurlyeq B.$$

proof

(1)

Since $A$ is positive semidefinite, $x^{\mathrm{T}}Ax\ge 0$. Then

$$\begin{array}{rcl}x{\mathbb{R}}^n,x^{\mathrm{T}}(B-\beta A)x& =& x^{\mathrm{T}}Bx-\beta x^{\mathrm{T}}Ax\\ & \ge & x^{\mathrm{T}}Bx-\alpha x^{\mathrm{T}}Ax\\ & >& 0\end{array}$$

$◻$

Definition alpha strongly convex and beta smooth

• $f$,
  • convex
• $\alpha >0$,
• $\beta >0$,

$f$ is said to be $\alpha$-strongly convex if

$$\begin{array}{rcl}& & f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{T}}(y-x)+\frac{\alpha }{2}\Vert y-x{\Vert }^2\le f(y)\\ \text{(1)}& & \iff & \mathrm{\nabla }f(x{)}^{\mathrm{T}}(y-x)+\frac{\alpha }{2}\Vert y-x{\Vert }^2\le f(y)-f(x)\end{array}.$$

$f$ is said to be $\beta$-smooth if

$$\begin{array}{rcl}& & f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{T}}(y-x)+\frac{\beta }{2}\Vert y-x{\Vert }^2\ge f(y)\\ \text{(2)}& & \iff & \mathrm{\nabla }f(x{)}^{\mathrm{T}}(y-x)+\frac{\beta }{2}\Vert y-x{\Vert }^2\ge f(y)-f(x)\end{array}.$$

■

Proposition

• $f$,
  • convex
• $\beta >0$,

Then the following conditions are equivalent;

(1) $f$ is $\beta$-smooth

(2)

$$\Vert \mathrm{\nabla }f(x)-\mathrm{\nabla }f(y)\Vert \le \beta \Vert x-y\Vert .$$

(3)

$$\alpha I\preccurlyeq {\mathrm{\nabla }}^{2}f(x)\preccurlyeq \beta I.$$

proof

(1) $\Rightarrow$ (2)

Let $x\in {\mathbb{R}}^n$ and $h>0$ be fixed. Let $y:=x+h(1,\dots ,1{)}^{\mathrm{T}}$.

$◻$

Definition gamma-well-conditioned

• $f$,

$f$ is said to be $\gamma$-well-condtiond if

• (1) $f$ is $\alpha$-strongly convex
• (2) $f$ is $\beta$-smooth convex

where

$$\gamma :=\frac{\alpha }{\beta }\le 1.$$

$\gamma$ is called the condition number of $f$.

■

2.1.1 Projections onto convex sets

Definition. projection onto convex sets

• $\mathcal{K}\subseteq {\mathbb{R}}^d$,
  • convex sets
• $y\in {\mathbb{R}}^d$,

Projection onto convex sets are defined

$${\mathrm{\Pi }}_{\mathcal{K}}(y):=\arg \underset{x\in \mathcal{K}}{min}\Vert x-y\Vert .$$

■

Theorem 2.1

• $\mathcal{K}\subseteq {\mathbb{R}}^d$,
  • convex set
• $y\in {\mathbb{R}}^d$,
• $x:={\mathrm{\Pi }}_{\mathcal{K}}(y)$,

$$\mathrm{\forall }z\in \mathcal{K},\Vert y-z\Vert \ge \Vert x-z\Vert .$$

■

2.1.1 Introduction to optimality conditions

In this section, we assume

$$x^{\ast }\in \arg \underset{x\in \mathcal{K}}{min}f(x)$$

Theorem 2.2 KKT

• $\mathcal{K}\subseteq {\mathbb{R}}^d$,
  • convex set
• $x^{\ast }\in \arg \underset{x\in \mathcal{K}}{min}f(x)$,

Then

$$\mathrm{\nabla }f(x^{\ast }{)}^{\mathrm{T}}(y-x^{\ast }))\ge 0.$$

proof.

$◻$

2.2 Gradient / subgradient descent

In this section, we prove the convergence rate of Gradient descent and Accelerated GD for each cases, $f$ is gamma-well-conditioned, $f$ is beta-smooth, and $f$ is alpha strongly convex.

Gradient descent

• general convex
  • $O(1/\sqrt{T})$,
• $\alpha$-strongly convex
  • $O(\frac{1}{\alpha T})$,
• $\beta$-smooth convex
  • $O(\frac{\beta }{T})$,
• $\gamma$-well-conditioned
  • $O(e^{-\gamma T})$,

Accelerated GD

• $\beta$-smooth convex
  • $O(\frac{\beta }{T^2})$,
• $\gamma$-well-conditioned
  • $O(e^{-\sqrt{\gamma }T})$,

2.2.1 Basic Gradient descent

ALgorithm 2 Gradient Decent Method

• $f:\mathcal{K}\to \mathbb{R}$,
  • convex function
• $\mathcal{K}$,
  • convex set
• $x_1\in \mathcal{K}$,
  • initial points
• $T\in \mathbb{N}$,
• $\{{\eta }_t\}$,
  • sequence of step sizes

Step1. For $t=1,\dots ,T$

Step2.

$$\begin{array}{rcl}{y}_{t+1}& :=& x_t-{\eta }_t\mathrm{\nabla }f(x_t),\\ x_{t+1}& :=& {\mathrm{\Pi }}_{\mathcal{K}}(y_{t+1})\end{array}$$

Step3. Go to Step2 until $t=T$

Step4. $x_{T+1}$,

■

Lemma

• $b>0$,

$$\begin{array}{rcl}x-\frac{1}{b}a& =& \arg \underset{z}{min}f(z)\\ f(z)& :=& \sum _{i=1}^d{a}_i(z_i-x_i)+\frac{b}{2}\Vert z-x{\Vert }^2\end{array}$$

proof

$$\begin{array}{rcl}& & \frac{\partial f}{\partial z_i}=0\\ & \iff & a_i+b(z_i-x_i)=0\\ \text{(3)}& & \iff & z_i=\frac{-a_i}{b}+x_i\end{array}$$

Then,

$$\begin{array}{rcl}f(x-\frac{1}{b}a)& =& -\sum _{i=}^d\frac{a_i^2}{b}+\frac{1}{2b}\Vert a{\Vert }^2\\ \text{(4)}& & =& -\frac{1}{2b}\Vert a{\Vert }^2\end{array}$$

$◻$

Theroem 2.3

• $\mathrm{\Gamma }>0$,
• $f$,
  • $\gamma$-well-conditioned function
• $h_t:=f(x_t)-f(x^{\ast })$,
• ${\eta }_t:-\frac{1}{\beta }>0$,

Then

$$h_{t+1}\le h_1{e}^{-\gamma t}.$$

proof

By strong convexity, for all $x,y\in \mathcal{K}$,

$$\begin{array}{rcl}f(y)& \ge & f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{T}}(y-x)+\frac{\alpha }{2}\Vert x-y{\Vert }^2(\because \alpha \text{-strong convexity})\\ & \ge & \underset{z\in \mathcal{K}}{min}\{f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{T}}(z-x)+\frac{\alpha }{2}\Vert x-z{\Vert }^2\}\\ & =& f(x)-\frac{1}{2\alpha }\Vert \mathrm{\nabla }f(x){\Vert }^2(\because z:=x-\frac{1}{\alpha }\mathrm{\nabla }f(x))\end{array}$$

Hence

$$\begin{array}{rcl}& & f(x^{\ast })\ge f(x_t)-\frac{1}{2\alpha }\Vert \mathrm{\nabla }f(x_t){\Vert }^2\\ \text{(5)}& & \iff & \Vert \mathrm{\nabla }f(x_t){\Vert }^2\ge 2\alpha (f(x_t)-f(x^{\ast }))=2\alpha h_t\end{array}$$ $$\begin{array}{rcl}{h}_{t+1}-h_t& =& f(x_{t+1}-x_t)-f(x_t)\\ & \le & (\mathrm{\nabla }f(x_t){)}^{\mathrm{T}}(x_{t+1}-x_t)+\frac{\beta }{2}\Vert x_{t+1}-x_t\Vert \\ & =& -{\eta }_t\Vert \mathrm{\nabla }f(x_t){\Vert }^2+\frac{\beta }{2}{\eta }_t^2\Vert \mathrm{\nabla }f(x_t){\Vert }^2\\ & =& -\frac{1}{2\beta }\Vert \mathrm{\nabla }f(x_t){\Vert }^2\\ & \le & -\frac{\alpha }{\beta }{h}_t(\because \text{(5)})\\ \text{(6)}& & =& -\gamma h_t.\end{array}$$

Thus,

$$\begin{array}{r}{h}_{t+1}\le h_t(1-\gamma )\le \cdots h_1{(1-\gamma )}^t\le h_1{e}^{-\gamma t}\end{array}$$

$◻$

Theorem 2.4

• $\mathrm{\Gamma }>0$,
• $f$,
  • $\gamma$-well-conditioned function
• $h_t:=f(x_t)-f(x^{\ast })$,
• ${\eta }_t:-\frac{1}{\beta }>0$,
• $\mathcal{K}$,
  • convex set

Then

$$h_{t+1}\le h_1\exp (-\frac{\gamma t}{4}).$$

proof

From $\beta$ smoothness, for every $x,x_t\in \mathcal{K}$,

$$\begin{array}{}\text{(7)}& \mathrm{\nabla }f(x_t)(x-x_t)\le f(x)-f(x_t)-\frac{\alpha }{2}\Vert x-x_t{\Vert }^2\end{array}.$$

By algorithm’s definition, we have

$$\begin{array}{}\text{(8)}& x_{t+1}=\arg \underset{x\in \mathcal{K}}{min}\{\mathrm{\nabla }f(x_t{)}^{\mathrm{T}}(x-x_t)+\frac{\beta }{2}\Vert x-x_t{\Vert }^2\}\end{array}.$$

To see this, letting ${\mathrm{\nabla }}_t:=\mathrm{\nabla }f(x_t)$,

$$\begin{array}{rcl}\arg \underset{x\in \mathcal{K}}{min}\{\Vert x-(x_t-{\eta }_t{\mathrm{\nabla }}_t){\Vert }^2\}& =& \arg \underset{x\in \mathcal{K}}{min}\left\{\sum _{i=1}^d{(x_i-(x_{t,i}-{\eta }_t{\mathrm{\nabla }}_{t,i}))}^2\right\}\\ & =& \arg \underset{x\in \mathcal{K}}{min}\left\{\sum _{i=1}^d(x_i^2-2x_i(x_{t,i}-{\eta }_t{\mathrm{\nabla }}_{t,i})+x_{t,i}^2-2x_{t,i}{\eta }_t{\mathrm{\nabla }}_{t,i}+{\eta }_t^2{\mathrm{\nabla }}_{t,i}^2)\right\}\\ & =& \arg \underset{x\in \mathcal{K}}{min}\left\{\sum _{i=1}^d(x_i^2-2x_i{x}_{t,i}+x_{t,i}^2-2x_i{\eta }_t{\mathrm{\nabla }}_{t,i}-2x_{t,i}{\eta }_t{\mathrm{\nabla }}_{t,i}+{\eta }_t^2{\mathrm{\nabla }}_{t,i}^2)\right\}\\ & =& \arg \underset{x\in \mathcal{K}}{min}\left\{\sum _{i=1}^d((x_i-x_{t,i}{)}^2+2x_i{\eta }_t{\mathrm{\nabla }}_{t,i}-2x_{t,i}{\eta }_t{\mathrm{\nabla }}_{t,i})\right\}\\ & =& \arg \underset{x\in \mathcal{K}}{min}\left\{\sum _{i=1}^{d}2{\eta }_t(\frac{1}{2{\eta }_t}(x_i-x_{t,i}{)}^2+{\mathrm{\nabla }}_{t,i}(x_i-x_{t,i}))\right\}\\ \text{(9)}& & =& \arg \underset{x\in \mathcal{K}}{min}\{\frac{1}{2{\eta }_t}\Vert x-x_{t,i}{\Vert }^2+{\mathrm{\nabla }}_t^{\mathrm{T}}(x-x_t)\}\end{array}$$ $$\begin{array}{rcl}{x}_{t+1}& =& {\mathrm{\Pi }}_{\mathcal{K}}(x_t-{\eta }_t\mathrm{\nabla }f(x_t))\\ & =& \arg \underset{x\in \mathcal{K}}{min}\{\Vert x-(x_t-{\eta }_t\mathrm{\nabla }f(x_t))\Vert \}\\ \text{(10)}& & =& \arg \underset{x\in \mathcal{K}}{min}\{\mathrm{\nabla }f(x_t{)}^{\mathrm{T}}(x-x_t)+\frac{1}{2{\eta }_t}\Vert x-x_t{\Vert }^2\}\end{array}$$

Thus, $\mathrm{\forall }\eta \in [0,1]$,

$$\begin{array}{rcl}{h}_{t+1}-h_t& =& f(x_{t+1})-f(x_t)\\ & \le & \mathrm{\nabla }f(x_t{)}^{\mathrm{T}}(x_{t+1}-x_t)+\frac{\beta }{2}\Vert x_{t+1}-x_t{\Vert }^2(\because \text{smoothness})\\ & =& \underset{x\in \mathcal{K}}{min}\{\mathrm{\nabla }f(x_t)(x-x_t)+\frac{\beta }{2}\Vert x-x_t{\Vert }^2\}(\because \text{(8)})\\ & \le & \underset{x\in \mathcal{K}}{min}\{f(x)-f(x_t)+\frac{\beta -\alpha }{2}\Vert x-x_t{\Vert }^2\}(\because \text{(7)})\\ & \le & \underset{x\in [x_t,x^{\ast }]}{min}\{f(x)-f(x_t)+\frac{\beta -\alpha }{2}\Vert x-x_t{\Vert }^2\}\\ & =& f((1-\eta )x_t+\eta x^{\ast })-f(x_t)+\frac{\beta -\alpha }{2}\Vert (1-\eta )x_t+\eta x^{\ast }-x_t{\Vert }^2\\ & \le & (1-\eta )f(x_t)+\eta f(x^{\ast })-f(x_t)+\frac{(\beta -\alpha ){\eta }^2}{2}\Vert -x_t+x^{\ast }{\Vert }^2(\because \text{convexity})\\ & =& -\eta f(x_t)+\eta f(x^{\ast })+\frac{(\beta -\alpha ){\eta }^2}{2}\Vert -x_t+x^{\ast }{\Vert }^2\\ \text{(11)}& & \le & -\eta h_t+\frac{(\beta -\alpha ){\eta }^2}{2}\Vert -x_t+x^{\ast }{\Vert }^2\end{array}$$

where

$$[x_t,x^{\ast }]:=\{(1-\eta )x_t+\eta x^{\ast }\mid \eta \in [0,1]\}.$$

For the second term,

$$\begin{array}{rcl}\frac{\alpha }{2}\Vert x^{\ast }-x_t{\Vert }^2& \le & \frac{\alpha }{2}\Vert x^{\ast }-x_t{\Vert }^2+\mathrm{\nabla }f(x^{\ast }{)}^{\mathrm{T}}(x_t-x^{\ast })(\because \text{ KKT condition})\\ & \le & f(x_t)-f(x^{\ast })(\because \alpha \text{-strongly})\\ & =& h_t\end{array}$$

Combining the above result, $\mathrm{\forall }\eta \in [0,1]$,

$$\begin{array}{rcl}{h}_{t+1}-h_t& \le & -\eta h_t+\frac{(\beta -\alpha ){\eta }^2}{\alpha }{h}_t\\ & \le & -\eta h_t+\frac{\beta {\eta }^2}{\alpha }{h}_t\\ & =& (\frac{\beta }{\alpha }{\eta }^2-\eta )h_t\\ \text{(12)}& & =& \{\frac{\beta }{\alpha }{(\eta -\frac{\alpha }{2\beta })}^2-\frac{\alpha }{4\beta }\}{h}_t\end{array}$$

Moreover, since $\gamma$-well-conditioned,

$$0\le \eta =\frac{\alpha }{2\beta }\le \frac{1}{2}.$$

Thus, we can achieve the minimizer

$$\begin{array}{rcl}{h}_{t+1}-h_t& \le & \underset{\eta \in [0,1]}{min}-\eta h_t+\frac{\beta {\eta }^2}{\alpha }{h}_t\\ & =& -\frac{\alpha }{4\beta }{h}_t\\ \text{(13)}& & =& -\frac{\gamma }{4}{h}_t.\end{array}$$

Thus,

$$\begin{array}{}\text{(14)}& h_{t+1}\le h_t(1-\frac{\gamma }{4})\le h_t{e}^{-\gamma /4}\end{array}$$

$◻$

2.3 Reductions to non-smooth and non-strongly convex functions

2.3.1 Reductions to smooth and non-strongly convex functions

Algorithm 3 gradient descent, reduction to beta-smooth functions

• $f$,
• $T$,
• $x_1\in \mathcal{K}$,
• $\tilde{\alpha }>0$,
  • parameter

Step1. Let

$$\begin{array}{}\text{(15)}& g(x):=f(x)+\frac{\tilde{\alpha }}{2}\Vert x-x_1{\Vert }^2\end{array}.$$

Step2. Apply Algorithm2 with parameters $g,T,{\eta }_t:=1/\beta$, $x_1$ and get $x_T$,

Step3 return $x_T$ in Step2.

■

Proposition propety of norm

• $\alpha >0$,

$$h(x):=\frac{\alpha }{2}\Vert x-x_1{\Vert }^2.$$

• (1) $h$ is convex.
• (2) $h$ is $\alpha$ smooth and $\alpha$ strongly convex.

proof

(1)

Hessian matrix of $h$ is diagonal matrix, that is, positve semidefinite.

(2)

$$\begin{array}{rcl}\mathrm{\nabla }h(x)& =& \alpha \\ h(y)-h(x)& =& \frac{\alpha }{2}(\Vert y-x_1{\Vert }^2-\Vert x-x_1{\Vert }^2)\\ & =& \frac{\alpha }{2}(\Vert y-x_1{\Vert }^2+\Vert y-x{\Vert }^2-\Vert y-x{\Vert }^2+2\sum _{i=1}^n(x^i-x_1^i)(y^i-x^i)-2\sum _{i=1}^n(x^i-x_1^i)(y^i-x^i)-\Vert x-x_1{\Vert }^2)\\ & =& \frac{\alpha }{2}(\Vert y-x_1{\Vert }^2+\Vert y-x{\Vert }^2+2\sum _{i=1}^n(x^i-x_1^i)(y^i-x^i)-\Vert (y-x)+(x-x_1){\Vert }^2)\\ & =& \alpha \sum _{i=1}^n(x^i-x_1^i)(y^i-x^i)+\frac{\alpha }{2}\Vert y-x{\Vert }^2\\ \text{(16)}& & =& \mathrm{\nabla }h(x{)}^{\mathrm{T}}(y-x)+\frac{\alpha }{2}\Vert y-x{\Vert }^2\end{array}$$

$◻$

Proposition alpha-strongnize

• $K\subseteq {\mathbb{R}}^n$,
  • convex
• $f:K\to \mathbb{R}$,
  • convex function
• $\hat{\alpha }>0$,

$$g(x):=f(x)+\frac{\hat{\alpha }}{2}\Vert x-x_1{\Vert }^2.$$

Then $g$ is $\alpha$-strongly convex.

proof

$$\begin{array}{rcl}\mathrm{\nabla }g(x)& =& \mathrm{\nabla }f(x)+\frac{\hat{\alpha }}{2}\mathrm{\nabla }\Vert x-x_1{\Vert }^2\\ & \le & \mathrm{\nabla }f(x)+\hat{\alpha }\left(Q\begin{array}{c}{x}^1-x_1^1\\ ⋮\\ x^n-x_1^n\end{array}\right)\end{array}$$

Thus,

$$\begin{array}{rcl}g(y)-g(x)& =& f(y)-f(x)+\frac{\hat{\alpha }}{2}\Vert y-x_1{\Vert }^2-\frac{\hat{\alpha }}{2}\Vert x-x_1{\Vert }^2\\ & \ge & \mathrm{\nabla }f(y{)}^{\mathrm{T}}(y-x)+\frac{\hat{\alpha }}{2}(\Vert y-x_1{\Vert }^2-\Vert x-x_1{\Vert }^2)(\because \text{convexity})\\ & =& \mathrm{\nabla }f(y{)}^{\mathrm{T}}(y-x)+\hat{\alpha }\sum _{i=1}^n(x^i-x_1^i)(y^i-x^i)-\hat{\alpha }\sum _{i=1}^n(x^i-x_1^i)(y^i-x^i)+\frac{\hat{\alpha }}{2}(\Vert y-x_1{\Vert }^2-\Vert x-x_1{\Vert }^2)\\ & =& \mathrm{\nabla }g(y{)}^{\mathrm{T}}(y-x)+\frac{\hat{\alpha }}{2}(\Vert y-x_1{\Vert }^2+\Vert y-x{\Vert }^2-\Vert y-x{\Vert }^2-2\sum _{i=1}^n(x^i-x_1^i)(y^i-x^i)-\Vert x-x_1{\Vert }^2)\\ & =& \mathrm{\nabla }g(y{)}^{\mathrm{T}}(y-x)+\frac{\hat{\alpha }}{2}(\Vert y-x_1{\Vert }^2+\Vert y-x{\Vert }^2-\Vert (y-x)+(x-x_1){\Vert }^2)\\ \text{(17)}& & =& \mathrm{\nabla }g(y{)}^{\mathrm{T}}(y-x)+\frac{\hat{\alpha }}{2}\Vert y-x{\Vert }^2\end{array}$$

$◻$

Proposition additivity of beta smooth

• ${\beta }_1>0$,
• $h_1$,
  • ${\beta }_1$ -smooth
• ${\beta }_2>0$,
• $h_2$,
  • ${\beta }_2$ -smooth
• (1) $h_1+h_2$ is $({\beta }_1+{\beta }_2)$-smooth

proof

$$\begin{array}{rcl}{h}_1(y)+h_2(y)-h_1(x)+h_2(x)& \le & \mathrm{\nabla }{h}_1(x{)}^{\mathrm{T}}(y-x)+\frac{{\beta }_1}{2}\Vert y-x{\Vert }^2+\mathrm{\nabla }{h}_2(x{)}^{\mathrm{T}}(y-x)+\frac{{\beta }_1}{2}\Vert y-x{\Vert }^2\\ & =& \mathrm{\nabla }(h_1(x)+h_2(x){)}^{\mathrm{T}}(y-x)+(\frac{{\beta }_1}{2}+\frac{{\beta }_2}{2})\Vert y-x{\Vert }^2.\end{array}$$

$◻$

Lemma 2.5

• $\beta >0$
• $f$,
  • $\beta$-smooth function,
• $D>0$
  • upper bound of diameter in $\mathcal{K}$,

$$x,y\in \mathcal{K},\Vert x-y\Vert \le D.$$

Algorithm 3 with parameter $\hat{\alpha }:=\frac{\beta \log t}{D^{2}t}$ converges as

$$h_{t+1}\le h_1^g\exp (-\frac{t\log t}{4(\log t+D^{2}t)})+\frac{\beta \log t}{2t}.$$

proof

$g$ defined in $\text{(15)}$ is $\hat{\alpha }$-strongly convex. Indeed,

By the previous proposition and proposition above, $g$ is $(\beta +\hat{\alpha })$-smooth.

Thus, $g$ is $\gamma =\frac{\hat{\alpha }}{\hat{\alpha }+\beta }$-well-conditioned.

$$\begin{array}{rclrc}{h}_t& =& f(x_t)-f(x^{\ast })& =& g(x_t)-g(x^{\ast })+\frac{\hat{\alpha }}{2}(\Vert x^{\ast }-x_1{\Vert }^2-\Vert x_t-x_1{\Vert }^2)\\ & \le & h_t^g+\frac{\hat{\alpha }}{2}\left(D^2\right)\\ & =& h_t^g+\frac{\hat{\alpha }}{2}{D}^2\end{array}$$

where $h_t^g:=g(x_t)-g(x^{\ast })$. Since $g$ is $\frac{\hat{\alpha }}{\hat{\alpha }+\beta }$-well-conditioned,

$$\begin{array}{rcl}{h}_{t+1}& \le & h_{t+1}^g+\frac{\hat{\alpha }}{2}{D}^2\\ & \le & h_1^g\exp (-\frac{\hat{\alpha }t}{4(\hat{\alpha }+\beta )})+\frac{\hat{\alpha }}{2}{D}^2(\because \text{theorem 2.4})\\ & =& h_1^g\exp (-\frac{t\beta \log t}{4\beta (\log t+D^{2}t)})+\frac{\beta \log t}{2t}\\ & =& h_1^g\exp (-\frac{t\log t}{4(\log t+D^{2}t)})+\frac{\beta \log t}{2t}\end{array}$$

$◻$

2.3.2 Reduction to strongly convex, non-smooth functions

Algorithm 4 Gradient descent reduction to non-smooth functions

• $f$,
  • $\alpha$ strongly convex
  • $G$-Lipschitz continuous
• $x_1$,
  • initial point
• $T\in \mathbb{N}$,
• $\delta >0$,

$${\hat{f}}_{\delta }(x):={\int }_{\mathbb{B}}f(x+\delta u)du.$$

Step1 Apply algorithm 2 on $\hat{f}$, $x_1$, $T$, $\{{\eta }_t=\delta \}$, return $x_T$.

■

Lemma 2.6

• ${\hat{f}}_{\delta }$,
  • Algorithm 4

Then

• (1) If $f$ is $\alpha$-strongly convex, then so is ${\hat{f}}_{\delta }$,
• (2) ${\hat{f}}_{\delta }$ is $\frac{dG}{\delta }$-smooth
• (3) $\Vert {\hat{f}}_{\delta }(x)-f(x)\Vert \le \delta G$ for all $x\in \mathcal{K}$,
  • TODO: we need to chekc whether the statement is correct or not

proof

(1) TODO

$$\begin{array}{rcl}{\hat{f}}_{\delta }(y)-{\hat{f}}_{\delta }(x)& \ge & {\int }_{\mathbb{B}}f(y+\delta u)-f(x+\delta u)du\\ & \ge & {\int }_{\mathbb{B}}\frac{\alpha }{2}\Vert y-x\Vert +\mathrm{\nabla }f(x+\delta u{)}^{\mathrm{T}}(y-x)du(\because \text{strongly convex})\\ & =& \frac{\alpha }{2}\Vert y-x\Vert +\mathrm{\nabla }{\int }_{\mathbb{B}}f(x+\delta u{)}^{\mathrm{T}}du(y-x)\\ & =& \frac{\alpha }{2}\Vert y-x\Vert +\mathrm{\nabla }\hat{f}(x{)}^{\mathrm{T}}(y-x)\end{array}$$

The 3rd inequality follows from the fact that $f$ is integrable over unit cube and differentiable and Lebesgue dominated convergence theorem.

(2) TODO

$$\mathbb{S}:=\{y\in {\mathbb{R}}^d\mid \Vert y\Vert =1\}.$$

By Stokes theorem,

$$\begin{array}{}\text{(18)}& {\int }_{\mathbb{S}}f(x+\delta u)udu=\frac{\delta }{d}\mathrm{\nabla }{\int }_{\mathbb{B}}f(x+\delta u)du\end{array}$$ $$\begin{array}{rcl}\Vert \mathrm{\nabla }{\hat{f}}_{\delta }(x)-\mathrm{\nabla }{\hat{f}}_{\delta }(y)\Vert & =& \frac{d}{\delta }\Vert {\int }_{\mathbb{S}}f(x+\delta u)udu-{\int }_{\mathbb{S}}f(y+\delta u)udu\Vert \\ & =& \frac{d}{\delta }\Vert {\int }_{\mathbb{S}}f(x+\delta u)u-f(y+\delta u)udu\Vert \\ & \le & \frac{d}{\delta }{\int }_{\mathbb{S}}\Vert f(x+\delta u)u-f(y+\delta u)u\Vert du(\because \text{Jensen's inequality})\\ & =& \frac{d}{\delta }{\int }_{\mathbb{S}}\left|(f(x+\delta u)-f(y+\delta u))\right|\Vert u\Vert du\\ & \le & \frac{d}{\delta }G{\int }_{\mathbb{S}}\Vert x-y\Vert \Vert u\Vert du(\because \text{Lipschitz continity})\\ & \le & \frac{d}{\delta }G\Vert x-y\Vert {\int }_{\mathbb{S}}1du(\because u\in \mathbb{S})\\ & =& \frac{d}{\delta }G\Vert x-y\Vert .\end{array}$$

By proposition, ${\hat{f}}_{\delta }$ is $\frac{d}{\delta }G$-smooth.

(3)

$$\begin{array}{rcl}|{\hat{f}}_{\delta }(x)-f(x)|& =& |{\int }_{\mathbb{B}}f(x+\delta u)-f(x)du|\\ & \le & {\int }_{\mathbb{B}}|f(x+\delta u)-f(x)|du(\because \text{Jensen's inequality})\\ & \le & G{\int }_{\mathbb{B}}\Vert \delta u\Vert du(\because \text{Lipschitz})\\ \text{(19)}& & =& G\delta {\int }_{\mathbb{B}}1du\end{array}$$

$◻$

Lemma 2.7

$$\delta :=\frac{dG}{\alpha }\frac{\log t}{t}.$$

Algorithm 4 converges as

$$h_{t+1}\le h_1\exp (-\frac{\log t}{4})+\frac{2d{G}^2\log t}{\alpha t}$$

proof

By lemma 2.6, the function ${\hat{f}}_{\delta }$ is $\gamma$-well conditioned for

$$\gamma :=\frac{\alpha \delta }{dG}.$$

Hence

$$\begin{array}{rcl}{h}_{t+1}& =& f(x_{t+1})-f(x^{\ast })\\ & =& \hat{f}(x_{t+1})+f(x_{t+1})-\hat{f}(x_{t+1})-\hat{f}(x^{\ast })+\hat{f}(x^{\ast })-f(x^{\ast })\\ & \le & \hat{f}(x_{t+1})+\delta G-\hat{f}(x^{\ast })+\delta G(\because \text{lemma 2.6 (3)})\\ & \le & h_1{e}^{-\frac{\gamma t}{4}}+2\delta G(\because \text{lemma 2.4})\\ & \le & h_1\exp (-\frac{\alpha \delta t}{4dG})+2\delta G\\ & \le & h_1\exp (-\frac{\log t}{4})+\frac{2d{G}^2\log t}{\alpha t}\\ \text{(20)}& & \le & h_1\exp (-\frac{\log t}{4})+\frac{2d{G}^2\log t}{\alpha t}\end{array}$$

$◻$

There is an algorithm for $\alpha$-strongly convex function, which does not rely on expectation. Even more the bound of the algorithm does not depend on the dimension $d$.

Theorem 2.8

• $f$,
  • $\alpha$-strongly convex
• $x_1,\dots ,x_t$,
  • the iterates of Algorithm 2 appied to $f$ with ${\eta }_t$

$${\eta }_t:=\frac{2}{\alpha (t+1)}.$$

Then

$$f\left(\frac{1}{t}\sum _{s=1}^t\frac{2s}{t+1}{x}_x\right)-f(x^{\ast })\le \frac{2G}{\alpha (t+1)}.$$

proof

$◻$

2.3.3 Reduction to general convex function

We can apply both the technique

$$\begin{array}{rcl}g(x)& :=& f(x)+\frac{\alpha }{2}\Vert x-x_1{\Vert }^2\\ {\hat{f}}_{\delta }(x)& :=& {\int }_{\mathbb{B}}g(x+\delta u)du\\ & =& {\int }_{\mathbb{B}}f(x+\delta u)+\frac{\alpha }{2}\Vert x+\delta u-x_1{\Vert }^{2}du\end{array}.$$

Then by proposition $g$ is $\alpha$-strongly convex. Moreover, by lemma 2.6, ${\hat{f}}_{\delta }$ is $dG/\delta$ smooth. Thus, we have the same inequality in lemme 2.7.

However, there is an algorithm which gives the better inequality than the inequality from lemma 2.7, which is $O(\frac{1}{\sqrt{t}})$. We will show this in next chapter.

2.4 Example: Support Vector Machine training

General linear classfication problem is stated as below.

• $d\in \mathbb{N}$,
  • the dimension of feature/input vector
• $n\in \mathbb{N}$,
• $a_i\in {\mathbb{R}}^d(i=1,\dots ,n)$,
  • input vector
• $b_i\in \{-1,1\}$,
  • label corresponding to input $a_i$,

A lot of loss functions can be considered for this classfication problems, but here we consider one of the simplest loss function. The following equation is the problem to solve.

$$\begin{array}{}\text{(21)}& \underset{x\in {\mathbb{R}}^d}{min}\sum _{i=1}^n{1}_{\mathrm{sign}(x^{\mathrm{T}}{a}_i\ne b_i)}\end{array}.$$

General classi

Support Vector Machine is pracitically used for classification. The soft margin SV relaxation replaces the 0/1 loss in $\text{(21)}$ with a convex loss, called the hinge-loss, given by

$$\begin{array}{rcl}{\ell }_{a,b}(x)& :=& \mathrm{hinge}(b{x}^{\mathrm{T}}a)\\ & :=& max\{0,1-b{x}^{\mathrm{T}}a\}.\end{array}$$

Here we consider the loss function with regularization.

$$\begin{array}{}\text{(22)}& \underset{x\in {\mathbb{R}}^d}{min}(\lambda \frac{1}{n}\sum _{i=1}^n{\ell }_{a_i,b_i}(x)+\frac{1}{2}\Vert x{\Vert }^2)\end{array}.$$

Algorithm 5 SVM training via subgradient descent

• $\{(a_i,b_i)\}$,
• $T\in \mathbb{N}$,
• $x_1:=0$,
• ${\eta }_t:=\frac{2}{t+1}$,
• $\lambda >0$,
  • regulariztion parameter

Step1.

$$\begin{array}{rcl}{\mathrm{\nabla }}_t& :=& \lambda \frac{1}{n}\sum _{i=1}^n{\ell }_{a_i,b_i}(x_t)+x_t\\ \mathrm{\nabla }{\ell }_{a,b}(x)& =& \{\begin{array}{ll}0& (b{x}^{\mathrm{T}}a>1)\\ -ba& \text{otherwise}\end{array}\end{array}$$

Step2. Update

$$\begin{array}{r}{x}_{t+1}:=x_t-{\eta }_t{\mathrm{\nabla }}_t\end{array}$$

Step3. end for

Step4. Return $\tilde{x}:=\frac{1}{T}\sum _{t=1}^T\frac{2t}{T+1}{x}_t$,

■

Theorem

In Algorithm 5, if $T>\frac{1}{ϵ}$,

$$f(\tilde{x})-f(x^{\ast })\in O(ϵ).$$

proof

■