.md .pdf

repository open issue

Contents

10.1. Basic Subgradient Method

The theory of subgradients for convex functions is discussed in Subgradients. This section discusses basic subgradient method for optimization. Primary references for this section are [8].

Recall that a vector $\mathbf{g}$ is a subgradient of $f$ at a point $\mathbf{x}$ if

$$f(\mathbf{y})\ge f(\mathbf{x})+⟨\mathbf{y}-\mathbf{x},\mathbf{g}⟩\mathrm{\forall }\mathbf{y}\in {\mathbb{R}}^n.$$

10.1.1. Unconstrained Minimization

We start with a simple case of minimizing a convex function $f:{\mathbb{R}}^n\to \mathbb{R}$.

1. The optimal value shall be denoted by $f^{\ast }$.

2. We shall assume that the optimal value is finite (i.e., $f^{\ast }>-\mathrm{\infty }$).

3. The set of optimal minimizers shall be denoted by $X^{\ast }$.

4. Since $f$ attains its optimal value, hence $X^{\ast }$ is nonempty.

5. A global minimizer will be denoted by ${\mathbf{x}}^{\ast }$.

The basic subgradient method uses the following iteration.

(10.1)$${\mathbf{x}}^{k+1}={\mathbf{x}}^k-t_k{\mathbf{g}}^k.$$

In this iteration

1. ${\mathbf{x}}^k$ is the current ($k$-th) iterate.

2. ${\mathbf{g}}^k$ is any subgradient of $f$ at ${\mathbf{x}}^k$. We have ${\mathbf{g}}^k\in \partial f({\mathbf{x}}^k)$.

3. $t_k>0$ is the step size for the $k$-th iteration in the negative subgradient direction $-{\mathbf{g}}^k$.

4. ${\mathbf{x}}^{k+1}$ is the new ($k+1$-th) iterate.

5. $\Vert t_k{\mathbf{g}}^k{\Vert }_2$ denotes the step-length.

Thus, in each iteration of the subgradient method, we take a step in the direction of a negative subgradient.

10.1.1.1. Descent Directions

Observation 10.1 (Negative subgradient need not be a descent direction)

1. Recall from Definition 9.22 that a descent direction of $f$ at $\mathbf{x}$ is a direction along which the directional derivative is negative; i.e., $f^{\prime }(\mathbf{x};\mathbf{d})<0$.

2. If $\mathbf{d}$ is a descent direction at $\mathbf{x}$, then there exists a step size $t>0$ such that

   $$f(\mathbf{x}+t\mathbf{d})<f(\mathbf{x}).$$

3. If $f$ is a differentiable function and $\mathbf{d}=-\mathrm{\nabla }f(\mathbf{x})$, then

   $$f^{\prime }(\mathbf{x};-\mathrm{\nabla }f(\mathbf{x}))=-\Vert \mathrm{\nabla }f(\mathbf{x}){\Vert }^2\le 0.$$

4. Hence, the negative gradient is always a descent direction if the gradient is nonzero.

5. However, for a nondifferentiable function $f$, a negative subgradient may not be a descent direction.

6. Recall from max formula (Theorem 8.219) that

   $$f^{\prime }(\mathbf{x};\mathbf{d})=sup\{⟨\mathbf{d},\mathbf{g}⟩|\mathbf{g}\in \partial f(\mathbf{x})\}.$$

7. Let $\tilde{\mathbf{g}}$ be the chosen subgradient at an iteration of the subgradient method.

8. Then

   $$f^{\prime }(\mathbf{x};-\tilde{\mathbf{g}})=\underset{\mathbf{g}\in \partial f(\mathbf{x})}{sup}\{⟨-\tilde{\mathbf{g}},\mathbf{g}⟩\}=-\underset{\mathbf{g}\in \partial f(\mathbf{x})}{inf}\{⟨\tilde{\mathbf{g}},\mathbf{g}⟩\}.$$

9. It is possible that the quantity $⟨\tilde{\mathbf{g}},\mathbf{g}⟩$ is negative for some other subgradient $\mathbf{g}$ at $\mathbf{x}$.

10. Hence the directional derivative along $-\tilde{\mathbf{g}}$ may be positive.

11. This argument shows that a negative subgradient is not necessarily a descent direction.

10.1.1.2. Tracking of the Best Estimate

1. Since the negative subgradient $-{\mathbf{g}}^k$ may not be a descent direction, hence it is quite likely that $f({\mathbf{x}}^{k+1})>f({\mathbf{x}}^k)$.

