Past exam of the optimisation for data science course of the University of Oxford / 2023 / 3 / b / Solution

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).