Introduction to
Calculus

Let f : D → ℝ be a function defined on a set D ⊆ ℝ, and let a be a limit point of D. The limit of f(x) as x approaches a is L, written

if for every ε > 0 there exists δ > 0 such that whenever 0 < |x − a| < δ and x ∈ D, we have |f(x) − L| < ε.

• $\lim_{x\to a}f(x)$the limit of f at a; the value L that f(x) approaches as x → a.
• $\varepsilon$an arbitrarily small positive tolerance on the output.
• $\delta$a positive radius around a ensuring the output stays within ε of L.

The right-hand limit of f(x) as x approaches a from the right is denoted $\lim_{x\to a^+} f(x)$ and defined by restricting the ε–δ condition to x > a. Similarly, the left-hand limit $\lim_{x\to a^-} f(x)$ restricts to x < a. The two-sided limit exists if and only if both one-sided limits exist and are equal:

• $\lim_{x\to a^+} f(x)$right-hand limit; x approaches a from above.
• $\lim_{x\to a^-} f(x)$left-hand limit; x approaches a from below.

A function f : D → ℝ is continuous at a point a ∈ D if

Equivalently, for every ε > 0 there exists δ > 0 such that |x − a| < δ and x ∈ D implies |f(x) − f(a)| < ε. A function is continuous on an interval if it is continuous at every point of that interval.

• $f \in C^0(D)$the set of all continuous functions on D.

Let f : [a, b] → ℝ be continuous on the closed interval [a, b]. If y₀ is any number between f(a) and f(b) (inclusive), then there exists at least one c ∈ [a, b] such that

• $[a, b]$a closed interval; includes both endpoints.
• $y_0$any value between f(a) and f(b).

If f : [a, b] → ℝ is continuous on a closed and bounded interval [a, b], then f attains both a maximum and a minimum value on [a, b]. That is, there exist c, d ∈ [a, b] such that

• $f(c)$the global minimum value of f on [a, b].
• $f(d)$the global maximum value of f on [a, b].

The derivative of a function f at a point a in its domain is the limit (if it exists):

Geometrically, f'(a) is the slope of the tangent line to the graph of f at x = a.

• $f'(a)$the derivative of f at a; also written $\frac{df}{dx}\big|_{x=a}$ or $Df(a)$.
• $h$an infinitesimal increment; the difference quotient approaches the derivative as h → 0.

If f is differentiable at a, then f is continuous at a. The converse is false: continuity does not guarantee differentiability (e.g., f(x) = |x| at x = 0).

For differentiable functions f, g and constant c ∈ ℝ:

If g is differentiable at x and f is differentiable at g(x), then h = f ∘ g is differentiable at x and

In Leibniz notation: $\frac{dy}{dx} = \frac{dy}{du}\cdot \frac{du}{dx}$.

Let f : [a, b] → ℝ be continuous on [a, b] and differentiable on (a, b). Then there exists at least one c ∈ (a, b) such that

If $\lim_{x\to a} f(x) = \lim_{x\to a} g(x) = 0$ or both limits are ±∞, then

provided the limit on the right exists.

The n-th derivative $f^{(n)}(x)$ is defined recursively:

• $f \in C^n$f is n-times continuously differentiable.
• $C^\infty$smooth functions; infinitely differentiable.

The Taylor polynomial of degree n for f centred at a is

• $R_n(x)$remainder: $f(x) - T_n(x) = O(|x-a|^{n+1})$.

For a partition $P = \{x_0,\dots,x_n\}$ of [a, b], the Riemann sum is

The Riemann integral is the limit as $\|P\| \to 0$.

Define $F(x) = \int_a^x f(t)\,dt$. If f is continuous at c, then F is differentiable at c and

If F is any antiderivative of f on [a, b], then

A sequence $(a_n)$ converges to L if

The series $\sum_{n=1}^\infty a_n$ converges to S if $\lim_{N\to\infty} S_N = S$, where $S_N = \sum_{n=1}^N a_n$.

• Comparison Test: $0 \le a_n \le b_n$ and $\sum b_n$ converges ⇒ $\sum a_n$ converges.
• Ratio Test: $\rho = \lim |a_{n+1}/a_n|$; converges if $\rho < 1$, diverges if $\rho > 1$.
• Integral Test: $\sum a_n$ converges iff $\int_1^\infty f(x)\,dx$ converges (when $f(n)=a_n$, f positive, decreasing).

Converges absolutely for $|x-c| < R$, diverges for $|x-c| > R$.

A function $f : \mathbb{R}^n \to \mathbb{R}$ assigns a real number to each point $x = (x_1,\dots,x_n)$. The limit $\lim_{x\to a}f(x)=L$ requires $0 < \|x-a\| < \delta \Rightarrow |f(x)-L|<\varepsilon$.

For $f : U \to \mathbb{R}^m$, the differential at x is the $m \times d$ matrix

If all partials up to order k exist and are continuous, f is $C^k$ and the order of differentiation is irrelevant: $\partial_1\partial_2\partial_1 f = \partial_1^2 \partial_2 f$.

• $\nabla^2 f(x)$symmetric $d\times d$ matrix; $h_1^T \nabla^2 f(x) h_2 = d^2 f(x)(h_1, h_2)$.

Let $f \in C^k$ and $[x, x+h] \subset U$. Then

In big-O form: $f(x+h) = \sum_{j=0}^{k} \frac{1}{j!} d^{j}f(x)(h,\dots,h) + o(\|h\|^k)$.

Differentiation Rules

• Constant multiple: $(c f)' = c f'$
• Sum: $(f+g)' = f' + g'$
• Product: $(fg)' = f'g + fg'$
• Quotient: $(f/g)' = (f'g - fg')/g^2$
• Chain: $(f\circ g)' = f'(g)\cdot g'$

Elementary Derivatives

• $\frac{d}{dx}x^n = nx^{n-1}$
• $\frac{d}{dx}e^x = e^x$, $\frac{d}{dx}\ln x = 1/x$
• $\frac{d}{dx}\sin x = \cos x$, $\frac{d}{dx}\cos x = -\sin x$
• $\frac{d}{dx}\arctan x = 1/(1+x^2)$