2. Even if the selected $-{\mathbf{g}}^k$ is a descent direction at ${\mathbf{x}}^k$, it is possible that the step size can be such that $f({\mathbf{x}}^{k+1})>f({\mathbf{x}}^k)$.

3. This happens since typically there is no local line search method invoked to select an appropriate step size in a subgradient method.

4. Since the negative subgradient itself may not be a descent direction, hence running a local line search will be futile.

5. The alternative is to track the best estimate of the optimal value so far using the following rule

   $$f_{\mathrm{best}}^k=min\{f_{\mathrm{best}}^{k-1},f({\mathbf{x}}^k)\}.$$

6. If the best estimate has decreased, we also update the estimate of the local minimizer as ${\mathbf{x}}_{\mathrm{best}}$ to ${\mathbf{x}}^{k+1}$.

7. It is easy to see that

   $$f_{\mathrm{best}}^k=min\{f({\mathbf{x}}^1),\dots ,f({\mathbf{x}}^k)\}.$$

8. We can see that the sequence $\{f_{\mathrm{best}}^k\}$ is a nonincreasing sequence.

9. Hence it has a limit.

10. The success of the subgradient method depends on whether the limit equals the optimal value.

10.1.1.3. Step Size Selection

In a gradient descent method, one typically uses a line search method to select the step size. Hence, it depends on current iterate and the function values in its neighborhood.

In a subgradient method, the step size selection is different. Typically, the step sizes (or step lengths) are determined beforehand and they don’t depend on the data computed during the execution of the algorithm. Following are some of the common methods for step size selection.

1. Constant step size. $t_k=t$ for some positive constant $t>0$ which is independent of $k$.

2. Constant step length.

   $$t_k=\frac{c}{\Vert {\mathbf{g}}^k{\Vert }_2}$$

   where $c>0$ is a predefined step length. Note that with this choice of step size, we have:

   $$\Vert {\mathbf{x}}^{k+1}-{\mathbf{x}}^k{\Vert }_2=\Vert t_k{\mathbf{g}}^k{\Vert }_2=c.$$

3. Square summable but not summable. We choose step sizes that satisfy the following constraints:

   $$t_k>0\mathrm{\forall }k,\sum _{k=1}^{\mathrm{\infty }}{t}_k^2<\mathrm{\infty },\sum _{k=1}^{\mathrm{\infty }}{t}_k=\mathrm{\infty }.$$

   As an example, fix some $a>0$ and $b\ge 0$ and let

   $$t_k=\frac{a}{b+k}.$$

4. Nonsummable diminishing. We choose step sizes that satisfy the following constraints:

   $$t_k>0\mathrm{\forall }k,\underset{k\to \mathrm{\infty }}{lim}{t}_k=0,\sum _{k=1}^{\mathrm{\infty }}{t}_k=\mathrm{\infty }.$$

   As and example, fix some $a>0$ and let

   $$t_k=\frac{a}{\sqrt{k}}.$$

5. Nonsummable diminishing step lengths: We choose step sizes as $t_k=\frac{c_k}{\Vert {\mathbf{g}}^k{\Vert }_2}$ where

   $$c_k>0,\underset{k\to \mathrm{\infty }}{lim}{c}_k=0,\sum _{k=1}^{\mathrm{\infty }}{c}_k=\mathrm{\infty }.$$

10.1.1.4. The Subgradient Method

We now present the overall template for the subgradient method.

Algorithm 10.1 (The subgradient method)

Inputs

1. $f$ : function to be minimized

2. ${\mathbf{x}}^1$: initial guess for the minimizer

3. $t_1$: initial step size

Outputs

1. $f_{\mathrm{best}}^1$: Best estimate of minimum value of $f$

2. ${\mathbf{x}}_{\mathrm{best}}^1$ the best estimate of the minimizer

Initialization

1. $f_{\mathrm{best}}=f({\mathbf{x}}^1)$.

2. ${\mathbf{x}}_{\mathrm{best}}={\mathbf{x}}^1$.

General iteration: for $k=1,2,\dots$, execute the following steps

1. Select a subgradient ${\mathbf{g}}^k$ from $\partial f({\mathbf{x}}^k)$.

2. Select a step size: $t_k$.

3. Update minimizer estimate: ${\mathbf{x}}^{k+1}={\mathbf{x}}^k-t_k{\mathbf{g}}^k$.

