Polynomial spectral-radius lower-bound conjecture for p-CLI methods

About 12 years old · traced to

Let 0<μ<L0<\mu<L, and let a(z)a(z) and b(z)b(z) be polynomials of degree at most p−1p-1 satisfying b(1)=1b(1)=1. For a polynomial, let ρ\rho denote the maximum modulus of its roots. Write

Q=Lμ.Q=\frac{L}{\mu}.

Polynomial lower-bound conjecture. There exists η∈[μ,L]\eta\in[\mu,L] such that

ρ(zp−(ηa(z)+b(z)))≥L/μ−1L/μ+1.\rho\bigl(z^p-(\eta a(z)+b(z))\bigr)\geq\frac{\sqrt{L/\mu}-1}{\sqrt{L/\mu}+1}.

This is presented as a reduction of the algorithmic conjecture to a question about polynomials, so it expresses the same proposed obstruction in purely analytic terms. The source gives no evidence that it has been resolved.

References

Primary source

Yossi Arjevani, “On Lower and Upper Bounds in Smooth Strongly Convex Optimization - A Unified Approach via Linear Iterative Methods”, arXiv:1410.6387 (2014).

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.