Step Size Seeders

Step Size Seeders#

Introduction#

In Pyralysis, step size seeders (StepSizeSeeder) estimate an initial step size \(\alpha_k\) before a Line Searchers refines it. Seeders use gradient history, function values, or proximal residuals to provide a good starting point, which reduces backtracking iterations and improves convergence.

Optimization paths for small, large, and seeded steps on quadratic level curves — **Why seeders matter** — illustrative paths on an ill-conditioned quadratic: (a) step too small (slow zig-zag); (b) step too large (oscillation); (c) seeded / near-optimal steps. Full discussion: Step size geometry: too short, too long, and why seeders help in Line Searchers.#

**Step-size seeder hierarchy** (`StepSizeSeeder`, Barzilai–Borwein family, and interpolation seeders).#

Note

Seeders do not replace line search. They only supply the initial guess passed to _get_initial_step_size(). See Line Searchers for Armijo, Brent, and related strategies.

Role in the optimization stack#

Each gradient-based optimizer (see Optimizers) calls a LineSearcher at every iteration. When a seeder is attached to the line searcher, the workflow is:

Optimizer computes a search direction \(d_k\).
Seeder estimates \(\alpha_k^{(0)}\) from history.
Line searcher accepts or backtracks from \(\alpha_k^{(0)}\) until its conditions hold.

Barzilai–Borwein family#

All BB seeders inherit from BarzilaiBorwein and share two secant step estimates computed from

\[s_{k-1} = x_k - x_{k-1}, \quad y_{k-1} = g_k - g_{k-1}\]

where \(g_k = \nabla f(x_k)\) [Barzilai and Borwein, 1988].

Long step (BB1)

\[\alpha^{\mathrm{LONG}}_k = \frac{s_{k-1}^T s_{k-1}}{s_{k-1}^T y_{k-1}} = \frac{\|s_{k-1}\|^2}{s_{k-1}^T y_{k-1}}\]

Short step (BB2)

\[\alpha^{\mathrm{SHORT}}_k = \frac{s_{k-1}^T y_{k-1}}{y_{k-1}^T y_{k-1}} = \frac{s_{k-1}^T y_{k-1}}{\|y_{k-1}\|^2}\]

On the first iteration (no history), all BB seeders return init_step (default 1.0). Invalid denominators yield np.nan; selection logic then falls back to the other variant or to min_step.

BarzilaiBorweinCyclic#

Class: BarzilaiBorweinCyclic

Cycles through BB1 and BB2 with configurable period cycle_length (default 4, must be \(\geq 2\)). At cycle position iteration % cycle_length:

Even position: prefer BB1, fall back to BB2.
Odd position: prefer BB2, fall back to BB1.

\[\begin{split}\alpha_k = \begin{cases} \alpha^{\mathrm{LONG}}_k & \text{if cycle position is even} \\ \alpha^{\mathrm{SHORT}}_k & \text{if cycle position is odd} \end{cases}\end{split}\]

Use when: you want explicit control over how often long vs short BB steps are tried; default cycle_length=4 alternates two BB1 and two BB2 steps per cycle.

BarzilaiBorweinAlternating#

Class: BarzilaiBorweinAlternating

Backward-compatible alias for BarzilaiBorweinCyclic(cycle_length=2): odd iterations prefer BB2, even iterations prefer BB1. Any cycle_length passed at construction is ignored.

BarzilaiBorweinAdaptiveMin1 (ABBmin1)#

Class: BarzilaiBorweinAdaptiveMin1

Adaptive rule from Dai & Fletcher [Dai and Fletcher, 2005] using a sliding window of recent BB2 values:

\[\begin{split}\alpha_k = \begin{cases} \min\{\alpha^{\mathrm{SHORT}}_i : i \in \text{window}\} & \text{if } \alpha^{\mathrm{SHORT}} / \alpha^{\mathrm{LONG}} < \tau \\ \alpha^{\mathrm{LONG}}_k & \text{otherwise} \end{cases}\end{split}\]

Parameters: tau (default 0.8), window (default 10).

Use when: ill-conditioned problems where short BB steps become overly conservative.

BarzilaiBorweinAdaptiveMin2 (ABBmin2)#

Class: BarzilaiBorweinAdaptiveMin2

Simpler adaptive rule:

\[\begin{split}\alpha_k = \begin{cases} \alpha_{k-1} & \text{if } \alpha^{\mathrm{SHORT}} / \alpha^{\mathrm{LONG}} < \tau \text{ and } \alpha_{k-1} \text{ exists} \\ \alpha^{\mathrm{LONG}}_k & \text{otherwise} \end{cases}\end{split}\]

Parameters: tau (default 0.9).

Use when: well-conditioned problems with relatively stable step sizes.

BarzilaiBorweinRetarded#

Class: BarzilaiBorweinRetarded

Uses a delayed gradient difference instead of the standard one-step difference:

\[y_k = g_k - g_{k-m}, \quad \alpha_k = \frac{s_k^T s_k}{s_k^T y_k}\]

where \(s_k = x_k - x_{k-1}\) and m is delay (default 3). When delay=1, this reduces to BB1 with the usual \(y_k = g_k - g_{k-1}\).

Falls back to init_step until the circular gradient buffer holds delay past gradients. Only BB1 is selected (BB2 is computed but not used).

Use when: you want BB1 with a longer effective gradient memory; can help on noisy or slowly varying curvature landscapes.

ProximalBarzilaiBorwein#

Class: ProximalBarzilaiBorwein

Extends BarzilaiBorweinCyclic for proximal objectives (FISTA). Replaces \(y\) with the proximal residual

\[r_k = \operatorname{prox}_{\rho}(x_k) - \operatorname{prox}_{\rho}(x_{k-1})\]

and uses cyclic BB1/BB2 proximal formulas:

\[\alpha^{\mathrm{LONG}}_k = \frac{s_k^T s_k}{s_k^T r_k}, \quad \alpha^{\mathrm{SHORT}}_k = \frac{s_k^T r_k}{r_k^T r_k}\]

with \(\rho = 1 / \alpha_{k-1}\) from the previous accepted step.

Requirements: exactly 0 or 1 non-differentiable term in the objective. With no non-smooth term the proximal map is the identity and gradient-based BB seeders should be used instead.

Not compatible with SDMM when multiple non-smooth terms are split separately; use gradient-based BB seeders for the inner SDMM optimizer. See Compressed Sensing & Proximal Methods.

Interpolation seeders#

CubicInterpolationSeeder#

Class: CubicInterpolationSeeder

Fits a cubic polynomial along the previous search direction using \(f(x_{k-1})\), \(f(x_k)\), and gradients at both points, finds the minimizer \(\alpha_{\mathrm{opt}}\) along that direction, then scales to the current direction:

\[\alpha_{\mathrm{new}} = \alpha_{\mathrm{opt}} \cdot \frac{\|\nabla f(x_k)\|}{\|\nabla f(x_{k-1})\|}\]

Use when: smooth objectives with varying curvature; more accurate than quadratic but needs reliable function and gradient history.

QuadraticInterpolationSeeder#

Class: QuadraticInterpolationSeeder

Same framework as the cubic seeder but with a quadratic fit (function value and gradients at endpoints of the previous step). Closed-form minimizer when the quadratic curvature coefficient is positive.

Use when: smoother, more stable alternative to cubic; good fallback when cubic interpolation fails numerically.

Shared parameters#

All seeders support:

Parameter	Default	Role
`init_step`	`1.0`	Step when history is insufficient
`min_step`	`1e-10`	Floor on accepted estimates
`curvature_tol`	`1e-12`	Denominator guard in BB formulas

Selection guide#

Problem type	Suggested seeder
General smooth imaging	`BarzilaiBorweinAlternating` or `Cyclic`
Ill-conditioned	`BarzilaiBorweinAdaptiveMin1`
Well-conditioned, stable	`BarzilaiBorweinAdaptiveMin2`
Longer gradient memory	`BarzilaiBorweinRetarded`
FISTA / single prox term	`ProximalBarzilaiBorwein`
Strongly quadratic local behavior	`CubicInterpolationSeeder`
Cubic unstable	`QuadraticInterpolationSeeder`
Fixed / no history	No seeder (line searcher default step)

Implementation example#

from pyralysis.optimization.linesearch import (
    BacktrackingArmijo,
    BarzilaiBorweinCyclic,
    BarzilaiBorweinRetarded,
    ProximalBarzilaiBorwein,
    CubicInterpolationSeeder,
)

# Gradient-based BB with 4-step cycle
seeder = BarzilaiBorweinCyclic(cycle_length=4, min_step=1e-10)
ls = BacktrackingArmijo(objective_function=of, seeder=seeder)

# Retarded BB1 with delay m=3
seeder = BarzilaiBorweinRetarded(delay=3, init_step=0.5)

# FISTA: attach ProximalBarzilaiBorwein to FISTABacktracking (see linesearchers)
from pyralysis.optimization.linesearch import FISTABacktracking
prox_seeder = ProximalBarzilaiBorwein(cycle_length=2)
fista_ls = FISTABacktracking(objective_function=of, seeder=prox_seeder)

References#

[1]

Jonathan Barzilai and Jonathan M. Borwein. Two-point step size gradient methods. IMA Journal of Numerical Analysis, 8(1):141–148, 1988. doi:10.1093/imanum/8.1.141.

[2]

Yu-Hong Dai and Roger Fletcher. Projected barzilai–borwein methods for large-scale box-constrained quadratic programming. Numerische Mathematik, 100(1):21–47, 2005. doi:10.1007/s00211-004-0543-6.