4. $k=k+1$.

5. Compute $f({\mathbf{x}}^k)$.

6. if $f_{\mathrm{best}}^{k-1}>f({\mathbf{x}}^k)$:

   1. Update best estimate of optimal value: $f_{\mathrm{best}}^k=f({\mathbf{x}}^k)$.

   2. Update best estimate of minimizer: ${\mathbf{x}}_{\mathrm{best}}^k={\mathbf{x}}^k$.

7. Otherwise, retain current values

   1. $f_{\mathrm{best}}^k=f_{\mathrm{best}}^{k-1}$.

   2. ${\mathbf{x}}_{\mathrm{best}}^k={\mathbf{x}}_{\mathrm{best}}^{k-1}$.

8. If stopping criterion is met, then STOP.

For a concrete implementation, we shall need the following:

1. A way to compute $f(\mathbf{x})$ at every $\mathbf{x}$.

2. A way to pick a subgradient $\mathbf{g}\in \partial f(\mathbf{x})$ at every $\mathbf{x}$.

3. A step size selection strategy.

4. A stopping criterion.

Note that there is no need to specify the complete subdifferential at every $\mathbf{x}$. The stopping criterion will be developed in the following as part of the convergence analysis of the algorithm.

10.1.2. Convergence Analysis

Our goal is to show that $f_{\mathrm{best}}^k\downarrow f^{\ast }$. Towards this, we will establish a suboptimality bound on the estimate of the optimal value after $k$ iterations.

We shall make the following assumptions in the analysis.

1. $f$ is a real valued convex function.

2. The optimal value $f^{\ast }$ is finite and the minimizer ${\mathbf{x}}^{\ast }$ exists.

3. The norm of the subgradients is bounded. i.e., there exists $G>0$ such that

   $$\Vert \mathbf{g}{\Vert }_2\le G\mathrm{\forall }\mathbf{g}\in \partial f(\mathbf{x})\mathrm{\forall }\mathbf{x}.$$

   Recall from Theorem 8.232 that if a convex function is Lipschitz continuous, then its subgradients are bounded.

4. A number $R$ that satisfies

   $$R\ge \Vert {\mathbf{x}}^{\ast }-{\mathbf{x}}^1{\Vert }_2$$

   for some ${\mathbf{x}}^{\ast }\in X^{\ast }$ is known beforehand. $R$ can be interpreted as an upper bound on the distance of the initial point to the set of optimal minimizers.

   $$R\ge \text{dist}({\mathbf{x}}^1,X^{\ast }).$$

Theorem 10.1 (Suboptimality bound for subgradient method)

Let $\Vert {\mathbf{x}}^1-{\mathbf{x}}^{\ast }{\Vert }_2\le R$.

After $k$ iterations of the subgradient method, we have

(10.2)$$f_{\mathrm{best}}^k-f^{\ast }\le \frac{R^2+\sum _{i=1}^k{t}_i^2\Vert {\mathbf{g}}_i{\Vert }_2^2}{2\sum _{i=1}^k{t}_i}.$$

If the subgradients of $f$ are bounded by $\Vert \mathbf{g}\Vert \le G$ for all $\mathbf{g}\in \partial f(\mathbf{x})$ for every $\mathbf{x}$, then this simplifies to:

(10.3)$$f_{\mathrm{best}}^k-f^{\ast }\le \frac{R^2+G^2\sum _{i=1}^k{t}_i^2}{2\sum _{i=1}^k{t}_i}.$$

Proof. Let ${\mathbf{x}}^{\ast }$ be a minimizer of $f$. From the subgradient inequality, we have

$$f^{\ast }=f({\mathbf{x}}^{\ast })\ge f({\mathbf{x}}^k)+⟨{\mathbf{x}}^{\ast }-{\mathbf{x}}^k,{\mathbf{g}}^k⟩.$$

Hence

$$⟨{\mathbf{x}}^{\ast }-{\mathbf{x}}^k,{\mathbf{g}}^k⟩\le f^{\ast }-f({\mathbf{x}}^k).$$

We first develop an upper bound on the distance between the $k+1$-th iterate and a minimizer.

$$\begin{array}{rl}\Vert {\mathbf{x}}^{k+1}-{\mathbf{x}}^{\ast }{\Vert }_2^2& =\Vert {\mathbf{x}}^k-t_k{\mathbf{g}}^k-{\mathbf{x}}^{\ast }{\Vert }_2^2\\ & =\Vert ({\mathbf{x}}^k-{\mathbf{x}}^{\ast })-t_k{\mathbf{g}}^k{\Vert }_2^2\\ & =\Vert {\mathbf{x}}^k-{\mathbf{x}}^{\ast }{\Vert }_2^2-2t_k⟨{\mathbf{x}}^k-{\mathbf{x}}^{\ast },{\mathbf{g}}^k⟩+t_k^2\Vert {\mathbf{g}}^k{\Vert }_2^2\\ & \le \Vert {\mathbf{x}}^k-{\mathbf{x}}^{\ast }{\Vert }_2^2-2t_k(f({\mathbf{x}}^k)-f^{\ast })+t_k^2\Vert {\mathbf{g}}^k{\Vert }_2^2.\end{array}$$

Applying this inequality recursively, we get

$$\Vert {\mathbf{x}}^{k+1}-{\mathbf{x}}^{\ast }{\Vert }_2^2\le \Vert {\mathbf{x}}^1-{\mathbf{x}}^{\ast }{\Vert }_2^2-2\sum _{i=1}^k{t}_i(f({\mathbf{x}}^i)-f^{\ast })+\sum _{i=1}^k{t}_i^2\Vert {\mathbf{g}}^i{\Vert }_2^2.$$

Using the fact that $\Vert {\mathbf{x}}^{k+1}-{\mathbf{x}}^{\ast }{\Vert }_2^2\ge 0$ and $\Vert {\mathbf{x}}^1-{\mathbf{x}}^{\ast }{\Vert }_2\le R$, we have

$$2\sum _{i=1}^k{t}_i(f({\mathbf{x}}^i)-f^{\ast })\le R^2+\sum _{i=1}^k{t}_i^2\Vert {\mathbf{g}}^i{\Vert }_2^2.$$

On the L.H.S., we can see that

$$\sum _{i=1}^k{t}_i(f({\mathbf{x}}^i)-f^{\ast })\ge \left(\sum _{i=1}^k{t}_i\right)\underset{i=1,\dots ,k}{min}(f({\mathbf{x}}^i)-f^{\ast })=\left(\sum _{i=1}^k{t}_i\right)(f_{\mathrm{best}}^k-f^{\ast }).$$

Combining this with the previous inequality, we get

$$2\left(\sum _{i=1}^k{t}_i\right)(f_{\mathrm{best}}^k-f^{\ast })\le R^2+\sum _{i=1}^k{t}_i^2\Vert {\mathbf{g}}^i{\Vert }_2^2.$$

This can be rewritten as

$$f_{\mathrm{best}}^k-f^{\ast }\le \frac{R^2+\sum _{i=1}^k{t}_i^2\Vert {\mathbf{g}}_i{\Vert }_2^2}{2\sum _{i=1}^k{t}_i}$$

as desired.

Applying the upper bound on the subgradient $\Vert \mathbf{g}{\Vert }_2\le G$, we have

$$f_{\mathrm{best}}^k-f^{\ast }\le \frac{R^2+G^2\sum _{i=1}^k{t}_i^2}{2\sum _{i=1}^k{t}_i}$$

as desired.

Based on this result, we can provide upper bounds on the estimation error for different step size selection strategies.

10.1.2.1. Constant Step Size

Corollary 10.1 (Convergence of subgradient method with constant step size)

If $t_k=t$ for all $k$, then we have

$$f_{\mathrm{best}}^k-f^{\ast }\le \frac{R^2+G^2{t}^{2}k}{2tk}.$$

The subgradient method converges to within $G^{2}t/2$ of the optimal value $f^{\ast }$. In other words,

$$\underset{k\to \mathrm{\infty }}{lim}{f}_{\mathrm{best}}^k-f^{\ast }\le \frac{G^{2}t}{2}.$$

Also, $f_{\mathrm{best}}^k-f^{\ast }\le G^{2}t$ within at most $R^2/(G^2{t}^2)$ steps.

Proof. By putting $t_k=t$ in (10.3), we obtain the desired upper bound. Taking the limit $k\to \mathrm{\infty }$, we see that

$$\underset{k\to \mathrm{\infty }}{lim}(f_{\mathrm{best}}^k-f^{\ast })\le \frac{G^{2}t}{2}.$$

Now,

