A Mini-Batch Counterexample to Last-Iterate Convergence in Definable Optimization

What the math gives to ML

This paper gives a concrete failure mode for mini-batch stochastic approximation that is stronger than a generic warning about noise: even convex, semialgebraic, piecewise-affine objectives can produce bounded iterates whose accumulation set is an entire flat interval rather than a single point. The mechanism is batch-dependent minimum-norm selection, which turns the updates on successive scales into lazy reflected random walks on nested dyadic lattices. For neural-network optimizers, the transferable lesson is to treat vanishing stepsize conditions such as \(\alpha_k=o(1/\log k)\) as insufficient for last-iterate stability when stochastic subgradients remain active on flat or nearly-flat regions. A practical adaptation is a convergence-safe decay or noise-damping guard that enforces square-summable effective update magnitudes, while measuring whether late iterates continue to explore a low-loss region.