Past exam of the optimisation for data science course of the University of Oxford / 2023 / 2

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.