$$\begin{array}{rl}& \frac{R^2+G^2{t}^{2}k}{2tk}\le G^{2}t\\ ⟺& R^2+G^2{t}^{2}k\le 2G^2{t}^{2}k\\ ⟺& R^2\le G^2{t}^{2}k\\ ⟺& k\ge \frac{R^2}{G^2{t}^2}.\end{array}$$

Since $f_{\mathrm{best}}^k$ is a nonincreasing sequence, hence for all $k\ge R^2/(G^2{t}^2)$, we must have

$$f_{\mathrm{best}}^k-f^{\ast }\le G^{2}t.$$

10.1.2.2. Constant Step Length

Corollary 10.2 (Convergence of subgradient method with constant step length)

Let $c$ be the constant step length for the subgradient method. Let $t_k=\frac{c}{\Vert {\mathbf{g}}^k{\Vert }_2}$ for every $k$. Then we have

$$f_{\mathrm{best}}^k-f^{\ast }\le \frac{R^2+c^{2}k}{2ck/G}.$$

The subgradient method converges to within $Gc/2$ of the optimal value $f^{\ast }$. In other words,

$$\underset{k\to \mathrm{\infty }}{lim}{f}_{\mathrm{best}}^k-f^{\ast }\le \frac{Gc}{2}.$$

Proof. By putting $t_i=\frac{c}{\Vert {\mathbf{g}}^i{\Vert }_2}$ in (10.2), we see that

$$f_{\mathrm{best}}^k-f^{\ast }\le \frac{R^2+\sum _{i=1}^k{c}^2}{2\sum _{i=1}^k{t}_i}.$$

Also, note that

$$\begin{array}{rl}& t_i=\frac{c}{\Vert {\mathbf{g}}^i{\Vert }_2}\\ ⟹& t_i\ge \frac{c}{G}\\ ⟹& \sum _{i=1}^k{t}_i\ge \frac{ck}{G}\\ ⟹& \frac{1}{\sum _{i=1}^k{t}_i}\le \frac{1}{ck/G}.\end{array}$$

Putting this back, we have

$$f_{\mathrm{best}}^k-f^{\ast }\le \frac{R^2+c^{2}k}{2ck/G}.$$

Taking the limit $k\to \mathrm{\infty }$, we see that

$$\underset{k\to \mathrm{\infty }}{lim}(f_{\mathrm{best}}^k-f^{\ast })\le \frac{Gc}{2}.$$

10.1.2.3. Square Summable Step Sizes

Corollary 10.3 (Convergence of subgradient method with square summable step sizes)

Let the step sizes satisfy the rule

$$t_k>0\mathrm{\forall }k,\sum _{k=1}^{\mathrm{\infty }}{t}_k^2<\mathrm{\infty },\sum _{k=1}^{\mathrm{\infty }}{t}_k=\mathrm{\infty }.$$

Further, let $T=\sum _{k=1}^{\mathrm{\infty }}{t}_k^2$.

Then we have

$$f_{\mathrm{best}}^k-f^{\ast }\le \frac{R^2+G^{2}T}{2\sum _{i=1}^k{t}_k}.$$

The subgradient method converges to $f^{\ast }$.

Proof. By putting the step size constraints into (10.3), we obtain

$$f_{\mathrm{best}}^k-f^{\ast }\le \frac{R^2+G^{2}T}{2\sum _{i=1}^k{t}_i}.$$

Taking the limit $k\to \mathrm{\infty }$, the denominator grows to $\mathrm{\infty }$ while the numerator converges to $R^2+G^{2}T$. Hence

$$\underset{k\to \mathrm{\infty }}{lim}{f}_{\mathrm{best}}^k-f^{\ast }=0.$$

10.1.2.4. Diminishing Step Sizes

Corollary 10.4 (Convergence of subgradient method with diminishing step sizes)

Let the step sizes satisfy the rule

$$t_k>0\mathrm{\forall }k,\underset{k\to \mathrm{\infty }}{lim}{t}_k=0,\sum _{k=1}^{\mathrm{\infty }}{t}_k=\mathrm{\infty }.$$

Then the subgradient method converges to $f^{\ast }$.

Proof. We shall show that the R.H.S. of (10.3) converges to 0 as $k\to \mathrm{\infty }$.

1. Let $ϵ>0$.

2. There exists integer $n_1$ such that $t_i\le ϵ/G^2$ for all $i>n_1$ since $t_k\to 0$.

