Dual vector formulation of the general adversary bound

For $A=J-F$, minimize $t$ over real symmetric blocks $Z_i=\left[\begin{array}{cc}{X}_i& W_i\\ W_i^T& Y_i\end{array}\right]⪰0$ subject to ${\sum }_i{\mathrm{\Delta }}_i\circ W_i=A$, ${\sum }_i{X}_i(xx)\le t$, and ${\sum }_i{Y}_i(yy)\le t$ for every input. By [F5,F6], each $Z_i$ is a Gram matrix of real vectors $u_{x,i},v_{y,i}$ with $W_i(x,y)=⟨u_{x,i}\mathrm{\mid }{v}_{y,i}{⟩}_D$ and the diagonal entries equal to their squared norms. Conversely, realify any complex feasible families by $u\mapsto (\mathrm{Re}u,\mathrm{Im}u)$ and $v\mapsto (\mathrm{Re}v,\mathrm{Im}v)$; norms are preserved and each real dot product is $\mathrm{Re}⟨u\mathrm{\mid }v{⟩}_D$. Since each target entry $A_{xy}$ is real, taking real parts preserves every constraint. Thus the real SDP has the filtered factorization value in [F12].

Add nonnegative scalar slacks $s_x=t-{\sum }_i{X}_i(xx)$ and $r_y=t-{\sum }_i{Y}_i(yy)$, and include $t\ge 0$, which is already forced by the PSD constraints. The equalities are $t-{\sum }_i{X}_i(xx)-s_x=0$, $t-{\sum }_i{Y}_i(yy)-r_y=0$, and ${\sum }_i{\mathrm{\Delta }}_i\circ W_i=A$. For unrestricted equality multipliers $p_x,q_y,\mathrm{\Lambda }$, the Lagrangian for minimizing $t$ is $L=t-{\sum }_x{p}_x(t-{\sum }_i{X}_i(xx)-s_x)-{\sum }_y{q}_y(t-{\sum }_i{Y}_i(yy)-r_y)+⟨\mathrm{\Lambda },A-{\sum }_i{\mathrm{\Delta }}_i\circ W_i{⟩}_F$. Its infimum over nonnegative scalar variables is finite only if $p_x,q_y\ge 0$ and ${\sum }_x{p}_x+{\sum }_y{q}_y\le 1$. The coefficient of $Z_i$ is $⟨H_i,Z_i{⟩}_F$, where $\mathrm{Diag}(p)$ is the diagonal matrix with entries $p_x$, similarly for $q$, and $H_i=\left[\begin{array}{cc}\mathrm{Diag}(p)& -({\mathrm{\Delta }}_i\circ \mathrm{\Lambda })\mathrm{/}2\\ -({\mathrm{\Delta }}_i\circ \mathrm{\Lambda }{)}^T\mathrm{/}2& \mathrm{Diag}(q)\end{array}\right]$. The factor $1\mathrm{/}2$ accounts for the two off-diagonal blocks in the Frobenius pairing [F3]. The infimum over $Z_i⪰0$ is finite exactly when $H_i⪰0$: a negative quadratic direction gives an unbounded rank-one ray, while PSD matrices pair nonnegatively. Hence the dual maximizes $⟨A,\mathrm{\Lambda }{⟩}_F$ subject to $p,q\ge 0$, $\sum p+\sum q\le 1$, and $H_i⪰0$ for each $i$.

