A subgradient $g \in \partial f(y)$ at a point $x$ is a $g$ such that $$f(y) \geq f(x) + g^T(y-x)$$ for all $y$ in the domain of $f$.
For $f(x) = ||x||_2$, we know that $\partial f(x) = \{\frac{x}{||x||_2}\}$ (if $x \neq 0$).
How do we find a subgradient $g$ of $f(x) = ||x||_2^2$? I've tried things like $x, \frac{x}{||x||_2}$, etc. but none of them worked.
(I will denote $\langle x, y \rangle = x^\top y$, i.e. the dot product, and $\|x\| = \|x\|_2$.)
Suppose $g$ is a subgradient. Then, for all $y$, $$\langle g, y - x\rangle \le \|y\|^2 - \|x\|^2 = \langle y + x, y - x\rangle\implies \langle y + x - g, y - x\rangle \ge 0.$$ I want a particularly revealing value of $y$. In particular, we have a non-negative inner product that will change depending on $y$. If I can choose $y$ so that $y + x - g$ and $y - x$ are negatives of each other, then the inner product turns into the form $-\langle v, v \rangle$, which is non-positive. Since it'd be non-negative too by assumption, it would be a particularly revealing value of $y$.
In particular, I want $y$ such that $$y + x - g = -(y - x) \implies y = g/2.$$ For this choice of $y$, we have $$0 \le \langle g/2 + x - g, g/2 - x\rangle = -\|g/2 - x\|^2 \le 0.$$ Thus, $$\|g/2 - x\|^2 = 0 \implies x = g/2 \implies g = 2x.$$ So, there's only one possibility for $g \in \partial(\|\cdot\|^2)(x)$: $g = 2x$. We can see that it is indeed a subgradient by \begin{align*} \|x - y\|^2 \ge 0 &\implies \|x\|^2 - 2\langle x, y \rangle + \|y\|^2 \ge 0 \\ &\implies \|y\|^2 \ge 2\langle x, y\rangle - \|x\|^2 \\ &\implies \|y\|^2 \ge 2\langle x, y - x\rangle + 2 \langle x, x \rangle - \|x\|^2 \\ &\implies \|y\|^2 \ge \langle 2x, y - x\rangle + \|x\|^2. \end{align*}