A minimax optimization with $\ell_p$ constraint

57 Views Asked by At

I have a minimax with general $\ell_p$ constraint optimization problem. The objective function is in the following, $$\min_{\mathbf{w} \in \mathbb{R}^d} \mathbb{E}_{(\mathbf{x}, y) \sim P}[\max_{\lVert \delta \rVert_p \leq \epsilon} 1 - y\langle \mathbf{w}, \mathbf{x + \delta}\rangle],$$ where $\mathbf{x} \in \mathbb{R}^d$ is a an instance, $y \in \{-1, +1\}$ is the cressponding label, and $P$ is the joint distribution over $\mathbf{x}$ and $y$. My question is what is the solution $\mathbf{w}^*$ and $\delta^*(\mathbf{x})$ for general $\ell_p$, and can $\mathbf{w}$ be written as some close form solution for $p \geq 1$?

For example, when $p = \infty$, the $\delta^*(x) = y\epsilon \text{sgn}(-\mathbf{w})$, but for the minimize problem $\mathbf{w}^*$ is involved with $\ell_1$ norm and I cannot find the close form solution for the $p=\infty$ case.