CS769 · Course revision reference

Optimization in Machine Learning: The Course Revision Guide

A reference to return to: convexity, convergence proofs, stochastic and adaptive methods, proximal optimization, and the mathematics behind policy gradients and expert routing.

November 21, 2026 · 53 min read · Mathematics

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\),

\[ D_{t+1}=D_t-2\eta_tg_t^\top(x_t-x^\star)+\eta_t^2\|g_t\|^2. \]

Equivalently, for \(\eta_t>0\),

\[ g_t^\top(x_t-x^\star)=\frac{D_t-D_{t+1}}{2\eta_t}+\frac{\eta_t}{2}\|g_t\|^2. \]

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

  1. Turn an inner product into distances: \(2u^\top v=\|u\|^2+\|v\|^2-\|u-v\|^2\).
  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.
  3. Optimize a free parameter: minimize \(R^2/(2\eta T)+\eta B^2/2\) over \(\eta>0\).
  4. 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.
  5. Contract: \(a_{t+1}\le\rho a_t\) gives \(a_T\le\rho^Ta_0\) for \(0\le\rho<1\).
  6. Weight before summing: weights proportional to \(t\) can turn a non-telescoping strongly convex bound into a telescoping one.
  7. Write an inequality both ways and add: this turns first-order convexity into monotonicity of the gradient.
  8. Restrict to a line: set \(\phi(t)=f(x+t(y-x))\) and integrate \(\phi'\).
  9. Add and subtract a cross term: useful for differences of products and composite expressions.
  10. Condition before taking expectation: use \(\mathbb E[g_t\mid x_t]=\nabla f(x_t)\), then the tower rule.
  11. Complete the square: this reveals a proximal step inside a quadratic model.
  12. 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:

\[x,y\in C,\quad\theta\in[0,1]\quad\Longrightarrow\quad\theta x+(1-\theta)y\in C.\]

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

\[ \|\theta(x-c)+(1-\theta)(y-c)\| \le\theta\|x-c\|+(1-\theta)\|y-c\|. \]

An ellipsoid can be written either as

\[\{x:(x-c)^\top P^{-1}(x-c)\le1\},\qquad P\succ0,\]

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

\[a^\top x\le b\le a^\top y\qquad(x\in C,\ y\in D).\]

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:

\[P_C(z)=\arg\min_{x\in C}\frac12\|x-z\|_2^2.\]

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

\[f(\theta x+(1-\theta)y)\le\max\{f(x),f(y)\}.\]

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:

\[\operatorname{epi}f=\{(x,t):t\ge f(x)\}.\]

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

\[f(\theta x+(1-\theta)y)\le\theta f(x)+(1-\theta)f(y).\]

Strict convexity replaces \(\le\) by \(<\) for distinct points and \(0<\theta<1\). Strong convexity asks for a uniform quadratic margin:

\[ f(\theta x+(1-\theta)y)\le\theta f(x)+(1-\theta)f(y) -\frac\mu2\theta(1-\theta)\|x-y\|^2. \]

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

\[\theta\|x\|^2+(1-\theta)\|y\|^2-\|\theta x+(1-\theta)y\|^2=\theta(1-\theta)\|x-y\|^2.\]

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:

\[f\text{ convex}\iff f(y)\ge f(x)+\nabla f(x)^\top(y-x).\]

For twice continuously differentiable functions:

\[f\text{ convex}\iff\nabla^2f(x)\succeq0\quad\text{everywhere}.\]

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:

\[ (\nabla f(x)-\nabla f(y))^\top(x-y)\ge0.\]

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

\[\frac{f(x+t(y-x))-f(x)}t\le f(y)-f(x),\qquad0<t\le1.\]

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

\[f(y)-f(x)=\int_0^1\nabla f(x+t(y-x))^\top(y-x)\,dt.\]

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

\[\nabla h=p,\qquad\nabla^2h=\operatorname{diag}(p)-pp^\top.\]

For any \(v\),

\[v^\top\nabla^2h\,v=\sum_i p_iv_i^2-\left(\sum_i p_iv_i\right)^2=\operatorname{Var}_p(v)\ge0.\]

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

\[\log\sum_i a_ib_i\le\frac12\log\sum_i a_i^2+\frac12\log\sum_i b_i^2.\]

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:

\[N(x)\ge0,\quad N(x)=0\iff x=0;\qquad N(ax)=|a|N(x);\qquad N(x+y)\le N(x)+N(y).\]

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

\[|N(x)-N(y)|\le N(x-y).\]

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

\[N_*(z)=\sup_{N(x)\le1}z^\top x,\]

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\),

