#+title: Following the Steepest Direction #+subtitle: In which we explore the basics of gradient descent. #+date: 2026-09-16 #+last_updated: 2026-10-28 #+status: finished #+ailvl: 2 #+keywords: optimization #+options: num:t #+bibliography: following-the-steepest-direction.bib #+pdf: media:notes/following-the-steepest-direction/following-the-steepest-direction.pdf #+html_head: #+html_head: * Following the steepest direction #+caption: First mention of the gradient descent algorithm by [cite/t:@cauchy1847methodegenerale]. #+name: fig:article-cauchy #+attr_html: :class historical-figure #+begin_figure [[file:article-cauchy.png]] #+end_figure Suppose that you want to solve the problem \[ \umin{x \in [-1,1]^{d}} f(x) , \] and you want to achieve a $\epsilon$-precision on the objective function $f$, /i.e./, you want to obtain an estimate $\hat x \in [-1,1]^d$ such that $f(\hat x)-f(x^{\star}) \leq \epsilon$, where $x^{\star}$ is a minimizer of $f$ over $[-1,1]^d$. Since $f$ is continuous, you cannot have access to all values $f(x)$ when $x$ describes the constraints $[-1,1]^{d}$, but you can allow yourself multiples calls to the “oracle” $f(x)$ in order to achieve this precision. A naive way to do so is to consider a discretization of $[-1,1]$ of precision $\epsilon$, that is \[ G_{\epsilon} = \setcond{k \epsilon}{k \in \set{-\lfloor \epsilon^{-1} \rfloor, \dots, \lfloor \epsilon^{-1} \rfloor}} , \] and $G_{\epsilon}^{d} = G_{\epsilon} \times \dots \times G_{\epsilon}$ its counterpart in dimension $d$. #+caption: Discretization of a black-box function on $[-1,1]$. The filled points are oracle evaluations, spaced by $\epsilon$; the minimizer $x^\star$ need not belong to the grid. #+name: fig:grid-discretization #+begin_figure #+begin_export html

Black-box discretization

Grid spacing ε0.25 Minimizer x⋆0.18

#+end_export #+begin_export latex \begin{tikzpicture}[x=3.8cm,y=2.3cm,>=stealth] \draw[->,black!75] (-1.15,0)--(1.15,0) node[right] {$x$}; \draw[->,black!75] (0,-.13)--(0,1.85) node[above] {$f(x)$}; \draw[thick,black!75] (-1,1.58)--(.18,.4)--(1,1.22); \foreach \k in {-4,...,4} { \pgfmathsetmacro{\gridx}{.25*\k} \pgfmathsetmacro{\gridy}{abs(\gridx-.18)+.4} \draw[dashed,blue!70!black] (\gridx,0)--(\gridx,\gridy); \fill[red!85!black] (\gridx,\gridy) circle[radius=2pt]; } \fill[black!75] (.18,.4) circle[radius=2pt]; \draw[black!60] (.18,.4)--(.33,.3); \node[right,inner sep=1pt] at (.33,.3) {$x^\star$}; \draw[<->,red!85!black] (0,.12)--(.25,.12) node[midway,above] {$\epsilon$}; \node[below,font=\small] at (-1,0) {$-1$}; \node[below,font=\small] at (1,0) {$1$}; \end{tikzpicture} #+end_export #+end_figure #+begin_proposition Grid-search guarantee Let $0<\epsilon\leq 1$ and let $f:[-1,1]^d\to\RR$ be $L$-Lipschitz, where $L>0$. Let $x^\star$ be any minimizer of $f$ on $[-1,1]^d$, and let $\hat x$ be any minimizer of $f$ over the finite grid $G_\epsilon^d$. Then \[ 0\leq f(\hat x)-f(x^\star)\leq L\sqrt{d}\,\epsilon. \] #+end_proposition Thus, for a prescribed objective-value tolerance $\delta>0$, choosing $\epsilon\leq\min\{1,\delta/(L\sqrt{d})\}$ guarantees $f(\hat x)-f(x^\star)\leq\delta$. #+begin_proof Lipschitz continuity implies continuity, so a minimizer $x^\star$ exists on the compact cube; a grid minimizer exists because the grid is finite and nonempty. For each coordinate, define \[ z_i=\epsilon\,\operatorname{sign}(x_i^\star) \left\lfloor\frac{|x_i^\star|}{\epsilon}\right\rfloor, \qquad i=1,\dots,d, \] with $\operatorname{sign}(0)=0$. Since $|x_i^\star|\leq 1$, we have $z\in G_\epsilon^d$ and $|z_i-x_i^\star|<\epsilon$ for every $i$. Consequently, $\norm{z-x^\star}\leq\sqrt{d}\,\epsilon$. By global optimality of $x^\star$, grid optimality of $\hat x$, and Lipschitz continuity, \[ 0\leq f(\hat x)-f(x^\star) \leq f(z)-f(x^\star) \leq L\norm{z-x^\star} \leq L\sqrt{d}\,\epsilon. \] #+end_proof This is a bound on objective values, rather than on $\norm{\hat x-x^\star}$. Lipschitz continuity alone cannot guarantee proximity to a chosen minimizer: for $f\equiv 0$, every grid point is a minimizer, including points far from $x^\star=0$. The issue is that the size of $G_{\epsilon}^{d}$ grows exponentially fast with the dimension $d$. In dimension 1, one needs to perform $2 \lfloor \epsilon^{-1} \rfloor+1$ evaluations of $f$, but in dimension $d$, one needs $(2 \lfloor \epsilon^{-1} \rfloor+1)^d$! This quantity gets prohibilitively large in a too fast manner: say you look at a very modest precision of $\epsilon = 10^{-2}$, then in dimension $d=1$, 201 computations of $f$ are needed, whereas in dimension $d=10$, you already need $201^{10}=107636749520976961802001$ evaluations (about $1.08\times 10^{23}$). This is known as the curse of dimensionality, a term introduced by [cite/t:@bellman1961adaptivecontrol chap. 5] for optimal control and (over)used since then in the optimization, statistics and machine learning communities [cite:@donoho2000highdimensionaldata]. Summary: we need to be (slightly) more clever. ** Descent direction Consider the class of algorithms of the form \[ x^{(t+1)} = x^{(t)} + \eta^{(t)} u^{(t+1)} , \] how to “optimaly choose” the direction $u^{(t+1)}$ such that $x^{(t+1)}$ is closer to a minimum of $f$? #+name: def:descent-direction #+begin_definition Let $f: \RR^{d} \to \RR$. A /descent direction/ $u \in \RR^{d}$ of $f$ at $x \in \RR^{d}$ is vector such that \[ \exists \epsilon > 0, \forall \eta \in (0, \epsilon), \quad f(x + \eta u) < f(x) . \] #+end_definition #+caption: Descent cone of the nonsmooth function $f(x_1,x_2)=|x_1|+|x_2|$ at $\bar x=(0,1)$. The level sets are diamonds. The shaded cone contains the strict descent directions $u_2<-|u_1|$; its dashed boundary rays are excluded. #+name: fig:nonsmooth-descent-cone #+begin_figure #+begin_export html

Nonsmooth descent cone

Direction angle (°)290

Rotate the direction u. Dashed boundary directions are excluded from the strict descent cone.