Integration Rules

• Linearity: $\int(c_1 f+c_2 g) = c_1\int f + c_2\int g$
• Parts: $\int u\,dv = uv - \int v\,du$
• FTC II: $\int_a^b f = F(b)-F(a)$

Multivariable Formulas

• Gradient: $\nabla f = (\partial_1 f,\dots,\partial_d f)^T$
• Divergence: $\nabla\cdot F = \sum \partial_i F_i$
• Laplacian: $\Delta f = \sum \partial_i^2 f$
• Det differential: $d(\det)(A)H = \operatorname{trace}(\operatorname{cof}(A)^TH)$
• Inverse differential: $d(A^{-1})H = -A^{-1}HA^{-1}$

A function $f : C \to \mathbb{R}$ on a convex set $C \subseteq \mathbb{R}^d$ is convex if for all $x, y \in C$ and $t \in [0, 1]$,

Geometrically, the chord connecting any two points on the graph lies above (or on) the graph. If the inequality is strict for $x \neq y$ and $t \in (0,1)$, f is strictly convex.

For a $C^2$ function, convexity is equivalent to the Hessian being positive semi-definite everywhere:

Convex functions have a crucial property: every local minimum is a global minimum. This makes convexity the central structural assumption in optimization for machine learning.

• $A \succeq 0$positive semi-definite; all eigenvalues are non-negative.
• $A \succ 0$strictly positive definite; all eigenvalues are strictly positive.

Let $f : \mathbb{R}^d \to \mathbb{R}$ be differentiable. A necessary condition for $x^*$ to be a local minimum is that the gradient vanishes:

Such a point is called a critical point. If f is convex, this condition is also sufficient for a global minimum. For constrained minimization $\min_{x \in C} f(x)$ over a convex set C, the first-order condition becomes the variational inequality:

• $x^*$an optimal point (minimizer); satisfies the stationarity condition.

Let $f \in C^2$ and $\nabla f(x^*) = 0$. Let $H = \nabla^2 f(x^*)$:

A saddle point is a critical point that is neither local min nor max. In neural network training, the loss landscape is typically non-convex and riddled with saddle points; their proliferation in high dimensions is a key challenge for gradient-based optimizers.

• saddle pointa critical point where H is indefinite; a min in some directions, max in others.

Gradient descent is the canonical first-order algorithm for minimizing a differentiable function. Starting from $x_0$, the update rule is

where $\eta > 0$ is the learning rate. For a convex, L-smooth function with step size $\eta = 1/L$, the convergence rate is

• $\eta$learning rate; controls the step size in the negative gradient direction.
• $L$Lipschitz constant of $\nabla f$; governs the maximum stable step size.

For an objective that is a sum over n training samples, $f(x) = \frac{1}{n}\sum_{i=1}^n \ell_i(x)$, SGD approximates the gradient with a mini-batch $\mathcal{B}$:

The estimator is unbiased: $\mathbb{E}[g_k] = \nabla f(x_k)$. Convergence requires a diminishing step-size schedule or adaptive methods (Adam, RMSProp). SGD is the workhorse of deep learning.

• $g_k$stochastic gradient; an unbiased estimate of $\nabla f(x_k)$.
• $\mathcal{B}$mini-batch; a random subset of training indices.

To minimize $f(x)$ subject to $g_i(x) = 0$, form the Lagrangian:

At an optimum, the KKT stationarity condition requires

For inequality constraints $h_j(x) \le 0$, KKT requires $\mu_j \ge 0$ and complementary slackness $\mu_j h_j(x^*) = 0$. These conditions underpin SVMs, duality theory, and constrained neural network training.

• $\mathcal{L}$Lagrangian; a penalized objective combining f and constraint violations.
• $\lambda_i, \mu_j$Lagrange / KKT multipliers for equality and inequality constraints.

Backpropagation is a systematic application of the chain rule on a computational graph to compute the gradient of a scalar loss $\mathcal{L}$ with respect to all parameters. For a network computing $z^{(l)} = \sigma(W^{(l)} z^{(l-1)} + b^{(l)})$, define the error signal $\delta^{(l)} = \partial \mathcal{L}/\partial z^{(l)}$. The recurrence is

and the weight gradients are

One forward pass (cache activations) plus one backward pass (propagate errors) gives all gradients in $O(\text{parameters})$ time.

• $\delta^{(l)}$error signal at layer l; gradient of the loss w.r.t. layer outputs.
• $\odot$element-wise (Hadamard) product.

For $f : \mathbb{R}^d \to \mathbb{R}^m$ with Jacobian $J = df(x) \in \mathbb{R}^{m\times d}$:

For scalar losses (m = 1), one VJP with $u = 1$ recovers the full gradient $\nabla f(x)$ in a single pass — this is why reverse-mode is preferred when d (number of parameters) vastly exceeds m.

• JVPJacobian–vector product; directional derivative of f in direction v.
• VJPvector–Jacobian product; gives gradients in one reverse pass.

A function is Lipschitz continuous with constant $K$ if $\|f(x)-f(y)\| \le K\|x-y\|$. A differentiable scalar function is L-smooth if

The descent lemma (key convergence tool) follows from L-smoothness:

This quadratic upper bound justifies the step size $\eta \le 1/L$ in gradient descent.

• $L$smoothness constant; bounds the curvature; governs stable step sizes.

A differentiable function $f$ is μ-strongly convex if for all $x, y$,

This ensures a unique global minimum and linear convergence. For an L-smooth, μ-strongly convex function, gradient descent converges as

• $\mu$strong convexity modulus; minimum curvature.
• $\kappa = L/\mu$condition number; large κ means slow convergence.

Let $g : \mathbb{R}^d \to \mathbb{R}^d$ be a diffeomorphism and $Y = g(X)$ where $X$ has density $p_X$. Then

The absolute Jacobian determinant $|\det\, dg(x)|$ accounts for local volume distortion. This formula is fundamental to normalizing flows, the reparameterization trick in VAEs, and latent variable models.