\[\|A\|_2\le\|A\|_F\le\|A\|_*\le\sqrt r\|A\|_F\le r\|A\|_2.\]

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\):

\[\frac{N((\theta A+(1-\theta)B)x)}{N(x)}\le\theta\frac{N(Ax)}{N(x)}+(1-\theta)\frac{N(Bx)}{N(x)}.\]

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:

\[g\in\partial f(x)\iff f(y)\ge f(x)+g^\top(y-x)\quad\text{for every }y.\]

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

\[\partial(af)=a\partial f\ (a>0),\qquad\partial(f+g)=\partial f+\partial g,\]
\[\partial[f(Ax+b)]=A^\top\partial f(Ax+b).\]

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

\[\partial\max_i f_i(x)=\operatorname{conv}\left(\bigcup_{i\in A(x)}\partial f_i(x)\right),\quad A(x)=\{i:f_i(x)=\max_j f_j(x)\}.\]

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,

\[0\in\partial f(x^\star)\iff x^\star\in\arg\min f.\]

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\),

\[x^\star\text{ minimizes }f\text{ over }C\iff\nabla f(x^\star)^\top(x-x^\star)\ge0\quad\forall x\in 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

\[-LI\preceq\nabla^2f(x)\preceq LI.\]

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

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\):

\[ f(y)-f(x)-\nabla f(x)^\top(y-x) =\int_0^1[\nabla f(x+t(y-x))-\nabla f(x)]^\top(y-x)\,dt. \]

Cauchy–Schwarz and smoothness bound the integrand above by \(Lt\|y-x\|^2\). Hence

\[f(y)\le f(x)+\nabla f(x)^\top(y-x)+\frac L2\|y-x\|^2.\]

For \(y=x-\nabla f(x)/L\), this becomes

\[f(y)\le f(x)-\frac1{2L}\|\nabla f(x)\|^2.\]

For an unconstrained strongly convex objective, minimize its quadratic lower model to obtain the Polyak–Łojasiewicz inequality:

\[\|\nabla f(x)\|^2\ge2\mu(f(x)-f^\star).\]

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:

\[f(x)-f^\star\ge\frac\mu2\|x-x^\star\|^2.\]

For convex \(L\)-smooth functions on \(\mathbb R^d\), co-coercivity strengthens monotonicity:

\[(\nabla f(x)-\nabla f(y))^\top(x-y)\ge\frac1L\|\nabla f(x)-\nabla f(y)\|^2.\]

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:

\[\min_w\sum_i\ell(F_w(x_i),y_i)+\lambda\Omega(w).\]

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\),

\[\nabla(a^\top x)=a,\qquad\nabla(x^\top Ax)=2Ax,\qquad\nabla\frac12\|Ax-b\|^2=A^\top(Ax-b).\]

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

\[\nabla f(w)=-\sum_i\frac{y_ix_i}{1+e^{y_ix_i^\top w}},\qquad0\preceq\nabla^2f(w)\preceq\frac14X^\top X.\]

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\),

\[\nabla f=2X^\top(Xw-y),\qquad\nabla^2f=2X^\top X.\]

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

\[w^\star=(X^\top X+\lambda I)^{-1}X^\top y.\]

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\),

\[\frac1T\sum_{t=0}^{T-1}(f(x_t)-f^\star)\le\frac{R^2}{2\eta T}+\frac{\eta B^2}{2}.\]

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:

\[\sum_{t=0}^{T-1}(f(x_t)-f^\star)\le\frac{D_0-D_T}{2\eta}+\frac\eta2\sum_{t=0}^{T-1}\|g_t\|^2\le\frac{R^2}{2\eta}+\frac{\eta TB^2}{2}.\]

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:

\[\min_{0\le t<T}(f(x_t)-f^\star)\le\frac{R^2+B^2\sum_t\eta_t^2}{2\sum_t\eta_t}.\]

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)\),

\[f(x_{t+1})\le f(x_t)-\eta\left(1-\frac{L\eta}{2}\right)\|g_t\|^2.\]

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

\[\frac1{2L}\sum_{t=0}^{T-1}\|g_t\|^2\le f(x_0)-f(x_T).\]

The distance identity and convexity give

\[\sum_{t=0}^{T-1}(f(x_t)-f^\star)\le\frac L2R^2+\frac1{2L}\sum_t\|g_t\|^2.\]

