Let $\beta\in\mathbb{R}^{d}$, we consider the function $\ell:\mathbb{R}^{d}\times \mathbb{R}\rightarrow \mathbb{R}$ given by $$\ell(x,y):=(y-\beta^{t}x)^{2}.$$
Calculate $$k:=\sup\left\{\left\|\theta\right\|_{*} \: |\: \ell^{*}(\theta)<\infty\right\}$$ where $\theta\in\mathbb{R}^{d}\times \mathbb{R}=\mathbb{R}^{d+1}$, $\left\|\theta\right\|_{*} =\sup_{\xi\in \mathbb{R}^{d+1}}\left\langle \theta,\xi\right\rangle $ and $$\ell^{*}(\theta)=\sup_{\xi\in \mathbb{R}^{d+1}}\left[\left\langle \theta,\xi\right\rangle - \ell(\xi)\right] .$$ (we recall $\left\langle \theta,\xi\right\rangle =\theta^{t}\xi$)
Remark: In my attempt I got $ k = 0 $, but I do not trust my answer since within the context in which this question is found this answer is not realistic.
Let's define $\theta\triangleq(\theta_x,\theta_y)$, so that $$\ell^*(\theta) = \sup_{x,y} x^T\theta_x + y\theta_y - (y-\beta^Tx)^2$$ The optimality conditions are $$\theta_x + 2(y-\beta^Tx)\beta = 0, \quad \theta_y - 2(y-\beta^Tx) = 0.$$ Substituting the second equation into the first, we have $$\theta_x + \theta_y \beta = 0$$ Now this might seem like a dead end, because it doesn't involve $x$ and $y$. But what it tells is is that if this relation is not satisfied, it is not possible to meet the optimality conditions for any $x$, $y$, so the supremum is indeed unbounded. On the other hand, if it is satisfied, then $$\ell^*(\theta) = \sup_{x,y} (y-\beta^Tx)\theta_y - (y-\beta^Tx)^2$$ and the minimum value of that can be easily verified to be $\theta_y^2/4$. So we have $$\ell^*(\theta) = \begin{cases} \theta_y^2/4 & \theta_x + \beta\theta_y = 0 \\ +\infty & \text{otherwise} \end{cases}$$ and indeed, $\theta$ can be arbitrarily large.