I proved that the function $g(x)=\underset{\mu\in\mathbb{R}^n}{\mathrm{inf}}\big\{||\mu||_{\infty}^2-\frac{1}{\beta}||x-\mu||^2_2\big\}$ (with $\beta >0$) is convex. Now, I need to use it to approximate $f(x)=||x||^2_{\infty}$. More specifically, I need to show that $$\frac{\beta}{n}g(x) \leq f(x) - g(x) \leq \beta g(x).$$
I thought that maybe I could say $g(x)\leq ||\mu||_{\infty}^2-\frac{1}{\beta}||x-\mu||^2_2$ for all $\mu\in\mathbb{R}^n$ and then plug in some convenient $\mu$, but this didn't get me anywhere. I also checked that $f(x)=||x||^2_{\infty} \leq ||x||^2_2$ (didn't help much). I tried using the triangle inequality for the term $||x-\mu||^2_2$, but I don't think this helps either. I'm probably overthinking this one.