#+end_export #+begin_export latex \begin{tikzpicture}[x=1.35cm,y=1.35cm,>=stealth] \begin{scope} \clip (-2,-2) rectangle (2,2); \fill[blue!8] (-2,-2) rectangle (2,2); \foreach \j in {10,9,...,1} { \pgfmathsetmacro{\level}{.4*\j} \pgfmathsetmacro{\shade}{3+2*\j} \path[fill=blue!\shade,draw=black!45,line width=.45pt] (\level,0)--(0,\level)--(-\level,0)--(0,-\level)--cycle; } \fill[blue!30,opacity=.55] (0,1)--(-3,-2)--(3,-2)--cycle; \draw[dashed,blue!75!black,thick] (0,1)--(-3,-2); \draw[dashed,blue!75!black,thick] (0,1)--(3,-2); \draw[->,very thick,black!80] (0,1)--(.45,-.2) node[midway,right,fill=white,inner sep=1pt] {$u$}; \fill[red!85!black] (0,1) circle[radius=2.3pt]; \end{scope} \draw[black!60] (-2,-2) rectangle (2,2); \foreach \v in {-2,-1,0,1,2} { \draw (\v,-2)--(\v,-2.06) node[below,font=\footnotesize] {$\v$}; \draw (-2,\v)--(-2.06,\v) node[left,font=\footnotesize] {$\v$}; } \node[right] at (2,-2) {$x_1$}; \node[above] at (-2,2) {$x_2$}; \node[above right,fill=white,inner sep=2pt] at (.08,1.05) {$\bar x=(0,1)$}; \node[blue!75!black,fill=white,inner sep=3pt] at (0,-1.55) {$u_2<-|u_1|$}; \end{tikzpicture} #+end_export #+end_figure Observe that if $f$ is differentiable, $\dotp{\nabla f(x)}{u} < 0$ implies this property, but the converse need not hold. For example, $f(z)=-z^2$ at $x=0$ has the descent direction $u=1$, but $f'(0)u=0$. The negative gradient $-\nabla f(\bar x)$ is the /direction of steepest descent/ at the point $\bar x$ when $\nabla f(\bar x)\neq 0$. #+name: prop:steepest-direction-grad #+begin_proposition The antigradient is the steepest direction Let $f: \RR^{d} \to \RR$ be a differentiable function at $\bar x \in \RR^{d}$. Assume that $\nabla f(\bar x)\neq 0$. Then, the problem \[ \min_{\norm{u} = 1} \dotp{\nabla f(\bar x)}{u} \] has a unique solution $u^{\star} = - \frac{\nabla f(\bar x)}{\norm{\nabla f(\bar x)}}$ . #+end_proposition #+begin_proof Let $u \in \RR^{d}$ such that $\norm{u} = 1$. Consider the function $\phi_{u}: \RR \to \RR$ defined by \[ \phi_{u}(t) = f(\bar x + t u). \] The function $\phi_u$ is differentiable at $0$ and its derivative reads $\phi_{u}'(0) = \dotp{\nabla f(\bar x)}{u}$. Denoting $\theta$ the angle between $\nabla f(\bar x)$ and $u$, we have that $\phi_{u}'(0) = \norm{\nabla f(\bar x)} \cos \theta$. Hence, minimizing $\dotp{\nabla f(\bar x)}{u}$ is equivalent to finding the minimum of $\cos \theta$, that is $\theta = (2k+1) \pi$ for some $k \in \ZZ$. Thus, we have \[ u^{\star} = - \frac{\nabla f(\bar x)}{\norm{\nabla f(\bar x)}} \quad \text{ and } \quad \dotp{\nabla f(\bar x)}{u^\star} = - \norm{\nabla f(\bar x)}. \] #+end_proof ** The gradient descent (GD) algorithm [[prop:steepest-direction-grad]] gives birth to what is known as the /gradient descent algorithm/ or /gradient descent method/. #+caption: Gradient Descent algorithm #+begin_algorithm - *Input:* Initialization $x^{(0)} \in \RR^{d}$, step-size policy $\eta^{(t)} > 0$. - *for* $t=0, \cdots$ *do* - \[ \begin{equation} \label{eq:gradient-descent}\tag{GD} x^{(t+1)} = x^{(t)} - \eta^{(t)} \nabla f(x^{(t)}) . \end{equation} \] #+end_algorithm The choice of the step-sizes $\eta^{(k)}$ is crucial, and there is several way to do it. 1. /Predetermined./ In this case, the sequence $(\eta^{(t)})$ is chosen beforehand, either with a constant step size $\eta^{(t)} = \eta \in \RR_{>0}$ or with a given function of $t$, $\eta^{(t)} = g(t)$, /e.g./, $g(t) = \eta (t+1)^{-1/2}$ for some $\eta > 0$. For some classes of optimization problem, it is possible to provide guarantees depending on the choice of $g$. 2. /Oracle./ This is the “optimal” descent that a gradient descent method can produce, defined by \[ \eta_{\text{oracle}}^{(t)} \in \uargmin{\eta \geq 0} f(x^{(t)} - \eta \nabla f(x^{(t)})) . \] Remark that this choice is only theoretical since it involves a new optimization problem that may be nonsolvable in closed form. This choice assumes that the line-search minimum is attained; this need not hold for a general $f$. 3. /Backtracking rule./ Start with a trial step-size and check whether the proposed gradient step decreases the objective sufficiently. If it does not, shrink the step-size by a fixed factor, for example divide it by two, and try again. Repeat until the test passes, then take the step. A common test is the Armijo condition \[ f(x^{(t)}-\eta\nabla f(x^{(t)})) \leq f(x^{(t)})-c\eta\norm{\nabla f(x^{(t)})}^{2}, \qquad 00\), and let $\kappa=L/\mu$ when $\mu>0$, and $\kappa=+\infty$ when $\mu=0$. We have $0 \leq \mu \leq L$ and $\kappa \geq 1$. #+caption: Gradient descent on two least-squares quadratics with the same initialization and minimizer, using $\eta=2/(\mu+L)$. A small condition number gives fast convergence; a large condition number produces a slow zigzag along an elongated valley. #+name: fig:ols-conditioning #+begin_figure #+begin_export html

Small condition number

Large condition number

Large condition number κ25 Iterations40

Both plots use the same initial point and minimizer, with μ = 1 and η = 2/(μ + L).

