Norm of a function, Smoothness Penalization I am seeking for some intuition why norm (for any reasonable norm on functions) of a function is smaller if the function is smoother.
 A: Norms may not necessarily be related smoothness in any way. 
The uniform norm $\|f\|_u=\sup_{x \in [0,1]} |f(x)|$ on the space of continuous functions $C[0,1]$ is unrelated to smoothness. There are nowhere differential functions of arbitrarily small uniform norm.
But on the space of $L_2[0,1]$ absolutely continuous functions the norm $\|f\|=\int_0^1|f(t)| \ dt+\int_0^1 |f'(t)| \ dt$ does measure smoothness in some sense.
A: spitespike gave a good explanation already, but here is a another point of view.
Suppose $\|\cdot\|$ is a translation-invariant norm on some space of functions on $\mathbb R$. Translation-invariant means $\|f\|=\|f(\cdot-h)\|$ for all $h\in\mathbb R$. Consider the convolution $f*\varphi$ with some mollifier $\varphi$. In functional terms, this is a weighted average of translates of $f$. By assumption, all of these translates belong to the closed ball of radius $\|f\|$. Therefore, the average is in this ball as well: 
$$\|f*\varphi\| \le \|f\|  \tag1$$
We see that making $f$ smoother does not increase its norm. If the norm is strictly convex, then strict inequality holds in (1).
