2

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?

Li haonan
  • 209

1 Answers1

3

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.

Theo Bendit
  • 50,900
  • Essentially, I'm attacking this question via its Fenchel conjugate. The reason I'm doing it this way is because this ties to something I'm studying in my PhD. Given a subset $C$ of a real Hilbert space (e.g. $\Bbb{R}^n$), the function $f(x) = \sup_{y \in C} \langle x, y \rangle - \frac{1}{2}|y|^2 = \frac{1}{2}(|x|^2 - \inf_{y \in C} |x - y|^2)$ is known as Asplund's "Indefinite Integral" (antiderivative is probably a better term). It's an anti-subderivative of the projection function onto $C$, in that $P_C(x) \subseteq \partial f(x)$ (with equality if $C$ is closed and convex!). – Theo Bendit Feb 18 '19 at 01:21