Is $f(x) = \lVert x-y \rVert^2+\lambda \lVert x \rVert_0$ not differentiable at $x=0$ or not differentiable at all? $\lVert x \rVert_0$ is the $\ell_0$ norm. I think $f(x)$ is not differentiable only at $x=0$. But one of the reviewers said that "$f(x)$ is never differentiable". Who is correct? Please help!!!
 A: Neither. It is differentiable everywhere (with derivative $0$) except at the coordinate axes $x_i=0$ (i.e. not just the origin $x=0$)
Note that the "$\ell_0$-norm" is not really a norm.
A: Let $x\in \Bbb R^n$ so that $f:\Bbb R^n\to \Bbb R$.
$$\| x - y \|^2 = \sum\limits_{k=1}^n (x_i-y_i)^2$$
is clearly differentiable everywhere, so differentiability of $f$ is equivalent to differentiability of $\|x\|_0$ (whenever $\lambda\neq 0$).
In the interior of each orthant, $\|x\|_0 = n$ is constant, and so differentiable with zero derivative. On the boundaries however, it's not even continuous; $\|x\|_0 = k < n$ on the boundaries, but there is always a direction $v$ where $\|x+\varepsilon v\|_0 = n$ for all (sufficiently small) $\varepsilon > 0$. So it's certainly not differentiable on any of the boundaries.
To be clear, the boundaries are the subspaces of $\Bbb R^n$ where $x_i = 0$ for some (possibly many) $i$. These are the $x_i$ axes, but also the $x_ix_j$ planes, etc. On any subspace where each of $x_i$ vanish for $i\in I \subset \{1,\dots, n\}$, the partials $\frac{\partial}{\partial x_i}\|x\|_0$ exist and are zero. In particular, at the origin, all partials exist and are zero, but the function is not differentiable there.
