I want to find sufficient conditions such that for a convex function $f \colon \mathbb{R}^n \to \mathbb{R}$, finding the best $x$ with $\lvert\lvert x \rvert\rvert_1 \leq \delta$ is equivalent to using L1-regularization :
$$ \inf_{\lvert\lvert x \rvert\rvert_1 \leq \delta} f(x) = \inf_{x} f(x)+\lambda \lvert\lvert x \rvert\rvert_1 \qquad\qquad (1) $$
- Are there such conditions?
- Are there any (standard) references that describe them?
What I tried so far:
From Slater's condition, I know that:
\begin{align*} \inf_{\lvert\lvert x \rvert\rvert_1 \leq \delta} f(x) &= \inf_{\lvert\lvert x \rvert\rvert_1 - \delta \leq 0} f(x) \\ &= \sup_{\lambda \geq 0} \inf_x f(x)+\lambda\Big(\lvert\lvert x\rvert\rvert_1-\delta\Big) \end{align*}
However, I don't really know how to continue from here.
From Slater's condition and convexity, you know that strong duality holds: \begin{align*} \inf_{\lvert\lvert x \rvert\rvert_1 \leq \delta} f(x) &= \inf_{\lvert\lvert x \rvert\rvert_1 - \delta \leq 0} f(x) \\ &= \sup_{\lambda \geq 0} \inf_x f(x)+\lambda\Big(\lvert\lvert x\rvert\rvert_1-\delta\Big) \\ &= \sup_{\lambda \geq 0} g(\lambda), \end{align*} with $$g(\lambda)=\inf_x f(x)+\lambda\Big(\lvert\lvert x\rvert\rvert_1-\delta\Big).$$ If the primal has an optimal solution $x^*$ (so there is a minum and not just an infimum), then the dual also has an optimal solution $\lambda^*$, so: $$\inf_{\lvert\lvert x \rvert\rvert_1 \leq \delta} f(x) = g(\lambda^*).$$ Therefore, the primal has the same objective value as $$\inf_x f(x)+\lambda^*\Big(\lvert\lvert x\rvert\rvert_1-\delta\Big),$$ where $\lambda^*$ is an optimal solution to the dual problem.