The Search Then Converge Paradigm for Stochastic Optimization

This direction is split into other directions: premature convergence (learning rate decay threshold). Its last version stays readable and citable here.

Version 1 of 177 papers113 conceptsfrozen 2026-10-04

In the early days of neural network research, Christian Darken and John E. Moody identified a fundamental tension in stochastic gradient descent (SGD). To reach the exact bottom of a minimum, the learning rate must eventually vanish to zero. However, if the learning rate decays too quickly, the optimizer "freezes"—it runs out of kinetic energy and stops moving before it ever reaches the global neighborhood.

This observation led to the Search-Then-Converge (STC) framework. Instead of decaying the learning rate from the first iteration, STC suggests a two-phase approach: a "search" phase where the learning rate remains high and constant to explore the loss landscape, followed by a "converge" phase where it decays to settle into the optimum.

The Geometry of Freezing

To understand why optimization fails, we must look at the cumulative distance an optimizer can travel. If a learning rate $\eta_t$ decays faster than $1/t$, the infinite sum of steps $\sum_{t=1}^{\infty} \eta_t$ may converge to a finite value. Mathematically, this means the model is physically incapable of moving further than a certain distance from its starting point, regardless of how many iterations you run.

Arnulf Jentzen and Philippe von Wurstemberger proved that when decay is too aggressive, the algorithm reaches a "frozen state" with a permanent residual error. This isn't just a theoretical curiosity; Per Kristian Lehre and Carsten Witt demonstrated that even popular metaheuristics like Particle Swarm Optimization can "run out of gas" before reaching the target if their update velocity decays exponentially.

Finding the Needle in the Haystack

Modern deep learning has added a new layer to this problem: the "Wide-minima Density Hypothesis." Research suggests that "flat" or "wide" minima generalize better than sharp ones, but these robust regions are statistically rare—a "needle in a haystack."

Nikhil Iyer and colleagues argue that standard schedules, which reduce the learning rate as soon as training loss plateaus, trap models in the first narrow minimum they encounter. They propose the Knee learning rate schedule, which maintains a high "explore" phase long after the loss has flattened. By refusing to "cool" the optimization process prematurely, the optimizer can bounce out of sharp valleys and continue searching until it falls into a wider, more stable region.

This intuition is echoed in the work of Bo Yang Hsueh and I-Chen Wu, who introduced Hyperbolic-Tangent Decay (HTD). By using an S-shaped curve, HTD keeps the learning rate high for an extended period before a rapid final collapse, allowing for more effective landscape exploration than traditional smooth decay functions.

When Decay Wastes Data

The conflict between decay and exploration becomes particularly acute in complex training setups like curriculum learning or decentralized optimization.

In Curriculum-Based LLM Pretraining, models are shown easy data first and high-quality data last. Kairong Luo and Zhenbo Sun found that standard decay schedules are fundamentally incompatible with this approach. By the time the model reaches the most valuable, high-quality data at the end of the curriculum, the learning rate has often decayed to near-zero. The model "wastes" its best data because it no longer has the step size necessary to integrate the new information.

Similarly, in Federated and Decentralized Learning, Riccardo Zaccone and Sai Praneeth Karimireddy showed that aggressive decay can cause algorithms to stagnate before they can overcome the bias introduced by heterogeneous data across different clients. If the learning rate drops too fast, the system "freezes" the initial bias into the final model.

Practical Paths to Convergence

If immediate decay is dangerous, what is the alternative? Several researchers have converged on a few robust strategies:

  1. The Search Phase Duration: Farhana Ferdousi Liza and Marek Grzes suggest that for complex tasks like language modeling, the "search" phase (constant high LR) should last for a significant portion of training—often one-third to two-thirds of the total epochs.
  2. Budgeted Linear Decay: Mengtian Li and Deva Ramanan argue that if you have a fixed compute budget, the most robust strategy is to decay the learning rate linearly to zero exactly at the end of that budget. This prevents the "premature cooling" that plagues adaptive optimizers.
  3. Polynomial Decay: For coupled problems like Actor-Critic reinforcement learning, Navdeep Kumar and Kfir Y. Levy found that a polynomial decay of $O(k^{-2/3})$ provides a superior balance between bias and variance compared to the standard square-root decay.

Ultimately, the goal of a learning rate schedule is to manage the transition from a global search to a local settlement. As Hideaki Iiduka has repeatedly demonstrated, while diminishing rates are a mathematical necessity for convergence proofs, the practical success of a model depends on ensuring the step size remains "appropriate" long enough to reach a high-quality solution.

Papers in this version

Showing 60 of 77 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_the_search_then_converge_paradigm_for_st_282e3079,
  title = {The Search Then Converge Paradigm for Stochastic Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-search-then-converge-paradigm-for-stochastic-optimization/rdr_282e3079ad23473f8efbda9a53674580},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_the_search_then_converge_paradigm_for_st_282e3079_v1,
  title = {The Search Then Converge Paradigm for Stochastic Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-search-then-converge-paradigm-for-stochastic-optimization/rdr_282e3079ad23473f8efbda9a53674580/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}