Introduction to lower bounds in optimization
Lower bounds on the complexity of optimization algorithms
· · AI 3/4 (co-written) · #optimization · PDF · Org
Most of the bounds that are described in the optimization literature are upper bounds of the form \(\norm{x^{(t)} - x^{\star}} \leq \alpha(t)\) or \(f(x^{(t)}) - f(x^{\star}) \leq \alpha(t)\). But what about finding the reverse-side inequality \(\norm{x^{(t)} - x^{\star}} \geq \beta(t)\)? Said otherwise, what can we achieve with a “gradient-descent-like” algorithm?
To formalize this notion, we consider algorithms, here sequences \((x^{(t)})_{t \geq 0}\), that build upon the previous iterates with only access to a first-order oracle:
Assumption 1: First-order method
We assume that a first-order method is given by a sequence \(x^{(t)}\) such that
\[x^{(t)} \in x^{(0)} + \Span \set{ \nabla f(x^{(0)}), \dots, \nabla f(x^{(t-1)}) } .\]We shall note that one can think of a more general way to define first-order methods, but for the sake of the results we aim to prove, such level of generality is enough.
With this assumption in mind, how to design a function adversarial to these type of schemes? The idea is to find a function such that the gradient at step \(t-1\) gives minimal information, i.e., it has a minimal nonzero partial derivatives. A way to define such function is to “stack” quadratic functions with increasing dependencies between variables:
where \(0 \leq \mu < L\) and \(1 \leq k \leq d\).
\[\frac{\partial f_{k}^{L,\mu}}{\partial x_i}(x) =\mu x_i+\frac{L-\mu}{4} \begin{cases} -x_2+2x_1-1 & \text{if } i=1<k,\\ -x_{i+1}+2x_i-x_{i-1} & \text{if } 2\leq i<k,\\ 2x_k-x_{k-1} & \text{if } i=k>1,\\ 2x_1-1 & \text{if } i=k=1,\\ 0 & \text{otherwise.} \end{cases}\]Set \(f = f_{k}^{L,\mu}\). Observe that if we start from \(x^{(0)} = 0\), then
\[x^{(1)} = x^{(0)} - \eta \nabla f(0) = + \eta \frac{L-\mu}{4} e_{1} \in \RR e_{1} ,\]that is only the first coordinate is updated after one iteration. What happens now that we have access to \(x^{(0)}\), \(\nabla f_{k}(x^{(0)})\) and \(\nabla f_{k}(x^{(1)})\)? An algorithm satisfying Assumption 1, we look at
\[x^{(2)} = x^{(0)} + \alpha \nabla f(x^{(0)}) + \beta \nabla f(x^{(1)}) .\]One can check that for any \((\alpha,\beta)\), \(x^{(2)} \in \RR e_{1} + \RR e_{2}\), and by an easy induction, we have \(x^{(t)} \in \sum_{k=1}^{t} \RR e_{k}\): any first-order methods will only be able to update at most one new coordinate at each iteration. We are going to prove the following result.
Theorem 2: Lower-bound for smooth convex optimization
For any \(d \geq 2\), \(x^{(0)} \in \RR^{d}\), \(L > 0\), \(t\in\NN\), \(0\leq t\leq(d-1)/2\), there exists a convex function \(f\) that is \(C^{\infty}\) and \(L\)-smooth such that any sequence satisfying Assumption 1 is such that
where \(x^{\star}\) is a minimizer of \(f\).
Remark that the rate \(1/t^{2}\) is not achieved by the gradient descent1! We also have a lower bound for the class of strongly convex functions.
Theorem 3: Lower-bound for smooth strongly convex optimization
For any \(d \geq 2\), \(x^{(0)} \in \RR^{d}\), \(0<\mu<L\), there exists a \(\mu\)-strongly convex function \(f\) that is \(C^{\infty}\) and \(L\)-smooth such that any sequence satisfying Assumption 1 is such that for all \(t\in\NN\) with \(0\leq t\leq(d-1)/2\), we have
where \(x^{\star}\) is the unique minimizer of \(f\) and \(K_f=L/\mu\).
Note that it is common in the literature to see Theorem 3 without the factor \(\frac{1}{8}\). This is due to an artifact of the proof since we prove this result in the finite dimensional case whereas Nesterov (2018) works in the infinite dimensional space \(\ell^{2}(\NN)\). Before proving these important results due to (Nemirovski & Yudin, 1983), we are going to prove several lemmas.
Lemma 4: Minimizers of \(f_{k}\)
Let \(d\geq 2\), \(L>0\), \(0\leq\mu<L\) and \(1\leq k\leq d\), then \(f_{k}^{L,\mu}\) defined in (1) is a \(\mu\)-strongly convex (eventually convex if \(\mu=0\)) \(C^{\infty}\)-function such that its gradient is \(L\)-Lipschitz.
If \(\mu=0\), it has a minimizer \(x^{k,\star}\) satisfying
\begin{equation*} x_{i}^{k,\star} = \begin{cases} 1 - \frac{i}{k+1} & \text{if } 1 \leq i \leq k \\ 0 & \text{otherwise,} \end{cases} \quad \text{and} \quad f_{k}^{L,0}(x^{k,\star}) = \frac{L}{8(k+1)} . \end{equation*}This minimizer is unique if \(k=d\). If \(k<d\), every minimizer has the displayed first \(k\) coordinates, while its remaining coordinates are arbitrary; the display chooses them to be zero.
If \(\mu>0\), it has a unique minimizer \(x^{k,\star}\) satisfying
\begin{equation*} x_{i}^{k,\star} = \frac{s^{2(k+1)}}{s^{2(k+1)} - 1} s^{-i} + \frac{1}{1 - s^{2(k+1)}} s^{i} , \end{equation*}for \(1 \leq i \leq k\), and \(x_{i}^{k,\star} = 0\) for \(i > k\), where \(s = \frac{\sqrt{K_{f}} + 1}{\sqrt{K_{f}} - 1}\).
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^{\infty}\) and its partial derivatives read
\[\frac{\partial^2 f_{k}}{\partial x_{i} \partial x_{j}}(x) = \mu 1_{\set{i=j}} + \frac{L - \mu}{4} \begin{cases} 2 & \text{if } i = j \leq k \\ - 1 & \text{if } j = i-1 \text{ and } 1 < i \leq k \\ - 1 & \text{if } j = i+1 \text{ and } 1 \leq i < k \\ 0 & \text{otherwise.} \end{cases}\]Thus, the Hessian matrix is given (for any \(x \in \RR^{d}\)) by
\[\nabla^{2} f_{k}(x) = \mu \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}{ccccc|c} 2 & -1 & 0 & & & \\ -1 & 2 & -1 & & & \\ & -1 & \ddots & \ddots & & 0_{k,d-k} \\ & & \ddots & \ddots & -1 & \\ & & & -1 & 2 & \\ \hline & & 0_{d-k,k} & & & 0_{d-k,d-k} \end{array} \right) .\]Observe that we have (since \(f_{k}\) is a quadratic form)
\begin{align*} f_{k}(x) &= \frac{1}{2} \dotp{\nabla^{2} f_{k}(x)x}{x} - \frac{L-\mu}{4} x_{1} + \frac{L-\mu}{8} . \end{align*}Note that:
The Hessian is definite (resp. semi-definite) positive if \(\mu>0\) (resp. \(\mu = 0\)). Indeed,
\[\begin{align*} \dotp{\nabla^{2} f_{k}(x)h}{h} &= \mu \norm{h}^{2} + \frac{L-\mu}{4} \dotp{L_{k} h}{h} . \end{align*}\]Since \(\dotp{L_{k} h}{h} = h_{1}^{2} + \sum_{i=1}^{k-1} (h_{i+1} - h_{i})^{2} + h_{k}^{2} \geq 0\) for any \(h\), the result follows depending on the value of \(\mu\).
Since \((a-b)^{2} \leq 2a^{2} + 2b^{2}\), we have
\[ \begin{aligned} &h_{1}^{2} + \sum_{i=1}^{k-1} (h_{i+1} - h_{i})^{2} + h_{k}^{2}\\ &\leq h_{1}^{2} + \sum_{i=1}^{k-1} ( 2 h_{i+1}^{2} + 2 h_{i}^{2} ) + h_{k}^{2}\\ &\leq 4 \sum_{i=1}^{k} h_{i}^{2} \leq 4 \sum_{i=1}^{d} h_{i}^{2} = 4 \norm{h}^{2}. \end{aligned} \]Hence,
\[ \dotp{\nabla^{2} f_{k}(x)h}{h} \leq \mu \norm{h}^{2} + (L - \mu) \norm{h}^{2} = L \norm{h}^{2} . \]
Thus, we have \(\mu \Id \preceq \nabla^{2} f_{k}(x) \preceq L \Id\).
Let us characterize a solution \(x^{k,\star}\), unique if \(\mu>0\) or \(k=d\) of the minimization of \(f_{k}\) over \(\RR^{d}\). We aim to solve \(\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 \leq i \leq k-1\), we get that
\[-x_{i-1}^{k,\star} + 2 x_{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}) .\]For the following two boundary equations, assume \(k\geq 2\). If \(k=1\), the single equation gives \(x_1^{1,\star}=(L-\mu)/(2(L+\mu))\). The boundary notation below covers both cases.
Similarly, we have
\[x_{1}^{k,\star} = \frac{1}{2} \frac{L-\mu}{L+\mu} (x_{2}^{k,\star} + 1) \quad \text{and} \quad 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 \leq i \leq k\) and \(y_{0} = 1\) and \(y_{k+1} = 0\). We have the relation
\[y_{i} = \alpha (y_{i+1} + y_{i-1}) \quad \text{where} \quad \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 \RR[X]\) whose discriminant is given by
\[\Delta = (-\alpha^{-1})^{2} - 4 = 16 \frac{L\mu}{(L - \mu)^{2}} .\]We distinguish two cases:
- If \(\mu = 0\), then the unique root is given by \(r = 1\).
If \(\mu > 0\), then the roots are given by
\[\begin{align*} r &= \frac{1}{2}(\alpha^{-1} - \sqrt{\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{\Delta}) = \frac{\sqrt{K_{f}} + 1}{\sqrt{K_{f}} - 1} = \frac{1}{r}. \end{align*}\]
Case \(\mu=0\). We have the affine relation \(y_{i} = (a + b i) 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
\begin{equation*} x_{i}^{k,\star} = \begin{cases} 1 - \frac{i}{k+1} & \text{if } 1 \leq i \leq k \\ 0 & \text{otherwise.} \end{cases} \end{equation*}The associated optimal value is given by
\[\begin{aligned} f_{k}(x^{k,\star}) &= \frac{L}{8} \left( \left( -\frac{1}{k+1} \right)^2 + \sum_{i=1}^{k-1} \frac{1}{(k+1)^{2}} + \left(1 - \frac{k}{k+1}\right)^{2} \right)\\ & = \frac{L}{8} \frac{k+1}{(k+1)^{2}} = \frac{L}{8} \frac{1}{k+1}. \end{aligned}\]Case \(\mu>0\). The solution can be written as
\[y_{i} = a r^{i} + b s^{i} \quad \text{with} \quad \begin{cases} a + b &= 1 \\ a r^{k+1} + b s^{k+1} &= 0. \end{cases}\]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} \quad \text{and} \quad 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} .\]We now turn to the proofs of Theorem 2 and Theorem 3.
Proof (of Theorem 2)
We restrict our attention to the case where \(x^{(0)} = 0\) w.l.o.g. Indeed, if \(x^{(0)} \neq 0\), we can set \(x \mapsto \tilde f(x) = f(x+x^{(0)})\) and the following proof carries on. Let \(k=t\), so that \(2k+1\leq d\), and set \(f=f_{2k+1}^{L,0}\) on \(\RR^d\).
If \(t=0\), then \(f(0)-f(x^\star)=L/16\) and \(\|x^\star\|^2=1/4\), which gives the claimed bound. In what follows, assume \(t=k\geq 1\).
Remark that
\[f(x^{(t)}) = f_{2k+1}^{L,0}(x^{(t)}) = f_{t}^{L,0}(x^{(t)}) \geq f_{t}^{\star} .\]Using Lemma 4, we have on one hand that \(f_{t}^{\star} = \frac{L}{8(t+1)}\), and then
\[\begin{gathered}f(x^{(k)}) - f(x^{\star}) \geq \frac{L}{8(k+1)} - \frac{L}{16(k+1)} = \frac{L}{16(k+1)} .\end{gathered}\]On the other hand,
\begin{align*} &\norm{x^{2k+1,\star} - x^{(0)}}^{2} = \norm{x^{2k+1,\star}}^{2} = \sum_{i=1}^{2k+1} (x^{2k+1,\star})_{i}^{2} \\ &= \sum_{i=1}^{2k+1} \left( 1 - \frac{i}{2(k+1)} \right)^{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)} \\ &\leq \frac{2k+1}{3} \leq \frac{2}{3} (k+1) . \end{align*}Thus,
\[\frac{f(x^{(t)}) - f(x^{\star})}{\norm{x^{2k+1,\star} - x^{(0)}}^{2}} \geq \frac{\frac{L}{16(k+1)}}{\frac{2}{3} (k+1)} = \frac{3L}{32(k+1)^{2}} ,\]that proves (2).
Proof (of Theorem 3)
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)})\). Let \(k=\lfloor(d-1)/2\rfloor\), \(D=2k+1\leq d\), and \(f=f_D^{L,\mu}\) on \(\RR^d\). Note that \(f\) does not depend on \(t\), and that \(0 \leq t \leq k\). Let \(a=\log s>0\). Using Lemma 4, we rewrite the coordinates of \(x^{\star} = x^{D,\star}\) as
\[x_i^{D,\star} = \frac{s^{2(D+1)-i} - s^{i}}{s^{2(D+1)} - 1} = \frac{\sinh((D+1-i)a)}{\sinh((D+1)a)}, \qquad 1\leq i\leq D.\]Since the coordinates of \(x^{(t)}\) after the first \(t\) are zero, setting \(m=D-t\), we have
\[\norm{x^{(t)}-x^{D,\star}}^2 \geq\frac{\sum_{j=1}^m\sinh^2(ja)}{\sinh^2((D+1)a)}, \qquad \norm{x^{(0)}-x^{D,\star}}^2 =\frac{\sum_{j=1}^D\sinh^2(ja)}{\sinh^2((D+1)a)}.\]We now compare these two sums. For each \(1\leq j\leq D\), let \(u=\lceil jm/D\rceil\). Since \(D\geq 2t+1\), we have \(D/m<2\), \(1\leq u\leq m\), \(u\leq j\), and \(j-u\leq t\); each value of \(u\) appears at most twice. Concavity of \(v\mapsto1-e^{-2av}\), which is zero at \(v=0\), gives
\[\frac{\sinh(ja)}{\sinh(ua)} =e^{(j-u)a}\frac{1-e^{-2ja}}{1-e^{-2ua}} \leq e^{ta}\frac{j}{u}\leq 2s^t.\]Hence,
\[\sum_{j=1}^D\sinh^2(ja)\leq 8s^{2t}\sum_{u=1}^m\sinh^2(ua).\]Combining it with the preceding expressions, we have
\[\norm{x^{(t)}-x^{D,\star}}^2 \geq\frac18s^{-2t}\norm{x^{(0)}-x^{D,\star}}^2 =\frac18\left(\frac{\sqrt{K_f}-1}{\sqrt{K_f}+1}\right)^{2t} \norm{x^{(0)}-x^{D,\star}}^2,\]proving (3). The value bound (4) is obtained by applying to this bound the quadratic lower bound of a \(\mu\)-strongly convex function at its minimizer,
\[f(x) \geq f(x^{\star}) + \frac{\mu}{2}\norm{x - x^{\star}}^{2} .\]More refined versions of these lower bounds, which provide tighter constants, can be found in Drori & Taylor (2022). However, these improvements come at the price of significantly more involved and technical proofs.
References
Footnotes
-
There exist algorithms that achieve it, in particular Nesterov’s acceleration method. ↩
AI disclosure
The original version from 2024 was written purely from handwritten notes. It contained several mistakes in the derivation of Theorem 3 that were identified and corrected by GPT-6 Astra.