Linear Convergence via Geometrically Increasing Step Sizes

17 concepts9 papers2 proposals

Standard optimization textbook wisdom dictates that as an algorithm approaches an optimal solution, it should decrease its step size. Reducing the learning rate prevents the optimizer from overshooting the minimum and ensures stable convergence.

However, a growing body of research turns this conventional wisdom on its head. In domains ranging from reinforcement learning (RL) to maximum-margin classification, researchers have found that traditional conservative step sizes cause optimization to stall, leading to slow, sub-linear convergence rates. To achieve fast, exponential (linear) convergence, the optimizer must do something counterintuitive: aggressively increase the step size over time.

To understand why this strategy works, we have to look closely at the geometry of the optimization landscapes in these problems.

The Problem of Vanishing Progress

The necessity of increasing step sizes is most apparent in policy gradient methods within reinforcement learning. Algorithms like Policy Gradient (PG) and Natural Policy Gradient (NPG) typically optimize a non-convex objective function. Historically, this led to theoretical predictions that these methods would converge slowly, at a sub-linear rate of $O(1/k)$.

The root cause of this slowness is not an inherent limitation of gradient descent, but rather a phenomenon known as softmax saturation.

When a policy is parameterized using a standard softmax function, the gradients depend heavily on the current action probabilities. As the policy improves and approaches an optimal, deterministic policy, the probability of choosing the optimal action nears $1$, while the probabilities of suboptimal actions approach $0$. In this regime, the gradient of the objective function vanishes exponentially.

Imagine driving a car toward a destination where an external force applies the brakes harder the closer you get. If you keep your foot steady on the gas pedal (a constant step size), your car will slow down to a crawl, taking an agonizingly long time to cover the final few inches. To maintain a constant speed, you must press down on the gas pedal exponentially harder as you approach the finish line.

Countering Saturation with Geometric Scaling

By exponentially increasing the step size over the course of training, we can precisely counteract the exponentially vanishing gradients.

In tabular settings, Bhandari et al. demonstrated that moving away from conservative, vanishing step sizes toward large step sizes or exact line searches allows policy gradient methods to exploit the geometric structure of the policy space, accelerating them to linear convergence. Taking this further, Khodadadian et al. showed that an adaptive, exponentially increasing step-size schedule allows first-order policy gradient methods to achieve super-linear convergence. This aggressive acceleration mimics the behavior of second-order optimization techniques (like Newton's method) by leveraging local geometry without ever explicitly computing a costly Hessian matrix.

When moving from tabular settings to function approximation, the environment's discount factor ($\gamma$) introduces additional structural challenges. As the policy improves, the effective horizon shifts, requiring larger updates to maintain steady progress.

To address this, Yuan et al. and Alfano et al. analyzed NPG with log-linear policy parametrizations. They proved that by scaling the learning rate geometrically according to the environment's discount factor, the algorithm overcomes the diminishing returns of standard gradient steps. This geometric schedule ensures that the effective step size in the policy space remains constant, unlocking an exponential rate of error reduction without requiring entropy regularization.

Standard Schedule:  [Large Steps] --------> [Small Steps]  --> Stalls due to vanishing gradients
Geometric Schedule: [Small Steps] --------> [Large Steps]  --> Maintains steady linear convergence

This mechanism is robust enough to extend to general function approximators, such as deep neural networks. Under the Approximate Mirror Policy Optimization (AMPO) framework, Alfano et al. proved that a geometrically increasing step size enables linear convergence to a global optimum even within complex, non-convex landscapes. Furthermore, Chen et al. demonstrated that combining these time-varying, exponentially increasing step sizes with Nesterov momentum allows policy gradient methods to match the fastest known rates of specialized optimization algorithms, directly neutralizing the vanishing gradient effect inherent to softmax policies.

The Broader Geometry of Margin Maximization

This geometric intuition is not unique to reinforcement learning; it emerges naturally in supervised learning and classification tasks on separable data.

When optimizing a classifier to maximize the margin between classes, the loss function's gradients begin to decay as the data points are pushed deeper into the correct side of the decision boundary. Just like the softmax policy approaching determinism, the optimizer experiences a flattening landscape.

The benefits of increasing step sizes in this context were noticed early in the history of deep learning. Examining the late stages of backpropagation, Ahmad et al. discovered that standard fixed learning rates bound the asymptotic convergence rate to a sluggish $1/t$. However, by increasing the step size linearly over time, they altered the optimization trajectory, boosting the convergence rate to $1/t^2$. This revealed that the standard speed limit was an artifact of rigid step-size selection rather than an inherent flaw in gradient descent.

Modern theoretical work confirms this across generic geometries. Wang et al. showed that employing step-size schedules proportional to the iteration count accelerates generic algorithms like Mirror Descent, transforming sub-linear bounds into quadratic convergence rates when searching for maximum-margin solutions.

Alternatively, practitioners often turn to adaptive optimizers like Adam to handle these geometric imbalances. As shown by Zhang et al., Adam's coordinate-wise scaling implicitly alters the optimization trajectory on separable data. This adaptation allows it to escape the slow logarithmic convergence rates typical of standard gradient descent, achieving polynomial-time convergence to the optimal margin.

Summary

Whether an agent is maximizing reward in an MDP or a classifier is maximizing a margin on separable data, optimization landscapes frequently flatten out near the global optimum. In these regimes, traditional constant or decaying step sizes cause the algorithm to stall.

By scaling step sizes upward—either linearly or geometrically—the optimizer aggressively expands its update magnitudes. This expansion perfectly balances the vanishing gradients, transforming slow, sub-linear crawls into fast, linear, and even super-linear convergence trajectories.

Key Foundational Work

On the Linear convergence of Natural Policy Gradient Algorithm (2021) — contributed 2 concept elements to this direction.
On the Linear Convergence of Policy Gradient Methods for Finite MDPs (2021) — contributed 2 concept elements to this direction.
Asymptotic Convergence of Backpropagation: Numerical Experiments (1989) — contributed 2 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_geometric_step_size_scheduling_257f33e4,
  title = {geometric step-size scheduling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/geometric-step-size-scheduling/rdr_257f33e4e154433899986b89e340b994},
  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_geometric_step_size_scheduling_257f33e4_v1,
  title = {geometric step-size scheduling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/geometric-step-size-scheduling/rdr_257f33e4e154433899986b89e340b994/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake