← All problems

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

1 year old · traced to

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 Vertx0−x∗Vert\backslashleq1Vert x_0-x^*Vert\backslashleq 1, the conjecture asserts: Worst-case performance conjecture. For all 0≤μg≤Lg0\leq \mu_g\leq L_g and 0≤μM≤LM0\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.

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

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.