Tightness of the intermediate regime for relatively inexact gradient descent

Let ff be a smooth convex function and consider relatively inexact gradient descent in the intermediate stepsize regime described in Theorem 1 of the source. The corresponding one-step worst-case rate is the rate established for that regime.

Intermediate-regime tightness conjecture. The intermediate regime in Theorem 1 is tight. Furthermore, the corresponding worst-case function is bivariate.

The conjecture asserts both attainability of the intermediate-regime bound and that a worst-case function requires two variables; the surrounding discussion says that no univariate function appears able to match the bound, suggesting a structural dimensional obstruction. Its resolution is not given in the supplied text.

Sources & referencesView supporting material

Primary source

Pierre Vernimmen and François Glineur, “Worst-case convergence analysis of relatively inexact gradient descent on smooth convex functions”, arXiv:2506.17145 (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.