Worst-case performance conjecture for gradient descent on linear-operator compositions

From papers

Let gg be a mugmu_g-strongly convex and LgL_g-smooth function, and let MM belong to the class of linear operators with singular values in [muM,LM][mu_M,L_M]. Write Cmug,LgmuM,LM\mathcal{C}_{mu_g,L_g}^{mu_M,L_M} for the corresponding class of functions F(x)=g(Mx)F(x)=g(Mx), and let Dmug,LgmuM,LM\mathcal{D}_{mu_g,L_g}^{mu_M,L_M} denote the analogous class with symmetric MM. For the worst-case performance w(F)w(\mathcal{F}) of the gradient method on a class F\mathcal{F}, measured by the criterion F(xN)F(x)F(x_N)-F(x^*) under Vertx0xVert\backslashleq1Vert x_0-x^*Vert\backslashleq 1, the conjecture asserts: Worst-case performance conjecture. For all 0μgLg0\leq \mu_g\leq L_g and 0μMLM0\leq \mu_M\leq L_M,

w(Cμg,LgμM,LM)=w(Dμg,LgμM,LM).w(\mathcal{C}_{\mu_g,L_g}^{\mu_M,L_M})=w(\mathcal{D}_{\mu_g,L_g}^{\mu_M,L_M}).

Here w(Dμg,LgμM,LM)w(\mathcal{D}_{\mu_g,L_g}^{\mu_M,L_M}) is the expression given in the cited prior conjecture. This conjecture says that the symmetry of the linear operator does not affect the worst-case performance of gradient descent, extending the previously studied zero-minimal-singular-value case; the supplied text does not establish its resolution.

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

Nizar Bousselmi, Zhicheng Deng, Jie Lu, Francois Glineur and Julien M. Hendrickx, “On the Convex Interpolation for Linear Operators”, arXiv:2511.16360 (2025).

Solutions 0

No solutions have been posted yet.