3. There also exists an integer $n_2$ such that

   $$\sum _{i=1}^{n_2}{t}_i\ge \frac{1}{ϵ}(R^2+G^2\sum _{i=1}^{n_1}{t}_i^2)$$

   since $t_i$ is nonsummable.

4. Let $n=max\{n_1,n_2\}$.

5. Then, for every $k>n$, we have

   $$\frac{R^2+G^2\sum _{i=1}^k{t}_i^2}{2\sum _{i=1}^k{t}_i}=\frac{R^2+G^2\sum _{i=1}^{n_1}{t}_i^2}{2\sum _{i=1}^k{t}_i}+\frac{G^2\sum _{i=n_1+1}^k{t}_i^2}{2\sum _{i=1}^{n_1}{t}_i+2\sum _{i=n_1+1}^k{t}_i}.$$

6. We can see that

   $$\sum _{i=1}^k{t}_i\ge \sum _{i=1}^{n_2}{t}_i\ge \frac{1}{ϵ}(R^2+G^2\sum _{i=1}^{n_1}{t}_i^2).$$

7. Hence

   $$\frac{R^2+G^2\sum _{i=1}^{n_1}{t}_i^2}{2\sum _{i=1}^k{t}_i}\le \frac{ϵ}{2}.$$

8. For every $i>n_1$, we have $t_i<ϵ/G^2$.

9. Hence

   $$G^2\sum _{i=n_1+1}^k{t}_i^2\le ϵ\sum _{i=n_1+1}^k{t}_i.$$

10. We can now see that

    $$\begin{array}{rl}& \frac{G^2\sum _{i=n_1+1}^k{t}_i^2}{2\sum _{i=1}^{n_1}{t}_i+2\sum _{i=n_1+1}^k{t}_i}\\ & <\frac{G^2\sum _{i=n_1+1}^k{t}_i^2}{2\sum _{i=n_1+1}^k{t}_i}\\ & \le \frac{ϵ\sum _{i=n_1+1}^k{t}_i}{2\sum _{i=n_1+1}^k{t}_i}\\ & =\frac{ϵ}{2}.\end{array}$$

11. Combining, we have

    $$\frac{R^2+G^2\sum _{i=1}^k{t}_i^2}{2\sum _{i=1}^k{t}_i}<\frac{ϵ}{2}+\frac{ϵ}{2}=ϵ$$

    for every $k>n$.

12. Thus, for every $ϵ>0$, there exists $n$ such that for all $k>n$, we have

    $$\frac{R^2+G^2\sum _{i=1}^k{t}_i^2}{2\sum _{i=1}^k{t}_i}<ϵ.$$

13. Hence

    $$\underset{k\to \mathrm{\infty }}{lim}\frac{R^2+G^2\sum _{i=1}^k{t}_i^2}{2\sum _{i=1}^k{t}_i}=0.$$

14. Hence the subgradient method converges.

10.1.2.5. Diminishing Step Lengths

Corollary 10.5 (Convergence of subgradient method with diminishing step lengths)

Let the step sizes $t_k=\frac{c_k}{\Vert {\mathbf{g}}^k{\Vert }_2}$ be chosen such that

$$c_k>0,\underset{k\to \mathrm{\infty }}{lim}{c}_k=0,\sum _{k=1}^{\mathrm{\infty }}{c}_k=\mathrm{\infty }$$

where $c_k$ is the step length for the $k$-th iteration.

Then the subgradient method converges to $f^{\ast }$.

Proof. From (10.2) we have

$$f_{\mathrm{best}}^k-f^{\ast }\le \frac{R^2+\sum _{i=1}^k{t}_i^2\Vert {\mathbf{g}}_i{\Vert }_2^2}{2\sum _{i=1}^k{t}_i}=\frac{R^2+\sum _{i=1}^k{c}_i^2}{2\sum _{i=1}^k{t}_i}.$$

1. We have

   $$\sum _{i=1}^k{t}_i=\sum _{i=1}^k\frac{c_i}{\Vert {\mathbf{g}}^i{\Vert }_2}\ge \sum _{i=1}^k\frac{c_i}{G}.$$

2. Hence we have

   $$f_{\mathrm{best}}^k-f^{\ast }\le \frac{R^2+\sum _{i=1}^k{c}_i^2}{(2/G)\sum _{i=1}^k{c}_i}.$$

3. Following an argument similar to the proof of Corollary 10.4, the R.H.S. converges to 0 as $k\to \mathrm{\infty }$.

