  Classical approach to regularization is to design norms enhancing smoothness
or sparsity and then to use this norm or some power of this norm as a
regularization function. The choice of the regularization function (for
instance a power function) in terms of the norm is mostly dictated by
computational purpose rather than theoretical considerations.
  In this work, we design regularization functions that are motivated by
theoretical arguments. To that end we introduce a concept of optimal
regularization called "minimax regularization" and, as a proof of concept, we
show how to construct such a regularization function for the $\ell_1^d$ norm
for the random design setup. We develop a similar construction for the
deterministic design setup. It appears that the resulting regularized
procedures are different from the one used in the LASSO in both setups.