• $|\det\, dg|$absolute Jacobian determinant; local volume scaling of the transformation.

The convex conjugate (Fenchel conjugate) of $f$ is

The function $f^*$ is always convex. For a convex, closed, proper f, the biconjugate satisfies $f^{**} = f$. The Fenchel–Young inequality states

Conjugates appear in dual SVM formulations, mirror descent, and the derivation of softmax from the log-partition function.

• $f^*(y)$conjugate of f; always convex regardless of f.

For a convex but possibly non-smooth $f$, a vector $s$ is a subgradient at x if

The subdifferential $\partial f(x)$ is the set of all subgradients. Optimality: $0 \in \partial f(x^*)$. The subgradient method is

Lasso regression, hinge loss, and ReLU activations all require subgradient reasoning. For $f(x)=|x|$ at $x=0$: $\partial f(0) = [-1,1]$.

• $\partial f(x)$subdifferential; set of all subgradients at x.

Automatic differentiation (AD) computes exact derivatives of programs via the chain rule on a computational graph — neither symbolic math nor finite differences.

• Forward mode (JVP): propagates tangents $\dot{v}_i = \partial v_i/\partial x_j$ alongside values; cost = O(d) passes for d inputs.
• Reverse mode (VJP): propagates adjoints $\bar{v}_i = \partial\mathcal{L}/\partial v_i$ backwards; cost = O(1) forward + backward for any number of inputs.

The fundamental update at each node in reverse mode:

• $\dot{v}_i$forward tangent of node i.
• $\bar{v}_i$reverse adjoint of node i; gradient of loss w.r.t. intermediate value.

The multivariate Gaussian density with mean $\mu$ and covariance $\Sigma \succ 0$:

Key matrix calculus identities for quadratic forms (constant symmetric A):

The log-determinant gradient (needed for MLE of $\Sigma$):

• $x^T A x$quadratic form; appears in Gaussian exponent and regularization.
• $\log\det\Sigma$log-determinant; in Gaussian log-likelihood and KL divergence.

Under dominated convergence, differentiation and integration may be exchanged:

For expectations over a fixed distribution: $\nabla_\theta\,\mathbb{E}_{p(x)}[f(x,\theta)] = \mathbb{E}_{p(x)}[\nabla_\theta f(x,\theta)]$.

When the distribution also depends on $\theta$, the log-derivative (REINFORCE) trick gives

These identities underpin the reparameterization trick in VAEs and the policy gradient theorem in reinforcement learning.

• $\nabla_\theta \log p$score function; its expectation under $p(\cdot;\theta)$ equals zero.

The Fourier transform of $f \in L^1(\mathbb{R}^d)$:

Differentiation becomes multiplication in frequency space: $\widehat{\partial_j f}(\xi) = 2\pi i\,\xi_j\,\hat{f}(\xi)$. This is central to understanding neural network expressivity, kernel methods (Bochner's theorem), and spectral analysis.

The Laplace transform:

• $\hat{f}(\xi)$Fourier transform at frequency $\xi$; turns derivatives into multiplications.

For a convex function $g$ and step size $\eta > 0$, the proximal operator is

The proximal gradient method minimizes composite objectives $f(x)+g(x)$ (smooth f, non-smooth g):

For $g(x)=\lambda\|x\|_1$ (Lasso), the proximal operator is soft-thresholding:

Proximal methods underlie ADMM, sparse representation, and many deep learning regularizers.

• $\operatorname{prox}_{\eta g}$proximal operator; balances proximity to v with minimizing g.

A point $x \in \Omega$ is a global minimizer (resp. maximizer) of $F$ on $\Omega$ if $F(y) \ge F(x)$ (resp. $F(y) \le F(x)$) for all $y \in \Omega$. Equivalently,

The set of all minimizers is denoted $\operatorname{argmin}_{\Omega} F$ (respectively $\operatorname{argmax}_{\Omega} F$). Minimizers need not be unique.

• $\operatorname{argmin}_{\Omega} F$the (possibly empty) set of global minimizers of $F$ on $\Omega$.
• $\operatorname{argmax}_{\Omega} F$the set of global maximizers.

A point $x \in \Omega$ is a local minimizer (resp. maximizer) of $F$ on $\Omega$ if there exists an open ball $B \subset \mathbb{R}^d$ containing $x$ such that

Thus a local extremum is only required to be optimal within some neighbourhood.

• local minimizera point that minimizes $F$ in a small neighbourhood intersected with $\Omega$.

An optimization problem consists of finding a minimizer (or maximizer) of an objective function $F$ on a set $\Omega$. We focus on minimization; maximization is symmetric.

The sublevel sets of $F$ are defined as $[F \le u]_{\Omega} = \{ x \in \Omega : F(x) \le u \}$. Note that

$F$ is called lower semicontinuous (l.s.c.) on $\Omega$ if its sublevel sets are closed in $\mathbb{R}^d$. This means: if a sequence $(x_n) \subset \Omega$ satisfies $F(x_n) \le u$ and converges to $x$, then $x \in \Omega$ and $F(x) \le u$. If, in addition, the sublevel sets are bounded for $u$ sufficiently close to $\inf F$, then $\operatorname{argmin}_{\Omega} F$ is an intersection of nested compact sets and therefore non‑empty — i.e., a minimizer exists.

• $[F \le u]_{\Omega}$sublevel set of $F$ at level $u$.
• l.s.c.lower semicontinuous; sublevel sets are closed.

Different assumptions on $F$ and $\Omega$ lead to distinct problem classes:

1. Unconstrained smooth optimization: $F$ is $C^1$ (or smoother) and $\Omega = \mathbb{R}^d$.
2. Constrained smooth optimization: $\Omega = \{ x \in \mathbb{R}^d : \gamma_i(x) \le 0,\; i=1,\dots,q \}$ with $F$ and all $\gamma_i$ of class $C^1$.
3. Convex optimization: $\Omega$ is convex (i.e., $x,y\in\Omega \Rightarrow [x,y]\subset\Omega$) and $F$ is convex ($F((1-t)x+ty) \le (1-t)F(x)+tF(y)$ for $x,y\in\Omega$).
4. Non‑smooth optimization: $F$ (or the constraints) lack differentiability; often arise in data science.
5. Linear programming: $F$ and all $\gamma_i$ are affine ($F(x) = b^T x + \beta$, $\gamma_i(x) = a_i^T x + c_i$).
6. Quadratic programming: $F$ is quadratic ($F(x) = \frac12 x^T A x - b^T x$) and the $\gamma_i$ are affine.
7. Combinatorial optimization: $\Omega$ is a discrete or finite set (e.g., $\mathbb{Z}^d$ or $\{0,1\}^d$).

• Convex seta set $\Omega$ such that the segment joining any two points in $\Omega$ is fully contained in $\Omega$.
• Convex functiona function satisfying $F((1-t)x+ty) \le (1-t)F(x) + t F(y)$ for all $x,y$ and $t\in[0,1]$.
• Affine functiona mapping of the form $x \mapsto b^T x + \beta$.

Let $\Omega \subset \mathbb{R}^d$ be open and $F : \Omega \to \mathbb{R}$ differentiable. Consider the problem $\min_{x\in\Omega} F(x)$.

Theorem 3.1 (Necessary conditions). If $x^*$ is a local minimum, then $\nabla F(x^*) = 0$. If $F$ is $C^2$, then $\nabla^2 F(x^*)$ is positive semidefinite.

Sufficient conditions. If $F$ is $C^2$, $\nabla F(x^*) = 0$, and $\nabla^2 F(x^*) \succ 0$, then $x^*$ is a local minimum.

For maximization, replace “positive semidefinite” by “negative semidefinite” (and similarly for definite).

Definition 3.2. A set $\Omega \subset \mathbb{R}^d$ is convex if $\forall x,y\in\Omega$, the segment $[x,y]\subset\Omega$. A function $F:\mathbb{R}^d \to (-\infty,+\infty]$ is convex if for all $x,y\in\mathbb{R}^d$, $\lambda\in[0,1]$,

If the inequality is strict for $\lambda\in(0,1)$ when finite, $F$ is strictly convex. The domain of $F$ is $\operatorname{dom}(F) = \{x : F(x) < \infty\}$; $F$ is proper if $\operatorname{dom}(F) \neq \emptyset$.

Proposition 3.5. For convex $F$, the function $\lambda \mapsto \frac{1}{\lambda}(F((1-\lambda)x+\lambda y)-F(x))$ is non‑decreasing (increasing if strictly convex).

Corollary 3.6. Any local minimum of a convex function is a global minimum.

• $\operatorname{dom}(F)$the effective domain of $F$ (points where $F$ is finite).

For a convex set $\Omega$, the affine hull $\operatorname{aff}(\Omega)$ is the smallest affine subspace containing $\Omega$. The relative interior is

Proposition 3.8. $\operatorname{relint}(\Omega)$ is non‑empty and convex. If $x\in\operatorname{relint}(\Omega)$, $y\in\Omega$, then $(1-\lambda)x+\lambda y \in \operatorname{relint}(\Omega)$ for all $\lambda\in[0,1)$.

Proposition 3.9. $x\in\operatorname{relint}(\Omega)$ iff for every $y\in\Omega$ there exists $\epsilon>0$ such that $x-\epsilon(y-x)\in\Omega$.

• $\operatorname{relint}(\Omega)$relative interior; always non‑empty for a non‑empty convex set.

Theorem 3.11. Let $F$ be convex and differentiable at $x\in\operatorname{int}(\operatorname{dom}(F))$. Then for all $y$,

Hence $\nabla F(x)=0$ implies $x$ is a global minimizer (unique if strictly convex). Conversely, if $F$ is $C^1$ on an open convex set and satisfies (3.5), then $F$ is convex.

Proposition 3.12. If $F$ is $C^2$ on an open convex domain, $F$ is convex iff $\nabla^2 F(x) \succeq 0$ for all $x$; strict convexity follows if $\nabla^2 F(x) \succ 0$.

Definition 3.13. A $C^1$ function $F$ is strongly convex (with modulus $m>0$) if

Proposition 3.14. A strongly convex function is strictly convex; if $\operatorname{dom}(F)=\mathbb{R}^d$, then $\operatorname{argmin} F$ is a single point. Moreover, (3.6) implies the quadratic growth condition (3.9).

Definition 3.15. $F$ is $L$-$C^k$ if it is $C^k$ and $\|d^k F(x) - d^k F(y)\| \le L\|x-y\|$. If $F$ is $L$-$C^1$ and strongly convex, one has the double inequality (3.8).

• $m$-strongly convexsatisfies (3.6); implies uniqueness of minimizer and quadratic growth.
• $L$-$C^k$$k$‑times differentiable with $L$‑Lipschitz $k$‑th differential.

Definition 3.17. A non‑zero vector $h$ is a direction of descent for $F$ at $x$ if $F(x+\epsilon h) < F(x)$ for small enough $\epsilon>0$.

Proposition 3.18. For $C^1$ $F$, if $h^T\nabla F(x) < 0$ then $h$ is a descent direction; conversely, any descent direction satisfies $h^T\nabla F(x) \le 0$.

The steepest descent direction for the Euclidean norm is $h = -\nabla F(x)$. More generally, given a positive definite matrix $A$, the steepest descent direction with respect to the norm $\|h\|_A = \sqrt{h^T A h}$ is $-\nabla_A F(x) = -A^{-1}\nabla F(x)$. Newton’s method uses $A = \nabla^2 F(x)$ (when positive definite).

• $-\nabla F(x)$steepest descent direction (Euclidean norm).
• $-\nabla_A F(x)$steepest descent for the norm induced by $A$.

Consider the iteration $x_{t+1} = x_t + \alpha_t h_t$ with $h_t$ a descent direction satisfying

Proposition 3.19. If $F$ is $L$-$C^1$ and (3.12) holds, then for sufficiently small $\alpha_t$,

Thus, if $F$ is bounded below, $\min_{t\le T} \|\nabla F(x_t)\|^2 = O(1/T)$.

Theorem 3.20 (convex case). If $F$ is convex and (3.14) holds ($F(x_{t+1})-F(x_t) \le -C\|\nabla F(x_t)\|^2$), then

Proposition 3.21 (strongly convex case). If $F$ is strongly convex with modulus $m$ and (3.14) holds, then

• linear convergenceachieved under strong convexity; the error decays geometrically.

A line search determines a step size $\alpha$ along a descent direction $h$. Let $f_h(\alpha) = F(x+\alpha h)$. The Armijo condition requires (with $c_1\in(0,1)$)

Backtracking: start with $\alpha = \alpha_{\max}$ and repeatedly multiply by $\rho\in(0,1)$ until (3.15) holds.

The weak Wolfe conditions add

The strong Wolfe conditions require $|h^T \nabla F(x+\alpha h)| \le c_2 |h^T \nabla F(x)|$.

Proposition 3.22. If $F$ is $L$-$C^1$ and (3.12), (3.15), (3.16a) hold, then there exists $C>0$ such that $F(x+\alpha h) \le F(x) - C\|\nabla F(x)\|^2$.

Proposition 3.23 / 3.24. Finite algorithms exist to find a step size satisfying the weak or strong Wolfe conditions, provided $F$ is $C^1$ and bounded below.

• $c_1$Armijo constant (typically small, e.g., $10^{-4}$).
• $c_2$Wolfe curvature constant (e.g., 0.9 for strong Wolfe).

When the gradient $\nabla F$ is too costly to compute exactly, a stochastic approximation can be used. The Robbins‑Monro type stochastic gradient descent (SGD) updates a parameter $x \in \mathbb{R}^d$ using random iterations:

where $\pi_x$ is a probability distribution on a set $S$ (which may depend on $x$), $H: \mathbb{R}^d \times S \to \mathbb{R}^d$ is an easily computable update direction, and $\alpha_{t+1}$ is the step size. The conditional distribution of $\xi_{t+1}$ given the past $U_t = (\xi_1,X_1,\dots,\xi_t,X_t)$ depends only on $X_t$ and is given by $\pi_{X_t}$.

• $\pi_x$probability distribution used to generate the stochastic update at $x$.
• $H(x,\xi)$a noisy estimate of the (negative) gradient direction.

Define the average direction

Write $X_{t+1} = X_t + \alpha_{t+1}\bar{H}(X_t) + \alpha_{t+1}\eta_{t+1}$ with $\eta_{t+1} = H(X_t,\xi_{t+1}) - \bar{H}(X_t)$. Then $\mathbb{E}[\eta_{t+1}\mid U_t] = 0$, making $M_T = \sum_{t=0}^T \alpha_{t+1}\eta_{t+1}$ a martingale.

Consider the following typical assumptions:

• (H1) There exists $C$ such that $\mathbb{E}_{\pi_x}[|H(x,\cdot)|^2] \le C(1+|x|^2)$.
• (H2) There exist $x^* \in \mathbb{R}^d$ and $\mu > 0$ such that $(x-x^*)^T\bar{H}(x) \le -\mu|x-x^*|^2$.
• (H3) $\sum_{k=1}^\infty \alpha_k = \infty$ and $\sum_{k=1}^\infty \alpha_k^2 < \infty$.

Under (H1)–(H3), the sequence $X_t$ converges in $L^2$ to $x^*$; in fact, almost‑sure convergence holds as well.

Lemma 3.25. If a non‑negative sequence $a_t$ satisfies $a_{t+1} \le (1-\delta_t)a_t + \epsilon_t$ with $0\le \delta_t\le 1$, let $v_{k,t} = \prod_{j=k+1}^t (1-\delta_j)$. Then

Lemma 3.26. Let $w_{st}$ ($s\le t$) be bounded with $\lim_{t\to\infty} w_{st}=0$ for each $s$, and $\sum_t |\beta_t| < \infty$. Then $\lim_{t\to\infty} \sum_{s=1}^t \beta_s w_{st} = 0$.

Using Lemma 3.25 with $\delta_t = 2\alpha_{t+1}\mu - C\alpha_{t+1}^2$ and $\epsilon_t = \tilde C \alpha_{t+1}^2$, one shows that $\mathbb{E}[|X_t-x^*|^2] \to 0$. In the constant step‑size case $\alpha_t = \alpha$, the mean‑square error satisfies $\limsup \mathbb{E}[|X_t-x^*|^2] = O(\alpha)$.

• $\bar{H}(x)$expected update direction; the deterministic flow follows $\dot{\bar{x}} = \bar{H}(\bar{x})$.
• $M_T$martingale noise term; its variance is controlled by the step‑size schedule.

Define the continuous‑time interpolation $X^\ell(\rho)$ by

The deterministic part of the algorithm is an Euler discretisation of the ordinary differential equation (ODE)

Proposition 3.27 (Benaïm). Assume $\bar{H}$ is Lipschitz and bounded. Then, for any $T>0$, there exists $C(T)$ such that for all $\rho\ge 0$,

where $\phi(\cdot,\omega)$ is the solution of (3.24) with $\bar{x}(0)=\omega$, and $\Delta(\rho,T)$ controls the cumulative martingale noise.

Using martingale inequalities (Doob’s inequality), one can show that $\Delta(\rho,T)$ is small with high probability, so the stochastic process stays close to the ODE solution over finite intervals.

Proposition 3.28. If $\bar{H} = -\nabla E$ is a gradient field with finitely many critical points and $X_t$ remains bounded, then $X_t$ converges to a critical point of $E$.

Theorem 3.29 (Lyapunov stability). Assume there exists a $C^2$ function $U$ with bounded second derivatives and $K_0>0$ such that for $|x|\ge K_0$, $\nabla U(x)^T \bar{H}(x) \le 0$ and $U(x) \ge \gamma|x|^2$, $\gamma>0$. Then the interpolated trajectories $X^\ell(\rho)$ are almost surely bounded. Hypothesis (H2) provides such a Lyapunov function ($U(x)=|x-x^*|^2$).

ADAM (Adaptive Moment Estimation) is a widely used variant of SGD that adapts the step sizes per coordinate using running averages of the first and second moments of the stochastic gradients.

Algorithm 3.30 (ADAM). Given parameters $\alpha$ (step size, e.g., 0.001), $\beta_1,\beta_2\in[0,1)$ (moment decay rates, e.g., 0.9 and 0.999), $\epsilon>0$ (small constant, e.g., $10^{-8}$), and initial state $X_0$, $m_0=0$, $v_0=0$:

1. At step $t$, obtain stochastic gradient $g_{t+1} = H(X_t, \xi_{t+1})$.
2. Update biased first moment: $m_{t+1} = \beta_1 m_t + (1-\beta_1) g_{t+1}$.
3. Update biased second moment: $v_{t+1} = \beta_2 v_t + (1-\beta_2) g_{t+1}^{\odot 2}$ (element‑wise square).
4. Compute bias‑corrected estimates:
   \[ \hat{m}_{t+1} = \frac{m_{t+1}}{1-\beta_1^{t+1}}, \qquad \hat{v}_{t+1} = \frac{v_{t+1}}{1-\beta_2^{t+1}}. \]
5. Update parameter:
   \[ X_{t+1} = X_t - \alpha \frac{\hat{m}_{t+1}}{\sqrt{\hat{v}_{t+1}} + \epsilon}, \]
   where all operations on vectors are element‑wise.

The bias correction accounts for the initialisation at zero, ensuring unbiased estimates of the moments. ADAM can be seen as a diagonal approximation of a natural gradient method.

• $\hat{m}_{t+1}$bias‑corrected moving average of the gradient (first moment).
• $\hat{v}_{t+1}$bias‑corrected moving average of the squared gradient (second moment).

When the exact gradient $\nabla F$ is too costly to compute, a stochastic approximation can be used. The Robbins–Monro type stochastic gradient descent (SGD) iterates

where $\pi_x$ is a probability distribution on a set $S$ (which may depend on $x$), $H:\mathbb{R}^d\times S\to\mathbb{R}^d$ is an easy‑to‑compute update, and $\alpha_{t+1}$ is the step size. The distribution of $\xi_{t+1}$ given the past $U_t=(\xi_1,X_1,\dots,\xi_t,X_t)$ depends only on $X_t$ and is given by $\pi_{X_t}$. Often $\pi_x$ can be taken independent of $x$ without loss of generality.

Define $\bar{H}(x) = \mathbb{E}_{\pi_x}[H(x,\cdot)]$. Then

$\mathbb{E}[\eta_{t+1}\mid U_t]=0$, so $M_T = \sum_{t=0}^T \alpha_{t+1}\eta_{t+1}$ is a martingale. Typical assumptions are:

• (H1) $\mathbb{E}_{\pi_x}[|H(x,\cdot)|^2] \le C(1+|x|^2)$.
• (H2) There exist $x^*\in\mathbb{R}^d$ and $\mu>0$ such that $(x-x^*)^T\bar{H}(x) \le -\mu|x-x^*|^2$.
• (H3) $\sum_{k=1}^\infty \alpha_k = \infty$ and $\sum_{k=1}^\infty \alpha_k^2 < \infty$.

Under (H1)–(H3) the sequence $X_t$ converges in $L^2$ (and almost surely) to $x^*$. With constant step size $\alpha_t=\alpha$, the mean‑square error satisfies $\limsup \mathbb{E}[|X_t-x^*|^2] = O(\alpha)$.

Define the continuous‑time interpolation $X^\ell(\rho)$ by $\tau_0=0$, $\tau_t=\tau_{t-1}+\alpha_t$,

The deterministic part follows the ODE $\partial_\rho \bar{x} = \bar{H}(\bar{x})$. Under Lipschitz and boundedness assumptions on $\bar{H}$, the process stays close to the ODE solution over finite intervals (Proposition 3.27). If $\bar{H}=-\nabla E$ is a gradient field with finitely many critical points and $X_t$ remains bounded, $X_t$ converges to a critical point of $E$ (Proposition 3.28). A Lyapunov function (e.g., $|x-x^*|^2$ under (H2)) guarantees boundedness (Theorem 3.29).

ADAM (Adaptive Moment Estimation) adapts step sizes per coordinate using running averages of the first and second moments of the stochastic gradient.

Algorithm 3.30 (ADAM). Given $\alpha$, $\beta_1,\beta_2\in[0,1)$, $\epsilon>0$, initial $X_0$, $m_0=0$, $v_0=0$:

1. Obtain stochastic gradient $g_{t+1} = H(X_t,\xi_{t+1})$.
2. $m_{t+1} = \beta_1 m_t + (1-\beta_1)g_{t+1}$.
3. $v_{t+1} = \beta_2 v_t + (1-\beta_2)g_{t+1}^{\odot 2}$ (element‑wise square).
4. Bias‑corrected estimates: $\hat{m}_{t+1} = m_{t+1}/(1-\beta_1^{t+1})$, $\hat{v}_{t+1} = v_{t+1}/(1-\beta_2^{t+1})$.
5. $X_{t+1} = X_t - \alpha\, \hat{m}_{t+1}/(\sqrt{\hat{v}_{t+1}}+\epsilon)$ (element‑wise).

Minimize a $C^1$ function $F$ over $\Omega = \{x\in\mathbb{R}^d : \gamma_i(x)=0,\; i\in E,\; \gamma_i(x)\le 0,\; i\in I\}$, where $E\cap I=\emptyset$. The active set at $x\in\Omega$ is $\mathcal{A}(x)=\{i\in\mathcal{C} : \gamma_i(x)=0\}$. Define the Lagrangian

Under the Mangasarian‑Fromovitz constraint qualification (MF‑CQ) – e.g., linear independence of $\{\nabla\gamma_i(x),\, i\in\mathcal{A}(x)\}$ – a minimizer $x^*$ satisfies the Karush–Kuhn–Tucker (KKT) conditions:

If all constraints are affine, the KKT conditions hold without any qualification (Theorem 3.33).

For a closed convex set $\Omega\subset\mathbb{R}^d$, the normal cone at $x\in\Omega$ is

If $F$ is $C^1$, a necessary condition for $x^*\in\operatorname{argmin}_\Omega F$ is $-\nabla F(x^*) \in N_\Omega(x^*)$. If $F$ is convex, this condition is also sufficient (Theorem 3.37). For convex constraints $\Omega$ defined by affine equalities and convex inequalities, the KKT conditions are equivalent to $-\nabla F(x^*) \in N_\Omega(x^*)$ (Farkas’ lemma).

Let $\Omega = \mathbb{S}_+^n$, the cone of positive semidefinite matrices. For a minimizer $A^*$ of a convex $F$ over $\Omega$, the normal cone yields: $-\nabla F(A^*)_s \in \mathbb{S}_+^n$ and $A^*\nabla F(A^*)_s = 0$ (Proposition 3.38). For example, with $F(A)=\frac12\operatorname{trace}(A^2)-\operatorname{trace}(BA)$ and $B$ diagonalised as $U^T D U$, the solution is $A^* = U^T D_+ U$, where $D_+$ replaces negative entries of $D$ by zero.

The projection of $x_0$ onto a closed convex $\Omega$ is the unique minimizer of $F(x)=\frac12|x-x_0|^2$ over $\Omega$, denoted $\operatorname{proj}_\Omega(x_0)$. It is characterized by

Examples: affine subspace (orthogonal projection), unit ball ($\operatorname{proj}_{\bar B(0,1)}(x_0)=x_0/|x_0|$ for $|x_0|\ge1$), positive semidefinite cone (set negative eigenvalues to zero). The projection is 1‑Lipschitz (Proposition 3.39).

To minimize $F$ over a closed convex $\Omega$, the projected gradient descent iterates

Equivalently, $x_{t+1} = \operatorname{argmin}_{y\in\Omega}\big( F(x_t) + \nabla F(x_t)^T(y-x_t) + \frac{1}{2\alpha_t}|y-x_t|^2 \big)$. Convergence properties are discussed in the proximal gradient framework (A2.88).

The epigraph of a convex function $F$ is $\operatorname{epi}(F) = \{(x,a)\in\mathbb{R}^d\times\mathbb{R} : F(x)\le a\}$. It is always convex. $F$ is closed if $\operatorname{epi}(F)$ is closed, equivalently, all sub‑level sets $\{x:F(x)\le a\}$ are closed (Proposition 3.41). Continuous convex functions are closed. The indicator function $\sigma_\Omega$ of a closed convex $\Omega$ is closed.

For a convex function $F$ and $x\in\operatorname{dom}(F)$, a vector $g\in\mathbb{R}^d$ is a subgradient if

The set of all subgradients, subdifferential $\partial F(x)$, is closed convex. If $F$ is differentiable at $x$, $\partial F(x)=\{\nabla F(x)\}$. At a relative interior point, $\partial F(x)\neq\emptyset$ and its projection onto the affine hull is compact (Proposition 3.45). Subdifferentials are additive under mild conditions (Theorem 3.46) and respect affine composition (Theorem 3.47).

The normal cone is the subdifferential of the indicator function: $\partial\sigma_\Omega(x)=N_\Omega(x)$ for $x\in\Omega$.

The directional derivative of a convex $F$ at $x\in\operatorname{dom}(F)$ in direction $h$ is

It is positively homogeneous and subadditive in $h$ (hence convex). $x^*$ is a minimizer iff $dF(x^*,h)\ge 0$ for all $h$. For $x\in\operatorname{ri}(\operatorname{dom}(F))$, $dF(x,h) = \max\{g^T h : g\in\partial F(x)\}$ (Proposition 3.52).

When $F$ is non‑differentiable, the direction $h = -\operatorname{argmin}\{|g| : g\in\partial F(x)\}$ (the minimal‑norm subgradient) is a descent direction. The subgradient descent iteration $x_{t+1}=x_t - \alpha_t g_t$ with $g_t\in\partial F(x_t)$ can be combined with averaging: define $\bar{x}_t = (\sum_{j=1}^t \alpha_j x_j)/(\sum_{j=1}^t \alpha_j)$, which converges to a minimizer under convexity and suitable step sizes.

For a closed convex function $F$, the proximal operator is

It satisfies $x \in x' + \partial F(x')$ iff $x' = \operatorname{prox}_F(x)$. Thus minimizers of $F$ are fixed points of $\operatorname{prox}_{\alpha F}$. The proximal operator is 1‑Lipschitz (Proposition 3.56). Example: $F(x)=\lambda|x|$ yields the soft‑thresholding operator $\operatorname{prox}_{\lambda|\cdot|}(x) = \operatorname{sign}(x)\max(|x|-\lambda,0)$. For $F=\sigma_\Omega$, $\operatorname{prox}_{\sigma_\Omega} = \operatorname{proj}_\Omega$.

