Suppose I have an infinite set $\mathcal{A}$. All I know about $\mathcal{A}$ is that elements of $\mathcal{A}$ have bounded $l_2$ norms. Suppose I have a constant $b$. Can I solve the following problem. (Even approximate solutions are okay)
$$\min_{x \in \mathrm{R}^d} \sup_{a \in \mathcal{A}}\left|a^Tx-b\right|^2$$
EDIT: The objective of this problem is not to find an exact solution but tell something about $||x^*||_2$. Providing an upper bound for it or similar.
EDIT: So this is a follow up. Let's assume $\mathcal{A}$ is compact. Then we can say the inner supremum is always attained at some $a^*$, so now we are left with $$\min_x (a^{*^T}x - b)^2$$, which can be solved as $x^* = (a^*a^{*^T})^\dagger ab$ where we used the pseudo inverse. Can we now say anything about $||x^*||_2$
First of all, since you seem to be interested in where the minimum occurs instead of what the minimum is, squaring makes no difference at all. Since squaring is a strictly increasing function on positive real numbers, $$\min_{x \in \Bbb R^d} \sup_{a \in \mathcal A}\left|a^Tx-b\right| = \sqrt{\min_{x \in \Bbb R^d} \sup_{a \in \mathcal A}\left|a^Tx-b\right|^2}$$ and occurs at the same $a, x$.
But $\left|a^Tx-b\right|= \pm a^Tx \pm b$ for the appropriate sign choices. If $a^Tx > b$, then increasing $a^Tx$ will increase $\left|a^Tx-b\right|$. If $a^Tx < b$, then decreasing $a^Tx$ will increase $\left|a^Tx-b\right|$. Thus the suprema of $\left|a^Tx-b\right|$ occur at extrema of $a^Tx$. But extrema of $a^Tx$ are also extrema of $a^T(mx)$ for $0 \ne m \in \Bbb R$. Letting $$a^*(x) = \arg\max_{a \in \overline{\mathcal A}}\left|a^Tx-b\right|,$$ we see that $a^*(mx) = a^*(x)$. However, for any $x$, we can choose $m = \frac b{[a^*(x)]^Tx}$ unless $[a^*(x)]^Tx = 0$. And for that choice of $m$, $$[a^*(mx)]^Tmx - b = 0$$
If $0\ne x \in \mathcal A$, then you can choose a constant $c$ such that $|x^T(cx) - b| > b$, so $|a^*(x)^Tx\ne 0$ for such $x$. This means that there are guaranteed to be $x$ with $a^*(x)^Tx - b = 0$.
If $M = \sup \{\|a\| : a \in \mathcal A\}$, then for any $x \notin \mathcal A^\perp, x_1 = \frac b{[a^*(x)]^Tx}x$ gives the minimum possible value of $0$ for $\sup_{a \in \mathcal A}\left|a^Tx_1-b\right|$. Thus $x^*$ can be $x_1$. But note that if we limit $\|x\| = 1$ while moving it towards $\mathcal A^\perp, [a^*(x)]^Tx$ approaches $0$. Thus $\|x_1\|$ can be arbitrarily large.
Thus if $\operatorname{span}\mathcal A \ne \Bbb R^d$, then $\mathcal A^\perp \ne \{0\}$, and there is no bound on the size $\|x^*\|$. I don't think it is bounded even when $\operatorname{span}\mathcal A = \Bbb R^d$, but I haven't worked that out yet.