First-order algorithms are governed by two curvature scales. Smoothness limits how rapidly the gradient can change; strong convexity prevents the objective from becoming too flat. Their ratio is the condition number that appears in convergence rates.
Lipschitz gradients and quadratic upper models
Definition. A differentiable function \(f:C\to\mathbb R\) on a convex set is \(L\)-smooth if \[ \|\nabla f(x)-\nabla f(y)\|\le L\|x-y\| \qquad(x,y\in C). \]
Descent lemma. If \(f\) is \(L\)-smooth on a convex set containing the segment \([x,y]\), then \[ f(y)\le f(x)+\langle\nabla f(x),y-x\rangle +\frac L2\|y-x\|^2. \]
Proof. Put \(v=y-x\). The fundamental theorem of calculus along the segment gives \[ f(y)-f(x) =\int_0^1\langle\nabla f(x+tv),v\rangle\,\mathrm{d}t. \] Subtract \(\langle\nabla f(x),v\rangle\), apply Cauchy-Schwarz and \(L\)-smoothness, and integrate: \[ \int_0^1 \|\nabla f(x+tv)-\nabla f(x)\|\,\|v\|\,\mathrm{d}t \le\int_0^1Lt\|v\|^2\,\mathrm{d}t =\frac L2\|v\|^2. \]
Minimizing this quadratic upper model over \(y\) gives \(y=x-L^{-1}\nabla f(x)\) and \[ f\!\left(x-\frac1L\nabla f(x)\right) \le f(x)-\frac1{2L}\|\nabla f(x)\|^2. \] This one inequality supplies the basic descent estimate for gradient methods.
Strong convexity and quadratic lower models
Definition. A proper convex function \(f\) is \(\mu\)-strongly convex, \(\mu>0\), if \(f-\frac\mu2\|\cdot\|^2\) is convex. Equivalently, for \(g\in\partial f(x)\), \[ f(y)\ge f(x)+\langle g,y-x\rangle +\frac\mu2\|y-x\|^2. \]
Consequences of strong convexity. A proper lower-semicontinuous \(\mu\)-strongly convex function has at most one minimizer. If \(x^\star\) is its minimizer, then \[ f(x)-f(x^\star)\ge\frac\mu2\|x-x^\star\|^2. \] If \(f\) is differentiable, then \[ \langle\nabla f(x)-\nabla f(y),x-y\rangle \ge\mu\|x-y\|^2. \]
Proof. At a minimizer, \(0\in\partial f(x^\star)\), so the defining lower model gives the quadratic-growth inequality. Two distinct minimizers would make its right side strictly positive, a contradiction. In the differentiable case, write the strong-convexity inequality once with \((x,y)\), once with \((y,x)\), and add them; the function values cancel and leave the strong monotonicity inequality.
Hessian bounds and the quadratic model
Twice-differentiable characterization. Let \(C\) be open and convex and \(f\in C^2(C)\). Then \(f\) is convex, \(\mu\)-strongly convex, or \(L\)-smooth precisely when, respectively, \[ \nabla^2f(x)\succeq0,\qquad \nabla^2f(x)\succeq\mu I,\qquad \nabla^2f(x)\preceq LI \quad(x\in C). \]
Proof. Restrict \(f\) to each line \(t\mapsto x+tv\). Its second derivative is \(v^\top\nabla^2f(x+tv)v\). The one-dimensional second-derivative criterion gives the lower bounds. Integrating \[ \nabla f(y)-\nabla f(x) =\int_0^1\nabla^2f(x+t(y-x))(y-x)\,\mathrm{d}t \] yields \(L\)-Lipschitz continuity when the operator norm of the Hessian is at most \(L\); the converse follows by taking directional difference quotients.
Quadratic objectives. For \(f(x)=\frac12x^\top Qx-b^\top x\) with symmetric \(Q\succ0\), the smoothness and strong-convexity constants are \(L=\lambda_{\max}(Q)\) and \(\mu=\lambda_{\min}(Q)\). The minimizer is \(x^\star=Q^{-1}b\), and the suboptimality is exactly \[ f(x)-f(x^\star) =\frac12(x-x^\star)^\top Q(x-x^\star). \]
Condition number and a change of geometry
The ratio \[ \kappa=\frac L\mu \] is the objective condition number. For a quadratic it equals the spectral condition number of \(Q\). Large \(\kappa\) means that equal-value contours are elongated: curvature is high in some eigendirections and low in others. Gradient descent must use a step small enough for the highest curvature while making slow progress along the lowest.
An invertible change of variables \(x=Sz\) replaces the Hessian by \(S^\top Q S\). Preconditioning, Newton's method, natural gradients, and mirror descent can all be read as attempts to choose a geometry in which the effective condition number is smaller.