Anytime Last Iterates in Fixed Dimension

Preprint Jul 2026

Sharp Dimension Dependence for the Last Iterate of the SubGradient Method

We study the last iterate of the projected subGradient Method (sGM) for convex Lipschitz objectives defined on $\mathbb{R}^d$. We prove that, for a finite horizon $n$ and a constant stepsize $\eta=\Theta(1/\sqrt n)$, the last iterate achieves an optimization error of order $d/\sqrt n$, showing that the extra $\log n$ f...

Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni et al. · 1 citation · ⚡1

Preprint Aug 2026

A lower bound for stepsize-based acceleration of gradient descent

This work presents a new lower bound of $\Omega(T^{-1.9319})$ for the last-iterate convergence rate of gradient descent with predetermined nonnegative stepsize schedules, and provides rigorous evidence that stepsize schedules alone cannot accelerate plain GD to the optimal $O(T^{-2})$ convergence rate.

Jian-Hao Ma, Yu-Xin Chen · 8 citations · ⚡2

Jul 2026

Data-Dependent Regret and Polyak Corrections for Constrained Online Convex Optimization

AdaOGD-PFS is proposed, an adaptive-step-size method that achieves O(sqrt(G_T) regret with per-round feasibility while preserving per-round feasibility and identifies a nonnegative Polyak correction P_T that enters the regret bound with a negative sign.

Wen-Tao Zhang · Trans. Mach. Learn. Res. · 0 citations

Optimal-Dimension U-Calibration by Bayesian Bootstrap

It is shown that the classical Bayesian bootstrap closes this gap in U-calibration, which asks one online probability fore-caster to have low regret for every bounded proper loss, including losses unknown when the forecasts are made.

Pahan Dewasurendra · 0 citations

Open access Aug 2026

Polynomial-Time Algorithm for Optimal Stopping with Fixed Accuracy

This work develops a novel expansion representation for the OS value and proves that truncating this expansion yields a simulation-based algorithm that implements an optimal stopping policy with computational complexity scaling polynomially in the time horizon and the underlying dimension.

Yi-Lun Chen, David A. Goldberg · Stochastic Systems · 0 citations

Preprint Aug 2026

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

We give a counterexample to the convergence conjecture in Remark 12 of [Bolte&Pauwels, 2021] for mini-batch stochastic approximation with definable potentials. The construction uses two convex piecewise-affine, hence semialgebraic, summands on $\mathbb{R}$. We choose a deterministic nonincreasing block stepsize sequenc...

Weiwei Kong · 0 citations