#+end_export #+begin_export latex \begin{tikzpicture}[x=1.4cm,y=1.4cm,>=stealth] \begin{scope}[shift={(0cm,0)}] \begin{scope} \clip (-2,-2) rectangle (2,2); \fill[orange!90] (-2,-2) rectangle (2,2); \path[fill=orange!90.00,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=3.8729833,y radius=3.2732684]; \path[fill=orange!86.46,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=3.7116090,y radius=3.1368822]; \path[fill=orange!82.92,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=3.5502347,y radius=3.0004960]; \path[fill=orange!79.38,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=3.3888604,y radius=2.8641098]; \path[fill=orange!75.83,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=3.2274861,y radius=2.7277236]; \path[fill=orange!72.29,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=3.0661118,y radius=2.5913374]; \path[fill=orange!68.75,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=2.9047375,y radius=2.4549513]; \path[fill=orange!65.21,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=2.7433632,y radius=2.3185651]; \path[fill=orange!61.67,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=2.5819889,y radius=2.1821789]; \path[fill=orange!58.12,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=2.4206146,y radius=2.0457927]; \path[fill=orange!54.58,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=2.2592403,y radius=1.9094065]; \path[fill=orange!51.04,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=2.0978660,y radius=1.7730204]; \path[fill=orange!47.50,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=1.9364917,y radius=1.6366342]; \path[fill=orange!43.96,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=1.7751174,y radius=1.5002480]; \path[fill=orange!40.42,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=1.6137431,y radius=1.3638618]; \path[fill=orange!36.88,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=1.4523688,y radius=1.2274756]; \path[fill=orange!33.33,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=1.2909944,y radius=1.0910895]; \path[fill=orange!29.79,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=1.1296201,y radius=0.9547033]; \path[fill=orange!26.25,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=0.9682458,y radius=0.8183171]; \path[fill=orange!22.71,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=0.8068715,y radius=0.6819309]; \path[fill=orange!19.17,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=0.6454972,y radius=0.5455447]; \path[fill=orange!15.62,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=0.4841229,y radius=0.4091585]; \path[fill=orange!12.08,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=0.3227486,y radius=0.2727724]; \path[fill=orange!8.54,draw=black!70,line width=.45pt,rotate around={0:(.3,-.2)}] (.3,-.2) ellipse[x radius=0.1613743,y radius=0.1363862]; \draw[blue!75!black,line width=.6pt] plot coordinates {(-1.3000000,0.9000000) (0.0333333,-0.3833333) (0.2555556,-0.1694444) (0.2925926,-0.2050926) (0.2987654,-0.1991512) (0.2997942,-0.2001415)}; \fill[orange!85!black] (-1.3000000,0.9000000) circle[radius=1.5pt]; \fill[orange!85!black] (0.0333333,-0.3833333) circle[radius=1.5pt]; \fill[orange!85!black] (0.2555556,-0.1694444) circle[radius=1.5pt]; \fill[orange!85!black] (0.2925926,-0.2050926) circle[radius=1.5pt]; \fill[orange!85!black] (0.2987654,-0.1991512) circle[radius=1.5pt]; \fill[orange!85!black] (0.2997942,-0.2001415) circle[radius=1.5pt]; \fill[black!75] (.3,-.2) circle[radius=1.8pt]; \end{scope} \draw[black!60] (-2,-2) rectangle (2,2); \draw (-2,-2)--(-2,-2.06) node[below,font=\footnotesize] {$-2$}; \draw (-2,-2)--(-2.06,-2) node[left,font=\footnotesize] {$-2$}; \draw (-1,-2)--(-1,-2.06) node[below,font=\footnotesize] {$-1$}; \draw (-2,-1)--(-2.06,-1) node[left,font=\footnotesize] {$-1$}; \draw (0,-2)--(0,-2.06) node[below,font=\footnotesize] {$0$}; \draw (-2,0)--(-2.06,0) node[left,font=\footnotesize] {$0$}; \draw (1,-2)--(1,-2.06) node[below,font=\footnotesize] {$1$}; \draw (-2,1)--(-2.06,1) node[left,font=\footnotesize] {$1$}; \draw (2,-2)--(2,-2.06) node[below,font=\footnotesize] {$2$}; \draw (-2,2)--(-2.06,2) node[left,font=\footnotesize] {$2$}; \node[right] at (2,-2) {$x_1$}; \node[above] at (-2,2) {$x_2$}; \node[above] at (0,2.18) {$\kappa=L/\mu=1.4$}; \end{scope} \begin{scope}[shift={(7.2cm,0)}] \begin{scope} \clip (-2,-2) rectangle (2,2); \fill[orange!90] (-2,-2) rectangle (2,2); \path[fill=orange!90.00,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=13.7840488,y radius=2.7568098]; \path[fill=orange!86.46,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=13.2097134,y radius=2.6419427]; \path[fill=orange!82.92,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=12.6353780,y radius=2.5270756]; \path[fill=orange!79.38,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=12.0610427,y radius=2.4122085]; \path[fill=orange!75.83,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=11.4867073,y radius=2.2973415]; \path[fill=orange!72.29,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=10.9123719,y radius=2.1824744]; \path[fill=orange!68.75,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=10.3380366,y radius=2.0676073]; \path[fill=orange!65.21,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=9.7637012,y radius=1.9527402]; \path[fill=orange!61.67,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=9.1893658,y radius=1.8378732]; \path[fill=orange!58.12,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=8.6150305,y radius=1.7230061]; \path[fill=orange!54.58,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=8.0406951,y radius=1.6081390]; \path[fill=orange!51.04,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=7.4663597,y radius=1.4932719]; \path[fill=orange!47.50,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=6.8920244,y radius=1.3784049]; \path[fill=orange!43.96,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=6.3176890,y radius=1.2635378]; \path[fill=orange!40.42,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=5.7433536,y radius=1.1486707]; \path[fill=orange!36.88,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=5.1690183,y radius=1.0338037]; \path[fill=orange!33.33,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=4.5946829,y radius=0.9189366]; \path[fill=orange!29.79,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=4.0203476,y radius=0.8040695]; \path[fill=orange!26.25,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=3.4460122,y radius=0.6892024]; \path[fill=orange!22.71,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=2.8716768,y radius=0.5743354]; \path[fill=orange!19.17,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=2.2973415,y radius=0.4594683]; \path[fill=orange!15.62,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=1.7230061,y radius=0.3446012]; \path[fill=orange!12.08,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=1.1486707,y radius=0.2297341]; \path[fill=orange!8.54,draw=black!70,line width=.45pt,rotate around={-65:(.3,-.2)}] (.3,-.2) ellipse[x radius=0.5743354,y radius=0.1148671]; \draw[blue!75!black,line width=.6pt] plot coordinates {(-1.3000000,0.9000000) (0.4715181,1.5840654) (-1.0633136,0.7372781) (0.4461456,1.3201504) (-0.8616400,0.5986275) (0.4245264,1.0952761) (-0.6897998,0.4804873) (0.4061054,0.9036672) (-0.5433797,0.3798235) (0.3904093,0.7404028) (-0.4186194,0.2940508) (0.3770351,0.6012900) (-0.3123147,0.2209664) (0.3656394,0.4827559) (-0.2217356,0.1586932) (0.3559294,0.3817565) (-0.1445558,0.1056321) (0.3476559,0.2956979) (-0.0787931,0.0604203) (0.3406062,0.2223698) (-0.0227586,0.0218966) (0.3345993,0.1598891) (0.0249867,-0.0109284) (0.3294811,0.1066510) (0.0656692,-0.0388976) (0.3251200,0.0612884) (0.1003335,-0.0627293) (0.3214040,0.0226363) (0.1298700,-0.0830356) (0.3182377,-0.0102981) (0.1550371,-0.1003380) (0.3155398,-0.0383605) (0.1764813,-0.1150809) (0.3132411,-0.0622716) (0.1947533,-0.1276429) (0.3112823,-0.0826457) (0.2103224,-0.1383466) (0.3096133,-0.1000058) (0.2235883,-0.1474669) (0.3081912,-0.1147978) (0.2348918,-0.1552381)}; \fill[orange!85!black] (-1.3000000,0.9000000) circle[radius=1.5pt]; \fill[orange!85!black] (0.4715181,1.5840654) circle[radius=1.5pt]; \fill[orange!85!black] (-1.0633136,0.7372781) circle[radius=1.5pt]; \fill[orange!85!black] (0.4461456,1.3201504) circle[radius=1.5pt]; \fill[orange!85!black] (-0.8616400,0.5986275) circle[radius=1.5pt]; \fill[orange!85!black] (0.4245264,1.0952761) circle[radius=1.5pt]; \fill[orange!85!black] (-0.6897998,0.4804873) circle[radius=1.5pt]; \fill[orange!85!black] (0.4061054,0.9036672) circle[radius=1.5pt]; \fill[orange!85!black] (-0.5433797,0.3798235) circle[radius=1.5pt]; \fill[orange!85!black] (0.3904093,0.7404028) circle[radius=1.5pt]; \fill[orange!85!black] (-0.4186194,0.2940508) circle[radius=1.5pt]; \fill[orange!85!black] (0.3770351,0.6012900) circle[radius=1.5pt]; \fill[orange!85!black] (-0.3123147,0.2209664) circle[radius=1.5pt]; \fill[orange!85!black] (0.3656394,0.4827559) circle[radius=1.5pt]; \fill[orange!85!black] (-0.2217356,0.1586932) circle[radius=1.5pt]; \fill[orange!85!black] (0.3559294,0.3817565) circle[radius=1.5pt]; \fill[orange!85!black] (-0.1445558,0.1056321) circle[radius=1.5pt]; \fill[orange!85!black] (0.3476559,0.2956979) circle[radius=1.5pt]; \fill[orange!85!black] (-0.0787931,0.0604203) circle[radius=1.5pt]; \fill[orange!85!black] (0.3406062,0.2223698) circle[radius=1.5pt]; \fill[orange!85!black] (-0.0227586,0.0218966) circle[radius=1.5pt]; \fill[orange!85!black] (0.3345993,0.1598891) circle[radius=1.5pt]; \fill[orange!85!black] (0.0249867,-0.0109284) circle[radius=1.5pt]; \fill[orange!85!black] (0.3294811,0.1066510) circle[radius=1.5pt]; \fill[orange!85!black] (0.0656692,-0.0388976) circle[radius=1.5pt]; \fill[orange!85!black] (0.3251200,0.0612884) circle[radius=1.5pt]; \fill[orange!85!black] (0.1003335,-0.0627293) circle[radius=1.5pt]; \fill[orange!85!black] (0.3214040,0.0226363) circle[radius=1.5pt]; \fill[orange!85!black] (0.1298700,-0.0830356) circle[radius=1.5pt]; \fill[orange!85!black] (0.3182377,-0.0102981) circle[radius=1.5pt]; \fill[orange!85!black] (0.1550371,-0.1003380) circle[radius=1.5pt]; \fill[orange!85!black] (0.3155398,-0.0383605) circle[radius=1.5pt]; \fill[orange!85!black] (0.1764813,-0.1150809) circle[radius=1.5pt]; \fill[orange!85!black] (0.3132411,-0.0622716) circle[radius=1.5pt]; \fill[orange!85!black] (0.1947533,-0.1276429) circle[radius=1.5pt]; \fill[orange!85!black] (0.3112823,-0.0826457) circle[radius=1.5pt]; \fill[orange!85!black] (0.2103224,-0.1383466) circle[radius=1.5pt]; \fill[orange!85!black] (0.3096133,-0.1000058) circle[radius=1.5pt]; \fill[orange!85!black] (0.2235883,-0.1474669) circle[radius=1.5pt]; \fill[orange!85!black] (0.3081912,-0.1147978) circle[radius=1.5pt]; \fill[orange!85!black] (0.2348918,-0.1552381) circle[radius=1.5pt]; \fill[black!75] (.3,-.2) circle[radius=1.8pt]; \end{scope} \draw[black!60] (-2,-2) rectangle (2,2); \draw (-2,-2)--(-2,-2.06) node[below,font=\footnotesize] {$-2$}; \draw (-2,-2)--(-2.06,-2) node[left,font=\footnotesize] {$-2$}; \draw (-1,-2)--(-1,-2.06) node[below,font=\footnotesize] {$-1$}; \draw (-2,-1)--(-2.06,-1) node[left,font=\footnotesize] {$-1$}; \draw (0,-2)--(0,-2.06) node[below,font=\footnotesize] {$0$}; \draw (-2,0)--(-2.06,0) node[left,font=\footnotesize] {$0$}; \draw (1,-2)--(1,-2.06) node[below,font=\footnotesize] {$1$}; \draw (-2,1)--(-2.06,1) node[left,font=\footnotesize] {$1$}; \draw (2,-2)--(2,-2.06) node[below,font=\footnotesize] {$2$}; \draw (-2,2)--(-2.06,2) node[left,font=\footnotesize] {$2$}; \node[right] at (2,-2) {$x_1$}; \node[above] at (-2,2) {$x_2$}; \node[above] at (0,2.18) {$\kappa=L/\mu=25$}; \end{scope} \end{tikzpicture} #+end_export #+end_figure Using [[eqref:eq:linear-unrolled]], we have \[ \| x^{(t)} - x^{\star} \|^{2} = \langle x^{(0)} - x^{\star} , (I - \eta H)^{2t} (x^{(0)} - x^{\star}) \rangle . \] Remark that the eigenvalues of $(I - \eta H)^{2t}$ are exactly given by $(1-\eta \lambda)^{2t}$ where $\lambda$ is an eigenvalue of $H$. Since all eigenvalues of $H$ are contained in $[\mu,L]$, one also can bound any $\rho \in \mathrm{eigen}((I - \eta H)^{2t})$ by \[ |\rho| \leq \left( \max_{\lambda \in [\mu,L]} | 1 - \eta \lambda | \right)^{2t} . \] Suppose that there is multiple minimizers. In this case, $H$ is not invertible and the smallest eigenvalue $\mu$ is equal to 0. Hence, there exists $v\neq 0$ such that $(I - \eta H)v = v$. Choose $x^{\star}$ a minimizer. Using $x^{(0)} = v + x^{\star}$, we have \[ \| x^{(t)} - x^{\star} \|^{2} = \langle v + x^{\star} - x^{\star} , (I - \eta H)^{2t} (v + x^{\star} - x^{\star}) \rangle = \langle v , (I - \eta H)^{2t} v \rangle = \| v \|_{2}^{2} . \] Hence, the method does not necessarly converge to this chosen $x^\star$: here $x^{(t)}=x^{(0)}$ is already a minimizer. For $0<\eta<2/L$, the iterates do converge to a minimizer, depending on the initialization. The situation is different when we assume that there is a unique minimizer. #+begin_proposition Convergence in norm Assume that [[eqref:eq:lstq]] has a unique minimizer $x^{\star}$. Then, the gradient descent iterates $x^{(t)}$ with constant step-size $\eta^{(t)} = \eta = \frac{2}{\mu + L}$ converges linearly in norm \[ \norm{x^{(t)} - x^{\star}}^{2} \leq \left( \frac{\kappa - 1}{\kappa + 1} \right)^{2t} \norm{x^{(0)} - x^{\star}}^{2} . \] #+end_proposition #+begin_proof Since there is a unique minimizer $x^{\star}$, we have $\mu > 0$. Observe that (using a spectral norm bound) \[ \langle x^{(0)} - x^{\star} , (I - \eta H)^{2t} (x^{(0)} - x^{\star}) \rangle \leq \left( \max_{\lambda \in [\mu,L]} | 1 - \eta \lambda | \right)^{2t} \| x^{(0)} - x^{\star} \|_{2}^{2} . \] Observe that $\max_{\lambda \in [\mu,L]} | 1 - \eta \lambda |$ is minimized for $\eta = \frac{2}{\mu + L}$, and value is $\frac{\kappa - 1}{\kappa + 1} \in [0,1)$. Indeed, \[ \max_{\lambda \in [\mu,L]} | 1 - \eta \lambda | = \max \left( | 1 - \eta \mu |, | 1 - \eta L | \right) . \] If $\mu=L$, this maximum is $|1-\eta L|$, minimized at $\eta=1/L$. For the following equivalences, assume \(\mu

