Input-distribution certificates upper-bound the nonnegative adversary value

Fix distributions $p_x(i)\ge 0$ with ${\sum }_i{p}_x(i)=1$ for each x, and let $\eta ={\min }_{f(x)\mathrm{\ne }f(y)}{\sum }_{i:x_i\mathrm{\ne }{y}_i}\sqrt{p_x(i)p_y(i)}>0$. Let $\mathrm{\Gamma }\ge 0$ be an admissible nonzero matrix. By [F4], choose a real orthonormal eigenbasis of the symmetric matrix $\mathrm{\Gamma }$; thus $\mathrm{\parallel }\mathrm{\Gamma }\mathrm{\parallel }={\max }_j\mathrm{\mid }{\lambda }_j\mathrm{\mid }={\max }_{\mathrm{\parallel }z\mathrm{\parallel }=1}\mathrm{\mid }{z}^{\mathsf{T}}\mathrm{\Gamma }z\mathrm{\mid }$ and ${\lambda }_{\max }(\mathrm{\Gamma })={\max }_{\mathrm{\parallel }z\mathrm{\parallel }=1}{z}^{\mathsf{T}}\mathrm{\Gamma }z$. For every real unit z, entrywise nonnegativity gives $\mathrm{\mid }{z}^{\mathsf{T}}\mathrm{\Gamma }z\mathrm{\mid }\le \mathrm{\mid }z{\mathrm{\mid }}^{\mathsf{T}}\mathrm{\Gamma }\mathrm{\mid }z\mathrm{\mid }\le {\lambda }_{\max }(\mathrm{\Gamma })$. Since $\mathrm{\Gamma }$ is nonzero admissible, it has a positive off-diagonal entry, so a vector supported equally on that pair has positive Rayleigh quotient and ${\lambda }_{\max }(\mathrm{\Gamma })>0$. Hence $\mathrm{\parallel }\mathrm{\Gamma }\mathrm{\parallel }={\lambda }_{\max }(\mathrm{\Gamma })$. If v is a unit top eigenvector, then $\mathrm{\mid }v\mathrm{\mid }$ is a nonnegative unit vector with $\mathrm{\mid }v{\mathrm{\mid }}^{\mathsf{T}}\mathrm{\Gamma }\mathrm{\mid }v\mathrm{\mid }\ge v^{\mathsf{T}}\mathrm{\Gamma }v={\lambda }_{\max }(\mathrm{\Gamma })$, so equality holds and $\delta :=\mathrm{\mid }v\mathrm{\mid }$ is also a top eigenvector.

For every cross-output pair the mismatch overlap is at least η; all coefficients Γ_xy δ_xδ_y are nonnegative. Therefore η||Γ||≤Σ_{x,y}Γ_xyδ_xδ_yΣ_iΔ_i(x,y)√(p_x(i)p_y(i)) =Σ_i s_i^T(Γ∘Δ_i)s_i, where (s_i)_x=δ_x√p_x(i).

By Cauchy–Schwarz [F5] and the induced norm definition [F3], each summand is at most ||Γ∘Δ_i||·||s_i||². Summing gives at most max_i||Γ∘Δ_i||·Σ_iΣ_xδ_x²p_x(i)=max_i||Γ∘Δ_i||, because every p_x is a probability distribution and ||δ||=1. Divide by η and the positive denominator to obtain the claimed upper certificate for Γ; maximizing over Γ proves Adv(f)≤1/η.