The primal is strictly feasible: assign each opposite-output entry of $A$ symmetrically to its first differing coordinate, obtaining $W_i$ with ${\sum }_i{\mathrm{\Delta }}_i\circ W_i=A$. Choose ${\lambda }_i>\mathrm{\parallel }{W}_i\mathrm{\parallel }$ and set $X_i=Y_i={\lambda }_{i}I$; Cauchy--Schwarz [F10,F11] gives $2\mathrm{\mid }{a}^T{W}_{i}b\mathrm{\mid }\le \mathrm{\parallel }{W}_i\mathrm{\parallel }(\mathrm{\parallel }a{\mathrm{\parallel }}^2+\mathrm{\parallel }b{\mathrm{\parallel }}^2)$, so each $Z_i$ is positive definite. Choose $t>0$ large enough that every slack $s_x,r_y$ is positive. The dual in step 2.1 is strictly feasible at $p_x=q_y=1\mathrm{/}(4\mathrm{\mid }D\mathrm{\mid })$ and $\mathrm{\Lambda }=0$: every $H_i$ is positive definite and the scalar slack $1-\sum p-\sum q=1\mathrm{/}2$ is positive. The primal infimum is finite and nonnegative. For any primal-feasible $(Z_i,s,r,t)$ and dual-feasible $(p,q,\mathrm{\Lambda })$, the cross constraint gives $⟨A,\mathrm{\Lambda }{⟩}_F={\sum }_i⟨{\mathrm{\Delta }}_i\circ \mathrm{\Lambda },W_i{⟩}_F$, while the block constraints give $\mathrm{tr}(H_i{Z}_i)={\sum }_x{p}_x{X}_i(xx)+{\sum }_y{q}_y{Y}_i(yy)-⟨{\mathrm{\Delta }}_i\circ \mathrm{\Lambda },W_i{⟩}_F\ge 0$. Summing and using ${\sum }_i{X}_i(xx)\le t$, ${\sum }_i{Y}_i(yy)\le t$, $p,q\ge 0$, ${\sum }_x{p}_x+{\sum }_y{q}_y\le 1$, and $t\ge 0$ yields $⟨A,\mathrm{\Lambda }{⟩}_F\le ({\sum }_x{p}_x+{\sum }_y{q}_y)t\le t$. Since a primal feasible point with finite $t$ exists, this proves the derived dual supremum is finite; $p=q=\mathrm{\Lambda }=0$ is also dual feasible. Arrange all $Z_i,s,r,t$ as diagonal blocks of one PSD matrix and constrain off-block entries to zero; the strict point makes this matrix positive definite. Maximizing $-t$ is the standard primal in [F3], with standard dual objective $-⟨A,\mathrm{\Lambda }{⟩}_F$ and the block constraints from step 2.1. Both sides are strictly feasible and have finite values, so [F3] gives equal attained optima; reversing signs yields an attained primal minimum and dual maximum with common value.

