An optimal variant of Kelley’s cutting-plane method

Abstract

We propose a new variant of Kelley’s cutting-plane method for minimizing a nonsmooth convex Lipschitz-continuous function over the Euclidean space. We derive the method through a constructive approach and prove that it attains the optimal rate of convergence for this class of problems.

Appendix: a tight lower-complexity bound

In this appendix, we refine the proof from [22, Sect. 3.2] to obtain a new lower-complexity bound on the class of nonsmooth, convex, and Lipschitz-continuous functions, which together with the results discussed above form a tight complexity result for this class of problems. More precisely, under the setting of Sect. 2.1, we show that for any first-order method, the worst-case absolute inaccuracy after N steps cannot be better than $\frac{LR}{\sqrt{N}}$, which is exactly the bound attained by Algorithm KLM.

In order to simplify the presentation, and following [22, Sect. 3.2], we restrict our attention to first-order methods that generate sequences that satisfy the following assumption:

Assumption 1

The sequence $\{x_i\}$ satisfies

$$\begin{aligned} x_i \in x_1 + \mathrm {span}\{f'(x_1),\dots ,f'(x_{i-1})\}, \end{aligned}$$

where $f'(x_i)\in \partial f(x_i)$ is obtained by evaluating a first-order oracle at $x_i$.

As noted by Nesterov [22, Page 59], this assumption is not necessary and can be avoided by some additional reasoning.

The lower-complexity result is stated as follows.

Theorem 2

For any $L,R>0$, $N,p\in \mathbb {N}$ with $N\le p$, and any starting point $x_1\in \mathbb {R}^p$, there exists a convex and Lipschitz-continuous function $f:\mathbb {R}^p\rightarrow \mathbb {R}$ with Lipschitz constant L and $\Vert x^*_f-x_1\Vert \le R$, and a first-order oracle $\mathcal {O}(x)= (f(x), f'(x))$, such that

$$\begin{aligned} f(x_N)-f^*\ge \frac{LR}{\sqrt{N}} \end{aligned}$$

for all sequences $x_1,\dots ,x_N$ that satisfies Assumption 1.

Proof

The proof proceeds by constructing a “worst-case” function, on which any first-order method that satisfies Assumption 1 will not be able to improve its initial objective value during the first N iterations.

Let $f_N:\mathbb {R}^p\rightarrow \mathbb {R}$ and $\bar{f}_N:\mathbb {R}^p\rightarrow \mathbb {R}$ be defined by

$$\begin{aligned}&f_N(x) = \max _{1\le i \le N} \langle x, e_i\rangle , \\&\bar{f}_N(x) =L\max (f_N(x), \Vert x\Vert -R(1+N^{-1/2})), \end{aligned}$$

then it is easy to verify that $\bar{f}_N$ is Lipschitz-continuous with constant L and that

$$\begin{aligned} \bar{f}_N^*= -\frac{LR}{\sqrt{N}} \end{aligned}$$

is attained for $x^*\in \mathbb {R}^p$ such that

$$\begin{aligned} x^*= -\frac{R}{\sqrt{N}}\sum _{i=1}^N e_i. \end{aligned}$$

We equip $\bar{f}_N$ with the oracle $\mathcal {O}_N(x)= (\bar{f}_N(x), \bar{f}'_N(x))$ by choosing $\bar{f}'_N(x)\in \partial \bar{f}_N(x)$ according to:

$$\begin{aligned} \bar{f}'_N(x) = {\left\{ \begin{array}{ll} L f'_N(x), &{} f_N(x)\ge \Vert x\Vert -R\left( 1+N^{-1/2}\right) ,\\ L\frac{x}{\Vert x\Vert }, &{} f_N(x)< \Vert x\Vert -R\left( 1+N^{-1/2}\right) , \end{array}\right. } \end{aligned}$$

(8.1)

where

$$\begin{aligned} f'_N(x) = e_{i^*}, \quad i^*= \min \{ i : f_N(x)=\langle x, e_i\rangle \}. \end{aligned}$$

(8.2)

We also denote

$$\begin{aligned} \mathbb {R}^{i,p} := \{x\in \mathbb {R}^d : \langle x, e_j\rangle =0,\ i+1\le j\le p\}. \end{aligned}$$

Now, let $x_1,\dots ,x_N$ be a sequence that satisfies Assumption 1 with $f=\bar{f}_N$ and the oracle $\mathcal {O}_N$, where without loss of generality we assume $x_1=0$. Then $\bar{f}'_N(x_1) = e_1$ and we get $x_2\in \mathrm {span}\{\bar{f}'_N(x_1)\}=\mathbb {R}^{1,p}$. Now, from $\langle x_2,e_2\rangle =\dots =\langle x_2,e_N\rangle =0$, we get that $\min \{ i : f_N(x)=\langle x, e_i\rangle \}\le 2$ and it follows by (8.1) and (8.2) that $f'_N(x_2)\in \mathbb {R}^{2,p}$ and $\bar{f}'_N(x_2)\in \mathbb {R}^{2,p}$. Hence, we conclude from Assumption 1 that $x_3 \in \mathrm {span}\{\bar{f}'_N(x_1),\bar{f}'_N(x_2)\}\subseteq \mathbb {R}^{2,p}$. It is straightforward to continue this argument to show that $x_i \in \mathbb {R}^{i-1,p}$ and $\bar{f}'_N(x_i)\in \mathbb {R}^{i,p}$ for $i=1,\dots ,N$, thus $x_N \in \mathbb {R}^{N-1,p}$. Finally, since for every $x\in \mathbb {R}^{N-1,p}$ we have $\bar{f}_N(x)\ge \langle x,e_N\rangle =0$, we immediately get

$$\begin{aligned} \bar{f}_N(x_{N})-\bar{f}_N^*\ge \frac{LR}{\sqrt{N}}, \end{aligned}$$

which completes the proof. $\square$