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

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.