= Solution
{c}
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^*$, which is unique by <strict convexity>. Let $L_{\max}=\max_iL_i$, $\ell=n/m$ and $\Delta_0=f(x^0)-f(x^*)$. 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=mL_{\max}$. With <step size> $1/\beta$, part (a) gives
$$
f\left(x-\frac1\beta\nabla_{\mathcal B}f(x)\right)\leq f(x)-\frac1{2\beta}\|\nabla_{\mathcal B}f(x)\|^2.
$$
Summing squared <partial derivatives> according to their inclusion <probabilities>,
$$
\mathbb E_{\mathcal B}\|\nabla_{\mathcal B}f(x)\|^2=\frac1\ell\|\nabla f(x)\|^2.
$$
For a <strongly convex function>, part 2(a) also yields the <strong convexity gradient inequality>
$$
\|\nabla f(x)\|^2\geq2\gamma\big(f(x)-f(x^*)\big).
$$
Indeed, substitute $y=x^*$ into the supporting inequality and complete the square in $x^*-x$: the expression $\nabla f(x)^Td+\gamma\|d\|^2/2$ is at least $-\|\nabla f(x)\|^2/(2\gamma)$ for every $d$.
Combining the last three estimates gives a contraction in <conditional expectation>:
$$
\mathbb E[f(X^{t+1})-f(x^*)\mid X^t]
\leq\left(1-\frac\gamma{\ell\beta}\right)\big(f(X^t)-f(x^*)\big).
$$
By the <tower property> and repeated application,
$$
\mathbb E[f(X^t)-f(x^*)]\leq\left(1-\frac\gamma{\ell\beta}\right)^t\Delta_0
\leq\exp\left(-\frac{\gamma t}{\ell\beta}\right)\Delta_0.
$$
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 needs
$$
\boxed{\begin{gathered}
O\left(\frac\beta\gamma\log\frac{\Delta_0}{\varepsilon}\right)\text{ epochs},\\
O\left(\frac{mL_{\max}}\gamma\log\frac{\Delta_0}{\varepsilon}\right)\text{ using }\beta=mL_{\max}.
\end{gathered}}
$$
to bring the expected <objective function> gap below $\varepsilon$, for $0<\varepsilon<\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_iL_i\leq nL_{\max}$. The <descent lemma> with <step size> $1/L_f$, together with the <strong convexity gradient inequality>, gives
$$
f(x^{t+1})-f(x^*)\leq\left(1-\frac\gamma{L_f}\right)\big(f(x^t)-f(x^*)\big).
$$
An <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> is
$$
\boxed{\begin{gathered}
O\left(\frac{L_f}\gamma\log\frac{\Delta_0}{\varepsilon}\right)\text{ epochs},\\
O\left(\frac{nL_{\max}}\gamma\log\frac{\Delta_0}{\varepsilon}\right)\text{ using }L_f=nL_{\max}.
\end{gathered}}
$$
\b[The common coordinate-based guarantees favour blocks by a factor $n/m=\ell$ in epochs.] In fact, with the conservative constants $\beta=mL_{\max}$ and $L_f=nL_{\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.
Back to article page
