#+title: Introduction to lower bounds in optimization #+description: Lower bounds on the complexity of optimization algorithms #+date: 2025-06-12 #+last_updated: 2026-10-28 #+status: finished #+ailvl: 3 #+keywords: optimization #+options: num:t #+bibliography: intro-to-lower-bounds.bib #+pdf: media:notes/intro-to-lower-bounds/intro-to-lower-bounds.pdf 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: #+name: ass:fom #+begin_assumption 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)}) } . \] #+end_assumption 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: \begin{equation} \label{eq:def-fk-fom} f_{k}^{L,\mu}(x) = \frac{L - \mu}{8} \left( (x_{1} - 1)^{2} + \sum_{i=1}^{k-1} (x_{i+1} - x_{i})^{2} + x_{k}^{2} \right) + \frac{\mu}{2} \norm{x}^{2} , \end{equation} 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=11,\\ 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 [[num:ass:fom]], 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. #+name: thm:lower-convex-smooth-fom #+begin_theorem 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 [[num:ass:fom]] is such that \begin{align} f(x^{(t)}) - f(x^{\star}) &\geq \frac{3L \norm{x^{(0)} - x^{\star}}^{2}}{32(t+1)^{2}} \label{eq:lower-bound-values-convex}\\ \end{align} where \(x^{\star}\) is a minimizer of \(f\). #+end_theorem Remark that the rate \(1/t^{2}\) is not achieved by the gradient descent[fn:1]! We also have a lower bound for the class of strongly convex functions. #+name: thm:lower-strongly-convex-smooth-fom #+begin_theorem Lower-bound for smooth strongly convex optimization For any \(d \geq 2\), \(x^{(0)} \in \RR^{d}\), \(0<\mu0\), \(0\leq\mu0\), 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}\). #+end_lemma #+begin_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: 1. 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\). 2. 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: 1. If \(\mu = 0\), then the unique root is given by \(r = 1\). 2. 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} . \] #+end_proof We now turn to the proofs of Theorem [[num:thm:lower-convex-smooth-fom]] and Theorem [[num:thm:lower-strongly-convex-smooth-fom]]. #+begin_proof :of thm:lower-convex-smooth-fom 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 [[num:lem:min-fk-convex-fom]], 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 [[eqref:eq:lower-bound-values-convex]]. #+end_proof #+begin_proof :of thm:lower-strongly-convex-smooth-fom 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 [[num:lem:min-fk-convex-fom]], 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 [[eqref:eq:lower-bound-iterates-strongly-convex]]. The value bound [[eqref:eq:lower-bound-values-strongly-convex]] 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} . \] #+end_proof More refined versions of these lower bounds, which provide tighter constants, can be found in [cite/t:@drori2022oraclecomplexity]. However, these improvements come at the price of significantly more involved and technical proofs. #+begin_ailvl The original version from 2024 was written purely from handwritten notes. It contained several mistakes in the derivation of Theorem [[num:thm:lower-strongly-convex-smooth-fom]] that were identified and corrected by GPT-6 Astra. #+end_ailvl [fn:1] There exist algorithms that achieve it, in particular Nesterov's acceleration method.