In a famous paper of Hastie et al., the authors have been using the following two optimization problems ($P1$ and $P2$) in $\beta$ interchangeably:
$$\begin{array}{ll} \text{minimize} & \lVert \beta \rVert_1\\ \text{subject to} & \lVert X^T(y - X\beta) \rVert_{\infty} \leq \lambda\end{array} \tag{P1}$$
and
$$\begin{array}{ll} \text{minimize} & \lVert X^T(y - X\beta) \rVert_{\infty}\\ \text{subject to} & \lVert \beta \rVert_{1} \leq s\end{array} \tag{P2}$$
Can someone please justify the equivalence between the two problems ($P1$ and $P2$) and how can one obtain $s$ from $\lambda$ for given problem $P1$ and vice-versa?
A constrained optimization problem like
$\min_x f(x)$ such that $g(x)\leq k_1$
is equivalent (through proper choice of the regularization parameter $k_2$) to
$\min_x f(x) + k_2 g(x)$
So, in some sense, both of the problems you are looking at are equivalent to
$\min_\beta c_1\|X^T(y-X\beta)\|_\infty + c_2\|\beta\|_1$
for proper choice of $c_1$ and $c_2$, given that the choices of $s$ and $\lambda$ are coherent. What I mean by coherence is that the choice of $s$ or $\lambda$ dictates what constant you get for the regularizer when you convert from a contrained problem to a regularized problem. For example, if $s$ was 0 then the regularizing constant would be $\infty$.