Let $f(x) : \{-1, 1\}^n \mapsto \mathbb{R}$ be a function such that $|f(x)| \le 1$. I would like to find the minimum-degree (multivariate) polynomial $P(x)$ such that:
$$|P(x) - f(x)| \le \epsilon$$ for every $x \in S \subseteq \{-1, 1\}^n$. Is there a convex relaxation for the degree of $P$, i.e., some convex objective function that gives a minimum-degree polynomial when the optimum is attained?
I assume $\epsilon$ is given and fixed.
I think you can solve this using linear programming (LP). Set $$P(x) = \sum_{\alpha \in \mathbb{N}^n} p_{\alpha} x^\alpha,$$ where $$x^\alpha := \prod_{i = 1}^n x^\alpha_i. $$ If $\text{deg}(P) = d$, then \begin{align} \label{eqn_1} p_\alpha = 0 \quad \forall \alpha \text{ satisfying } \sum_{i=1}^n \alpha > d. \end{align} You want to find the polynomial $P$ that satisfies your condition of approximating $f$. I'd solve this by first fixing the degree of $P$ to $k = 1$. Then look for coefficients $p_{\alpha}$ that satisfy $$ f(x)-\epsilon \leq P(x) \leq \epsilon + f(x) \quad \forall x \in S \text{ and } \text{deg}(P) = k.$$ Note that for each $x \in S$, you get a linear constraint on the coefficients $p_\alpha$. The constraint $\text{deg}(P) = k$ is also linear on $p_\alpha$, since it evaluates to setting certain coefficients to $0$. If this problem does not have a solution for degree $k=1$, simply increase $k$ by $1$, and try again. Whenever you find a feasible solution/polynomial, stop the recursion. You have found your minimal degree polynomial.
This approach, specifically the LP, is rather brute force; you can probably improve it by using some ideas from polynomial interpolation. For example, if the degree $k > |S|$, then $P(x)$ can equal $f(x)$ for all $x \in S$.