no. 15 · Monday 16 November 2026
Accelerating Stochastic Gradient Method Using Large Stepsize for Smooth Strongly Convex Minimization
Abstract
We study predetermined stepsize schedules for stochastic gradient methods on m-strongly convex, M-smooth objectives with conditionally unbiased gradient estimates and bounded conditional variance. We derive an exact tight analysis on every schedule with stepsizes in [0,2/(M+1)]. We then characterize the globally optimal one- and two-step schedules over all nonnegative stepsizes. Both optimal schedules depend on the ratio of the initial optimality gap to the noise level and exhibit several distinct regimes. As the influence of stochastic noise diminishes, the optimal stepsizes become larger, reflecting a balance between the benefits of faster iterate convergence and the perturbations induced by stochastic noise. These solutions motivate serial and silver composition rules with explicit performance bounds. For arbitrary horizons, we construct a schedule combining a balanced Silver prefix with constant and decreasing short steps, with the prefix length selected through explicit thresholds. Its certified upper bound never exceeds the exact optimum over all short-step schedules and is strictly smaller whenever a nonempty Silver prefix is selected. Finally, we prove global optimality of the proposed schedule on an explicit sufficient interval of the initial-error-to-variance ratio.
- comments
- 46 pages, 5 figures
- fields
- Optimization and Control