Introduction to lower bounds in optimization

Proof. We drop the exponents $L,\mu$ in the definition of $f_k=f_k^{L,\mu }$. The function $f_k$ being a quadratic form, it is $C^{\mathrm{\infty }}$ and its partial derivatives read

$$\frac{\partial f_k}{\partial x_i\partial x_j}(x)=\mu 1_{\{i=j\}}+\frac{L-\mu }{4}\{\begin{array}{ll}2& \text{if }i=j\le k\\ -1& \text{if }j=i-1\text{ and }1<i\le k\\ -1& \text{if }j=i+1\text{ and }1\le i<k\\ 0& \text{otherwise.}\end{array}$$

Thus, the Hessian matrix is given (for any $x\in {\mathbb{R}}^d$) by

$${\mathrm{\nabla }}^2{f}_k(x)=\mu {\mathrm{Id}}_d+\frac{L-\mu }{4}{L}_k,$$

where $L_k$ is a (thresholded) discrete Laplacian operator with Dirichlet boundary conditions that is tridiagonal

$$L_k=\left(\begin{array}{cccccc}2& -1& 0& & & \$0_{k,d-k}\$\\ -1& 2& -1& & & \\ & -1& \ddots & \ddots & & \\ & & \ddots & \ddots & -1& \\ & & & -1& 2& \\ 0_{d-k,k}& 0_{d-k,d-k}\end{array}\right).$$

Observe that we have (since $f_k$ is a quadratic form)

$$\begin{array}{rl}{f}_k(x)& =\frac{1}{2}⟨{\mathrm{\nabla }}^2{f}_k(x)x,x⟩-\frac{L-\mu }{4}{x}_1+\frac{L-\mu }{8}.\end{array}$$ Note that:

• 1. The Hessian is definite (resp. semi-definite) positive if $\mu >0$ (resp. $\mu =0$). Indeed,

  $$

  $$\begin{array}{rl}⟨{\mathrm{\nabla }}^2{f}_k(x)h,h⟩& =\mu \Vert h{\Vert }^2+\frac{L-\mu }{4}⟨L_{k}h,h⟩.\end{array}$$ Since $⟨L_{k}h,h⟩=h_1^2+\sum _{i=1}^k(h_{i+1}-h_i{)}^2+h_k^2\ge 0$ for any $h$, the result follows depending on the value of $\mu$.

• 2. Since $(a-b{)}^2\le 2a^2+2b^2$, we have

  $$h_1^2+\sum _{i=1}^k(h_{i+1}-h_i{)}^2+h_k^2\le h_1^2+\sum _{i=1}^k(2h_{i+1}^2+2h_i^2)+h_k^2\le 4\sum _{i=1}^k{h}_i^2\le 4\sum _{i=1}^d{h}_i^2=4\Vert h{\Vert }^2.$$

  Hence,

  $$⟨{\mathrm{\nabla }}^2{f}_k(x)h,h⟩\le \mu \Vert h{\Vert }^2+(L-\mu )\Vert h{\Vert }^2=L\Vert h{\Vert }^2.$$

Thus, we have $\mu \mathrm{Id}⪯{\mathrm{\nabla }}^2{f}_k(x)⪯L\mathrm{Id}$.

Let us characterize the (unique) solution $x^{k,\star }$ of the minimization of $f_k$ over ${\mathbb{R}}^d$. We aim to solve $\mathrm{\nabla }{f}_k(x^{k,\star })=0$ to find a critical point (which will be a minimum since we just proved that the Hessian is at least semidefinite positive), that is

$$\mu x^{k,\star }+\frac{L-\mu }{4}{L}_k{x}^{k,\star }-\frac{L-\mu }{4}{e}_1=0.$$

Projecting this relation on each coordinate $2\le i\le k-1$, we get that

$$-x_{i-1}^{k,\star }+2x_i^{k,\star }-x_{i-1}^{k,\star }=-\frac{4\mu }{L-\mu }{x}_i^{k,\star },$$

which leads to

$$x_i^{k,\star }=\frac{1}{2}\frac{L+\mu }{L-\mu }(x_{i+1}^{k,\star }+x_{i-1}^{k,\star }).$$

Similarly, we have

$$x_1^{k,\star }=\frac{1}{2}\frac{L+\mu }{L-\mu }(x_2^{k,\star }+1)\text{and}{x}_k^{k,\star }=\frac{1}{2}\frac{L+\mu }{L-\mu }{x}_{k-1}^{k,\star }.$$

Consider $y_0,\dots ,y_{k+1}$ defined by $y_i=x_i^{k,\star }$ for $1\le i\le k$ and $y_0=1$ and $y_{k+1}=0$. We have the relation

$$y_i=\alpha (y_{i+1}+y_{i-1})\text{where}\alpha =\frac{1}{2}\frac{L+\mu }{L-\mu }>0.$$

We can rewrite it as the second-order linear recursion $y_{i+2}-{\alpha }^{-1}{y}_{i+1}+y_i=0$. The associated trinom is $P=X^2-{\alpha }^{-1}X+1\in \mathbb{R}[X]$ whose discriminant is given by

$$\mathrm{\Delta }=(-{\alpha }^{-1}{)}^2-4=16\frac{L\mu }{(L-\mu {)}^2}.$$

We distinguish two cases:

• 1. If $\mu =0$, then the unique root is given by $r=1$.

• 2. If $\mu >0$, then the roots are given by

  $$

  $$\begin{array}{rl}r& =\frac{1}{2}({\alpha }^{-1}-\sqrt{\mathrm{\Delta }})=\frac{\sqrt{\frac{L}{\mu }}-1}{\sqrt{\frac{L}{\mu }}+1}=\frac{\sqrt{K_f}-1}{\sqrt{K_f}+1}\\ s& =\frac{1}{2}({\alpha }^{-1}+\sqrt{\mathrm{\Delta }})=\frac{\sqrt{K_f}+1}{\sqrt{K_f}-1}=\frac{1}{r}.\end{array}$$

Case $\mu =0$. We have the affine relation $y_i=(a+bi)r$ with constraints $y_0=a=1$ and $y_{k+1}=a+b(k+1)=0$. In turn, we have $y_i=1-\frac{i}{k+1}$ and thus

$$x_i^{k,\star }=\{\begin{array}{ll}1-\frac{i}{k+1}& \text{if }1\le i\le k\\ 0& \text{otherwise.}\end{array}$$

The associated optimal value is given by

$$f_k(x^{k,\star })=\frac{L}{8}((-\frac{1}{k+1})+\sum _{i=1}^{k-1}\frac{1}{(k+1{)}^2}+{(1-\frac{k}{k+1})}^2)=\frac{L}{8}\frac{k+1}{(k+1{)}^2}=\frac{L}{8}\frac{1}{k+1}.$$

Case $\mu >0$. The solution can be written as

$$y_i=a{r}^i+b{s}^i\text{with}\{\begin{array}{ll}a+b& =1\\ a{r}^{k+1}+b{s}^{k+1}& =0.\end{array}$$

Thus, we have $b=1-a$, hence $\frac{a}{a-1}=s^{2(k+1)}>0$, and in turn we have

$$a=\frac{s^{2(k+1)}}{s^{2(k+1)}-1}\text{and}b=\frac{1}{1-s^{2(k+1)}}.$$

Hence,

$$y_i=\frac{s^{2(k+1)}}{s^{2(k+1)}-1}{s}^{-i}+\frac{1}{1-s^{2(k+1)}}{s}^i.$$

□

Proof of Theorem 1. We restrict our attention the the case where $x_0=0$ w.l.o.g. Indeed, if $x_0\ne 0$, we can set $x\mapsto \tilde{f}(x)=f(x+x_0)$ and the following proof carry on. Let $d=2k+1$ and set $f=f_{2k+1}^{L,0}$.

Remark that

$$f(x^{(t)})=f_{2k+1}^{L,0}(x^{(t)})=f_t^{L,0}(x^{(t)})\ge f_t^{\star }.$$

Using Lemma 1, we have on one hand that $f_t^{\star }=\frac{L}{8(t+1)}$, and then

$$f(x^{(t)})-f(x^{\star })=\frac{L}{8(k+1)}-\frac{L}{8\dot{2}(k+1)}=\frac{L}{16(k+1)}.$$

On the other hand,

$$\begin{array}{rl}& \Vert x^{2k+1,\star }-x_0{\Vert }^2=\Vert x^{2k+1,\star }{\Vert }^2=\sum _{i=1}^{2k+1}(x^{2k+1,\star }{)}_i^2\\ & =\sum _{i=1}^{2k+1}{(1-\frac{i}{2(k+1)})}^2\\ & =\sum _{i=1}^{2k+1}1-\frac{2}{2(k+1)}\sum _{i=1}^{2k+1}i+\frac{1}{4(k+1{)}^2}\sum _{i=1}^{2k+1}{i}^2\\ & =(2k+1)-\frac{1}{k+1}\frac{2(k+1)(2k+1)}{2}+\frac{1}{4(k+1{)}^2}\frac{2(k+1)(4k+3)(2k+1)}{6}\\ & =\frac{1}{3}\frac{(2k+1)(4k+3)}{4(k+1)}\\ & \le \frac{2k+1}{3}\le \frac{2}{3}(k+1).\end{array}$$ Thus,

$$\frac{f(x^{(t)})-f(x^{\star })}{\Vert x^{2k+1,\star }-x_0{\Vert }^2}\ge \frac{\frac{L}{16(k+1)}}{\frac{2}{3}(k+1)}=\frac{3L}{32(k+1{)}^2},$$

that proves (2).

□

Proof of Theorem 2. The proof follows the same strategy as before, but we start with a bound on the iterates instead of the objective function. Assume that $x^{(0)}=0$, otherwise let $\tilde{f}=f(\cdot +x_0)$. Consider $d=2k+1$ and $f=f_{2k+1}^{L,\mu }$. We rewrite the coordinate of $x^{2k+1,\star }$ as

$$x_i^{2k+1,\star }=\frac{s^{4(k+1)}}{s^{4(k+1)}-1}{s}^{-i}+\frac{1}{1-s^{4(k+1)}}{s}^i=s^{-i}(1-\frac{s^{2i}-1}{s^{4(k+1)}-1}).$$

On one hand, we have:

$$\Vert x^{(0)}-x^{2k+1,\star }{\Vert }^2=\sum _{i=1}^{2k+1}(x_i^{2k+1,\star }{)}^2=\sum _{i=1}^{2k+1}{s}^{-2i}{(1-\frac{s^{2i}-1}{s^{4(k+1)}-1})}^2\le \sum _{i=1}^{2k+1}{s}^{-2i},$$

where we used that for all $1\le i\le 2k+1$, we have

$$0\le 1-\frac{s^{2i}-1}{s^{4(k+1)}-1}\le 1.$$

Bounding the tail of the geometric sums, we obtain

$$\begin{array}{}\text{(6)}& \Vert x^{(0)}-x^{2k+1,\star }{\Vert }^2\le 2\sum _{i=1}^{k+1}{s}^{-2i}.\end{array}$$

On the other hand, observe that for $t<k+1$, one has $x^{(t)}\in {\mathbb{R}}^{k,2k+1}$, thus

$$\Vert x^{(t)}-x^{2k+1,\star }{\Vert }^2\ge \sum _{i=k+1}^{2k+1}(x_i^{2k+1,\star }{)}^2=\sum _{i=k+1}^{2k+1}{s}^{-2i}{(1-\frac{s^{2i}-1}{s^{4(k+1)}-1})}^2.$$

Since $s>0$, we have

$$\frac{1-s^{2i}}{s^{4(k+1)}-1}\le \frac{1-s^{2(k+1)}}{s^{4(k+1)}-1},$$

and in turn,

$$1\ge {(1-\frac{s^{2i}-1}{s^{4(k+1)}-1})}^2\ge {(1-\frac{s^{2(k+1)}-1}{s^{4(k+1)}-1})}^2\ge 0.$$

Thus,

$$\begin{array}{rl}\Vert x^{(k)}-x^{2k+1,\star }{\Vert }^2& \ge {(1-\frac{s^{2(k+1)}-1}{s^{4(k+1)}-1})}^2\sum _{i=k+1}^{2k+1}{s}^{-2i}\\ \text{(7)}& & ={(1-\frac{s^{2(k+1)}-1}{s^{4(k+1)}-1})}^2{s}^{-2k}\sum _{i=1}^{k+1}{s}^{-2i}.\end{array}$$ Observe that

$${(1-\frac{s^{2(k+1)}-1}{s^{4(k+1)}-1})}^2\ge \frac{1}{4}.$$

Combining it with (6) and (7), we have

$$\Vert x^{(t)}-x^{2k+1,\star }{\Vert }^2\ge \frac{1}{8}{s}^{-2k}\Vert x^{(0)}-x^{2k+1,\star }{\Vert }^2\ge \frac{1}{8}{\left(\frac{\sqrt{K_f}-1}{\sqrt{K_f}+1}\right)}^{2t}\Vert x^{(0)}-x^{2t+1,\star }{\Vert }^2,$$

proving (4). The value bound (5) is obtained by applying the following inequality

$$f(x)\ge f(x^{\star })+\frac{\mu }{2}\Vert x-x^{\star }{\Vert }^2,$$

to $f$. □