Lower Bounds for Anytime Acceleration of Gradient Descent

What the math gives to ML

The paper turns unusually large, non-adaptive gradient steps into explicit worst-case obstructions rather than merely analyzing conventional descent steps. Its most transferable object is the quadratic residual polynomial p_n(lambda) = product_{k=1}^n (1 - eta_k lambda), together with bounds showing that an oversize step cannot be made harmless by surrounding steps unless the cumulative step budget is large. This suggests two practical adaptations: design anytime learning-rate schedules by minimizing the worst prefix polynomial over a curvature interval, and add an overshoot controller that limits each step using observed loss or gradient residuals. These ideas are most relevant to optimizer and scheduler design when the training horizon or curvature is unknown.