Substitute the first inequality and move \(f(x_0)-f(x_T)\) to the left. The index shift is the key step:

\[\sum_{t=1}^{T}(f(x_t)-f^\star)\le\frac L2R^2.\]

Objective values decrease, so the last value is at most this average:

\[f(x_T)-f^\star\le\frac{LR^2}{2T}.\]

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:

\[\min_{0\le t<T}\|\nabla f(x_t)\|^2\le\frac{2L(f(x_0)-f_{\inf})}{T}.\]

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:

\[g_t^\top(x_t-x^\star)\ge f(x_t)-f^\star+\frac\mu2D_t.\]

At \(\eta=1/L\), it leads to

\[D_{t+1}\le(1-\mu/L)D_t.\]
Proof C: the contraction argument and a shorter function-value proof

Insert the strengthened inequality into the distance update:

\[D_{t+1}\le(1-\mu\eta)D_t+2\eta(f^\star-f(x_t))+\eta^2\|g_t\|^2.\]

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

\[f(x_T)-f^\star\le\frac L2D_T\le\frac L2(1-\mu/L)^TR^2.\]

Since \(1-u\le e^{-u}\), a sufficient count is

\[T\ge\frac L\mu\log\frac{LR^2}{2\epsilon}.\]

A shorter proof uses PL directly:

\[f(x_{t+1})-f^\star\le f(x_t)-f^\star-\frac1{2L}\|g_t\|^2\le(1-\mu/L)(f(x_t)-f^\star).\]

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

\[\bar x_T=\frac{2}{T(T+1)}\sum_{t=1}^Tt x_t.\]

Then

\[f(\bar x_T)-f^\star\le\frac{2B^2}{\mu(T+1)}.\]
Proof D: why weighting by time removes the logarithm

The one-step relation is

\[f(x_t)-f^\star\le\frac{\eta_tB^2}{2}+\left(\frac1{2\eta_t}-\frac\mu2\right)D_t-\frac1{2\eta_t}D_{t+1}.\]

Substitute the schedule and multiply by \(t\):

\[t(f(x_t)-f^\star)\le\frac{B^2}{\mu}+\frac\mu4\left[t(t-1)D_t-t(t+1)D_{t+1}\right].\]

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:

\[v_{t+1}=\beta v_t-\eta\nabla f(x_t),\qquad x_{t+1}=x_t+v_{t+1}.\]

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

\[\eta=\frac4{(\sqrt L+\sqrt\mu)^2},\qquad\beta=\left(\frac{\sqrt L-\sqrt\mu}{\sqrt L+\sqrt\mu}\right)^2.\]

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\),

\[ \begin{aligned} x_{t+1}&=y_t-\frac1L\nabla f(y_t),\\ a_{t+1}&=\frac{1+\sqrt{1+4a_t^2}}2,\\ y_{t+1}&=x_{t+1}+\frac{a_t-1}{a_{t+1}}(x_{t+1}-x_t). \end{aligned} \]

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.

For a descent direction \(d\), Armijo backtracking seeks

\[f(x+\eta d)\le f(x)+c_1\eta\nabla f(x)^\top d,\qquad0<c_1<1.\]

Strong Wolfe additionally requires

\[|\nabla f(x+\eta d)^\top d|\le c_2|\nabla f(x)^\top d|,\qquad c_1<c_2<1.\]

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:

\[\mathbb E[g_t\mid w_t]=\nabla f(w_t).\]

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,

\[\mathbb E[g_t^\top(w_t-w^\star)]=\mathbb E[\nabla f(w_t)^\top(w_t-w^\star)]\ge\mathbb E[f(w_t)]-f^\star.\]

If \(\mathbb E\|g_t\|^2\le B^2\), taking expectations and telescoping gives

\[\frac1T\sum_{t=0}^{T-1}(\mathbb E f(w_t)-f^\star)\le\frac{R^2}{2\eta T}+\frac{\eta B^2}{2}.\]

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)\):

\[v_t=\nabla f_{i_t}(w_t)-\nabla f_{i_t}(\tilde w)+\tilde\mu.\]

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\):

\[ \begin{aligned} m_t&=\beta_1m_{t-1}+(1-\beta_1)g_t,\\ v_t&=\beta_2v_{t-1}+(1-\beta_2)g_t\odot g_t,\\ \hat m_t&=m_t/(1-\beta_1^t),\qquad\hat v_t=v_t/(1-\beta_2^t),\\ w_{t+1}&=w_t-\alpha_t\hat m_t/(\sqrt{\hat v_t}+\varepsilon). \end{aligned} \]

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:

\[m_t=(1-\beta_1)\sum_{s=1}^t\beta_1^{t-s}g_s.\]

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

\[\hat v_t=\frac{\beta_2(1-\beta_2^{t-1})}{1-\beta_2^t}\hat v_{t-1}+\frac{1-\beta_2}{1-\beta_2^t}g_t^2.\]

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:

\[x_{t+1}=\arg\min_x\left\{f(x_t)+\nabla f(x_t)^\top(x-x_t)+\frac1{2\eta}\|x-x_t\|^2+c(x)\right\}.\]

Completing the square gives

\[z_t=x_t-\eta\nabla f(x_t),\qquad x_{t+1}=\operatorname{prox}_{\eta c}(z_t),\]
\[\operatorname{prox}_{\eta c}(z)=\arg\min_x\left\{c(x)+\frac1{2\eta}\|x-z\|^2\right\}.\]
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

\[\frac{y-x^+}{\eta}-\nabla f(y)\in\partial c(x^+).\]

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

\[F(x^+)\le F(z)+\frac1\eta(x^+-y)^\top(z-x^+)+\frac1{2\eta}\|x^+-y\|^2.\]

The right-hand distance terms simplify to

\[F(x^+)\le F(z)+\frac1{2\eta}\bigl(\|y-z\|^2-\|x^+-z\|^2\bigr).\]

Take \(z=y\) for descent. Take \(z=x^\star\) for a telescoping gap bound. Sum and use monotonicity:

\[F(x_T)-F^\star\le\frac1T\sum_{t=1}^T(F(x_t)-F^\star)\le\frac{R^2}{2\eta T}.\]

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

\[y_t=(1-\theta_t)x_{t-1}+\theta_tu_{t-1},\qquad x_t=\operatorname{prox}_{\eta c}(y_t-\eta\nabla f(y_t)),\]
\[u_t=x_{t-1}+\frac{x_t-x_{t-1}}{\theta_t}.\]

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\),

\[\frac{\Delta_t}{\theta_t^2}+\frac{\|u_t-x^\star\|^2}{2\eta}\le\frac{1-\theta_t}{\theta_t^2}\Delta_{t-1}+\frac{\|u_{t-1}-x^\star\|^2}{2\eta}.\]

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

\[F(x_T)-F^\star\le\frac{2R^2}{\eta(T+1)^2}.\]

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:

\[x_{t+1}=x_t-[\nabla^2f(x_t)]^{-1}\nabla f(x_t).\]

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\):

\[H^+=H+\frac{ss^\top}{s^\top y}-\frac{Hyy^\top H}{y^\top Hy}.\]

BFGS in Hessian form updates \(B\):

\[B^+=B-\frac{Bss^\top B}{s^\top Bs}+\frac{yy^\top}{y^\top s}.\]

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

\[v^\top H^+v=\|a\|^2-\frac{(a^\top b)^2}{\|b\|^2}+\frac{(s^\top v)^2}{s^\top y}.\]

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

\[\alpha_k=-\frac{\nabla f(x_k)^\top d_k}{d_k^\top Ad_k},\qquad x_{k+1}=x_k+\alpha_kd_k.\]

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,