Optimal constant step size

L (μ = 1)3 Chosen step size η0.5

#+end_export #+begin_export latex \begin{tikzpicture}[x=6cm,y=1.4cm,>=stealth] \draw[->,black!75] (0,0)--(1.32,0) node[right] {$\eta$}; \draw[->,black!75] (0,0)--(0,2.95) node[above] {$q(\eta)$}; \draw[thick,black!75] (0,1)--(.333333,0)--(1.2,2.6); \draw[thick,black!75] (0,1)--(1,0)--(1.2,.2); \draw[very thick,red!85!black] (0,1)--(.5,.5)--(1.2,2.6); \draw[densely dotted,red!85!black] (.5,0)--(.5,.5); \fill[red!85!black] (.5,.5) circle[radius=1.8pt]; \node[red!85!black,anchor=west] at (1.22,2.6) {$\max\{|1-\eta L|,|1-\eta\mu|\}$}; \node[anchor=west] at (1.22,.2) {$|1-\eta\mu|$}; \node[left] at (0,1) {$1$}; \draw (.333333,0)--(.333333,-.06) node[below] {$\frac{1}{L}$}; \draw[red!85!black] (.5,0)--(.5,-.06) node[below] {$\frac{2}{L+\mu}$}; \draw (1,0)--(1,-.06) node[below] {$\frac{1}{\mu}$}; \end{tikzpicture} #+end_export #+end_figure Hence, \[ \min_{\eta > 0} \max_{\lambda \in [\mu,L]} | 1 - \eta \lambda | = \min_{\eta > 0} \max \left( | 1 - \eta \mu |, | 1 - \eta L | \right) . \] Moreover, we have the following set of equivalence \begin{align*} | 1 - \eta L | &\leq | 1 - \eta \mu | \\ (1 - \eta L)^{2} &\leq (1 - \eta \mu)^{2} \\ \eta L^{2} - 2L &\leq \eta \mu^{2} - 2 \mu \\ \eta &\leq \frac{2}{L + \mu} . \end{align*} This minima is achieved when the two curve $| 1 - \eta L |$ and $| 1 - \eta \mu |$ intersect. #+end_proof /Choice independant from the strong-convexity constant $\mu$/: It is possible to chose a smaller or equal stepsize (hence no faster) by taking the value $\eta = 1/L$. In this case, we get \[ \max_{\lambda \in [\mu,L]} | 1 - \eta \lambda | = 1 - \frac{\mu}{L} = 1 - \frac{1}{\kappa} . \] In both cases, we obtained a linear (or geometric, or exponential depending on the community) rate \[ \| x^{(t)} - x^{\star} \|^{2} \leq c^{2t} \| x^{(0)} - x^{\star} \|^{2} , \] where $c = \frac{\kappa - 1}{\kappa + 1}$ or $c = 1 - \frac{1}{\kappa}$ depending on the choice of the step-size. It is possible to also speaks in term of iteration complexity. Assuming the choice of $\eta = 1/L$, observe that \[ \left( 1 - \frac{1}{\kappa} \right)^{2t} \leq \exp(-\frac{1}{\kappa})^{2t} = \exp(-\frac{2t}{\kappa}) . \] Thus, to obtain a fraction $\epsilon \| x^{(0)} - x^{\star} \|^{2}$ for $0<\epsilon<1$, it is sufficient to perform $t$ iterations with \[ t \geq \left\lceil \frac{\kappa}{2} \log \frac{1}{\epsilon} \right\rceil . \] *** Convergence in value As we say, if $\mu = 0$, the iterates need not converge to a chosen minimizer, although they converge to a minimizer for $0<\eta<2/L$. But the story is different for the convergence in value. #+begin_proposition Convergence in value Let $x^{\star}$ any solution of [[eqref:eq:lstq]], assume $L>0$, and let $t\geq 1$. The gradient descent iterates $x^{(t)}$ with constant step-size $\eta^{(t)} = \eta = \frac{1}{L}$ converges with a $O(1/t)$ rate \[ f(x^{(t)}) - f(x^{\star}) \leq \frac{1}{4t\eta} \norm{x^{(0)} - x^{\star}}_{2}^{2} . \] If moreover, [[eqref:eq:lstq]] has a unique solution, the convergence is linear: \[ f(x^{(t)}) - f(x^\star) \leq \left( 1 - \frac{1}{\kappa} \right)^{2t} (f(x^{(0)}) - f(x^\star)) . \] #+end_proposition #+begin_proof Observe that $f$ has an /exact/ Taylor expansion of order 2. Indeed, for any $x \in \mathbb{R}^{p}$ and any minimizer $x^{\star}$: \begin{align} f(x) - f(x^{\star}) &= \langle \nabla f(x^{\star}), x - x^{\star} \rangle + \frac{1}{2} \langle x - x^{\star}, H (x - x^{\star}) \rangle \nonumber \\ &= \frac{1}{2} \langle x - x^{\star}, H (x - x^{\star}) \rangle . \label{eq:taylor-exact} \end{align} Using the (exact) Taylor expansion [[eqref:eq:taylor-exact]] of $f$, we have \[ f(x^{(t)}) - f(x^\star) = \frac{1}{2} \langle x^{(t)} - x^\star, H (x^{(t)} - x^{\star}) \rangle . \] Using [[eqref:eq:linear-unrolled]], we have \[ f(x^{(t)}) - f(x^\star) = \frac{1}{2} \langle (I - \eta H)^{t} (x^{(0)} - x^{\star}) , H (I - \eta H)^{t} (x^{(0)} - x^{\star}) \rangle . \] Since $(I - \eta H)$ is symmetric, we have \[ f(x^{(t)}) - f(x^\star) = \frac{1}{2} \langle x^{(0)} - x^{\star} , (I - \eta H)^{2t} H (x^{(0)} - x^{\star}) \rangle . \] Using the fact that for a symmetric positive semidefinite matrix $B$, we have $\langle B w,w\rangle\leq\|B\|_{sp}\|w\|^2$, with $B=(I-\eta H)^{2t}$ and $w=H^{1/2}(x^{(0)}-x^\star)$, and that $B$ commutes with $H$, we have \[ f(x^{(t)}) - f(x^\star) \leq \left\| (I - \eta H)^{2t} \right\| \frac{1}{2} \langle x^{(0)} - x^{\star} , H (x^{(0)} - x^{\star}) \rangle . \] Using again [[eqref:eq:taylor-exact]], we have \[ f(x^{(t)}) - f(x^\star) \leq \left\| (I - \eta H)^{2t} \right\| (f(x^{(0)}) - f(x^\star)) . \] /Case $\mu > 0$./ Now, we have according to the previous section, the following linear rate. \[ f(x^{(t)}) - f(x^\star) \leq \left( 1 - \frac{1}{\kappa} \right)^{2t} (f(x^{(0)}) - f(x^\star)) . \] /Case $\mu = 0$./ Let's study the eigenvalues of[fn:1] $(I - \eta H)^{2t} H$. We keep our analysis restricted to $0<\eta \leq \frac{1}{L}$. \begin{align*} | \lambda (1 - \eta \lambda)^{2t} | &\leq \lambda \exp(-\eta \lambda)^{2t} \\ &= \lambda \exp(-2t\eta\lambda) \\ &= \frac{1}{2t\eta} 2t\eta\lambda \exp(-2t\eta\lambda) & \text{insert the term } 2t\eta \\ &\leq \frac{1}{2t\eta} \sup_{\rho \geq 0} \rho \exp(-\rho) & \text{crude bound} \\ &= \frac{1}{2et\eta} & \text{maximum at } \rho = 1 \\ &\leq \frac{1}{4t\eta} & e > 2 . \end{align*} Hence, we obtain the claimed $O(1/t)$ rate. #+end_proof ** Convergence of gradient descent for nonconvex functions Unfortunately, not every functions are quadratic, and we need to deep diver in the analysis of the gradient descent algorithm to understand its behavior on generic function. We are going to explore several class of functions that leads to different rates, either in norm or in objective values. *** Coercive continuously differentiable function The following proposition show a very weak result without any quantification of the /rate of convergence/ of gradient descent. #+name: prop:cvgt-gd-coercive-c1 #+begin_proposition Convergence of [[eqref:eq:gradient-descent]] for coercive $C^{1}$ functions Let $f: \RR^{d} \to \RR$ be a coercive function and assume moreover that it is continuously differentiable. For any initial guess $x^{(0)}$, the /oracle/ GD iterates $x^{(t)}$ converge up to a subsequence towards a critical point of $f$. #+end_proposition #+begin_proof /(i) The value sequence is (strictly)decreasing (unless it reaches a critical point)./ We recall that the oracle GD chose the step-size $\eta^{(t)}$ as \begin{gathered}\phi^{(t)}(\eta) \eqdef f(x^{(t)}-\eta\nabla f(x^{(t)})),\qquad \eta^{(t)}\in\uargmin{\eta\geq 0}\phi^{(t)}(\eta) . \end{gathered} If $\nabla f(x^{(t)})\neq 0$, coercivity implies $\phi^{(t)}(\eta)\to+\infty$ as $\eta\to+\infty$, so the oracle step exists. If the gradient is zero, the line-search objective is constant and the iterate stays unchanged. Hence, evaluating $\phi^{(t)}$ at $\eta^{(t)}$ and 0 leads to \[ f(x^{(t+1)}) = \phi^{(t)}(\eta^{(t)}) {\,\leq\,} \phi^{(t)}(0) = f(x^{(t)}) . \] Suppose that $f(x^{(t+1)}) = f(x^{(t)})$. Thus, 0 is a minimizer of $\phi^{(t)}$ and therefore its one-sided first-order condition reads $\frac{d}{d \eta}\phi^{(t)}(0) \geq 0$. Given $\eta \geq 0$, we have \[ \frac{d}{d \eta}\phi^{(t)}(\eta) = \dotp{-\nabla f(x^{(t)})}{\nabla f (x^{(t)} - \eta \nabla f(x^{(t)}))} . \] Evaluating this expression at $\eta = 0$ gives us $- \norm{\nabla f(x^{(t)})}^2\geq 0$, hence $\nabla f(x^{(t)}) = 0$ that means $x^{(t)}$ is a critical point. /(ii) The iterates sequence is converging (up to a subsequence)./ Consider the set $S = \setcond{x \in \RR^{d}}{f(x) \leq f(x^{(0)})}$. Remark that: - $f$ is continuous, thus $S$ is closed; - $f$ is coercive, thus $S$ is bounded. Hence, $S$ is compact. Observe that for all $t \geq 0$, $x^{(t)} \in S$. Using Bolzano--Weierstrass theorem, we get that the sequence $(x^{(t)})$ has a convergent subsequence towards some $x^{*}$. Let us denote it by $(x^{(\psi(t))})_{t \geq 0}$ where $\psi : \NN \to \NN$ is increasing. The value sequence is decreasing and bounded below, so it converges to $\ell$. By continuity, $\ell=f(x^*)$. /(iii) The limit of the iterates sequence is a critical point./ Suppose that $x^{*}$ is not a critical point. Using /(i)/, we now that $x^{**}$ defined as $x^{**} = x^{*} - \eta^{*} \nabla f(x^{*}) \neq x^{*}$, where $\eta^{*} > 0$ is the oracle step, is such that $f(x^{**}) < f(x^{*})$. Consider the sequence $y^{(t)} = x^{(\psi(t))}$ converging to $x^{*}$. Remark that, using the continuity of the map $z \mapsto z - \eta^{*} \nabla f(z)$ for a contiously differentiable function $f$, we have \begin{equation} \label{eq:coercive-cvgt-lim-next-crit} \lim_{t \to +\infty} \left( y^{(t)} - \eta^{*} \nabla f(y^{(t)}) \right) = x^{*} - \eta^{*} \nabla f(x^{*}) = x^{**} . \end{equation} By definition of $\phi^{(t)}$, we also have for all $t \geq 0$ that \[ \phi^{(\psi(t))}(\eta^{*}) \geq \phi^{(\psi(t))}(\eta^{(\psi(t))}) \geq \ell=f(x^{*}). \] Hence, \[ f(y^{(t)} - \eta^{*} \nabla f(y^{(t)})) \geq f(x^{*}) \] Using [[eqref:eq:coercive-cvgt-lim-next-crit]], we get that $f(x^{**}) \geq f(x^{*})$, that is a contradiction. In conclusion, $x^{*}$ is a critical point. The same argument applies to any convergent subsequence. #+end_proof Remark that if in addition $f$ has a unique critical point, which is then its unique global minimizer, then $x^{(t)}$ converges to this global minimizer. #+name: cor:cvgt-gd-coercive-c1-min #+begin_corollary Let $f: \RR^{d} \to \RR$ be a coercive, continuously differentiable function with a unique critical point $x^{\star}$. For any initial guess $x^{(0)}$, the /oracle/ GD iterates $x^{(t)}$ converge towards $x^{\star}$ #+end_corollary #+begin_proof See Exercise [[num:ex:cvgt-gd-coercive-c1-min]]. #+end_proof *** Smooth function bounded from below Consider a function $f: \RR^{d} \to \RR$ that is $L$-smooth, but not necessarly convex. In addition, we suppose that $f$ has full domain and is bounded below on $\RR^{d}$. The following proposition gives a $O(1/\sqrt{T})$ rate for the 1st-order optimality using a constant step-size. A similar proof is doable for the oracle or the backtracking gradient descent. #+begin_proposition Convergence of [[eqref:eq:gradient-descent]] for $L$-smooth functions Let $f: \RR^{d} \to \RR$ be a $L$-smooth function with $L>0$, bounded from below by $\bar f \in \RR$. For any initial guess $x^{(0)}$, the GD iterates $x^{(t)}$ with step-size $\eta^{(t)} = \eta \in (0,2/L)$ satisfy $\nabla f(x^{(t)})\to 0$, and moreover \[ \min_{0 \leq t \leq T} \norm{\nabla f(x^{(t)})} \leq \frac{1}{\sqrt{T+1}} \left( \omega^{-1} L (f(x^{(0)}) - \bar f) \right)^{1/2} , \] where $\omega = 2 \alpha (1-\alpha)$, $0<\alpha<1$, and $\eta = \frac{2\alpha}{L}$. #+end_proposition #+begin_proof /(i) Bound on one step of gradient descent./ For $x \in \RR^{d}$, let $y = x - \eta \nabla f(x)$. Using [[prop:grad-smooth-upper-bound]], we have that \begin{align*} f(y) &\leq f(x) + \dotp{\nabla f(x)}{y - x} + \frac{L}{2} \norm{y - x}^{2} \\ &=f(x) + \dotp{\nabla f(x)}{-\eta \nabla f(x)} + \frac{L}{2} \norm{\eta \nabla f(x)}^{2} \\ &=f(x) - \eta \norm{\nabla f(x)}^{2} + \frac{L \eta^{2}}{2} \norm{\nabla f(x)}^{2} \\ &=f(x) - \eta(1 - \frac{L\eta}{2}) \norm{\nabla f(x)}^{2} . \end{align*} To ensure that $f(y) \leq f(x)$, we need to require that $\eta(1 - \frac{L\eta}{2}) \geq 0$ that is $0\leq\eta\leq\frac{2}{L}$. We can parameterize $\eta$ as $\eta = \frac{2 \alpha}{L}$ with $\alpha \in (0,1)$. Hence, we get the descent \begin{equation} \label{eq:cvgt-gd-lip-descent} f(x) - f(y) \geq \frac{2 \alpha(1-\alpha)}{L} \norm{\nabla f(x)}^{2} . \end{equation} /(ii) Convergence of 1st-order optimality./ Applying [[eqref:eq:cvgt-gd-lip-descent]] to $x = x^{(t)}$ and $y = x^{(t+1)}$, we get that \begin{equation} \label{eq:cvgt-gd-lip-descent-iter} f(x^{(t)}) - f(x^{(t+1)}) \geq \frac{2 \alpha(1-\alpha)}{L} \norm{\nabla f(x^{(t)})}^{2} . \end{equation} Summing inequality [[eqref:eq:cvgt-gd-lip-descent-iter]] for $t = 0 \dots T$, we obtain \begin{equation*} \sum_{t=0}^{T} f(x^{(t)}) - f(x^{(t+1)}) \geq \frac{2 \alpha(1-\alpha)}{L} \sum_{t=0}^{T }\norm{\nabla f(x^{(t)})}^{2} . \end{equation*} Observing that the l.h.s. telescopes, we have \begin{equation} \label{eq:cvgt-gd-lip-descent-sum} \frac{2 \alpha(1-\alpha)}{L} \sum_{t=0}^{T }\norm{\nabla f(x^{(t)})}^{2} \leq f(x^{(0)}) - f(x^{(T+1)}) \leq f(x^{(0)}) - \bar f , \end{equation} by definition of $\bar f$. Since [[eqref:eq:cvgt-gd-lip-descent-sum]] is true for all $T \in \NN$, we get $\nabla f(x^{(t)})$ converges towards 0. /(iii) Rate of convergence./ Using the fact that for all $t = 0 \dots T$, we have \[ \min_{0\leq s\leq T}\norm{\nabla f(x^{(s)})}\leq\norm{\nabla f(x^{(t)})} \] for each $0\leq t\leq T$, we have from [[eqref:eq:cvgt-gd-lip-descent-sum]] that \[ \frac{2 \alpha(1-\alpha)}{L} (T+1) \min_{0 \leq t \leq T} \norm{\nabla f(x^{(t)})}^{2} \leq f(x^{(0)}) - \bar f , \] Hence, the claimed result. #+end_proof *Note that we cannot say /anything/ in this context about the rate of convergence of $f(x^{(t)})$ or $(x^{(t)})$!* One can show that $\eta = \frac{1}{L}$ is the optimal step-size with respect to the bound in [[eqref:eq:cvgt-gd-lip-descent]]. ** Convergence of gradient descent for convex functions *** Convex $L$-smooth function When $f$ is supposed to be convex, we can have a rate of convergence in objective values. #+name: prop:cvgt-convex-smooth-gd #+begin_proposition Rate of [[eqref:eq:gradient-descent]] for convex $L$-smooth functions Let $f: \RR^{d} \to \RR$ be a convex $L$-smooth function with $L>0$ and at least one minimizer. For any initial guess $x^{(0)}$, the GD iterates $x^{(t)}$ with step-size $\eta^{(t)} = \eta \in (0,\frac{2}{L})$ converge towards an optimal point $x^{\star}$ of $f$, and moreover \[ f(x^{(t)}) - f^{\star} \leq \frac{ 2(f(x^{(0)}) - f^{\star}) \norm{x^{(0)} - x^{\star}}^{2} }{ t \eta (2 - L \eta) (f(x^{(0)}) - f^{\star}) + 2 \norm{x^{(0)} - x^{\star}}^{2} } . \] If $x^{(0)}$ is a minimizer, the iterates are stationary and the first bound is understood as zero. Moreover, if $\eta = \frac{1}{L}$, then \[ f(x^{(t)}) - f^{\star} \leq \frac{2 L \norm{x^{(0)} - x^{\star}}^{2}}{t + 4} . \] #+end_proposition #+begin_proof Let $x^{\star}$ a minimizer of $f$. If $f(x^{(0)})=f(x^\star)$, the iterates are stationary and the bounds are understood as zero. Otherwise $r^{(0)}>0$. In the following divisions, assume $\delta^{(t+1)}>0$; if an iterate is a minimizer, all later iterates stay there and the claimed bounds are immediate. We consider $r^{(t)} = \norm{x^{(t)} - x^{\star}}$ the lack of optimality[fn:2]. We have \begin{align*} (r^{(t+1)})^{2} &= \norm{x^{(t)} - x^{\star} - \eta \nabla f(x^{(t)})}^{2} \\ &= (r^{(t)})^{2} - 2\eta \dotp{\nabla f(x^{(t)})}{x^{(t)} - x^{\star}} + \eta^{2} \norm{\nabla f(x^{(t)})}^{2} \end{align*} Using the co-coercivity of the gradient ([[prop:grad-smooth-cocoercive]]), we have that \begin{equation*} \dotp{\nabla f(x^{(t)}) - \underbrace{\nabla f(x^{\star})}_{=0}}{x^{(t)} - x^{\star}} \geq \frac{1}{L} \norm{\nabla f(x^{(t)}) - \underbrace{\nabla f(x^{\star})}_{=0}}^{2} . \end{equation*} Thus, \[ (r^{(t+1)})^{2} \leq (r^{(t)})^{2} - \eta(\frac{2}{L} - \eta) \norm{\nabla f(x^{(t)})}^{2} . \] In particular, we get that $r^{(t)} \leq r^{(0)}$ for all $t \geq 0$. Using the smoothness of $f$, [[prop:grad-smooth-upper-bound]] gives us the bound \begin{align*} f(x^{(t+1)}) &\leq f(x^{(t)}) + \dotp{\nabla f(x^{(t)})}{x^{(t+1)} - x^{(t)}} + \frac{L}{2} \norm{x^{(t+1)} - x^{(t)}}^{2} \end{align*} Using the gradient descent update, we have that \begin{equation*} f(x^{(t+1)}) \leq f(x^{(t)}) - \eta(1 - \frac{L\eta}{2}) \norm{\nabla f(x^{(t)})}^{2} . \end{equation*} Now, let $\delta^{(t)} = f(x^{(t)}) - f(x^{\star})$. Using the differential characterization of convexity ([[prop:convex-diff]]), we have \[ \delta^{(t)} \leq \dotp{\nabla f(x^{(t)})}{x^{(t)} - x^{\star}} . \] Using Cauchy--Schwarz inequality, we have \[ \delta^{(t)} \leq \norm{\nabla f(x^{(t)})} \norm{x^{(t)} - x^{\star}} = r^{(t)} \norm{\nabla f(x^{(t)})} \leq r^{(0)} \norm{\nabla f(x^{(t)})} . \] Hence, we have \[ \delta^{(t+1)} \leq \delta^{(t)} - \frac{q}{(r^{(0)})^{2}} (\delta^{(t)})^{2} , \] where $q = \eta(1 - \frac{L\eta}{2})$. Multiplying both side by $\frac{1}{\delta^{(t)}\delta^{(t+1)}} > 0$, we get that \[ \frac{1}{\delta^{(t)}} \leq \frac{1}{\delta^{(t+1)}} - \frac{q}{(r^{(0)})^{2}} \frac{\delta^{(t)}}{\delta^{(t+1)}} . \] Since $(f(x^{(t)}))$ is nonincreasing, we have $\frac{\delta^{(t)}}{\delta^{(t+1)}} \geq 1$, hence \[ \frac{1}{\delta^{(t+1)}} \geq \frac{1}{\delta^{(t)}} + \frac{q}{(r^{(0)})^{2}} . \] Summing $T$ inequalities of this type, we obtain \[ \frac{1}{\delta^{(T)}} \geq \frac{1}{\delta^{(0)}} + T \frac{q}{(r^{(0)})^{2}} . \] We conclude using a bit of computation: \begin{equation*} \delta^{(T)} \leq \left(\frac{1}{\delta^{(0)}} + T \frac{q}{(r^{(0)})^{2}} \right)^{-1} = \left( \frac{(r^{(0)})^{2} + T q \delta^{(0)}}{\delta^{(0)}(r^{(0)})^{2}} \right)^{-1} = \frac{\delta^{(0)}(r^{(0)})^{2}}{(r^{(0)})^{2} + T q \delta^{(0)}} \end{equation*} Replacing $q$, $r^{(0)}$ and $\delta^{(0)}$ by their expression gives the result. Maximizing the descent $\eta(2 - L\eta)$ gives the optimal step-size $\eta = \frac{1}{L}$. Injecting this value, we get that \[ \delta^{(T)} \leq \frac{2L\delta^{(0)}(r^{(0)})^{2}}{2L(r^{(0)})^{2} + T\delta^{(0)}} . \] Using the smoothness ([[prop:grad-smooth-upper-bound]]), we have \[ f(x^{(0)}) \leq f^{\star} + \dotp{\nabla f(x^{\star})}{x^{(0)} - x^{\star}} + \frac{L}{2} (r^{(0)})^{2} = f^{\star} + \frac{L}{2} (r^{(0)})^{2} \] Thus, \[ 2L (r^{(0)})^{2} + T \delta^{(0)} \geq (4 + T) \delta^{(0)} , \] which is the claimed result. Finally, the nonincreasing distances to any minimizer make the iterates bounded. A convergent subsequence exists, and the value bound and continuity show that its limit $\bar x$ is a minimizer. Since $\|x^{(t)}-\bar x\|$ is nonincreasing and tends to zero along that subsequence, the whole sequence converges to $\bar x$. #+end_proof *** Strongly convex $L$-smooth function We now prove the linear convergence of [[eqref:eq:gradient-descent]] when dealing with strongly convex functions. #+begin_proposition Rate of [[eqref:eq:gradient-descent]] for strongly convex smooth functions Let $f: \RR^{d} \to \RR$ be a $\mu$-strongly convex $L$-smooth function with $0<\mu\leq L$. For any initial guess $x^{(0)}$, the GD iterates $x^{(t)}$ with step-size $\eta^{(t)} = \eta \in (0,\frac{2}{\mu + L}]$ converge towards an optimal point of $f$, and moreover \[ \norm{x^{(t)} - x^{\star}}^{2} \leq \left( 1 - \frac{2 \eta \mu L}{\mu + L} \right)^{t} \norm{x^{(0)} - x^{\star}}^{2} . \] Moreover, if $\eta = \frac{2}{\mu + L}$, then \begin{align*} \norm{x^{(t)} - x^{\star}}^{2} & \leq \left( \frac{K_{f} - 1}{K_{f} + 1} \right)^{2t} \norm{x^{(0)} - x^{\star}}^{2} \\ f(x^{(t)}) - f^{\star} &\leq \frac{L}{2} \left( \frac{K_{f} - 1}{K_{f} + 1} \right)^{2t} \norm{x^{(0)} - x^{\star}}^{2} , \end{align*} where $K_{f} = L / \mu$. #+end_proposition #+begin_proof Let $r^{(t)} = \norm{x^{(t)} - x^{\star}}$. We start like the proof of [[prop:cvgt-convex-smooth-gd]]: \begin{align*} (r^{(t+1)})^{2} &= \norm{x^{(t)} - x^{\star} - \eta \nabla f(x^{(t)})}^{2} \\ &= (r^{(t)})^{2} - 2\eta \dotp{\nabla f(x^{(t)})}{x^{(t)} - x^{\star}} + \eta^{2} \norm{\nabla f(x^{(t)})}^{2} \end{align*} Using [[prop:smooth-strongly-coco]], we have \[ \dotp{\nabla f(x^{(t)}) - \nabla f(x^{\star})}{x^{(t)} - x^{\star}} \geq \frac{\mu L }{\mu + L} \norm{x^{(t)}-x^{\star}}^{2} + \frac{1}{\mu + L} \norm{\nabla f(x^{(t)}) - \nabla f(x^{\star})}^{2} , \] that is \[ \dotp{\nabla f(x^{(t)}) - \nabla f(x^{\star})}{x^{(t)} - x^{\star}} \geq \frac{\mu L }{\mu + L} (r^{(t)})^{2} + \frac{1}{\mu + L}\norm{\nabla f(x^{(t)})}^{2} . \] Hence, \begin{align*} (r^{(t+1)})^{2} &\leq \left( 1 - \frac{2 \eta \mu L}{\mu + L} \right) (r^{(t)})^{2} + \eta \left( \eta - \frac{2}{\mu + L} \right) \norm{\nabla f(x^{(t)})}^{2} . \end{align*} Since $\eta - \frac{2}{\mu + L} \leq 0$, we can drop it and we obtain the recursion $(r^{(t+1)})^{2} \leq (1-q) (r^{(t)})^{2}$ with $q = \frac{2 \eta \mu L}{\mu + L}$, that proves the first claim (linear rate). Let $\eta = \frac{2}{\mu + L}$. We have \[ 1 - q = 1 - \frac{4\mu L}{(\mu+L)^{2}} = \frac{(L - \mu)^{2}}{(L+\mu)^{2}} = \left( \frac{K_{f} - 1}{K_{f} + 1} \right)^{2}. \] The last inequality is yet another use of [[prop:grad-smooth-upper-bound]]. #+end_proof Gradient descent does not reach the best rates that a first-order method can achieve, namely $1/t^{2}$ for smooth convex functions and a linear rate governed by $\sqrt{K_{f}}$ instead of $K_{f}$ for smooth strongly convex ones, as shown in [[/intro-to-lower-bounds/][Introduction to lower bounds in optimization]]. # TODO Polyak assumption ** An invitation to flow The joint study of ordinary differential equations and iterative algorithms is very fruitful. Imagine that the iterate $x^{(t)}$ can be viewed as “snapshot” $x^{(t)} = x(t \eta)$ of a smooth curve $x:[0,+\infty)\to\RR^d$, for some learning rate $\eta>0$. Let $\tau = t \eta$, observe that \[ x(\tau + \eta) = x^{(t+1)} = x^{(t)} - \eta \nabla f(x^{(t)}) = x(\tau) - \eta \nabla f(x(\tau)) . \] Reorganizing the terms, we get that \[ \frac{1}{\eta} \left( x(\tau + \eta) - x(\tau) \right) = - \nabla f(x(\tau)) . \] Assuming enough regularity, we can let $\eta$ goes to 0, and we obtain the ODE \[ \dot x(\tau) = - \nabla f(x(\tau)) , \] where $\dot x(\tau) = \frac{dx}{d\tau}(\tau)$ is the derivative of $x$ along the time. The Cauchy problem \begin{equation} \label{eq:gradient-flow}\tag{GF} \begin{cases} \dot x(\tau) = - \nabla f(x(\tau)) & \text{if } \tau \geq 0 \\ x(0) = x^{(0)} ,& \end{cases} \end{equation} is known as the /gradient flow/ of $f$. One can thus interpret the step-size (or learning rate) $\eta$ as the discretization precision of the gradient flow. It is possible to derive a similar convergence result for [[eqref:eq:gradient-flow]] as for the gradient descent. #+name: thm:gradient-flow-convergence-convex #+begin_theorem Convergence of the gradient flow Let $f: \RR^{d} \to \RR$ be convex, continuously differentiable, and have at least one minimizer. Then, for any initial point $x^{(0)}$, the dynamics $\tau \mapsto x(\tau)$ converges towards an optimal point $x^{\star}$ of $f$, and moreover, for all $\tau>0$, one has \[ f(x(\tau)) - f(x^\star) \leq \frac{\norm{x^{(0)} - x^{\star}}^{2}}{2\tau} . \] #+end_theorem #+begin_proof Let $z$ a minimizer of $f$. By convexity, we have \[ \frac{d}{d\tau}\frac12\norm{x(\tau)-z}^2 =-\dotp{\nabla f(x(\tau))}{x(\tau)-z} \leq -(f(x(\tau))-f(z))\leq 0. \] The continuous vector field gives a local solution. Its distance to $z$ is nonincreasing, so it stays bounded and extends to all $\tau\geq 0$. Monotonicity of $\nabla f$ makes the distance between two solutions with the same starting point nonincreasing, so the solution is unique. Moreover, \[ \frac{d}{d\tau}f(x(\tau))=-\norm{\nabla f(x(\tau))}^2\leq 0. \] Integrating the first inequality and using this monotonicity, we obtain \[ \tau(f(x(\tau))-f(z)) \leq\int_0^\tau(f(x(s))-f(z))\,ds \leq\frac12\norm{x^{(0)}-z}^2. \] Hence, the claimed value bound holds for any minimizer $z$. Since the trajectory is bounded, it has a limit point $\bar x$ along a sequence of times tending to infinity. The value bound and continuity show that $\bar x$ is a minimizer. Its distance to the trajectory is nonincreasing and tends to zero along that sequence, so $x(\tau)$ converges to $\bar x$. Taking $z=\bar x=x^\star$ gives the displayed bound. #+end_proof ** Complements *** Optimization for multinomial regression We study here a method for classification with $K$ classes called the /multinomial logistic regression/ or /softmax classification/. The objective function reads for $W \in \RR^{p \times K}$, \begin{equation} \label{eq:gd-softmax-classif-loss} f(W) = - \sum_{i=1}^{n} \sum_{k=1}^{K} \mathbf{1}_{y_{i} = k} \log \left( \hat p(y_{i} = k \mid x_{i}) \right) + \lambda \norm{W}_{\text{Fro}}^{2} , \end{equation} where \begin{equation*} \hat p(y_{i} = k \mid x_{i}) = \frac{\exp(x_{i}^{\top} W_{k})}{\sum_{l=1}^{K} \exp(x_{i}^{\top} W_{l})} . \end{equation*} Here $x_i\in\RR^p$, $y_i\in\{1,\dots,K\}$, $W_k$ denotes the $k$-th column of $W$, and $\lambda\geq 0$. The /softmax/ function $\sigma: \RR^{K} \to \RR^{K}$ is defined as \[ \sigma(x) = (\sigma_{1}(x),\dots,\sigma_{K}(x))^{\top} \quad \text{where} \quad \sigma_{i}(x) = \frac{e^{x_{i}}}{\sum_{j=1}^{K} e^{x_{j}}} . \] We also introduce the /negative log-softmax/ functions $\psi_{i}: \RR^{K} \to \RR$ defined as \[ \psi_{k}(x) = -\log \sigma_{k}(x) . \] Thus, our loss is expressed as \[ f(W) = \sum_{i=1}^{n} \sum_{k=1}^{K} \mathbf{1}_{y_{i} = k} \psi_k(W^\top x_i) + \lambda \norm{W}_{\text{Fro}}^{2} , \] #+name: lem:lem:jaco-softmax #+begin_lemma Jacobian of the softmax Let $x \in \RR^{K}$, \[ \Jaco{\sigma}(x) = \diag(\sigma(x)) - \sigma(x) \sigma(x)^{\top} . \] #+end_lemma #+begin_proof Observe that for $j \in \{1, \dots, K \}$, we have \[ \frac{\partial \left( \sum_{k=1}^{K} e^{x_{k}} \right)^{-1}}{\partial x_{j}} = - \frac{1}{\left( \sum_{k=1}^{K} e^{x_{k}} \right)^{2}} \frac{\partial \left( \sum_{k=1}^{K} e^{x_{k}} \right)}{\partial x_{j}} = - \frac{e^{x_{j}}}{\left( \sum_{k=1}^{K} e^{x_{k}} \right)^{2}} = - \frac{1}{\sum_{k=1}^{K} e^{x_{k}}} \sigma_{j}(x). \] Now, take $i,j \in \{ 1,\dots, K \}$. Then, two cases occurs: /If $i \neq j$./ We have \[ \frac{\partial \sigma_{i}}{\partial x_{j}}(x) = e^{x_{i}} \frac{\partial \left( \sum_{k=1}^{K} e^{x_{k}} \right)^{-1}}{\partial x_{j}} = - \sigma_{i}(x) \sigma_{j}(x) . \] /If $i = j$./ \[ \frac{\partial \sigma_{j}}{\partial x_{j}}(x) = e^{x_{j}} \frac{\partial \left( \sum_{k=1}^{K} e^{x_{k}} \right)^{-1}}{\partial x_{j}} + e^{x_{j}} \left( \sum_{k=1}^{K} e^{x_{k}} \right)^{-1} = \sigma_{j}(x) (1 - \sigma_{j}(x)) . \] #+end_proof #+name: lem:lem:grad-logsoftmax #+begin_lemma Gradient of the negative logsoftmax Let $i \in \{1,\dots,K\}$ and $x \in \RR^{K}$. Then, \[ \nabla \psi_{i}(x) = \sigma(x) - e_{i} \quad \text{and} \quad \nabla^{2} \psi_{i}(x) = \Jaco{\sigma}(x) . \] #+end_lemma #+begin_proof Let $k \in \{1,\dots,K\}$. Then, \[ \frac{\partial \psi_{i}(x)}{\partial x_{k}} = - \frac{1}{\sigma_{i}(x)} \frac{\partial \sigma_{i}(x)}{\partial x_{k}} = \begin{cases} \sigma_{k}(x) & \text{if } i \neq k \\ \sigma_{k}(x) - 1 & \text{if } i = k. \end{cases} \] Differentiating $\nabla\psi_i(x)=\sigma(x)-e_i$ gives $\nabla^2\psi_i(x)=\Jaco{\sigma}(x)$. #+end_proof #+name: lem:lem:convexity-logsoftmax #+begin_lemma Convexity of the negative logsoftmax For all $k \in \{1, \dots, K\}$, $\psi_{k}$ is convex. #+end_lemma #+begin_proof Using the preceding lemma, we have for any $v\in\RR^K$ \[ v^\top\nabla^2\psi_k(x)v =\sum_{j=1}^K\sigma_j(x)v_j^2 -\left(\sum_{j=1}^K\sigma_j(x)v_j\right)^2 =\sum_{j=1}^K\sigma_j(x)(v_j-\bar v)^2\geq 0, \] where $\bar v=\sum_{j=1}^K\sigma_j(x)v_j$, since $\sum_j\sigma_j(x)=1$. Hence, $\psi_k$ is convex. #+end_proof ** Exercises #+begin_exercise Consider the problem \[ \min_{x \in \RR^{d}} f(x) = \frac{1}{2} \| A x - b \|^{2} , \] where $A\in\RR^{n\times d}$, $n,d\geq 1$, $b\in\RR^n$, and the entries $A_{i,j}\sim\Nn(0,1)$ are independent and identically distributed. Explain why: 1. for $d\geq 2$, bad conditioning is possible, even though the entries of $A$ are Gaussian 2. almost surely, $f$ satisfies the Polyak--Łojasiewicz inequality $\norm{\nabla f(x)}^2\geq 2\mu_+(f(x)-f^\star)$, where $\mu_+$ is the smallest positive eigenvalue of $A^\top A$ #+end_exercise #+name: ex:cvgt-gd-coercive-c1-min #+begin_exercise Prove [[cor:cvgt-gd-coercive-c1-min]]. #+end_exercise #+begin_answer :of ex:cvgt-gd-coercive-c1-min Proof by contradiction. Suppose that $x^{(t)}$ does not converge towards $x^{\star}$, /i.e./, \[ \exists \epsilon > 0, \forall T \in \NN, \exists t \geq T, \quad \norm{x^{(t)} - x^{\star}} > \epsilon . \] Using boundedness from step $(ii)$, extract a convergent subsequence staying at distance at least $\epsilon$ from $x^\star$. By step $(iii)$, its limit is a critical point distinct from $x^\star$. Conclude that you have two critical points. #+end_answer #+begin_exercise Show that the coefficient $2\alpha(1-\alpha)/L$ in [[eqref:eq:cvgt-gd-lip-descent]] is maximized for $\alpha = \frac{1}{2}$. #+end_exercise * Propositions used from Lecture 1 :PROPERTIES: :APPENDIX: t :END: We recall here the propositions from Lecture 1 used in this lecture. All norms in this appendix are Euclidean. #+name: prop:convex-diff #+begin_proposition Differential characterization of convexity Let $f$ be a differentiable function on an open set $\Omega\subseteq\RR^p$, and $C\subseteq\Omega$ a convex subset of $\Omega$. Then $f$ is convex on $C$ if, and only if, \[ \forall x,\bar x\in C,\quad f(x)\geq f(\bar x)+\dotp{\nabla f(\bar x)}{x-\bar x}. \] #+end_proposition #+name: prop:grad-smooth-upper-bound #+begin_proposition Quadratic upper-bound Let $f$ a $L$-smooth function, with $L>0$. Then, for all $x,y\in\mathrm{dom}f$, \begin{equation} \label{eq:lsmooth-cs} \dotp{\nabla f(x)-\nabla f(y)}{x-y}\leq L\norm{x-y}^2. \end{equation} Moreover, if $\mathrm{dom}f$ is convex, then [[eqref:eq:lsmooth-cs]] is equivalent to \[ f(y)\leq f(x)+\dotp{\nabla f(x)}{y-x}+\frac{L}{2}\norm{x-y}^2, \quad\forall x,y\in\mathrm{dom}f. \] #+end_proposition #+name: prop:grad-smooth-cocoercive #+begin_proposition Co-coercivity of the gradient Let $f$ be a full-domain convex $L$-smooth function, with $L>0$. Then, $\nabla f$ is $1/L$-co-coercive, i.e., \[ \forall x,y\in\RR^n,\quad \dotp{\nabla f(x)-\nabla f(y)}{x-y} \geq\frac{1}{L}\norm{\nabla f(x)-\nabla f(y)}^2. \] #+end_proposition #+name: prop:smooth-strongly-coco #+begin_proposition Strengthened co-coercivity Let $f:\RR^n\to\RR$ have full effective domain and be $L$-smooth and $\mu$-strongly convex, where $0<\mu\leq L$. For any $x,y\in\RR^n$, we have \[ \dotp{\nabla f(x)-\nabla f(y)}{x-y} \geq\frac{\mu L}{\mu+L}\norm{x-y}^2 +\frac{1}{\mu+L}\norm{\nabla f(x)-\nabla f(y)}^2. \] #+end_proposition #+begin_ailvl The first version from 2024 was written from handwritten notes. The 2026 update was proofread by GPT-6 Astra, and the interactive figures were entirely generated by the same model from the non-interactive TikZ version. The org-mode conversion from tex was also done by AI. #+end_ailvl [fn:1] Note the presence of $H$ /after/ $(I - \eta H)^{2t}$. [fn:2] Note that we do not assume that $x^{(t)}$ converges towards this specific $x^{\star}$.