Minimize $F = G + H$ with $G$ $C^1$ and $H$ closed convex. The proximal gradient descent iteration is

If $G$ is $L$‑$C^1$ and $\alpha_t \le 2/L$, the objective decreases. A stationary point satisfies $-\nabla G(x)\in\partial H(x)$, which is the optimality condition.

Theorem 3.57 (convex case). If $G$ is $L$‑$C^1$ and convex, $H$ closed convex, and a minimizer $x^*$ exists, then with constant step $\alpha \le 1/L$,

Theorem 3.58 (strongly convex case). If, in addition, $G$ is $C^2$ with eigenvalues of $\nabla^2 G$ in $[m,L]$, $m>0$, then with constant step $\alpha < 1/L$,

These results include projected gradient descent as a special case ($H=\sigma_\Omega$).

When $G=0$, the scheme reduces to the proximal point algorithm:

It converges to a minimizer for any $\alpha>0$ if $F$ is closed convex (a consequence of Theorem 3.57).

Consider minimizing a closed convex function $F$ over a closed convex set $\Omega \subset \operatorname{ri}(\operatorname{dom}(F))$. For a minimizer $x^*$, the optimality condition generalizes to

where $N_\Omega(x)$ is the normal cone. This follows because the indicator $\sigma_\Omega$ is closed convex and $\partial\sigma_\Omega(x)=N_\Omega(x)$. The condition is both necessary and sufficient (Theorem 3.59).

Now specialise to $\Omega = \{x\in\mathbb{R}^d : \gamma_i(x)=0,\;i\in E,\; \gamma_i(x)\le 0,\;i\in I\}$ with $\gamma_i$ affine for $i\in E$ and closed convex for $i\in I$. For $x\in\Omega$ with active set $\mathcal{A}(x)=\{i\in\mathcal{C}:\gamma_i(x)=0\}$, define

The KKT conditions in the non‑smooth case read $0 \in \partial F(x^*) + N'_\gamma(x^*)$, which holds provided $N_\Omega(x^*) = N'_\gamma(x^*)$. The Slater constraint qualification (Sl‑CQ) ensures this equality:

• (Sl 1) The vectors $\{b_i : i\in E\}$ (gradients of affine equalities) are linearly independent.
• (Sl 2) There exists $x$ such that $\gamma_i(x)=0$ for $i\in E$ and $\gamma_i(x) < 0$ for all $i\in I$.

Sl‑CQ is weaker than the Mangasarian‑Fromovitz CQ when the $\gamma_i$ are $C^1$, but is equivalent under differentiability (Proposition 3.61). Theorem 3.62 states that under Sl‑CQ, if $x^*$ is a minimizer, then there exist $s_0\in\partial F(x^*)$, $s_i\in\partial\gamma_i(x^*)$ for $i\in\mathcal{A}(x^*)$, and multipliers $\lambda_i\ge 0$ (with $\lambda_i=0$ for inactive constraints) such that $s_0 + \sum \lambda_i s_i = 0$.

