Basic g-composable schedules capture minimax-optimal gradient-norm schedules

For each positive integer nn, let hRnh\in\mathbb{R}^n be a fixed-step gradient-descent schedule, and let xnx_n be the resulting iterate. Let F1,δ\mathfrak{F}_{1,\delta} be the set of all problem instances (f,x0)(f,x_0) in which ff is 11-smooth and convex and the initialization satisfies

f(x0)f(x)δ.f(x_0)-f(x_\star)\leq\delta.

A schedule is basic if it is built from the empty schedule using the paper's composition operations, and it is gg-composable if it has the paper's gradient-norm convergence guarantee.

Basic g-composable schedule conjecture. For each nn, every minimax-optimal stepsize schedule solving

minhRn  max(f,x0)F1,δ12f(xn)2\min_{h\in\mathbb{R}^n}\;\max_{(f,x_0)\in\mathfrak{F}_{1,\delta}}\frac{1}{2}\|\nabla f(x_n)\|^2

is basic and gg-composable.

This is presented as complementary to the conjecture about OBS-F schedules and is motivated by the exact correspondence between basic ff-composable and basic gg-composable schedules. The supplied text gives no resolution status.

Sources & referencesView supporting material

Primary source

Benjamin Grimmer, Kevin Shu and Alex L. Wang, “Composing Optimized Stepsize Schedules for Gradient Descent”, arXiv:2410.16249 (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.