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

Let 0<μ<L0<\mu<L, and let a(z)a(z) and b(z)b(z) be polynomials of degree at most p1p-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.

Sources & referencesView supporting material

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.