Define the Lagrangian $\mathcal{L}(x,\lambda) = F(x) + \sum_{i\in\mathcal{C}} \lambda_i \gamma_i(x)$, with $\lambda\in D = \{\lambda : \lambda_i\ge 0,\; i\in I\}$. For any $x\in\Omega$, $\lambda\in D$, we have $\mathcal{L}(x,\lambda) \le F(x)$. Let

so that $\mathcal{L}^*(\lambda) \le F(x)$ for all $x\in\Omega$. The dual problem is $\hat d = \sup_{\lambda\in D} \mathcal{L}^*(\lambda)$ and the primal problem is $\hat p = \inf_{x\in\Omega} F(x)$. Always $\hat d \le \hat p$ (weak duality).

Under the Slater conditions, the duality gap vanishes: $\hat d = \hat p$. Moreover, any solution $\lambda^*$ of the dual provides multipliers satisfying the KKT conditions, and conversely (Theorem 3.63). The pair $(x^*,\lambda^*)\in\Omega\times D$ satisfies the KKT conditions iff it is a saddle point of $\mathcal{L}$:

Thus, under constraint qualifications, solving the primal is equivalent to finding a saddle point of $\mathcal{L}$, and the dual optimum equals the primal optimum.

Consider the quadratic program (support vector machine formulation) with variables $x\in\mathbb{R}^d$, $x_0\in\mathbb{R}$, $\xi\in\mathbb{R}^N$, parameter $\gamma>0$:

where $b_k\in\{-1,1\}$, $a_k\in\mathbb{R}^n$. Introduce multipliers $\alpha_k\ge 0$ (for the second constraint) and $\eta_k\ge 0$ (for $\xi^{(k)}\ge 0$). The Lagrangian is

Minimizing over the primal variables yields $\sum\alpha_k b_k = 0$, $x = \sum\alpha_k b_k a_k$, and $\gamma - \eta_k - \alpha_k = 0$ with $\eta_k\ge 0 \Rightarrow 0\le\alpha_k\le\gamma$. Substituting back gives the dual problem

The dual is a quadratic program with simple box constraints and one linear equality constraint, and its solution $\alpha^*$ yields the primal minimizer $x^* = \sum \alpha_k^* b_k a_k$.

The dual function $\mathcal{L}^*$ is concave; maximizing it is equivalent to minimizing $-\mathcal{L}^*$. The proximal point algorithm applied to $-\mathcal{L}^*$ yields

Define the augmented Lagrangian function $\phi(x,\mu) = F(x) + \sum_{i\in\mathcal{C}} \mu_i \gamma_i(x) - \frac{1}{2\alpha_t}\|\mu-\lambda(t)\|^2$. Under appropriate conditions (e.g., compact sub‑level sets of $F$ on $\Omega$), minimax equality holds:

The inner maximization over $\mu$ can be solved in closed form: for $i\in E$, $\mu_i = \lambda_i(t) + \alpha_t \gamma_i(x)$; for $i\in I$, $\mu_i = \max(0, \lambda_i(t) + \alpha_t \gamma_i(x))$. Substituting back gives the augmented Lagrangian algorithm:

Starting from $\lambda(0)$, the iterates $\lambda(t)$ converge to a solution of the dual problem, and cluster points of $x(t)$ (if they exist) are primal minimizers. The method works for convex problems; with small $\alpha_t$ it can also be applied to non‑convex settings.

Consider the problem $\min_{x,z} \{ G(x) + H(z) : Ax + Bz = c \}$ with $G,H$ closed convex. The augmented Lagrangian method (with equality constraints) would jointly minimize over $(x,z)$. ADMM splits this into two easier subproblems. With fixed step size $\alpha>0$ and scaled multiplier $u = \lambda/\alpha$, the iterations are (after removing constants):

This is the Alternative Direction Method of Multipliers (ADMM), also known as Douglas‑Rachford splitting. Under the assumptions that $G$ and $H$ are closed convex and the Lagrangian $\mathcal{L}(x,z,\lambda)=G(x)+H(z)+\lambda^T(Ax+Bz-c)$ has a saddle point, the iterates converge: $x_t, z_t$ to a primal solution, and $u_t$ (or $\lambda_t$) to a dual solution. ADMM is particularly efficient when the proximal operators of $G$ and $H$ are easy to compute.