Arjevani et al.'s lower-bound conjecture for polynomial iterations

From papers

Let q(z)q(z) be a degree-pp monic real polynomial such that q(1)=0q(1)=0. Let r(z)r(z) be any polynomial of degree p1p-1, and let 0<bc<0<bc<\ell. Then there exists ν[μ,]\nu\in[\mu,\ell] such that

ρ(q(z)νr(z))/μ1/μ+1.\rho(q(z)-\nu\cdot r(z))\geq\frac{\sqrt{\ell/\mu}-1}{\sqrt{\ell/\mu}+1}.

Arjevani et al.'s lower-bound conjecture. For every such qq, rr, and μ\mu, some ν[μ,]\nu\in[\mu,\ell] satisfies the stated spectral-radius lower bound. This conjecture concerns tight lower bounds for stationary polynomial methods, and the surrounding paper proves it; the source does not provide further status evidence in the candidate metadata.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Noah Golowich, Sarath Pattathil and Constantinos Daskalakis, “Tight last-iterate convergence rates for no-regret learning in multi-player games”, arXiv:2010.13724 (2020).

Solutions 0

No solutions have been posted yet.