Let $(p,q,\mathrm{\Lambda })$ be an attained dual maximizer from step 3.1. If $\sum p+\sum q<1$, add the deficit to one $p_x$; this adds a nonnegative diagonal matrix to each $H_i$, preserving feasibility and objective, and normalizes $\sum p+\sum q=1$. On positive supports define $M_{xy}={\mathrm{\Lambda }}_{xy}\mathrm{/}(2\sqrt{p_x{q}_y})$. If $p_x=0$, PSD of each $H_i$ forces its off-diagonal row to vanish: for every other coordinate vector $e_j$, $0\le (e_x+s{e}_j{)}^T{H}_i(e_x+s{e}_j)$ for all real $s$, so the linear coefficient is zero. The same holds for a zero $q_y$. Thus ${\mathrm{\Lambda }}_{xy}=0$ for distinct $x,y$ whenever either weight is zero, because distinct Boolean inputs differ in some coordinate; diagonal entries do not affect the objective since $A_{xx}=0$. Set zero-support rows and columns of $M$ to zero. On positive supports, congruence by $\mathrm{Diag}(p{)}^{-1\mathrm{/}2}\oplus \mathrm{Diag}(q{)}^{-1\mathrm{/}2}$ turns $H_i⪰0$ into $\left[\begin{array}{cc}I& -K_i\\ -K_i^T& I\end{array}\right]⪰0$, with $K_i={\mathrm{\Delta }}_i\circ M$. This block matrix is PSD exactly when $\mathrm{\parallel }{K}_i\mathrm{\parallel }\le 1$: if the norm is at most one, its quadratic form $\mathrm{\parallel }u{\mathrm{\parallel }}^2+\mathrm{\parallel }v{\mathrm{\parallel }}^2-2u^T{K}_{i}v$ is nonnegative by [F10,F11] and $2ab\le a^2+b^2$; conversely, substituting $(su,v)$ for every real $s$ forces $\mathrm{\mid }{u}^T{K}_{i}v\mathrm{\mid }\le \mathrm{\parallel }u\mathrm{\parallel }\mathrm{\parallel }v\mathrm{\parallel }$, and choosing $u=K_{i}v\mathrm{/}\mathrm{\parallel }{K}_{i}v\mathrm{\parallel }$ when $K_{i}v\mathrm{\ne }0$ gives $\mathrm{\parallel }{K}_{i}v\mathrm{\parallel }\le \mathrm{\parallel }v\mathrm{\parallel }$. If a support is empty, the zero-support argument gives $M=0$, which is feasible. The objective is $a^T(A\circ M)b$ for $a_x=\sqrt{2p_x}$ and $b_y=\sqrt{2q_y}$; $\mathrm{\parallel }a{\mathrm{\parallel }}^2+\mathrm{\parallel }b{\mathrm{\parallel }}^2=2$, hence $\mathrm{\parallel }a\mathrm{\parallel }\mathrm{\parallel }b\mathrm{\parallel }\le 1$ and [F10,F11] give $⟨A,\mathrm{\Lambda }{⟩}_F\le \mathrm{\parallel }A\circ M\mathrm{\parallel }$. Conversely, for any feasible $M$, take real unit left/right singular vectors $a,b$ of $A\circ M$ attaining its norm by [F8,F9]; if that matrix is zero, use arbitrary unit vectors in the nonempty output classes. Set $p_x=a_x^2\mathrm{/}2$, $q_y=b_y^2\mathrm{/}2$, and ${\mathrm{\Lambda }}_{xy}=a_x{b}_y{M}_{xy}$. The weights sum to one. On positive supports, diagonal sign congruence reduces the dual constraints to the norm condition just proved; zero coordinates have zero off-diagonal blocks. The dual objective is $\mathrm{\parallel }A\circ M\mathrm{\parallel }$. Therefore the dual optimum equals the supremum of $\mathrm{\parallel }A\circ M\mathrm{\parallel }$ over ${\max }_i\mathrm{\parallel }{\mathrm{\Delta }}_i\circ M\mathrm{\parallel }\le 1$.

