Tightness of the intermediate regime for relatively inexact gradient descent
Tightness of the intermediate regime for relatively inexact gradient descent
Let 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.