Schedule Free Optimization for Anytime Convergence

30 concepts20 papers1 proposal

When training a machine learning model, practitioners routinely face a frustrating constraint: they must decide exactly how long they plan to train before the first gradient step is even taken. Popular learning rate schedules, such as cosine decay, are explicitly tied to a pre-specified time horizon $T$. If you stop training early at $T/2$, the model performs poorly because the learning rate has not decayed enough to allow the parameters to settle. Conversely, if you decide to extend training past $T$, the learning rate flatlines or drops to zero, preventing the model from learning anything new.

To escape this constraint, a rapidly growing body of research focuses on anytime convergence (or horizon-independent optimization). The goal is to design algorithms that achieve optimal convergence rates at every single iteration of training, completely decoupling the optimization process from a fixed computational budget.

The Core Dilemma: Why Standard Decay Fails Anytime

To understand why anytime convergence is challenging, consider standard Stochastic Gradient Descent (SGD). To filter out stochastic gradient noise and guarantee convergence, the effective step size must decrease over time.

If we know the total horizon $T$ in advance, we can choose a constant step size proportional to $1/\sqrt{T}$. This works beautifully at step $T$, but provides weak guarantees at intermediate steps. If we instead try to make the algorithm horizon-independent by setting a time-varying step size proportional to $1/\sqrt{t}$ (where $t$ is the current step), we run into a fundamental mathematical bottleneck.

As formalized by Kornowski et al. (2024), achieving accelerated convergence rates at every intermediate step requires step-size sequences that can grow aggressively large. However, these large steps inherently risk massive overshooting, causing vanilla gradient descent to fail spectacularly on intermediate iterations. This trade-off exposes a deep tension between optimizing for a single terminal point and maintaining peak performance throughout the entire training trajectory.

Mechanism 1: Unifying Iterate Averaging with Momentum

The most prominent modern solution to this problem completely eliminates the traditional learning rate decay schedule. Instead of forcing the primary parameters to slow down, "schedule-free" optimization techniques maintain two distinct representations of the model: a primary iterate that moves quickly to explore the loss landscape, and a running average iterate that smoothly tracks the solution.

Traditional Schedule (e.g., Cosine Decay):
Step 0 -----------------------------> Step T (Optimal only here)

Schedule-Free / Horizon-Independent:
Step 0 ====[Optimal]====[Optimal]====[Optimal]====> (Ready to stop at any point)

As demonstrated by Defazio et al. (2024), by directly unifying iterate averaging with a modified momentum buffer, the optimizer can continuously track the Pareto frontier of loss versus training time. This allows the model to achieve state-of-the-art performance across diverse architectures—from convex problems to large-scale Transformers—without needing to know the stopping time in advance.

Building on this intuition, Pun et al. (2025) introduced adaptive, Polyak-style versions of these algorithms. By utilizing real-time loss values to dynamically adjust the step size and averaging weights, the optimizer ensures that the model remains in a theoretically optimized, deployment-ready state at every single training step. While Kasimbeg et al. (2025) note that schedule-free methods still require careful calibration of other hyperparameters like weight decay, they successfully remove the temporal dependency on a fixed training duration.

Mechanism 2: Suffix Averaging and Doubling Schemes

For non-smooth or strongly convex optimization, standard full iterate averaging suffers from a well-known logarithmic bottleneck ($\log t$), which slows down convergence. When the horizon $T$ is known, practitioners can bypass this by averaging only the final fraction of iterations (e.g., the last $T/2$ steps). But how do you perform "suffix averaging" if you do not know when the algorithm will end?

In a foundational paper, Rakhlin et al. (2012) proposed a horizon-independent doubling scheme. The algorithm divides an indefinite training run into epochs of exponentially increasing length ($1, 2, 4, 8, \dots$). At the end of each epoch, the algorithm resets its averaging buffer, effectively ensuring that the current average is always dominated by recent, highly optimized iterates. This simple meta-strategy recovers the theoretically optimal $O(1/t)$ convergence rate without requiring a predefined terminal step.

