Past exam of the optimisation for data science course of the University of Oxford / 2023 (B6.2, A17941W1)

Solutions to all three questions of the optimisation for data science course of the University of Oxford Part B examination, sat on 7 June 2023. Source: original released PDF, bundle pages 300–303; paper pages 1–4. The original question numbering is retained without reproducing the question statements. Two printing errors on paper page 3 are addressed explicitly in parts 2(c) and 2(f).

Unless a subscript indicates the L1 norm, $\Vert \cdot \Vert$ denotes the Euclidean norm. In Question 1, the regularization weight is $\lambda \ge 0$ and the step size is positive. The big O notation in part 1(d) is interpreted for fixed $x$ as the step size tends to zero, with the necessary subdifferential qualification explained there.

Put $z=x-\alpha \nabla f(x)$ and $\tau =\alpha \lambda$. The proximal operator for the L1 norm separates into independent scalar minimization problems:The subgradient optimality condition is $0\in p_i-z_i+\tau \partial |p_i|$. By the subgradient of the absolute value, a positive solution must satisfy $p_i=z_i-\tau >0$, and a negative solution must satisfy $p_i=z_i+\tau <0$. At zero, the subgradient optimality condition holds exactly when $|z_i|\le \tau$. The squared term makes the objective function a strictly convex function, so these cases give its unique minimiser.

Thus the proximal operator is the soft-thresholding operatorConsequently the requested proximal gradient mapping, rather than just the proximal operator, isThe corresponding proximal gradient method update is $x_i^{+}=S_{\alpha \lambda }(x_i-\alpha {\partial }_{i}f(x))$. Small coordinates are set exactly to zero. When $\lambda =0$, the soft-thresholding operator is the identity and the proximal gradient mapping reduces to $\nabla f(x)$.

Again write $z=x-\alpha \nabla f(x)$ and $\tau =\alpha \lambda$, and let $z_{\ell }$ denote its $\ell$th block of $k$ coordinates. The block mixed norm in this part makes the proximal operator separate over blocks. For a single block, its minimiser solvesAt a nonzero $u$, the gradient of the Euclidean norm is $u/\Vert u\Vert$. The subgradient optimality condition therefore becomesThus $u$ points in the direction of $z_{\ell }$ and $\Vert z_{\ell }\Vert =\Vert u\Vert +\tau$. This yields $u=(1-\tau /\Vert z_{\ell }\Vert )z_{\ell }$ when $\Vert z_{\ell }\Vert >\tau$.

At zero, the subdifferential of the Euclidean norm is the closed Euclidean unit ball: the subgradient inequality is $q^{T}w\le \Vert w\Vert$ for every $w$, which is equivalent to $\Vert q\Vert \le 1$ by the Cauchy-Schwarz inequality and the choice $w=q$. Hence zero solves the subgradient optimality condition exactly when $\Vert z_{\ell }\Vert \le \tau$. This also covers $z_{\ell }=0$ and avoids division by zero.

The resulting radial soft thresholding isIf $y_{\ell }$ is the corresponding block of $x$, the required proximal gradient mapping isWhole blocks can become zero, while nonzero blocks retain their direction after the gradient step. For a block of size one, radial soft thresholding agrees with the soft-thresholding operator in part (a).

Set $g_j=G_{1/L}(x^j)$, $r_j=\Vert x^j-x^{\ast }{\Vert }^2$ and ${\delta }_j=\varphi (x^j)-\varphi (x^{\ast })$. Here $g_j$ is the proximal gradient mapping, $r_j$ is a squared Euclidean distance, and ${\delta }_j\ge 0$ because $x^{\ast }$ is a global minimizer. The update gives $x^{j+1}=x^j-g_j/L$.

First use the supplied inequality (1) with $z=x^j$:Thus the objective function values, and hence the errors ${\delta }_j$, are nonincreasing. Next use (1) with $z=x^{\ast }$:Expansion of the squared Euclidean norm givesso the last bound is exactly ${\delta }_{j+1}\le L(r_j-r_{j+1})/2$.

The telescoping sum over $j=0,\dots ,k-1$ therefore givesSince each summand is at least ${\delta }_k$, we obtain the proximal gradient objective error boundThe bound holds for the last iterate. The monotonicity of the objective function values is what converts an averaged estimate into this last-iterate estimate.

Fix $x$, and write $p=x-\alpha G_{\alpha }(x)$ and $g=G_{\alpha }(x)$. The supplied subgradient relation gives $v=v_{\alpha }\in \lambda \partial \psi (p)$ with $g=\nabla f(x)+v$. The evaluation point in $\nabla f$ is $x$, whereas $v$ is a subgradient at the new point $p$.

Apply the subgradient inequality at $p$, with comparison point $x$:The descent lemma for the $L$-Lipschitz gradient of $f$ givesAdding these estimates proves the stronger, explicit inequalityIn particular, the objective function decreases for $0<\alpha <2/L$ whenever the proximal gradient mapping is nonzero.

To justify the requested big O notation, we must check that $g$, which depends on $\alpha$, stays bounded. Suppose $\partial (\lambda \psi )(x)$ is nonempty, and choose a fixed $w$ in this subdifferential. This holds for a finite-valued convex function on ${\mathbb{R}}^n$, including both norms in parts (a) and (b). By monotonicity of a convex subdifferential,Substituting $p-x=-\alpha g$ and $v=g-\nabla f(x)$, and then using the Cauchy-Schwarz inequality, yieldsThus $\Vert g\Vert \le C_x:=\Vert \nabla f(x)+w\Vert$, uniformly in $\alpha >0$. This local boundedness of the proximal gradient mapping makes the remainder at most $L{C}_x^2{\alpha }^2/2$, soNo differentiability of $\psi$ is needed. If an proper extended-real function is allowed as the regularization term, the subdifferential condition at $x$ is a qualification for this uniform remainder; the preceding explicit descent inequality remains the useful statement whenever its quantities are finite.

Let $d=y-x$ and take $0<t\le 1$. Rearrange the defining inequality for a strongly convex function, applied to $x+td$:Because $f$ is differentiable at $x$, its directional derivative in direction $d$ isTaking the limit in the rearranged inequality givesThis is the supporting affine function inequality strengthened by a positive squared Euclidean distance. Differentiability at $x$ alone suffices; no derivative at $y$ is used.

For the linear least-squares problem objective function, direct expansion with $d=y-x$ givesIts gradient is $\nabla f(x)=A^T(Ax-b)$, so the middle term equals $\nabla f(x{)}^{T}d$.

Use the supplied thin singular value decomposition $A=US{V}^T$. Since $U^{T}U=I_n$, the linear map $w\mapsto Uw$ preserves the Euclidean norm. The square matrix $V$ is an orthogonal matrix, so $\Vert V^{T}d\Vert =\Vert d\Vert$. ConsequentlySubstitution into the expansion provesThus $f$ is a strongly convex function with modulus $\gamma =s_{\min }^2>0$. This modulus is sharp: choose $d=V{e}_i$ for an index attaining the smallest singular value. The Hessian matrix is $A^{T}A=V{S}^2{V}^T$, so the same conclusion says that its smallest eigenvalue is $s_{\min }^2$.

There is a summation-index misprint. On the native PDF, paper page 3, equation (4) has $X^k$ inside a sum indexed by $j$. The intended telescoping estimate has $X^j$ inside that sum; this is the estimate proved below and used in part (d). The index mismatch is present in the original PDF, rather than being introduced by the transcription.

Take the expectation of the supplied conditional expectation bound (3), using the tower property:Rearranging and forming a telescoping sum givesBecause $x^{\ast }$ is a global minimizer, $f(X^k)\ge f(x^{\ast })$ for every realisation. Hence the corrected equation (4) isAll expectations at a finite iteration are finite here: a deterministic starting point and finitely many choices of the sampled index produce only finitely many possible iterates. The bound controls accumulated squared gradients, with an additive contribution from the stochastic gradient noise floor.

Write ${\Delta }_0=f(x^0)-f(x^{\ast })$. Dividing the corrected estimate from part (c) by $k/(2L)$ gives the averaged stationarity bound for stochastic gradient descentThe Cauchy-Schwarz inequality, first within each expectation and then over the $k$ indices, givesThusEquivalently, if $J$ is chosen independently of the run with the discrete uniform distribution on $\{0,\dots ,k-1\}$, then $\mathbb{E}\Vert \nabla f(X^J){\Vert }^2\le M+2L{\Delta }_0/k$. The same bound for the expected Euclidean norm follows by the Cauchy-Schwarz inequality.

The guarantee is averaged or best-iterate stationarity. It does not assert that every last iterate converges, or that the limiting Euclidean norm equals $\sqrt{M}$. The squared gradient bound has excess $O(k^{-1})$ above $M$; the displayed expected Euclidean norm bound is within $O(k^{-1/2})$ of $\sqrt{M}$, including the zero-noise case. For fixed $M>0$, it is sharper:For example, to ensure ${\min }_{j<k}\mathbb{E}\Vert \nabla f(X^j)\Vert \le \sqrt{M}+\epsilon$ with $\epsilon >0$, it suffices that $k\ge 2L{\Delta }_0/(2\sqrt{M}\epsilon +{\epsilon }^2)$. The big O notation here concerns these upper bounds, rather than an asserted asymptotic equality for the stochastic gradient noise floor.

