Research collection
Gradient-Descent Dimension Gaps
An investigation of dimension dependence in the worst-case behavior of gradient descent under prescribed step schedules.
Current state
We currently have three research notes. One note demonstrates that, for every finite horizon from three steps onward, there is a full-dimensional cube of positive step schedules whose two-dimensional worst case strictly exceeds the one-dimensional one, witnessed by a common fixed planar function. It also constructs one infinite positive schedule whose every prefix of length at least three exhibits the gap. A second note certifies two kinds of robust gap around the underlying rational three-step schedule: a larger schedule-dependent interpolation neighborhood and a smaller neighborhood witnessed by one fixed planar function. A final note shows that, for an -step schedule, the unrestricted supremum of the terminal function-value gap equals its supremum in dimension , without assuming attainment. Exact-verification supplements replay the finite rational certificates.
Future plans
We continue to investigate whether and how the minimax step schedule itself depends on the dimension. The collection remains open to further results and verification supplements as the investigation develops.
Details
- Phase
- Public working collection
- Domain
- Smooth convex optimization · performance estimation · exact verification
- My role
- Author