(a) What is meant by the subdifferential $\partial f(x)$ of a convex function $f: \mathbb{R}^{d} \rightarrow \mathbb{R}$ at $x \in \mathbb{R}^{d}$ ? Write down the subdifferential $\partial f(x)$ of the function $f: \mathbb{R} \rightarrow \mathbb{R}$ given by $f(x)=\gamma|x|$, where $\gamma>0$.

Show that $x$ minimises $f$ if and only if $0 \in \partial f(x)$.

What does it mean for a function $f: \mathbb{R}^{d} \rightarrow \mathbb{R}$ to be strictly convex? Show that any minimiser of a strictly convex function must be unique.

(b) Suppose we have input-output pairs $\left(x_{1}, y_{1}\right), \ldots,\left(x_{n}, y_{n}\right) \in\{-1,1\}^{p} \times\{-1,1\}$ with $p \geqslant 2$. Consider the objective function

$$f(\beta)=\frac{1}{n} \sum_{i=1}^{n} \exp \left(-y_{i} x_{i}^{T} \beta\right)+\gamma\|\beta\|_{1}$$

where $\beta=\left(\beta_{1}, \ldots, \beta_{p}\right)^{T}$ and $\gamma>0$. Assume that $\left(y_{i}\right)_{i=1}^{n} \neq\left(x_{i 1}\right)_{i=1}^{n}$. Fix $\beta_{2}, \ldots, \beta_{p}$ and define

$$\kappa_{1}=\sum_{\substack{1 \leqslant i \leqslant n: \\ x_{i 1} \neq y_{i}}} \exp \left(-y_{i} \eta_{i}\right) \quad \text { and } \quad \kappa_{2}=\sum_{i=1}^{n} \exp \left(-y_{i} \eta_{i}\right)$$

where $\eta_{i}=\sum_{j=2}^{p} x_{i j} \beta_{j}$ for $i=1, \ldots, n$. Show that if $\left|2 \kappa_{1}-\kappa_{2}\right| \leqslant \gamma$, then

$$\operatorname{argmin}_{\beta_{1} \in \mathbb{R}} f\left(\beta_{1}, \beta_{2}, \ldots, \beta_{p}\right)=0 .$$

[You may use any results from the course without proof, other than those whose proof is asked for directly.]