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

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.