Huber loss is defined by $$\mathcal{H}(u) = \begin{cases} \frac{1}{2}\|u\|_2^2 & \|u\|_2 \leq 1 \\ \|u\|_2- \frac{1}{2} & \|u\|_2 > 1 \end{cases} . $$
From the graph it's evident, but I'm just stuck on the rigorous proof. It happens not to be the minimum or maximum of two different convex functions here. So any ideas?
For the corrected version, consider the function $$f(x) = \sup_{\|y\| \le 1} x \cdot y - \frac{1}{2}\|y\|^2.$$ For each given $y$, the function $x \mapsto x \cdot y - \frac{1}{2}\|y\|^2$ is affine, and hence $f$ is convex.
I claim that $f = \mathcal{H}$. Note first that $$x \cdot y - \frac{1}{2}\|y\|^2 = \frac{1}{2}\|x\|^2 - \frac{1}{2}\|x - y\|^2.$$ Thus, if $\|x\| \le 1$, the maximum of the above expression, over $y$ such that $\|y\| \le 1$, is $\frac{1}{2}\|x\|^2$. Hence $f(x) = \frac{1}{2}\|x\|^2$.
Suppose instead that $\|x\| > 1$. To maximise the above expression, one must minimise the $\|x - y\|^2$ term, again with $y$ restricted to the unit ball, i.e. where $\|y\| \le 1$. This occurs when $y = \frac{x}{\|x\|}$. So, we get $$f(x) = x \cdot \frac{x}{\|x\|} - \frac{1}{2}\left\| \frac{x}{\|x\|}\right\|^2 = \|x\| - \frac{1}{2},$$ as required. Thus $\mathcal{H}$ is the supremum of affine functions, and hence is convex.