Write $D_b=\{x\in D:f(x)=b\}$ and partition coordinates as $D_0\bigsqcup D_1$; both classes are nonempty. For $M$ with cross-blocks $B$ and $C$, $A\circ M$ sends $(\xi ,\eta )\in {\mathbb{R}}^{D_0}\oplus {\mathbb{R}}^{D_1}$ to $(B\eta ,C\xi )$, so $\mathrm{\parallel }A\circ M\mathrm{\parallel }=\max \{\mathrm{\parallel }B\mathrm{\parallel },\mathrm{\parallel }C\mathrm{\parallel }\}$: the upper bound follows from $\mathrm{\parallel }B\eta {\mathrm{\parallel }}^2+\mathrm{\parallel }C\xi {\mathrm{\parallel }}^2\le \max \{\mathrm{\parallel }B\mathrm{\parallel },\mathrm{\parallel }C\mathrm{\parallel }{\}}^2(\mathrm{\parallel }\xi {\mathrm{\parallel }}^2+\mathrm{\parallel }\eta {\mathrm{\parallel }}^2)$, and the reverse follows by restricting to one summand and using [F8,F9] to attain each block norm. Each $B_i=B\circ {\mathrm{\Delta }}_i$ and $C_i=C\circ {\mathrm{\Delta }}_i$ is a coordinate restriction of $M\circ {\mathrm{\Delta }}_i$, hence has norm at most one by [F10]. If $B$ is larger, $\mathrm{\Gamma }=\left[\begin{array}{cc}0& B\\ B^T& 0\end{array}\right]$ is symmetric, vanishes on equal-output pairs, has norm $\mathrm{\parallel }B\mathrm{\parallel }$, and $\mathrm{\Gamma }\circ {\mathrm{\Delta }}_i=\left[\begin{array}{cc}0& B_i\\ B_i^T& 0\end{array}\right]$ has norm $\mathrm{\parallel }{B}_i\mathrm{\parallel }\le 1$; these norm identities follow by the same block calculation and $\mathrm{\parallel }{B}_i^T\mathrm{\parallel }=\mathrm{\parallel }{B}_i\mathrm{\parallel }$ from [F8,F9]. If $C$ is larger, use $\mathrm{\Gamma }=\left[\begin{array}{cc}0& C^T\\ C& 0\end{array}\right]$. If both blocks vanish the objective is zero. For each nonzero constructed $\mathrm{\Gamma }$, its denominator is positive by [F1] and at most one, so its adversary ratio is at least $\mathrm{\parallel }\mathrm{\Gamma }\mathrm{\parallel }$; hence every feasible $M$ has objective at most ${\mathrm{Adv}}^{\pm }(f)$. Conversely, [F1] supplies an admissible maximizing $\mathrm{\Gamma }$ with $d={\max }_i\mathrm{\parallel }\mathrm{\Gamma }\circ {\mathrm{\Delta }}_i\mathrm{\parallel }>0$; $M=\mathrm{\Gamma }\mathrm{/}d$ is feasible and $\mathrm{\parallel }A\circ M\mathrm{\parallel }=\mathrm{\parallel }\mathrm{\Gamma }\mathrm{\parallel }\mathrm{/}d={\mathrm{Adv}}^{\pm }(f)$. Thus the supremum in step 4.1 is an attained maximum equal to ${\mathrm{Adv}}^{\pm }(f)$.

By [F3], the primal optimum is attained with real families $u,v$. Define $w_{x,i}=u_{x,i}$ on $D_0$ and $w_{x,i}=v_{x,i}$ on $D_1$. For an opposite-output pair, the primal cross constraint gives one in the $0$-to-$1$ order, and its transpose gives one in reverse order. Their class costs satisfy $C_0\le {\max }_x{\sum }_i\mathrm{\parallel }{u}_{x,i}{\mathrm{\parallel }}^2$ and $C_1\le {\max }_y{\sum }_i\mathrm{\parallel }{v}_{y,i}{\mathrm{\parallel }}^2$. To impose equal-output zero constraints, tensor each $w_{x,i}$ with $\mathrm{\mid }{x}_i\oplus f(x)⟩$. When $x_i\mathrm{\ne }{y}_i$, these labels agree if $f(x)\mathrm{\ne }f(y)$ and are orthogonal if $f(x)=f(y)$; hence cross-output sums stay one and equal-output sums vanish, while norms are unchanged. The label Gram product is PSD by [F7], in agreement with these explicit tensor vectors.

Conversely, every single-family certificate $w$ gives a primal factorization by $u_{x,i}=w_{x,i}$ and $v_{y,i}=w_{y,i}$, with cost $\max \{C_0,C_1\}$. Step 6.1 yields a certificate of cost at most the attained primal value; this converse shows its cost cannot be smaller. Thus the certificate minimum is attained and equals the primal value and ${\mathrm{Adv}}^{\pm }(f)$ by step 5.1. Both $C_0,C_1$ are positive because an opposite-output constraint equals one. Rescaling $w_x$ by $\alpha >0$ on $D_0$ and ${\alpha }^{-1}$ on $D_1$ preserves cross-output constraints, multiplies the two costs by ${\alpha }^2$ and ${\alpha }^{-2}$, and preserves equal-output zero constraints; choosing $\alpha =(C_1\mathrm{/}{C}_0{)}^{1\mathrm{/}4}$ balances the costs.