Overrelaxation for Faster Convergence in Iterative Solvers

26 concepts16 papers1 proposal

Many core problems in machine learning and optimization rely on iterative algorithms that repeatedly apply a contractive map or project onto a constraint set. Think of classical methods like the Expectation-Maximization (EM) algorithm, coordinate descent, or alternating minimization. In their standard formulations, these algorithms calculate an update direction and take a step size exactly equal to one ($\alpha = 1$). While mathematically clean and often guaranteed to converge stably, this conservative step size can lead to painfully slow convergence, characterized by asymptotic "zig-zagging" near the solution.

Overrelaxation is a simple yet remarkably powerful modification: instead of stopping exactly at the computed update or constraint boundary, the algorithm intentionally overshoots by choosing a step size $\alpha$ strictly between 1 and 2 (typically around 1.5 to 1.9). This article builds the geometric and algebraic intuition for why this overshooting strategy consistently accelerates convergence across a vast array of optimization frameworks.


The Geometry of Overshooting: Hyperplanes and Projections

To understand why overshooting helps, consider the problem of finding a point at the intersection of multiple linear constraints (hyperplanes). A classic approach is the Kaczmarz method, which iteratively projects the current estimate orthogonally onto one hyperplane at a time.

If the hyperplanes meet at an acute angle, standard orthogonal projections ($\alpha = 1$) create a slow, cascading zig-zag path down the narrow corridor toward the intersection. Each step is perpendicular to the constraint, meaning it makes zero progress along the constraint itself.

Standard Projection (α = 1):        Overrelaxed Projection (α > 1):
     \          /                         \          /
      \--->    /                           \-------->
       \  |   /                             \      /
        \<   /                               \    /
         \  |                                 \  /
          \/                                   \/

Now, imagine setting $\alpha > 1$. Instead of stopping on the hyperplane, the update pushes the estimate through and slightly beyond the boundary. As shown by Jesús A. De Loera et al. in A Sampling Kaczmarz-Motzkin Algorithm for Linear Feasibility, this overshooting mechanism breaks the orthogonal trap. By crossing the boundary, the next projection step is pulled much deeper into the feasible region, effectively cutting across the corner of the corridor.

This same principle underpins the accelerated projection methods developed by Alexis Thibault et al. in Overrelaxed Sinkhorn-Knopp Algorithm for Regularized Optimal Transport, where overrelaxed projections dramatically speed up optimal transport computations by bypassing the slow asymptotic crawling of standard matrix scaling.


Extrapolating Alternating Optimization and Splitting Methods

The intuition carries over directly to alternating optimization (AO) and proximal splitting methods like the Alternating Direction Method of Multipliers (ADMM). In these settings, we optimize a global objective by solving a sequence of simpler subproblems over subsets of variables.

A standard AO step updates a variable block to its exact minimum given the other blocks. However, this greedy local optimization ignores the fact that other blocks will move in subsequent steps. By introducing a relaxation parameter $\alpha > 1$, the update rule scales the contribution of the new subproblem solution against the previous iterate:

$$x^{(k+1)} = (1 - \alpha)x^{(k)} + \alpha \tilde{x}^{(k+1)}$$

where $\tilde{x}^{(k+1)}$ is the standard update. When $\alpha \in (1, 2)$, this acts as an extrapolation step. Ivan V. Oseledets et al. proved in Local convergence of alternating low-rank optimization methods with overrelaxation that when linearized around a critical point, this overrelaxed AO is mathematically equivalent to a block Successive Over-Relaxation (SOR) linear solver. This connection allows non-linear tensor and matrix decompositions to inherit the well-studied acceleration properties of linear SOR solvers.

In ADMM and augmented Lagrangian methods, this extrapolation allows for more aggressive steps toward dual feasibility. André M. H. Teixeira et al. in Optimal scaling of the ADMM algorithm for distributed quadratic programming and Euhanna Ghadimi et al. in Optimal Parameter Selection for the Alternating Direction Method of Multipliers (ADMM): Quadratic Problems demonstrated that choosing an over-relaxation constant between 1.5 and 1.8 consistently minimizes error across various network topologies.

Similarly, Hung Nien et al. leveraged this in Relaxed Linearized Algorithms for Faster X-Ray CT Image Reconstruction, showing that setting the parameter close to 2 provides a massive speedup without adding computational or memory overhead. This practical acceleration is further generalized in the unified proximal splitting frameworks analyzed by Daichi Kitahara et al. in Proximal Splitting Algorithms for Convex Optimization: A Tour of Recent Advances, with New Twists.


The Theoretical Payoff: Inverse Complexity Bounds

Why does a larger step size guarantee faster convergence theoretically? In proximal algorithms, the mathematical bounds on iteration complexity are often tied directly to the step size.

Li Shen 0005 established in An Algorithmic Framework of Variable Metric Over-Relaxed Hybrid Proximal Extra-Gradient Method that the theoretical complexity bounds are inversely proportional to the magnitude of the over-relaxed step size. By proving convergence for fixed, large over-relaxed steps, the author showed that you can directly compress the upper bound on the number of iterations required to reach a given precision, bypassing the need for expensive adaptive line searches.


Synergy with Inertia and Momentum

It is crucial to distinguish overrelaxation from inertia (or momentum, like Nesterov's acceleration or FISTA). While both techniques accelerate convergence by modifying the update trajectory, they operate on different principles:

  1. Inertia uses information from previous iterations to maintain velocity across steps.
  2. Overrelaxation scales the current step size to overshoot the immediate subproblem target.

These two forces can be combined synergistically. Ch. Dossal et al. explored this interaction in Stability of Over-Relaxations for the Forward-Backward Algorithm, Application to FISTA, using an over-relaxation parameter to interpolate between standard forward-backward updates and FISTA to study stability under perturbations.

More recently, Chunxiang Zong et al. in A Relaxed Inertial Method for Solving Monotone Inclusion Problems with Applications demonstrated that combining inertial terms with relaxation parameters yields highly robust solvers for monotone inclusion problems, leveraging both historical momentum and aggressive step sizes.


Ubiquity Across Domains: From Graphs to Latent Variables

The beauty of overrelaxation is its plug-and-play nature across diverse mathematical frameworks:

Conclusion

Overrelaxation works because it rejects the short-sightedness of exact local updates. By intentionally overshooting the immediate target, it compensates for the structural under-correction of iterative steps, flattening the zig-zag paths of projections and coordinate descents into a straight, rapid line toward global equilibrium.

Key Foundational Work

Approximate Expectation Maximization (2003) — contributed 2 concept elements to this direction.
Distributed Latent Variable Models of Lexical Co-occurrences (2005) — 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_relaxed_hyperplane_projection_63c6b1bc,
  title = {relaxed hyperplane projection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/relaxed-hyperplane-projection/rdr_63c6b1bc97a94c9da6f47252bbf5c0f4},
  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_relaxed_hyperplane_projection_63c6b1bc_v1,
  title = {relaxed hyperplane projection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/relaxed-hyperplane-projection/rdr_63c6b1bc97a94c9da6f47252bbf5c0f4/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