Yes, this is true. Since there exists a 'decoder' $Q$ which gives a value (close to) $\frac{1}{2}$, the pair $(A,Q)$ are $(\ell_2, \ell_1)$-instance optimal (see this talk of Foucart for details).
Josiah Park
- 3.2k
- 13
- 28