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

At least 5 years old · documented by

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 p−1p-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.

References

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).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.