Condition on $X^k=x$, and set $r=x-x^{\ast }$, $g=\nabla f(x)$ and $h=\nabla f_{S_k}(x)$. Since the sampled index is independent of $X^k$ and has the discrete uniform distribution, $h$ is an unbiased stochastic gradient:Write ${\sigma }_k^2=\mathbb{E}[\Vert h-g{\Vert }^2\mid X^k=x]\le M$. Expanding $h=g+(h-g)$ and using the zero conditional mean of $h-g$ proves the stochastic gradient second-moment identityThe stochastic gradient descent update is $X^{k+1}=x-h/L$. Expanding the squared Euclidean distance and using the preceding identities givesThe subgradient inequality for the differentiable convex function $f$ gives $f(x)-f(x^{\ast })\le g^{T}r$. Combining this with (3),Removing the temporary notation for the conditioning point yieldsThe noise contributes twice in this argument: once in the supplied bound (3), and once in converting the expected squared step into the squared gradient. Each contribution is at most $M/(2L)$.

The printed distance needs a square. The native PDF, paper page 3, prints $\Vert x^0-x^{\ast }\Vert$ in the final bound, but the general conclusion from (5) contains $\Vert x^0-x^{\ast }{\Vert }^2$. We first prove the corrected statement and then show that the printed version can fail.

Take the expectation in (5), use the tower property, and sum over $j=0,\dots ,k-1$. The squared Euclidean distances form a telescoping sum:Discard the final nonnegative squared Euclidean distance. The smallest of $k$ numbers is at most their arithmetic mean, soThis is an $O(k^{-1})$ bound above the stochastic gradient noise floor $M/L$ for the best expected objective function value. By Jensen's inequality, it also bounds $\mathbb{E}f({\bar{X}}^k)-f(x^{\ast })$ for the averaged iterate ${\bar{X}}^k=k^{-1}{\sum }_{j=0}^{k-1}{X}^{j+1}$, because $f$ is a convex function.

To test the printed version, take one component function, $f_1(x)=f(x)=x^2/4$, with $L=1$, $x^{\ast }=0$ and $x^0=10$. This convex quadratic function has $\nabla f(x)=x/2$, hence it has a $1$-Lipschitz gradient. The stochastic gradient descent update is deterministic, its conditional variance is zero, and the assumed positive bound $M=1/10$ is valid. At $k=1$, the new iterate is $X^1=5$, soThus the printed inequality is false under its stated assumptions. The squared Euclidean distance in the corrected bound resolves the defect.

Fix $x$ and put $g={\nabla }_{\mathcal{B}}f(x)$, the block coordinate gradient. For $t\ge 0$, define the one-variable function $q(t)=f(x-tg)$. By the chain rule,The last equality holds because the coordinates of $g$ outside $\mathcal{B}$ are zero. The fundamental theorem of calculus and the Cauchy-Schwarz inequality therefore giveFor $\alpha \ge 0$, the supplied condition (6), applied at the fixed starting point $x$ with parameter $t$, bounds the integrand by $L_{\mathcal{B}}t\Vert g{\Vert }^2$. Integration yieldsThis argument needs only the given directional Lipschitz continuity and continuous differentiability; convexity is not needed for this part. If the block coordinate gradient is zero, the inequality is equality.

The subgradient inequality for the differentiable convex function $f$ givesThus $y$ is a global minimizer of $\varphi$ with value zero. Subtracting an affine function preserves convexity.

We must also justify using part (a) for $\varphi$, since its partial derivative can differ from that of $f$. First show that condition (6) for a singleton block implies the full coordinate Lipschitz continuity estimateIf ${\partial }_{i}f(z)\ne 0$, choose $\alpha =-t/{\partial }_{i}f(z)$ in (6). If it is zero but ${\partial }_{i}f(z+t{e}_i)\ne 0$, apply the same argument starting at $z+t{e}_i$ and reverse the displacement. If both partial derivatives are zero, the estimate is immediate. The availability of all real $\alpha$ in (6) justifies these choices.

Now ${\partial }_i\varphi (z)={\partial }_{i}f(z)-{\partial }_{i}f(y)$, so differences of this partial derivative along coordinate lines are unchanged. Hence $\varphi$ has the same coordinate Lipschitz continuity constant $L_i$ and satisfies the singleton version of (6). Apply part (a) to $\varphi$ with step size $1/L_i$:Combining with its already established nonnegativity provesThe coordinate estimate survives subtraction of the supporting affine function. This is the step that allows the arbitrary comparison point $y$ to be exploited in part (c).

