claimroutineinferred_dep

Lipschitz payoff gives R-independent invariance error

Lipschitz payoff gives invariance error rs(kqt)r_s(kqt), independent of RR
gives the RR-independent invariance error
Claim·§A.2 The finite ordering transfer·inside lemLow-influence functions cannot beat opt_q(J)

Statement (paper)

Let p:Rq→Sq\mathsf p:\mathbb R^q\to\mathcal S_q be Euclidean projection and let Ψ(x1,…,xk)=P0ml(p(x1),…,p(xk))\Psi(x_1,\ldots,x_k)=P_0^{\mathrm{ml}}(\mathsf p(x_1),\ldots,\mathsf p(x_k)). Then Ψ\Psi is Lipschitz with constant at most kq\sqrt{kq}, and for each cc the invariance estimate of [GuruswamiEtAl2011OrderingCSP, Theorem 10.1], applied to Ψ\Psi with vector dimension kqkq and influence threshold kqtkqt, has error at most rs(kqt)r_s(kqt), where rs(u)=Ckqkq uλ/(18log⁡(1/α))r_s(u)=C_{kq}\sqrt{kq}\,u^{\lambda/(18\log(1/\alpha))}; in particular this error is independent of RR.

In plain English

The payoff Ψ(x1,…,xk)=P0ml(p(x1),…,p(xk))\Psi(x_1,\ldots,x_k)=P_0^{\mathrm{ml}}(\mathsf p(x_1),\ldots,\mathsf p(x_k)), with p\mathsf p the projection onto Sq\mathcal S_q, is kq\sqrt{kq}-Lipschitz. So the invariance theorem of Guruswami et al. (vector dimension kqkq, influence threshold kqtkqt) bounds the integral-versus-Gaussian error by rs(kqt)=Ckqkq (kqt)λ/(18log⁡(1/α))r_s(kqt)=C_{kq}\sqrt{kq}\,(kqt)^{\lambda/(18\log(1/\alpha))}, which does not depend on RR.

Why it's here

This applies the invariance theorem to the hypotheses checked in the two preceding claims: the common Gaussian ensemble with matching moments and atoms above α\alpha, and the variance, influence and tail bounds for the smoothed functions. Projection onto Sq\mathcal S_q makes the payoff smooth enough for the theorem. The error is then an explicit function of kqtkqt alone, which gives the rsr_s term in the parent lemma, with rs(u)→0r_s(u)\to0 as u↓0u\downarrow0 and no dependence on RR.
Classified routine:
Direct application of the invariance principle of Guruswami et al. 2011 (Theorem 10.1, ordering CSPs), with a simple Lipschitz bound because Euclidean projection onto the simplex is 1-Lipschitz and the multilinear payoff is bounded. This is a bookkeeping step that combines the two preceding claims.

Uses

claimCommon Gaussian ensemble matching local momentsclaimInvariance hypotheses hold for smoothed functions

Used by

claimGaussian side is a random q-assignment

Sources

PaperOpen
Section
§A.2 The finite ordering transfer
Page
—
Label
—
Line
appendices/finite-consequences.tex:623
Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    inferred_dep
    outline: "Lipschitz payoff gives R-independent invariance error" rests on claim-lem-ordering-rounding-2
  • info
    inferred_dep
    outline: "Lipschitz payoff gives R-independent invariance error" rests on claim-lem-ordering-rounding-3