\[V^\pi(s)=\mathbb E_{a,s'}[r(s,a,s')+\gamma V^\pi(s')],\]
\[Q^\pi(s,a)=\mathbb E_{s'}[r(s,a,s')+\gamma\mathbb E_{a'\sim\pi}Q^\pi(s',a')].\]

For optimal values, replace the policy expectation over the next action by a maximum:

\[V^*(s)=\max_a\mathbb E_{s'}[r(s,a,s')+\gamma V^*(s')],\]
\[Q^*(s,a)=\mathbb E_{s'}[r(s,a,s')+\gamma\max_{a'}Q^*(s',a')].\]

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

\[\nabla J=\mathbb E[R(\tau)\nabla\log p_\theta(\tau)].\]

The trajectory density factors as

\[p_\theta(\tau)=p(s_0)\prod_t\pi_\theta(a_t\mid s_t)p(s_{t+1}\mid s_t,a_t).\]

Only the policy factors depend on \(\theta\), so

\[\nabla\log p_\theta(\tau)=\sum_t\nabla\log\pi_\theta(a_t\mid s_t).\]

Past rewards contribute zero to the expected score at time \(t\). Replacing the total return by reward-to-go yields

\[\nabla J=\mathbb E\left[\sum_t\nabla\log\pi_\theta(a_t\mid s_t)G_t\right].\]

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:

\[ \begin{aligned} \mathbb E_{a\sim\pi}[b(s)\nabla\log\pi(a\mid s)] &=b(s)\sum_a\pi(a\mid s)\frac{\nabla\pi(a\mid s)}{\pi(a\mid s)}\\ &=b(s)\nabla\sum_a\pi(a\mid s)=0. \end{aligned} \]

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)\),

\[z_j^\ell=\sum_iw_{ij}^\ell a_i^{\ell-1},\qquad\sigma'(z)=\sigma(z)(1-\sigma(z)).\]

Writing \(\delta_j^\ell=\partial\mathcal L/\partial z_j^\ell\),

\[\frac{\partial\mathcal L}{\partial w_{ij}^\ell}=\delta_j^\ell a_i^{\ell-1},\qquad\delta_j^\ell=\sigma'(z_j^\ell)\sum_pw_{jp}^{\ell+1}\delta_p^{\ell+1}.\]

An \(\ell_2\) penalty adds its gradient separately, with the coefficient determined by the exact loss normalization.

For softmax logits \(z\),

\[\frac{\partial\log p_a}{\partial z_b}=\mathbf1[a=b]-p_b,\qquad\frac{\partial p_a}{\partial z_b}=p_a(\mathbf1[a=b]-p_b).\]

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,

\[\frac{\partial\mathcal L}{\partial E_i}=G_i\frac{\partial\mathcal L}{\partial y},\qquad\frac{\partial\mathcal L}{\partial G_i}=E_i^\top\frac{\partial\mathcal L}{\partial y}.\]

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

\[H_i(x)=(xW_g)_i+\xi_i\operatorname{softplus}((xW_{\rm noise})_i),\qquad\xi_i\sim\mathcal N(0,1),\]

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\),

\[\mathcal L(x,\lambda,\nu)=f(x)+\sum_i\lambda_i g_i(x)+\sum_j\nu_jh_j(x),\qquad\lambda_i\ge0.\]

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:

\[\nabla f(x^\star)+\sum_i\lambda_i^\star\nabla g_i(x^\star)+\sum_j\nu_j^\star\nabla h_j(x^\star)=0,\]
\[\lambda_i^\star g_i(x^\star)=0.\]

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,

\[\mathcal L(x^\star,\lambda,\nu)\le\mathcal L(x^\star,\lambda^\star,\nu^\star)\le\mathcal L(x,\lambda^\star,\nu^\star).\]

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\),

\[P_C(z)=z-\frac{\max(a^\top z-b,0)}{\|a\|^2}a.\]

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

\[\min_{w,p}\frac12\|Aw-y\|^2+\lambda\sum_i p_i.\]

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\):

\[\mathcal L=\frac12\|z\|^2+\lambda\|w\|_1+v^\top(Aw-y-z).\]

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

\[\max_v-\frac12\|v\|^2-v^\top y\quad\text{subject to}\quad\|A^\top v\|_\infty\le\lambda.\]

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

\[\min_{L,S}\|L\|_*+\lambda\|S\|_1\quad\text{subject to }X=L+S\]

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

\[\sup_y\inf_x f(x,y)\le\inf_x\sup_y f(x,y).\]

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

\[g^\top(x-x_0)=a^\top x+b-f(x_0)(c^\top x+d).\]

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)\),

\[\phi_k(X)=\max_{U^\top U=V^\top V=I_k}\operatorname{tr}(U^\top XV).\]

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\),

\[\partial\|X\|_*=\{U_rV_r^\top+W:U_r^\top W=0,\ WV_r=0,\ \|W\|_2\le1\}.\]

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

\[2x_1-14+\lambda_1=0,\qquad2x_2-6+\lambda_1=0.\]

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
\[v_{t+1}=0.9(1,-2)-0.1(4,-5)=(0.5,-1.3),\qquad x_{t+1}=(2.5,1.7).\]

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,

\[\sum_a p_a\frac{\partial\log p_a}{\partial z_b}=\sum_a p_a(\mathbf1[a=b]-p_b)=p_b-p_b\sum_a p_a=0.\]

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

\[\|u+v\|_1=\sum_{i\in S}|u_i|+\sum_{i\notin S}|v_i|=\|u\|_1+\|v\|_1.\]

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:

← All writing