Doubling Scheme Structure:
| Epoch 1 (1 step) | Epoch 2 (2 steps) | Epoch 3 (4 steps) | Epoch 4 (8 steps) | ...
^ Reset Average    ^ Reset Average     ^ Reset Average     ^ Reset Average

To avoid the discrete jumps of epoch resets, Tao et al. (2021) developed continuous gradient and primal-dual averaging methods. By employing adaptive step-size sequences and continuous weight modulations, their approach strips away the logarithmic penalty smoothly, providing optimal last-iterate convergence rates natively.

Mechanism 3: Adaptive and Idealized Step Sizes

Another way to achieve horizon independence is to replace time-dependent clocks entirely with state-dependent feedback. If an algorithm determines its step size based on the geometry of the loss surface rather than the iteration counter, it naturally becomes agnostic to the total time horizon.

A prime example is the stochastic Polyak step size analyzed by Gower et al. (2025). Because these idealized step sizes scale dynamically with the current batch loss, the optimizer automatically takes large steps when far from the optimum and naturally scales down as it approaches convergence. This feedback loop guarantees anytime optimality: the algorithm extracts the maximum possible error reduction for the amount of computational work performed, regardless of when the user decides to terminate the run.

Generalization Across Complex Machine Learning Paradigms

The principles of horizon-independent scheduling are not restricted to standard empirical risk minimization; they have been successfully extended to highly complex, multi-loop, and constrained optimization landscapes:

  • Heavy-Tailed Noise and LLM Stability: Large language model training often suffers from extreme gradient spikes. Chezhegov et al. (2026) and Nguyen et al. (2023) developed horizon-agnostic parameterizations for Clipped SGD. By using time-varying clipping thresholds that do not depend on a fixed $T$, they guarantee stable, high-probability last-iterate convergence under heavy-tailed noise.
  • Bilevel and Minimax Problems: Tasks like hyperparameter tuning, meta-learning, and adversarial training are notoriously sensitive to scheduling. Giang-Tran et al. (2025) and Giang-Tran et al. (2026) introduced projection-free and dual dynamic smoothing frameworks for these settings. Their decreasing step-size and regularization decay sequences ensure anytime convergence without requiring a pre-specified target precision or iteration budget.
  • Reinforcement Learning and Games: In multi-agent systems and continuous control, interactions can continue indefinitely. Jin et al. (2024) applied any-time parameter scheduling to average-reward Q-learning, ensuring learning rates and discount factors remain valid regardless of execution duration. Similarly, Cai et al. (2025) provided algorithmic reductions that guarantee last-iterate convergence in games without periodic restarts, while Siska et al. (2024) utilized anytime annealing schedules to optimize continuous-space policies.
  • Composite and Constrained Optimization: For problems involving complex nonlinear constraints, Zhao et al. (2019) and Alacaoglu et al. (2024) demonstrated that single-loop algorithms can simultaneously hit theoretical lower bounds for smooth, nonsmooth, and stochastic components using step-size and penalty schedules that adapt continuously without pre-tuning.

By shifting the optimization paradigm from fixed-horizon planning to continuous, adaptive tracking, these methods provide practitioners with unprecedented flexibility. Whether managing uncertain compute budgets, training models that learn indefinitely, or avoiding the costly "black art" of schedule tuning, anytime convergence ensures that your current iterate is always your best iterate.

Key Foundational Work

An Optimal Algorithm for Stochastic Three-Composite Optimization (2019) — contributed 2 concept elements to this direction.
Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization (2012) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_horizon_independent_optimization_cc712886,
  title = {horizon-independent optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/horizon-independent-optimization/rdr_cc712886133342968d46c7df5fa2e939},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_horizon_independent_optimization_cc712886_v1,
  title = {horizon-independent optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/horizon-independent-optimization/rdr_cc712886133342968d46c7df5fa2e939/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake