In stochastic optimization, there is a long-standing tension between what theorists analyze and what practitioners actually do. Optimization theory frequently relies on iterate averaging (such as Polyak-Ruppert averaging), where the final output is the average of all parameter vectors visited during training. Averaging acts as a low-pass filter, smoothing out stochastic noise to guarantee optimal convergence rates like $O(1/T)$ for strongly convex functions.
Practitioners, however, almost universally discard this history and deploy the last iterate—the final weights of the model. Tracking a running average requires extra memory, slows down training, and fundamentally "blurs" structural properties like sparsity. For instance, in sparse regularized problems like Lasso, averaging dense intermediate steps destroys the exact zeros that proximal methods work hard to create, a limitation highlighted by Xi Chen et al. in Optimal Regularized Dual Averaging Methods for Stochastic Optimization.
Despite its practical dominance, using the last iterate historically came with a mathematical penalty: a logarithmic suboptimality gap. As shown by Ohad Shamir et al. in Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes, the last iterate of standard Stochastic Gradient Descent (SGD) on non-smooth strongly convex objectives converges at a rate of $O(\log T / T)$, which is a factor of $\log T$ slower than the minimax-optimal rate. This gap represents a real efficiency loss in large-scale machine learning, forcing a difficult trade-off between theoretical speed limits and practical deployment benefits (Yunwen Lei et al. in Optimal Stochastic and Online Learning with Individual Iterates).
Why the Last Iterate Fails: The Geometry of Non-Smoothness
To understand why this logarithmic penalty occurs, we must look at the geometry of the optimization path. In smooth optimization, gradients naturally shrink as the algorithm approaches the optimum. This self-stabilizing behavior allows the last iterate of SGD to inherently achieve optimal convergence rates without any averaging, as demonstrated by Alexander Rakhlin et al. in Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization.
Smooth Landscape:
Iterates naturally decelerate as gradients vanish → Last iterate is optimal.
Non-Smooth Landscape:
Gradients remain large near the optimum → Iterates bounce around → Last iterate is suboptimal.
In non-smooth optimization, however, subgradients do not vanish near the minimum; they remain bounded away from zero. Consequently, the error does not decrease monotonically. Instead, the optimization path continuously bounces around the optimum due to persistent variance and sharp landscape features.
If we use a standard step-size schedule (such as $\eta_t \propto 1/t$), the steps shrink too rapidly to correct for early mistakes, yet remain large enough to cause late-stage oscillations. Christopher Liaw et al. proved in Tight analyses for non-smooth stochastic gradient descent that this $\log T$ penalty is not an artifact of loose mathematical analysis—it is a real geometric property of the optimization path.
Interestingly, this penalty depends heavily on dimensionality. Tomer Koren et al. noted in Open Problem: Tight Convergence of SGD in Constant Dimension that existing lower bounds for last-iterate suboptimality require the problem's dimension to scale with the number of iterations, leaving open the possibility that low-dimensional spaces naturally escape this penalty.
Suffix Averaging: The Best of Both Worlds
If full averaging blurs the solution by including highly biased early iterates, and the last iterate is too volatile, a natural compromise is to average only the tail end of the trajectory.
Alexander Rakhlin et al. demonstrated that suffix averaging—averaging only a final fraction (e.g., the last 50%) of the iterates—completely recovers the optimal $O(1/T)$ rate. This works because it discards the distant, high-bias history while retaining enough recent iterates to cancel out the stochastic variance. Christopher Liaw et al. confirmed that some form of averaging is mathematically mandatory if one sticks to standard step-size rules.
To make this practical for streaming settings where the total number of iterations $T$ is unknown, Ohad Shamir et al. introduced polynomial-decay averaging. This scheme applies an "on-the-fly" polynomial weight to updates, heavily favoring later iterates and achieving optimality without requiring a fixed time horizon.
Modifying the Dynamics to Achieve Pure Last-Iterate Optimality
Can we eliminate averaging entirely and achieve information-theoretic optimality on the exact final iterate? Yes, but it requires changing either the step-size schedule or the underlying optimization dynamics.
Tailored Step-Size Schedules
Prateek Jain et al. resolved this challenge in Making the Last Iterate of SGD Information Theoretically Optimal (and its extended work here). They showed that the last-iterate penalty is a failure of the standard $1/t$ step-size sequence, not of SGD itself. By designing new step-size schedules that decay more gradually before dropping sharply, they altered the contraction geometry of the algorithm, forcing the final iterate to hit the information-theoretic speed limit directly without any averaging.
Momentum and Primal-Dual Tracking
Another way to stabilize the final iterate is through momentum. Wei Tao et al. proved in The Role of Momentum Parameters in the Optimal Convergence of Adaptive Polyak's Heavy-ball Methods that incorporating Polyak's Heavy-ball momentum allows the individual last iterate to achieve the optimal $O(1/\sqrt{t})$ rate, bypassing the standard SGD last-iterate slowdown of $O(\log t / \sqrt{t})$.
For strongly convex objectives, Wei Tao developed Gradient Descent Averaging (GDA) and Primal-Dual Averaging (SC-PDA) in Gradient Descent Averaging and Primal-dual Averaging for Strongly Convex Optimization. These methods maintain a coupled tracking of primal and dual variables, systematically stripping away the $\log t$ factor from the final iterate by ensuring that the gradient steps are informed by the global convergence state rather than just the local gradient.
Broader Horizons: Mirror Descent and Adaptive Stability
The quest for last-iterate optimality spans across modern optimization paradigms:
- Mirror Descent: Zijian Liu et al. extended last-iterate analysis to non-Euclidean geometries in Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods. They proved that the final iterate of Composite Stochastic Mirror Descent (CSMD) matches optimal averaging rates even when relaxing restrictive assumptions like bounded domains or strictly bounded noise.
- Clipped Gradients: In heavy-tailed noise settings, standard high-probability analyses rely on union bounds over all iterations, which artificially reintroduces a suboptimal $\log T$ penalty. Ta Duy Nguyen et al. bypassed this in Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tailed Noise using a martingale-based "whitebox" analysis, proving that clipped gradient methods achieve optimal high-probability rates on their final iterate.
However, achieving last-iterate optimality remains a delicate balancing act. As David A. R. Robin et al. cautioned in Stab-SGD: Noise-Adaptivity in Smooth Optimization with Stability Ratios, adaptive methods that rely purely on local noise metrics can sometimes degrade to a last-iterate rate of $O(T^{-1/3})$ in weakly convex landscapes. This underscores that to completely eliminate the last-iterate suboptimality gap, step-size control and trajectory dynamics must be explicitly engineered to handle the non-vanishing variance of the optimization path.
Key Foundational Work
Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes (2013) — contributed 1 concept elements to this direction.
Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization (2012) — contributed 1 concept elements to this direction.
Optimal Regularized Dual Averaging Methods for Stochastic Optimization (2012) — contributed 1 concept elements to this direction.