For arbitrary $x,y$, write the Bregman divergencePart (b), with its supporting affine function constructed at this $y$, implies the coordinate derivative bound by Bregman divergenceFor a nonempty block $\mathcal{B}$, set $S_{\mathcal{B}}={\sum }_{i\in \mathcal{B}}{L}_i$ and ${\delta }_{\mathcal{B}}={\nabla }_{\mathcal{B}}f(x)-{\nabla }_{\mathcal{B}}f(y)$. Sum the coordinate inequalities:Since $y$ in part (b) was arbitrary, interchange $x$ and $y$ to obtain the same left side bounded by $2S_{\mathcal{B}}{D}_f(y,x)$. Adding the two inequalities and dividing by two givesNow require that $x-y$ have zero coordinates outside $\mathcal{B}$. The last dot product is then ${\delta }_{\mathcal{B}}^T(x-y)$. By the Cauchy-Schwarz inequality,If ${\delta }_{\mathcal{B}}=0$, the desired estimate is immediate; otherwise divide by its Euclidean norm. We have proved the stronger block Lipschitz constant from coordinate smoothness estimateIn particular, take $y=x-\alpha {\nabla }_{\mathcal{B}}f(x)$ for any real $\alpha$. This proves (6), with a valid choiceThe least admissible Lipschitz constant is therefore no larger than this choice. For the empty block, the block coordinate gradient vanishes identically and its least nonnegative Lipschitz constant is zero. The proof uses only $C^1$ differentiability, convexity and coordinate Lipschitz continuity, with no assumed Hessian matrix.

The supporting inequality in part 2(a) bounds $f$ below by an affine function plus a positive squared Euclidean norm, making it a coercive function. Its continuity gives a global minimizer $x^{\ast }$, which is unique by strict convexity. Let $L_{\max }={\max }_i{L}_i$, $\ell =n/m$ and ${\Delta }_0=f(x^0)-f(x^{\ast })$. Here $m$ is the block size, so its role differs from the number of component functions in Question 2. Use randomized block coordinate descent with uniformly sampled blocks of size $m$, independently at each update. Sampling uniformly from a fixed partition into $\ell$ equal-sized blocks gives the same calculation, since each coordinate has inclusion probability $1/\ell =m/n$.

Let $\beta$ be a common upper bound on the block Lipschitz constants. Part (c) permits $\beta =m{L}_{\max }$. With step size $1/\beta$, part (a) givesSumming squared partial derivatives according to their inclusion probabilities,For a strongly convex function, part 2(a) also yields the strong convexity gradient inequalityIndeed, substitute $y=x^{\ast }$ into the supporting inequality and complete the square in $x^{\ast }-x$: the expression $\nabla f(x{)}^{T}d+\gamma \Vert d{\Vert }^2/2$ is at least $-\Vert \nabla f(x){\Vert }^2/(2\gamma )$ for every $d$.

Combining the last three estimates gives a contraction in conditional expectation:By the tower property and repeated application,An optimization epoch counts $n$ coordinate partial derivative evaluations: it comprises $\ell$ block updates or one full gradient update. With sampling with replacement, an optimization epoch is this work measure; it need not visit every coordinate. Consequently the block method needsto bring the expected objective function gap below $\epsilon$, for $0<\epsilon <{\Delta }_0$, up to integer rounding.

For the steepest descent method, use a global Lipschitz gradient constant $L_f$. Part (c) with the full block permits $L_f={\sum }_i{L}_i\le n{L}_{\max }$. The descent lemma with step size $1/L_f$, together with the strong convexity gradient inequality, givesAn exact line search along the negative gradient does at least as well in objective function decrease per update. Ignoring its additional work, the resulting epoch complexity isThe common coordinate-based guarantees favour blocks by a factor $n/m=\ell$ in epochs. In fact, with the conservative constants $\beta =m{L}_{\max }$ and $L_f=n{L}_{\max }$, both methods have the same guaranteed contraction per update, while a block update uses only $m$ coordinate partial derivatives.

This compares the bounds justified by the given constants. For a particular objective function, sharper constants give the comparison $\beta /\gamma$ against $L_f/\gamma$; an actual speedup of $\ell$ is not universal. Computing a block coordinate gradient also need not cost exactly $m/n$ of a full gradient evaluation. The epoch complexity comparison assumes that coordinate partial derivative counts are a useful measure of work, and does not itself establish a wall-clock comparison.