# Breaking a Logarithmic Barrier in the Stopping Time Convergence Rate of Stochastic First-order Methods

arXiv: https://arxiv.org/abs/2506.23335 · HTML: https://mlsanity.com/paper/2506.23335/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jun 2025.

## Built on by (most cited first, 1 of 1)

- [The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives](https://mlsanity.com/paper/2609.08537/) (2026)

## Abstract (arXiv)

This work provides a novel convergence analysis for stochastic optimization in terms of stopping times, addressing the practical reality that algorithms are often terminated adaptively based on observed progress. Unlike prior approaches, our analysis: 1. Directly characterizes convergence in terms of stopping times adapted to the underlying stochastic process. 2. Breaks a logarithmic barrier in existing results. Key to our results is the development of a lemma to control the large deviation property of almost super-martingales. This lemma might be of broader interest.