4. Hence

   $$\underset{k\to \mathrm{\infty }}{lim}{f}_{\mathrm{best}}^k-f^{\ast }=0.$$

10.1.2.6. On the Suboptimality Bound

If we run the subgradient method for $k$ iterations, we get a suboptimality bound given by (10.3).

$$f_{\mathrm{best}}^k-f^{\ast }\le \frac{R^2+G^2\sum _{i=1}^k{t}_i^2}{2\sum _{i=1}^k{t}_i}.$$

A natural question is how tight can this bound be by an appropriate selection of step sizes $t_1,\dots ,t_k$.

1. Note that the R.H.S. is a convex and symmetric function of $t_1,\dots ,t_k$.

2. Hence, at the optimal value, we must have $t_1=\cdots =t_k$.

3. Let $t=t_1=\cdots =t_k$.

4. Then the suboptimality bound reduces to

   $$\frac{R^2+G^{2}k{t}^2}{2kt}.$$

5. This is minimized at $t=\frac{R}{G\sqrt{k}}$.

6. In other words, the finite sequence of step-sizes $t_1,\dots ,t_k$ that minimizes the suboptimality bound in (10.3) after exactly $k$ iterations is given by

   $$t_i=\frac{R}{G\sqrt{k}},\mathrm{\forall }i=1,\dots ,k.$$

7. It must be noted that this suboptimality bound is dependent on the number of iterations.

8. This choice of constant step size gives us the bound

   $$f_{\mathrm{best}}^k-f^{\ast }\le \frac{RG}{\sqrt{k}}.$$

Theorem 10.2 (A bound on the suboptimality bound)

Let $t_1,\dots ,t_k$ be any choice of step sizes for the subgradient method for $k$ iterations. Then we must have

$$\frac{R^2+G^2\sum _{i=1}^k{t}_i^2}{2\sum _{i=1}^k{t}_i}\ge \frac{RG}{\sqrt{k}}$$

where the L.H.S. is the step-size selection dependent suboptimality bound on $f_{\mathrm{best}}^k-f^{\ast }$.

Accordingly, the number of steps required to achieve a guaranteed accuracy of $f_{\mathrm{best}}^k-f^{\ast }\le ϵ$ for some $ϵ>0$ is at least $(RG/ϵ{)}^2$ as per the suboptimality bound (10.3) irrespective of the step size selection.

Proof. We have already shown that the suboptimality bound is minimized by the constant step size selection where $t_i=\frac{R}{G\sqrt{k}}$ for every $i=1,\dots ,k$ and is given by $\frac{RG}{\sqrt{k}}$.

1. Let $ϵ>0$ be the required guaranteed accuracy.

2. Then $ϵ\ge \frac{RG}{\sqrt{k}}$ since $\frac{RG}{\sqrt{k}}$ is the minimum guaranteed suboptimality bound after $k$ iterations as per (10.3).

3. Hence we have $\sqrt{k}\ge \frac{RG}{ϵ}$.

4. Hence we have $k\ge {\left(\frac{RG}{ϵ}\right)}^2$.

We note that the suboptimality bound of $ϵ$ can be guaranteed in $k$ iterations only if we use the constant step sizes of $t=\frac{R}{G\sqrt{k}}$.

Observation 10.2 (Interpretation of $RG$)

Initial uncertainty

1. Assume that $f$ is Lipschitz continuous with the constant $G$.

2. By Lipschitz continuity, we have

   $$f^1-f^{\ast }\le G\Vert {\mathbf{x}}^1-{\mathbf{x}}^{\ast }{\Vert }_2\le RG.$$

3. Hence $RG$ is an estimate of the initial uncertainty in $f^{\ast }$.

Reduction in uncertainty

1. If our goal is to achieve $f_{\mathrm{best}}^k-f^{\ast }\le ϵ$, then $ϵ$ is an estimate of the final uncertainty in $f^{\ast }$.

2. Hence $RG/ϵ$ is the ratio of initial uncertainty in $f^{\ast }$ to the final uncertainty in $f^{\ast }$.

3. By Theorem 10.2, we require a minimum of $(RG/ϵ{)}^2$ iterations to achieve this much reduction in uncertainty.

This analysis shows that the subgradient method is very slow. To achieve a 1000x reduction in the uncertainty of $f^{\ast }$, we need a million iterations at least.

previous

10. Subgradient Methods

next

11. Proximal Algorithms