These notes are meant for the moment when the ideas are familiar but the details have started to blur. You remember that smoothness gives a quadratic bound, that strong convexity improves convergence, and that Adam keeps two moving averages—but you want to recover the argument without rereading an entire course.
The aim is to keep the definitions, assumptions, proofs, and examples together. A rate is much easier to remember when you can see which inequality produces it. A counterexample is often more useful than another definition.
This reference grew out of my CS769 Optimization in Machine Learning revision notes for lectures 3–24. It brings together the course themes and supplementary practice material; it is a personal study guide, not an official syllabus or answer key. Repeated questions have been merged by concept, and conditions that compact cheat sheets tend to omit are stated explicitly.
For a gentler first pass through derivatives, gradients, and subgradients, start with Optimization, Connected: A Revision Guide. This post is the broader reference to come back to afterward.
How to use these notes
For a quick pass: read the definitions in sections 2–7, the rate table in section 8, the optimizer comparison in section 12, and the self-check at the end.
For proof revision: work through the toolkit, the four GD proofs, the stochastic extension, and the proximal-gradient proof. Try to reproduce each argument before opening its derivation.
For applications: revisit loss classification, policy gradients, MoE routing, and the structured-optimization examples. Ask what each term measures and what assumptions actually hold.
Proofs and solutions are expandable. The controls above let you open them all for a full reading or print the reference with every derivation visible.
1. Notation and the proof toolkit
Unless stated otherwise, vectors are in finite-dimensional Euclidean space and \(\|\cdot\|\) is the Euclidean norm. Matrix \(\|A\|_2\) means the spectral norm. Domains are convex when we apply convexity or integrate along a line segment.
| Symbol | Meaning |
|---|---|
| \(x^\star\), \(f^\star\) | A minimizer and its objective value; existence is assumed in rate statements |
| \(R=\|x_0-x^\star\|\) | Initial distance to a chosen minimizer |
| \(g_t\) | A gradient, subgradient, or stochastic estimate, specified in context |
| \(B\) | Bound on subgradient norms, or a stochastic second-moment bound |
| \(L\) | Gradient-Lipschitz constant; the smoothness parameter |
| \(\mu>0\) | Strong-convexity parameter |
| \(\kappa=L/\mu\) | Condition-number bound for a smooth, strongly convex objective |
| \(\eta_t\) | Optimization step size; \(\gamma\) is reserved for RL discounting |
| \(D_t=\|x_t-x^\star\|^2\) | Squared distance used in telescoping proofs |
The calculus underneath the notation
The gradient collects partial derivatives of a scalar objective. Its differential is \(df=\nabla f(x)^\top dx\), the linear approximation to the change caused by a displacement. The directional derivative is \(D_vf(x)=\nabla f(x)^\top v\); a negative value identifies a local descent direction. Among Euclidean unit directions, the negative normalized gradient gives the steepest local decrease when the gradient is nonzero.
A vector-valued function has a Jacobian, with one row per output. A scalar objective has a Hessian of second derivatives; its quadratic form \(v^\top\nabla^2f(x)v\) describes directional curvature. Under the usual convention the scalar Jacobian is the gradient’s transpose.
The identity behind most first-order proofs
For the update \(x_{t+1}=x_t-\eta_tg_t\),
Equivalently, for \(\eta_t>0\),
This is algebra. It does not require convexity, smoothness, or even that \(g_t\) be a gradient. The assumptions enter when we bound its two sides.
Moves worth recognizing immediately
- Turn an inner product into distances: \(2u^\top v=\|u\|^2+\|v\|^2-\|u-v\|^2\).
- Telescope: \(\sum_{t=0}^{T-1}(a_t-a_{t+1})=a_0-a_T\). Drop the final term only when its sign allows it.
- Optimize a free parameter: minimize \(R^2/(2\eta T)+\eta B^2/2\) over \(\eta>0\).
- Choose the output: best objective value is at most the average; convexity transfers an average of values to the value at an averaged iterate. A last-iterate guarantee needs its own justification.
- Contract: \(a_{t+1}\le\rho a_t\) gives \(a_T\le\rho^Ta_0\) for \(0\le\rho<1\).
- Weight before summing: weights proportional to \(t\) can turn a non-telescoping strongly convex bound into a telescoping one.
- Write an inequality both ways and add: this turns first-order convexity into monotonicity of the gradient.
- Restrict to a line: set \(\phi(t)=f(x+t(y-x))\) and integrate \(\phi'\).
- Add and subtract a cross term: useful for differences of products and composite expressions.
- Condition before taking expectation: use \(\mathbb E[g_t\mid x_t]=\nabla f(x_t)\), then the tower rule.
- Complete the square: this reveals a proximal step inside a quadratic model.
- Use normalization: \(\sum_a\nabla\pi(a\mid s)=\nabla1=0\) removes policy-gradient baselines.
From a rate to an iteration count: \(RB/\sqrt T\le\epsilon\) requires \(T\ge R^2B^2/\epsilon^2\). Round up to an integer. Logarithmic formulas should be clipped at zero when the initial bound is already below the requested tolerance.
2. Convex sets and the geometry underneath
A set \(C\) is convex if every segment between two of its points remains in the set:
Halfspaces, affine sets, norm balls, and ellipsoids are convex. Intersections preserve convexity; arbitrary unions do not. Two disjoint intervals are the simplest counterexample.
A norm ball is convex because
An ellipsoid can be written either as
or as \(\{c+P^{1/2}u:\|u\|_2\le1\}\). The second form makes its scaling and rotation explicit.
The convex hull of \(S\) is the set of all finite convex combinations \(\sum_i\theta_ix_i\), where \(x_i\in S\), \(\theta_i\ge0\), and \(\sum_i\theta_i=1\). Combining two such combinations produces another one, so the hull is convex even when \(S\) is not.
Separation, support, and projection
For two nonempty, disjoint convex sets in finite dimensions, a separating hyperplane gives \(a\ne0\) and \(b\) such that
Strict separation needs additional conditions. A point outside a nonempty closed convex set can be strictly separated from that set.
A supporting hyperplane touches the boundary of a convex set and leaves the set on one side. Applying this geometry to an epigraph explains subgradients—but a supporting plane at a domain boundary may be vertical, so it need not define a finite subgradient.
For a nonempty closed convex set, Euclidean projection exists and is unique:
Uniqueness here comes from the strictly convex squared Euclidean distance. It need not hold if Euclidean distance is replaced by an arbitrary norm.
Sublevel sets, epigraphs, and quasiconvexity
The sublevel set \(L_\alpha(f)=\{x:f(x)\le\alpha\}\) is convex whenever \(f\) is convex. The converse fails: \(f(x)=x^3\) has interval-shaped sublevel sets but is not convex on \(\mathbb R\).
A function is quasiconvex when all its sublevel sets are convex, equivalently
Another example is \(-e^{-(x-m)^2}\): its nontrivial sublevel sets are intervals around \(m\), although its second derivative changes sign. Avoid using \(\log|x|\) on \(\mathbb R\setminus\{0\}\) as an interval example: excluding zero leaves a gap in both the domain and the sublevel sets.
The epigraph retains more information:
A function is convex if and only if its epigraph is convex. To prove the reverse direction, take the two epigraph points \((x,f(x))\) and \((y,f(y))\) and apply convexity to their combination.
3. Convex functions and the calculus of convexity
The defining inequality is
Strict convexity replaces \(\le\) by \(<\) for distinct points and \(0<\theta<1\). Strong convexity asks for a uniform quadratic margin:
Equivalently, \(f(x)-\mu\|x\|^2/2\) is convex. Strong convexity does not require differentiability: hinge loss plus a positive squared Euclidean regularizer is an example.
The identity that connects these definitions is
Closure rules
| Construction | Conditions for convexity |
|---|---|
| \(\sum_i a_if_i\) | Convex \(f_i\) and \(a_i\ge0\) |
| \(f(Ax+b)\) | Convex \(f\) |
| \(\max_i f_i(x)\) or \(\sup_s f_s(x)\) | Each function convex; respect the effective domain |
| \(h(g(x))\) | Convex nondecreasing \(h\) and convex \(g\); or convex nonincreasing \(h\) and concave \(g\) |
| \(\inf_{y\in C}F(x,y)\) | Jointly convex \(F\) and convex \(C\); infimum need not be attained |
| \(t f(x/t)\) | Convex \(f\), with \(t>0\) and \(x/t\) in its domain |
For a vector-valued inner map, check the outer function’s monotonicity separately in every coordinate. For example, log-sum-exp is convex and increasing in each argument, so applying it to convex components preserves convexity.
Monotonicity cannot be dropped from the composition rule: the affine, hence convex, outer function \(h(t)=-t\) composed with \(g(x)=x^2\) gives \(-x^2\).
First-order, second-order, and monotonicity tests
For differentiable functions on an open convex domain:
For twice continuously differentiable functions:
Positive definiteness everywhere is sufficient for strict convexity, but not necessary: \(x^4\) is strictly convex and has zero curvature at zero. Strong convexity is equivalent to \(\nabla^2f(x)\succeq\mu I\) under the same differentiability and domain assumptions.
Convexity also has a gradient characterization:
Strict convexity gives strict inequality for \(x\ne y\); strong convexity gives the lower bound \(\mu\|x-y\|^2\).
Derivation: first-order convexity and monotone gradients
Convexity gives
Let \(t\downarrow0\) to get the first-order inequality. Conversely, apply that inequality at \(z=\theta x+(1-\theta)y\) toward both \(x\) and \(y\), multiply by \(\theta\) and \(1-\theta\), and add. The gradient terms cancel.
Writing the first-order inequality in both directions and adding gives gradient monotonicity. For the converse, use
Monotonicity bounds the integrand below by \(\nabla f(x)^\top(y-x)\). Strong monotonicity adds \(\mu t\|y-x\|^2\); its integral gives the required \(\mu/2\) term.
Log-sum-exp: a useful test case
Let \(h(z)=\log\sum_i e^{z_i}\) and \(p_i=e^{z_i}/\sum_j e^{z_j}\). Then
For any \(v\),
So log-sum-exp is convex. It is not strictly convex on the full space, since \(h(z+c\mathbf1)=h(z)+c\) is affine along the all-ones direction.
Alternative proof: midpoint convexity and Cauchy–Schwarz
Set \(a_i=e^{x_i/2}\) and \(b_i=e^{y_i/2}\). Cauchy–Schwarz gives
This is the midpoint convexity inequality. Continuity extends it to every mixing weight. Equality holds when \(a\) and \(b\) are proportional, meaning \(x-y=c\mathbf1\), not just when \(x=y\).
4. Vector norms, matrix norms, and duality
A norm satisfies positive definiteness, absolute homogeneity, and the triangle inequality:
Drop positive definiteness and you get a seminorm. For symmetric \(A\), \(\sqrt{x^\top Ax}\) is a norm exactly when \(A\succ0\); a singular PSD matrix gives a seminorm.
Every norm is a convex function and obeys the reverse triangle inequality
A norm on a nontrivial vector space is not strictly convex as a function on the whole space, because it is linear along positive rays. The separate phrase “strictly convex norm” describes the geometry of its unit sphere; Euclidean norm has that property. Norms are not differentiable at the origin.
The dual norm is
and Hölder’s inequality is \(|z^\top x|\le N_*(z)N(x)\). The pairs are \(\ell_p\leftrightarrow\ell_q\) with \(1/p+1/q=1\), including \(\ell_1\leftrightarrow\ell_\infty\) and self-dual \(\ell_2\).
| Matrix quantity | Formula |
|---|---|
| Induced norm | \(M_N(A)=\sup_{x\ne0}N(Ax)/N(x)\) |
| Spectral norm | \(\|A\|_2=\sigma_1(A)=\sqrt{\lambda_{\max}(A^\top A)}\) |
| Induced \(\ell_1\) norm | Maximum absolute column sum |
| Induced \(\ell_\infty\) norm | Maximum absolute row sum |
| Frobenius norm | \(\|A\|_F=(\sum_i\sigma_i^2)^{1/2}\) |
| Nuclear norm | \(\|A\|_*=\sum_i\sigma_i\) |
| Schatten \(p\) norm, \(p\ge1\) | \(\|\sigma(A)\|_p\) |
| Ky Fan \(k\) norm | \(\sum_{i=1}^k\sigma_i(A)\) |
Spectral and nuclear norms are dual under the trace inner product \(\langle A,B\rangle=\operatorname{tr}(A^\top B)\). For rank \(r\),
The nuclear norm is the convex envelope of rank on the spectral-norm unit ball. The domain restriction matters; it is not an unrestricted identity. See Fazel’s account of rank and cardinality envelopes.
Proof template: an induced norm is convex and submultiplicative
For fixed \(x\ne0\), use the triangle inequality and homogeneity of \(N\):
Take the supremum and use \(\sup(a+b)\le\sup a+\sup b\). This proves convexity without assuming that \(M_N\) is a norm.
Its norm axioms follow similarly: \(M_N(A)=0\) forces \(Ax=0\) for every \(x\); scalar factors pull out in absolute value; triangle inequality follows from the same supremum argument.
Finally, \(N(ABx)\le M_N(A)N(Bx)\le M_N(A)M_N(B)N(x)\), so \(M_N(AB)\le M_N(A)M_N(B)\).
Useful counterexamples: the count of nonzeros and matrix rank fail absolute homogeneity. Squared norm also fails homogeneity of degree one. For \(0<p<1\), the usual \(\ell_p\) expression fails triangle inequality. Individual singular values \(\sigma_k\) for \(k\ge2\) are not convex, even though their leading partial sums are: \(\sigma_2(\operatorname{diag}(1,0))=\sigma_2(\operatorname{diag}(0,1))=0\), but \(\sigma_2(I/2)=1/2\).
5. Subgradients, their calculus, and optimality
A convex subgradient supports the function globally from below:
The subdifferential is a closed convex set, possibly empty. For a proper convex function, it is nonempty at points in the relative interior of its effective domain. At a differentiable interior point, it equals \(\{\nabla f(x)\}\).
| Function | Subdifferential |
|---|---|
| \(|x|\) | \(\{-1\}\) for \(x<0\); \([-1,1]\) at zero; \(\{1\}\) for \(x>0\) |
| \(\max(0,x)\) | \(\{0\}\) for \(x<0\); \([0,1]\) at zero; \(\{1\}\) for \(x>0\) |
| \(\|x\|_1\) | Coordinatewise sign away from zero, any value in \([-1,1]\) at zero |
| A norm \(N(x)\) | \(\{z:N_*(z)\le1,\ z^\top x=N(x)\}\) |
| Indicator \(I_C(x)\), \(x\in C\) | Normal cone \(\{g:g^\top(y-x)\le0\ \forall y\in C\}\) |
For finite convex functions on the full space, the familiar rules are
For extended-valued functions, the sum and affine-chain equalities need domain qualification conditions, such as appropriate relative-interior intersections. A finite maximum of finite convex functions has
Do not transfer this finite-max formula to an arbitrary infinite supremum without checking attainment and regularity.
For a convex outer function \(p\) with a chosen nonnegative subgradient \(a\in\partial p(q(x))\), and convex inner functions with \(g_i\in\partial q_i(x)\), the vector \(\sum_i a_ig_i\) is a subgradient of the composition. The nonnegative coefficients let us combine the inner supporting inequalities in the correct direction.
What certifies a minimum?
For an unconstrained convex objective,
A zero subgradient makes the supporting plane constant. Conversely, the defining inequality for a global minimizer is precisely the subgradient inequality with zero.
Every local minimum of a convex function is global. Strict convexity makes the minimizer unique if it exists. It does not prove existence: \(e^x\) is strictly convex and bounded below on \(\mathbb R\), but never attains its infimum.
A sufficient existence condition is a nonempty compact sublevel set together with lower semicontinuity. Boundedness alone is not enough if the domain or sublevel set is not closed.
For differentiable convex \(f\) over a convex feasible set \(C\),
The gradient need not vanish at a constrained optimum. In normal-cone language, \(-\nabla f(x^\star)\in N_C(x^\star)\).
Two short proofs: local means global; strict means unique
If a local minimizer \(x\) had a better point \(y\), a sufficiently small positive \(\theta\) would place \(z=(1-\theta)x+\theta y\) inside its local neighborhood. Convexity would give \(f(z)\le(1-\theta)f(x)+\theta f(y)<f(x)\), a contradiction.
If a strictly convex function had two distinct minimizers, their midpoint would have a value strictly below the minimum, also a contradiction.
6. Lipschitz continuity, smoothness, and strong convexity
These properties bound different things. Keep the function, its gradient, and its curvature separate.
| Property | Definition or characterization |
|---|---|
| \(B\)-Lipschitz | \(|f(x)-f(y)|\le B\|x-y\|\) |
| \(L\)-smooth | \(\|\nabla f(x)-\nabla f(y)\|\le L\|x-y\|\) |
| \(\mu\)-strongly convex | \(f(y)\ge f(x)+g^\top(y-x)+\mu\|y-x\|^2/2\) for convex subgradients \(g\) |
On an open convex domain, differentiable \(f\) is \(B\)-Lipschitz exactly when \(\|\nabla f\|\le B\). The analogous convex-subgradient statement holds at interior points. Boundary normal components can be unbounded, so “every subgradient is bounded” needs this qualification.
For a \(C^2\) function on an open convex domain, smoothness is equivalent to
For a convex function, the lower bound is already zero, and the test simplifies to \(0\preceq\nabla^2f\preceq LI\). An upper Hessian bound alone is insufficient outside convexity: \(-x^4\) has Hessian \(-12x^2\le L\) for any positive \(L\), but its gradient is not globally Lipschitz.
Likewise, convexity of \(L\|x\|^2/2-f(x)\) gives a one-sided upper-curvature bound. It characterizes smoothness when \(f\) is also convex; it is not a general replacement for gradient Lipschitzness.
Examples to keep straight
- \(x^2\) is globally \(2\)-smooth and \(2\)-strongly convex, but not globally Lipschitz.
- \(|x|\) is globally \(1\)-Lipschitz and convex, but nonsmooth.
- \(x^4\) is strictly convex, but neither globally smooth nor strongly convex on \(\mathbb R\).
- \(|x|^{3/2}\) is differentiable, but its gradient is not Lipschitz near zero.
- \(f(x)=x|x|/2\) has derivative \(|x|\), so it is \(1\)-smooth even though its second derivative fails to exist at zero.
- For \(f(x)=x^3/3\) on \([-M,M]\), a tight smoothness constant is \(2M\).
Global smoothness bounds growth in magnitude by a quadratic relative to a fixed base point. The converse is false: at-most-quadratic growth does not by itself control derivative oscillations. Strong convexity on the full space forces at least quadratic growth, so it is incompatible with global function Lipschitzness there.
A bounded domain is not enough by itself to give Lipschitzness. A bounded gradient is enough; continuous differentiability on a neighborhood of a compact convex set is a useful sufficient condition. Differentiability almost everywhere is not enough.
Derivation: the descent lemma and three useful inequalities
Integrate along the segment from \(x\) to \(y\):
Cauchy–Schwarz and smoothness bound the integrand above by \(Lt\|y-x\|^2\). Hence
For \(y=x-\nabla f(x)/L\), this becomes
For an unconstrained strongly convex objective, minimize its quadratic lower model to obtain the Polyak–Łojasiewicz inequality:
The smooth descent step gives the complementary inequality \(\|\nabla f(x)\|^2\le2L(f(x)-f^\star)\). At an unconstrained minimizer, strong convexity also gives quadratic growth:
For convex \(L\)-smooth functions on \(\mathbb R^d\), co-coercivity strengthens monotonicity:
Sum constants add. If \(h(x)=f(Ax+b)\) and \(f\) is \(L\)-smooth, then \(h\) is \(L\|A\|_2^2\)-smooth: apply the chain rule and the operator-norm bound twice. A product of bounded Lipschitz functions is Lipschitz; the boundedness is essential, as \(x\cdot x\) shows.
7. Classifying the objectives used in ML
The common template is a fit term plus a regularizer:
Convexity below refers to linear predictors with fixed features, not arbitrary neural-network parameterizations. Assume finite data, binary labels in \(\{-1,1\}\) where relevant, and positive regularization coefficients. Constants here are for sums; divide the data-loss constants by \(n\) for averages.
| Objective | Lipschitz on the full space? | Smooth? | Convexity |
|---|---|---|---|
| Logistic loss | Yes | Yes | Convex |
| Multiclass linear softmax loss | Yes | Yes | Convex |
| Hinge loss | Yes | Generally no | Convex |
| Nonconstant least squares | Generally no | Yes | Strongly convex iff the design has full column rank |
| Positive squared \(\ell_2\) regularizer | No | Yes | Strongly convex |
| Positive \(\ell_1\) regularizer | Yes | No | Convex |
| Logistic plus squared \(\ell_2\) | No | Yes | Strongly convex |
| Hinge plus squared \(\ell_2\) | No | Generally no | Strongly convex |
| Least squares plus \(\ell_1\) | Generally no | No | Strongly convex iff the design has full column rank |
Derivatives worth being able to produce
For symmetric \(A\),
For nonsymmetric \(A\), the quadratic gradient is \((A+A^\top)x\).
Logistic loss. Write \(\ell(t)=\log(1+e^t)\), \(t_i=-y_ix_i^\top w\). Then \(\ell'=\sigma\) and \(\ell''=\sigma(1-\sigma)\le1/4\), giving
Valid constants are \(B=\sum_i\|x_i\|\) and \(L=\lambda_{\max}(X^\top X)/4\). Adding \(\lambda\|w\|^2/2\) adds \(\lambda w\) to the gradient and \(\lambda I\) to the Hessian, giving strong convexity parameter \(\lambda\).
Hinge loss. For one example, \(\max(0,1-yx^\top w)\) has subgradient \(-yx\) below margin one, zero above it, and \(-a yx\) with \(a\in[0,1]\) at the margin. This gives the same simple sum bound \(B=\sum_i\|x_i\|\).
Least squares. For \(f(w)=\|Xw-y\|^2\),
Thus \(L=2\lambda_{\max}(X^\top X)\) and, when positive, \(\mu=2\lambda_{\min}(X^\top X)\). If \(n<d\), the Hessian is singular, so there is no global strong convexity. Ridge with objective \(\|Xw-y\|^2+\lambda\|w\|^2\) has
Lasso has no analogous general closed form for an arbitrary design matrix. Soft thresholding is exact for an identity or suitably orthogonal design, and appears as a proximal step more generally.
Multiclass softmax. For one sample, \(\ell(z,y)=-z_y+\log\sum_c e^{z_c}\). Then \(\nabla_z\ell=p-e_y\) and \(\nabla_z^2\ell=\operatorname{diag}(p)-pp^\top\). The gradient norm is at most \(\sqrt2\) and the Hessian is PSD and bounded. A valid, conservative parameter-space smoothness bound for summed linear-model losses is \(\sum_i\|x_i\|^2\).
Other patterns. Quadratic-over-linear \(x^2/t\) is convex for \(t>0\): its Hessian is \(2vv^\top/t^3\) with \(v=(t,-x)\). Log barriers are convex on their positive-slack domain. PCA with an orthogonality constraint is a nonconvex optimization problem even though eigendecomposition solves its standard form exactly. Check both objective and feasible set.
8. Convergence rates at a glance
These are worst-case guarantees with their prescribed outputs, not promises that one optimizer wins on every dataset. Assume a minimizer exists, the stated bounds hold along the iterates, and proximal subproblems are solved exactly. Constrained nonsmooth problems can use projected updates to keep iterates in the region where the bounds apply.
| Problem class and method | Step size | Guaranteed error | Output |
|---|---|---|---|
| Convex, bounded subgradients | \(R/(B\sqrt T)\) | \(RB/\sqrt T\) | Best or averaged iterate |
| Strongly convex, bounded subgradients | \(2/[\mu(t+1)]\), \(t\ge1\) | \(2B^2/[\mu(T+1)]\) | Average weighted by \(t\) |
| Convex, \(L\)-smooth GD | \(1/L\) | \(LR^2/(2T)\) | Last iterate |
| Smooth, strongly convex GD | \(1/L\) | \((L/2)(1-\mu/L)^TR^2\) | Last iterate |
| Accelerated smooth convex method | \(1/L\), prescribed momentum | \(2LR^2/(T+1)^2\) for a standard variant | Algorithm’s output iterate |
| Convex composite proximal gradient | \(0<\eta\le1/L\) | \(R^2/(2\eta T)\) | Last iterate |
| Accelerated convex composite method | \(1/L\), prescribed acceleration | \(2LR^2/(T+1)^2\) | Algorithm’s output iterate |
The corresponding tolerance dependence is \(\epsilon^{-2}\), \(\epsilon^{-1}\), \(\epsilon^{-1}\), \(\log(1/\epsilon)\), \(\epsilon^{-1/2}\), \(\epsilon^{-1}\), and \(\epsilon^{-1/2}\), respectively. Constants and assumptions still matter.
For \(R=2\), \(B=3\), \(L=5\), and \(\epsilon=0.01\), the first bound asks for \(360{,}000\) steps; smooth GD asks for \(1{,}000\). These are sufficient theoretical counts, not measured runtimes.
In the black-box first-order oracle model, with suitable dimension and problem-class assumptions, the characteristic worst-case lower rates are \(T^{-1/2}\) for Lipschitz convex objectives and \(T^{-2}\) for smooth convex objectives. Acceleration closes the smooth-class gap left by ordinary GD. A lower bound for a problem class is not a lower bound on every individual instance.
9. Four convergence proofs to reconstruct from memory
All four proofs reuse the distance identity. What changes is the inequality used to control the inner product and gradient norm.
A. Convexity and bounded subgradients
Convexity gives \(f(x_t)-f^\star\le g_t^\top(x_t-x^\star)\). If \(\|g_t\|\le B\), then for fixed \(\eta>0\),
Choose \(\eta=R/(B\sqrt T)\) to get \(RB/\sqrt T\), assuming \(R,B>0\). If either is zero, handle that trivial case separately.
Proof A: telescope, tune the step, and choose an output
Substitute convexity into the identity and sum:
Divide by \(T\). Differentiating the bound with respect to \(\eta\) gives \(-R^2/(2T\eta^2)+B^2/2=0\), hence the stated step size.
The best iterate is no worse than the average value. For \(\bar x=T^{-1}\sum_{t=0}^{T-1}x_t\), Jensen gives \(f(\bar x)\le T^{-1}\sum_t f(x_t)\). Neither argument certifies the last iterate.
A fixed, untuned step leaves the bound \(\eta B^2/2\) as \(T\) grows. That is a floor in the guarantee, not a claim that every problem actually stalls there.
With varying steps, multiply by \(2\eta_t\) before summing:
The same bound holds for the step-weighted average by Jensen. Conditions \(\sum_t\eta_t=\infty\) and \(\sum_t\eta_t^2<\infty\) make this bound vanish. The schedule \(\eta_t\propto1/\sqrt{t+1}\) does not have a finite square sum, but the displayed bound still gives \(O(\log T/\sqrt T)\).
B. Convexity and smoothness
The descent lemma gives, for \(g_t=\nabla f(x_t)\),
At \(\eta=1/L\), the decrease is at least \(\|g_t\|^2/(2L)\). This replaces the bounded-gradient assumption in Proof A.
Proof B: use descent to remove the gradient-norm sum
Smoothness telescopes to
The distance identity and convexity give
Substitute the first inequality and move \(f(x_0)-f(x_T)\) to the left. The index shift is the key step:
Objective values decrease, so the last value is at most this average:
For \(0<\eta\le1/L\), the same argument gives \(R^2/(2\eta T)\). Strict decrease away from stationarity is guaranteed for \(0<\eta<2/L\), but the displayed rate proof uses the smaller range.
Without convexity, descent still gives a stationarity guarantee for a lower-bounded smooth function:
Small gradient is not a certificate of global optimality and can occur near a saddle.
C. Smoothness and strong convexity
Strong convexity strengthens the inner-product bound:
At \(\eta=1/L\), it leads to
Proof C: the contraction argument and a shorter function-value proof
Insert the strengthened inequality into the distance update:
At \(\eta=1/L\), sufficient decrease and \(f^\star\le f(x_{t+1})\) make the last two terms nonpositive. Iteration gives \(D_T\le(1-\mu/L)^TR^2\).
Smoothness at \(x^\star\), where the unconstrained gradient is zero, gives
Since \(1-u\le e^{-u}\), a sufficient count is
A shorter proof uses PL directly:
This version only needs smoothness and the PL inequality, which some nonconvex functions also satisfy.
The squared-distance bound gives a distance contraction factor \(\sqrt{1-\mu/L}\). “Linear convergence” refers to geometric error decay, not to a linearly shrinking error. Reducing the tolerance tenfold adds about \(\kappa\log10\) iterations in the exponential bound.
D. Strong convexity and bounded subgradients
For nonsmooth strongly convex objectives, assume \(\|g_t\|\le B\) along the iterates. This can hold on a bounded feasible region with projected updates; it cannot hold globally for a strongly convex function on the entire space.
Use \(\eta_t=2/[\mu(t+1)]\) for \(t=1,\ldots,T\) and output
Then
Proof D: why weighting by time removes the logarithm
The one-step relation is
Substitute the schedule and multiply by \(t\):
The distance terms telescope from \(t=1\) to \(T\). The initial coefficient is zero, and the final term is nonpositive. Thus \(\sum_t t(f(x_t)-f^\star)\le TB^2/\mu\).
Normalize by \(T(T+1)/2\) and apply Jensen. This explains both the \(1/T\) rate and the absence of an initial-distance term in this particular bound. A common unweighted analysis with \(\eta_t=1/(\mu t)\) instead produces a \(\log T/T\) term.
The same distance inequality survives Euclidean projection because projection cannot increase distance to a feasible minimizer.
10. Momentum, acceleration, and step-size selection
Heavy-ball momentum keeps a velocity:
Equivalently, \(x_{t+1}=x_t-\eta\nabla f(x_t)+\beta(x_t-x_{t-1})\). Gradients that repeatedly point in similar directions accumulate movement. Stability depends on the objective, step size, and momentum together; \(0\le\beta<1\) alone is not a convergence theorem.
For positive-definite quadratics, the classical tuned parameters are
Do not promote the quadratic result to a universal accelerated guarantee for all smooth strongly convex objectives. Results beyond quadratics require additional analysis; see Wang et al. on heavy-ball acceleration beyond quadratics.
A standard accelerated convex scheme
Initialize \(x_0\), \(y_0=x_0\), and \(a_0=1\). For \(t\ge0\),
For convex \(L\)-smooth objectives this gives the characteristic \(O(LR^2/T^2)\) guarantee. Evaluating the gradient at the extrapolated point is central. An arbitrary fixed momentum coefficient is not interchangeable with the schedule in the theorem. Accelerated objective values need not decrease every step.
Line search
For a descent direction \(d\), Armijo backtracking seeks
Strong Wolfe additionally requires
These conditions are useful for smooth objectives. They are not a direct replacement for a horizon-tuned nonsmooth subgradient schedule.
11. Stochastic gradients and variance reduction
For \(f(w)=n^{-1}\sum_i f_i(w)\), uniformly sampling \(i_t\) gives the unbiased estimate \(g_t=\nabla f_{i_t}(w_t)\). One sample gradient usually costs much less than all \(n\) gradients, although actual speedup depends on batching and hardware.
The key statement is conditional:
A single sampled gradient need not satisfy the full objective’s supporting inequality. Its conditional expectation does.
SGD proof: exactly where the expectation enters
The distance identity holds for the random vector \(g_t\). By the tower rule,
If \(\mathbb E\|g_t\|^2\le B^2\), taking expectations and telescoping gives
The same tuning yields \(RB/\sqrt T\) for an averaged iterate in expectation. Strong convexity and the time-weighted proof give \(2B^2/[\mu(T+1)]\) under the corresponding moment and feasibility assumptions.
Do not substitute a variance bound \(\mathbb E\|g_t-\nabla f(w_t)\|^2\le\sigma^2\) for a second-moment bound without also controlling the gradient norm.
Mini-batches
For \(m\) conditionally independent samples with variance \(\sigma^2\), the mean has variance \(\sigma^2/m\). Write the centered errors as \(e_j\); independence and zero mean kill cross terms in \(\mathbb E\|m^{-1}\sum_j e_j\|^2\).
Sampling without replacement has a finite-population correction. Taking \(m=n\) recovers the full gradient when every sample is used exactly once; drawing \(n\) samples with replacement does not make the variance vanish.
SAG, SAGA, and SVRG
SAG stores a previous gradient for each sample, refreshes one, and steps using the average of the stored values. Its estimator is generally biased, but its memory permits linear convergence under appropriate smooth finite-sum strong-convexity assumptions. Generic storage is \(O(nd)\); some linear models only need one scalar per sample.
SAGA also keeps a gradient table but uses an unbiased correction. SVRG uses a snapshot \(\tilde w\) and full snapshot gradient \(\tilde\mu=\nabla f(\tilde w)\):
Its expectation is \(\nabla f(w_t)\). It avoids storing all \(n\) gradients, at the cost of snapshot passes and recomputation. As both points approach a common optimum, the correction’s noise can vanish. These linear-rate results are stronger than generic noisy SGD’s \(O(1/T)\) strongly convex guarantee, but they use extra finite-sum structure.
SGD’s noise can help leave some unstable regions; it does not guarantee escape from every local minimum or saddle. Nor does SGD universally generalize better than every adaptive optimizer.
12. Adaptive optimizers: what is remembered?
Adaptive methods rescale coordinates using gradient history. They still have hyperparameters, and their guarantees depend on the objective and update details. All operations below are coordinatewise; a small \(\varepsilon>0\) prevents division by zero.
| Method | Memory | Update idea |
|---|---|---|
| SGD | None | \(w_{t+1}=w_t-\alpha_tg_t\) |
| Heavy ball | Past velocity | Add momentum to the gradient step |
| AdaGrad | Sum of all squared gradients | Divide by the square root of accumulated squares |
| RMSProp | Exponential average of squares | Downweight older squared gradients |
| Adam | Exponential averages of gradients and squares | Bias-correct both, then divide |
| AMSGrad | Adam-like moments plus a running maximum | Prevent the second-moment denominator from shrinking |
AdaGrad: \(s_t=s_{t-1}+g_t\odot g_t\) and \(w_{t+1}=w_t-\alpha g_t/(\sqrt{s_t}+\varepsilon)\). Rarely updated coordinates retain larger effective steps. For a constant nonzero gradient magnitude and negligible \(\varepsilon\), the update magnitude decays as \(\alpha/\sqrt t\).
RMSProp: \(v_t=\beta_2v_{t-1}+(1-\beta_2)g_t\odot g_t\). Use \(w_{t+1}=w_t-\alpha g_t/(\sqrt{v_t}+\varepsilon)\). Under a constant squared gradient \(c^2\), \(v_t=c^2(1-\beta_2^t)\to c^2\); unlike AdaGrad’s accumulator it does not grow indefinitely in this example.
Adam, with \(m_0=v_0=0\):
The second moment is a mean of squared gradients, not the centered variance. Bias correction removes the effect of zero initialization on an exponentially weighted history. It does not make a history of changing gradients an unbiased estimate of the current gradient.
Derivation: moving averages and bias correction
Unroll the first moment:
The weights sum to \(1-\beta_1^t\). If all gradients have the same mean \(g\), then \(\mathbb E[m_t]=(1-\beta_1^t)g\), so division removes that initialization bias. The squared-gradient argument is identical under a constant second-moment assumption.
If you write a recurrence directly for the corrected second moment, it is
Applying the raw-moment recurrence to \(\hat v_{t-1}\) and then dividing again would double-correct it.
A two-step numerical check
Let \(g_1=(2,4)\), \(g_2=(4,2)\), and \(\alpha=0.1\). Ignore \(\varepsilon\). Use \(\beta_2=0.9\) for RMSProp and \((\beta_1,\beta_2)=(0.9,0.999)\) for Adam.
| Method | State after step 2 | Magnitude of update 2 |
|---|---|---|
| AdaGrad | \(s_2=(20,20)\) | \((0.0894,0.0447)\) |
| RMSProp | \(v_2=(1.96,1.84)\) | \((0.2857,0.1474)\) |
| Adam | \(m_2=(0.58,0.56)\); \(v_2=(0.019996,0.019984)\) | Approximately \((0.0965,0.0932)\) |
For Adam, divide by \(1-0.9^2=0.19\) and \(1-0.999^2=0.001999\) before taking the update. At the first step, AdaGrad and Adam each move by \(0.1\) in these positive coordinates; uncorrected RMSProp moves by approximately \(0.316\).
Variants and what the theory actually says
AdaMax replaces the squared-gradient accumulator with an exponentially weighted infinity-norm-style maximum. AdaDelta also tracks past squared updates. NAdam introduces a Nesterov-style correction; exact formulas depend on the variant.
AMSGrad uses a running maximum of second-moment estimates. With a constant or nonincreasing base step, its corresponding denominator-based step multiplier cannot grow. This addresses a failure in Adam’s original general convergence argument; it is not a guarantee that every quantity in the update decreases. Reddi et al., On the Convergence of Adam and Beyond.
It would be incorrect to say adaptive methods have no nonconvex theory: for example, AdaGrad-Norm has nonconvex convergence results under stated assumptions. Ward, Wu, and Bottou.
Likewise, experiments in which adaptive methods generalize worse than SGD are evidence about those settings, not a universal ranking. Optimizer choice, tuning, model, and data all matter. Wilson et al., The Marginal Value of Adaptive Gradient Methods in Machine Learning.
13. Proximal gradient: preserve the difficult term
Consider \(F(x)=f(x)+c(x)\), where \(f\) is convex and \(L\)-smooth and \(c\) is proper, closed, and convex. The second term may be nonsmooth or extended-valued, such as an indicator encoding constraints.
Linearize only \(f\), add a quadratic model, and leave \(c\) intact:
Completing the square gives
| Penalty or constraint | Proximal result |
|---|---|
| \(c=0\) | \(z\) |
| \(c(x)=\lambda\|x\|_1\) | \(\operatorname{sign}(z)\odot\max(|z|-\eta\lambda,0)\) |
| \(c=I_C\), closed convex \(C\) | Euclidean projection \(P_C(z)\) |
| \(c=I_{[l,r]}\) | \(\min(\max(z,l),r)\) |
| \(c(x)=\lambda\|x\|^2/2\) | \(z/(1+\eta\lambda)\) |
| \(c(x)=\lambda\|x\|_1+\mu\|x\|^2/2\) | Soft threshold at \(\eta\lambda\), then divide by \(1+\eta\mu\) |
| \(c(x)=-\lambda\log x\), \(x>0\), \(\lambda>0\) | \((z+\sqrt{z^2+4\eta\lambda})/2\) |
For soft thresholding, solve \(0\in(x-z)/\eta+\lambda\partial|x|\) by splitting into positive, negative, and zero cases. The zero case is possible exactly when \(|z|\le\eta\lambda\).
Proximal-gradient rate: the three-point inequality
Let \(x^+\) be the step from \(y\). Its optimality condition is
For any \(z\), combine this supporting inequality with smoothness of \(f\) and \(\eta\le1/L\). Convexity replaces \(f(y)+\nabla f(y)^\top(z-y)\) by a lower bound on \(f(z)\), producing
The right-hand distance terms simplify to
Take \(z=y\) for descent. Take \(z=x^\star\) for a telescoping gap bound. Sum and use monotonicity:
This exploits the smooth-plus-proximable structure, rather than treating the entire objective as an arbitrary nonsmooth function.
Accelerated proximal proof: the weighted potential
One useful variant uses \(\theta_t=2/(t+1)\) for \(t\ge1\), \(u_0=x_0\), and
Apply the preceding three-point inequality with \(z=x_{t-1}\) and with \(z=x^\star\), weight by \(1-\theta_t\) and \(\theta_t\), then add. Since \(x_t-y_t=\theta_t(u_t-u_{t-1})\), the inner product reduces to a difference of squared distances. With \(\Delta_t=F(x_t)-F^\star\),
For \(t\ge2\), \((1-\theta_t)/\theta_t^2=(t^2-1)/4\le1/\theta_{t-1}^2\). At \(t=1\), \(\theta_1=1\) eliminates the initial gap. The potential therefore telescopes to
With \(\eta=1/L\), this is the accelerated composite rate. The initial point must have finite objective value, and every proximal step must be well-defined and solved exactly for this proof.
A discontinuous penalty is a separate case
Suppose \(c(x)=0\) on \([0,\theta]\) and \(M>0\) outside, with \(\theta\ge0\). This penalty is not convex, so the preceding convex rates do not apply. Its scalar proximal problem can still be solved by comparing candidates.
If \(z\) is inside, choose \(z\). Otherwise compare the clipped point, whose cost is \(\operatorname{dist}(z,[0,\theta])^2/(2\eta)\), with \(z\) itself, whose cost is \(M\). Choose the lower cost; at equality both are minimizers. Solvability of a proximal subproblem does not imply convexity of the penalty.
14. Newton, quasi-Newton, and conjugate gradient
Newton’s method minimizes a local second-order model:
In implementation, solve a linear system rather than explicitly forming the inverse. A positive-definite Hessian makes the direction a descent direction. Indefinite or singular Hessians require safeguards, and full Newton steps are not globally reliable without additional assumptions or damping. A dense factorization costs roughly \(O(d^3)\), though structure can change that cost substantially.
The Newton decrement is \(\lambda_N^2=\nabla f^\top H^{-1}\nabla f\) for \(H\succ0\). Half this quantity is the predicted quadratic-model decrease. Treating it as a certified objective-gap stopping rule requires further conditions, such as an appropriate self-concordant analysis.
Quasi-Newton updates
Let \(s=x^+-x\) and \(y=\nabla f(x^+)-\nabla f(x)\). DFP updates an inverse-Hessian approximation \(H\):
BFGS in Hessian form updates \(B\):
Both preserve positive definiteness when the starting matrix is positive definite and \(s^\top y>0\). Strong convexity ensures this for a nonzero displacement; Wolfe line search is another way to obtain the curvature condition. L-BFGS stores a limited history of these displacement pairs.
DFP proof: Cauchy–Schwarz plus its equality case
For \(v\ne0\), put \(a=H^{1/2}v\) and \(b=H^{1/2}y\). Then
Both terms are nonnegative. The first is zero only when \(v=cy\) for some nonzero \(c\). Then the second equals \(c^2s^\top y>0\). Thus the sum is strictly positive for every nonzero \(v\).
The proof for Hessian-form BFGS is the same argument with the roles of \(s\) and \(y\) exchanged. The secant equations are \(H^+y=s\) and \(B^+s=y\); keep straight which matrix approximates which object.
Conjugate gradient
For \(f(x)=x^\top Ax/2-b^\top x\) with \(A\succ0\), directions satisfy \(d_i^\top Ad_j=0\) for \(i\ne j\). Exact line search along \(d_k\) gives
In exact arithmetic, conjugate gradient solves the system in at most \(d\) steps. Finite precision loses exact conjugacy, so that finite-termination statement is not a literal runtime guarantee.
15. Bellman equations and policy gradients
In reinforcement learning, the policy is the object being optimized. For autoregressive language models, a useful abstraction takes the prompt and generated prefix as the state, the next token as the action, and a completed response as a trajectory.
For discounted returns, \(G_t=\sum_{k\ge0}\gamma^kr_{t+k+1}\) with \(0\le\gamma<1\). Bounded rewards make the infinite sum converge. Finite episodic problems can use \(\gamma=1\).
Bellman equations
With expectations over transitions and the policy,
For optimal values, replace the policy expectation over the next action by a maximum:
The advantage is \(A^\pi(s,a)=Q^\pi(s,a)-V^\pi(s)\); it can be negative.
The log-derivative trick
For an undiscounted finite episode, let \(J(\theta)=\mathbb E_{\tau\sim p_\theta}[R(\tau)]\). Assuming differentiation and expectation can be interchanged, policy-independent reward and environment dynamics give
The trajectory density factors as
Only the policy factors depend on \(\theta\), so
Past rewards contribute zero to the expected score at time \(t\). Replacing the total return by reward-to-go yields
Discounted objectives require consistent time weights or a discounted occupancy convention; do not mix the finite undiscounted formula with a different objective silently. The policy-gradient framework is developed in Sutton et al., Policy Gradient Methods for Reinforcement Learning with Function Approximation.
Why an action-independent baseline preserves the gradient
Condition on \(s\) and treat \(b(s)\) as fixed in the score estimator:
A learned baseline is normally detached when forming this policy-gradient term. An arbitrary action-dependent baseline cannot be pulled outside the sum. A suitable baseline can reduce variance; action independence alone does not guarantee that every choice reduces it.
Exact \(Q^\pi\) can replace sampled reward-to-go by conditional expectation. Exact advantage subtracts \(V^\pi\). A TD residual \(r_t+\gamma V(s_{t+1})-V(s_t)\) has the correct conditional advantage mean when \(V=V^\pi\); an approximate critic can introduce bias. A fixed ranking of all these estimators by variance is not universal.
LLM training context
A common pipeline is next-token pretraining, supervised instruction tuning, preference/reward modeling, and policy optimization; direct preference optimization is an alternative preference-learning route. This is a useful conceptual map, not a requirement that every system follow every stage.
A KL penalty to a reference policy discourages distributional drift. The sampled log ratio \(\log\pi_\theta(a\mid s)-\log\pi_{\rm ref}(a\mid s)\) estimates a statewise KL in expectation under \(\pi_\theta\); a single sampled ratio can be negative. KL regularization does not guarantee prevention of reward hacking. Verifiable rewards also depend on the verifier and can be exploited when checks are incomplete.
If the reward includes a parameter-dependent regularizer, account for that dependence when differentiating the full objective. The simple score-function derivation above assumed a fixed reward.
16. Backpropagation and Mixture of Experts
Backpropagation is repeated chain rule with intermediate derivatives reused rather than recomputed. For a sigmoid unit \(a_j^\ell=\sigma(z_j^\ell)\),
Writing \(\delta_j^\ell=\partial\mathcal L/\partial z_j^\ell\),
An \(\ell_2\) penalty adds its gradient separately, with the coefficient determined by the exact loss normalization.
For softmax logits \(z\),
These are logit derivatives. Gradients with respect to model parameters require another chain-rule multiplication.
Dense experts
For \(y=\sum_iG_i(x)E_i(x)\), with scalar gates and vector expert outputs,
The gate derivative is a scalar inner product. If \(E_2=(2,4)\) and \(\partial\mathcal L/\partial y=(2,-1)\), that gate derivative is zero. If \(G_1=0.6\), the first expert’s output gradient is \((1.2,-0.6)\).
Hard routing is not the maximum-score function
Hard top-1 chooses \(i^\star=\arg\max_i s_i(x)\) and returns \(E_{i^\star}(x)\). Away from ties, the chosen index is locally constant: the task loss provides no ordinary derivative through the discrete selection itself. Unselected expert parameters receive no task gradient through this token’s routed output, though shared parameters and auxiliary losses can still receive gradients.
This is different from \(m(x)=\max_i s_i(x)\). For differentiable convex scores, the subdifferential of \(m\) is the convex hull of the active score gradients. That formula does not differentiate the hard-routed output and should not be used as if it did.
Also, the formal partial derivative with respect to an independently variable dense gate is \(E_i^\top\nabla_y\mathcal L\) even at \(G_i=0\). A zero hard gate and differentiation through its selection mechanism are different operations.
Noisy top-\(k\) can form scores
retain the top \(k\), set the other logits to \(-\infty\), and apply softmax. Softplus supplies a positive noise scale. Load-balancing objectives encourage broader expert use; they do not guarantee that every expert trains on every batch.
17. Supplementary tools: constraints, duality, and structure
These topics extend the core first-order material and are useful for interpreting optimization problems and practice questions. Their inclusion here does not imply a particular exam’s syllabus.
Lagrangians and KKT
For \(\min f(x)\) subject to \(g_i(x)\le0\) and \(h_j(x)=0\),
The dual function \(q(\lambda,\nu)=\inf_x\mathcal L(x,\lambda,\nu)\) is concave, even when the primal is nonconvex. For fixed \(x\), the Lagrangian is affine in the multipliers. Weak duality follows because \(\mathcal L(x,\lambda,\nu)\le f(x)\) for feasible \(x\) and nonnegative inequality multipliers.
For a differentiable convex problem, KKT consists of primal feasibility, dual feasibility, stationarity, and complementary slackness:
KKT is sufficient in the convex setting; a constraint qualification such as Slater’s condition gives the usual necessity and strong-duality result. Standard convex formulations use convex inequality functions and affine equality functions. A nonlinear equality can happen to describe a convex set, so “every representation of a convex feasible set must use affine equalities” would be too strong.
At a primal-dual saddle point,
This is an inequality, not equality for all arguments. These definitions and qualification conditions are treated systematically in Boyd and Vandenberghe, Convex Optimization.
Projection formulas
For a halfspace \(a^\top x\le b\), with \(a\ne0\),
For a box, clip each coordinate. For a feasible box intersected with a halfspace, the candidate is \(x(\lambda)=\operatorname{clip}(z-\lambda a,l,u)\). Use \(\lambda=0\) if it is feasible; otherwise solve \(a^\top x(\lambda)=b\) for a nonnegative multiplier. The left side is nonincreasing, so bisection is useful after bracketing a solution.
Lasso reformulations and duality
For \(\lambda>0\), introducing \(p\) with \(-p_i\le w_i\le p_i\) rewrites Lasso as
For fixed \(w\), the smallest feasible \(p_i\) is \(|w_i|\), so the minimizers in \(w\) are unchanged. The objective is now smooth, with linear constraints. Projection onto each cone \(|w_i|\le p_i\) is unchanged inside; zero if \(p_i\le-|w_i|\); otherwise \(((|w_i|+p_i)\operatorname{sign}(w_i)/2,(|w_i|+p_i)/2)\).
Derivation: the Lasso dual
Introduce \(z=Aw-y\) and multiplier \(v\):
Minimizing over \(z\) gives \(z=v\) and contribution \(-\|v\|^2/2\). Minimizing over \(w\) gives zero when \(\|A^\top v\|_\infty\le\lambda\), and \(-\infty\) otherwise. Therefore the dual is
Changing the loss normalization changes the quadratic coefficient in the dual. Strong duality holds under the standard finite-valued convex affine-constraint qualification here.
Low rank, sparsity, and decomposability
Robust PCA separates \(X=L+S\) into low-rank structure and sparse corruption. The convex relaxation
uses the nuclear norm for rank and the entrywise \(\ell_1\) norm for sparsity. Exact recovery needs additional assumptions; merely writing this objective does not prove recovery.
A regularizer is decomposable across appropriate subspaces when it adds exactly. For \(\ell_1\), vectors on disjoint coordinate supports satisfy \(\|u+v\|_1=\|u\|_1+\|v\|_1\). Group norms have the analogous property on disjoint groups. Nuclear norm is additive for matrices with orthogonal row and column spaces. Euclidean norm is generally not additive on orthogonal vectors: \(\|e_1+e_2\|_2=\sqrt2<2\).
Restricted strong convexity asks for quadratic curvature only on a specified family of differences. For a \(k\)-sparse difference in least squares, it is enough to control \(X_S^\top X_S/n\succeq\alpha_k I\) on each relevant support. This can hold when the full Hessian is singular.
Graph-signal objectives often combine reconstruction \(\|X-V\alpha\|_F^2\), graph smoothness \(\operatorname{tr}(\alpha^\top\Delta\alpha)\), and row sparsity \(\sum_i\|\alpha_{i,:}\|_2\). Orthonormality of \(V\), Laplacian sign constraints, and a trace normalization enforce structure and scale. With fixed graph quantities the coefficient problem can be convex; joint graph/basis learning is generally nonconvex. An orthogonality constraint also prevents an automatic “convex in every block” conclusion.
Min–max and submodularity
Weak min–max duality says
Equality requires extra structure or a saddle point. An infimum or supremum need not be attained.
For a finite ground set and nonnegative similarities, facility location \(F(S)=\sum_i\max_{j\in S}s_{ij}\), with empty-set baseline zero, is monotone submodular. The gain of adding \(j\) is \(\sum_i\max(0,s_{ij}-\max_{k\in S}s_{ik})\), which decreases as \(S\) grows. Column-set rank is also submodular: a column that adds a new direction to a larger span also adds a new direction to a smaller span. These are set-function statements, distinct from convexity in a continuous matrix variable.
18. Worked revision problems
These problems consolidate the mathematical patterns from the notes. The solutions are self-contained rather than tied to unverified past-paper numbering or marking schemes.
Problem 1 · A corner can be the optimum
For \(f(x)=\max(2x,-x)\), establish convexity, compute \(\partial f(0)\), certify a minimum, and take one subgradient step from \(x_0=2\) with \(\eta=0.5\).
Show solution
It is a maximum of affine functions, hence convex. The left and right slopes are \(-1\) and \(2\), so it is nondifferentiable at zero and \(\partial f(0)=[-1,2]\). Since zero belongs to this interval, zero is a global minimizer. At \(x_0=2\), the active slope is \(2\), giving \(x_1=2-0.5(2)=1\).
Problem 2 · Find the curvature constants
Let \(f(w)=\|Xw-y\|^2+\lambda\|w\|^2/2\) with \(\lambda>0\). Find \(L\) and \(\mu\). What changes when \(n<d\)?
Show solution
The Hessian is \(2X^\top X+\lambda I\), so \(L=2\lambda_{\max}(X^\top X)+\lambda\) and \(\mu=2\lambda_{\min}(X^\top X)+\lambda\). When \(n<d\), the unregularized matrix is singular; regularization still guarantees \(\mu=\lambda\) as a tight lower eigenvalue in that case. The factor \(1/2\) on the regularizer matters.
Problem 3 · Soft thresholding and elastic net
For \(y=(3.5,-4,1.2,-0.8)\) and \(\lambda=1.5\), minimize \(\|x-y\|^2/2+\lambda\|x\|_1\). Then evaluate the elastic-net prox at \(z=(3,-1,0)\) with \(\eta=1\), \(\lambda=2\), \(\mu=1\).
Show solution
Soft thresholding gives \(x^\star=(2,-2.5,0,0)\) and \(\|x^\star\|^2=10.25\). For elastic net, threshold at two to obtain \((1,0,0)\), then divide by \(1+\eta\mu=2\): the result is \((0.5,0,0)\).
Problem 4 · A linear-fractional quasigradient
Let \(f(x)=(a^\top x+b)/(c^\top x+d)\) on the positive-denominator domain. Show that \(g=a-f(x_0)c\) satisfies \(g^\top(x-x_0)\ge0\Rightarrow f(x)\ge f(x_0)\).
Show solution
Use the identity \(a^\top x_0+b=f(x_0)(c^\top x_0+d)\). Then
Nonnegativity and division by the positive denominator give the result. Sublevel and superlevel sets are halfspaces intersected with the domain, so this function is both quasiconvex and quasiconcave. For a general differentiable quasiconvex function, only the appropriate strict-direction implication follows from its gradient; a zero gradient need not certify a minimum.
Problem 5 · Convexity of a spectral quantity
Show that \(\phi_k(X)=\sum_{i=1}^k\sigma_i(X)\) is convex. Explain why proving each singular value convex would be invalid.
Show solution and subdifferential
Use the variational representation, for \(1\le k\le\min(m,n)\),
The trace inequality bounds the right side by the sum of leading singular values, with equality at their singular vectors. Each expression is linear in \(X\), so the maximum is convex. The counterexample in section 4 rules out convexity of individual \(\sigma_k\) for \(k\ge2\).
The general subdifferential is the convex hull of coefficient matrices \(UV^\top\) attaining the maximum. For \(k<\min(m,n)\), a strict positive gap \(\sigma_k>\sigma_{k+1}\) gives gradient \(U_kV_k^\top\). Ties need the convex-hull formula. For the full nuclear norm at rank \(r\),
The full-norm, rank-deficient case needs this separate treatment; a blanket claim of differentiability without considering zero singular values is unsafe.
Problem 6 · Positive definiteness and a quadratic optimum
Minimize \(x_1^2+x_2^2-14x_1-6x_2\) subject to \(x_1+x_2\le2\) and \(x_1+2x_2\le3\).
Show KKT solution
The Hessian is \(2I\), so the objective is strongly convex. The unconstrained solution \((7,3)\) is infeasible. Try the first constraint active and the second inactive. Stationarity gives
Together with \(x_1+x_2=2\), this gives \((x_1,x_2)=(3,-1)\) and \(\lambda_1=8\). The second constraint has value \(1\le3\), and its multiplier is zero. Primal feasibility, nonnegative multipliers, stationarity, and complementary slackness all hold. Hence the unique optimum is \((3,-1)\), with value \(-26\).
For comparison, imposing only the second constraint gives \((5,-1)\), which violates the first. Imposing both gives \((1,1)\) with a negative second multiplier. One valid KKT point already suffices to certify the convex optimum.
Problem 7 · Momentum arithmetic
Take \(x_t=(2,3)\), \(v_t=(1,-2)\), \(\beta=0.9\), \(\eta=0.1\), and \(\nabla f(x_t)=(4,-5)\). Compute the next velocity and point.
Show solution
Keep the velocity update and position update separate. Mixing the two is a common sign error.
Problem 8 · Projection, proximity, and a jump
Find the proximal point for \(c(x)=0\) on \([0,1]\) and \(c(x)=2\) elsewhere, with \(z=3\) and \(\eta=1\). Is it unique? Can the convex proximal-gradient rate be used for this penalty?
Show solution
The best inside point is \(1\), with cost \((1-3)^2/2=2\). The best outside point is \(3\), with cost \(2\). Both are minimizers. The penalty has a jump and is nonconvex, so the convex composite theorem does not apply. This illustrates why uniqueness and rate claims cannot be inferred just from the word “proximal.”
Problem 9 · Sampling and policy normalization
A density on \([0,1]\) is \(p(x)=2x\). Transform a uniform sample \(u=0.64\) into a sample from this density. Separately, show that the mean softmax logit score is zero.
Show solution
The CDF is \(F(x)=x^2\), so inverse-CDF sampling gives \(x=\sqrt u=0.8\). For the softmax score,
The second identity is the algebra behind action-independent baselines.
Problem 10 · Decomposability and reversed inclusions
If \(M\subseteq\bar M\), which way does the orthogonal-complement inclusion go? Why is \(\ell_1\) decomposable across a support and its complement?
Show solution
\(\bar M^\perp\subseteq M^\perp\): a vector orthogonal to every member of the larger space is also orthogonal to every member of the smaller space.
If \(u\) is supported on \(S\) and \(v\) on \(S^c\), every coordinate contains at most one nonzero term. Therefore
No cancellation or reinforcement can occur within a coordinate because the supports are disjoint.
19. The final self-check
Before calling a proof complete, check the following.
| Claim or shortcut | What to check |
|---|---|
| “The Hessian is PSD” | Everywhere on a convex domain, or only at one point? |
| “The function is smooth” | A gradient-Lipschitz bound; outside convexity, both curvature signs matter |
| “The minimum exists” | Attainment, not just a finite infimum |
| “Strictly convex” | Uniqueness if a minimum exists, not necessarily strong convexity |
| “The subgradient is bounded” | Domain interior and chosen norm; boundary normals can change the statement |
| “The last iterate converges at this rate” | Does the proof actually bound a best or averaged iterate? |
| “SGD is unbiased” | Conditional expectation at the current iterate, and the sampling distribution |
| “Variance is divided by batch size” | Independent samples, or a without-replacement correction |
| “Momentum accelerates” | Which algorithm, schedule, objective class, and measured error? |
| “Adaptive methods generalize worse” | A finding in some experiments, not a theorem for all tasks |
| “The router has a subgradient” | Maximum score versus discrete selection and the routed output |
| “A baseline reduces variance” | A suitable choice is needed; unbiasedness alone is not variance reduction |
| “A constraint is convex” | The feasible set and the standard formulation both deserve attention |
For rate proofs, reconstruct this sequence: one-step relation → class assumption → telescope or contract → choose the step → identify the output → solve for the tolerance.
For property questions, start with the simplest route: closure rules, then derivatives or Hessians, then the definition. To disprove a claim, produce one concrete violating example. A matrix being positive semidefinite is a statement about quadratic forms, not about every entry being nonnegative.
For objective-reading questions, label every term by what it measures and encourages. Then examine each constraint, the variable with respect to which convexity is claimed, and whether the problem is jointly convex. These habits transfer beyond any particular course or exam.
References and further reading
The organization and worked examples above are based on my course revision notes. These primary sources provide context and fuller treatments for the definitions and qualifications used here:
- Boyd and Vandenberghe — Convex Optimization: convex geometry, optimality, duality, and numerical methods.
- Fazel — Convex Envelopes of Rank and Cardinality Functions: the domains on which nuclear and sparsity envelopes apply.
- Sutton et al. — Policy Gradient Methods for Reinforcement Learning with Function Approximation: policy gradients and function approximation.
- Wilson et al. — The Marginal Value of Adaptive Gradient Methods in Machine Learning: empirical and theoretical comparisons of adaptive and non-adaptive methods.
- Reddi et al. — On the Convergence of Adam and Beyond: convergence failures and the motivation for AMSGrad.
- Ward, Wu, and Bottou — AdaGrad Stepsizes: Sharp Convergence Over Nonconvex Landscapes: nonconvex results for AdaGrad-Norm.
- Wang et al. — Provable Acceleration of Heavy Ball beyond Quadratics: why extending quadratic momentum results requires care.