Trajectory-Adaptive Stopping Rules for SGD under Strong Convexity

Stochastic gradient descent (SGD) is typically analyzed at a deterministic horizon, even though practical stopping decisions are made adaptively by monitoring the evolving trajectory. This mismatch creates a fundamental certification problem: fixed-time guarantees do not generally remain valid at data-dependent stopping times, while deterministic horizons derived from worst-case bounds can be highly conservative. We address this problem for strongly convex SGD by constructing fully observable, trajectory-adaptive upper confidence sequences for the squared distance to the optimum and the suboptimality of a weighted average. Our approach treats the evolving SGD trajectory as a sequential experiment whose observations provide evidence about the unknown optimization error. The main ingredient is a time-uniform empirical-Bernstein inequality for processes with time-varying conditional means and predictable ranges that may grow without bound. Numerical experiments show that the resulting stopping rules can require several orders of magnitude fewer iterations than natural deterministic horizons.