qqn-torch 0.1.0

Quadratic Quasi-Newton optimizer for torch

qqn-torch

QQN (Quadratic Quasi-Newton) — a drop-in replacement for torch.optim.LBFGS that searches a quadratic path blending the steepest-descent and quasi-Newton directions.

What is QQN?

Classic quasi-Newton methods (like L-BFGS) take a single direction -H∇f and line-search along it. This works well near a minimum but can be fragile far from it, where the curvature approximation is unreliable.

QQN instead constructs a quadratic path that interpolates between the steepest-descent direction and the quasi-Newton direction:

d(t) = t(1-t)·(-∇f) + t²·(-H∇f)

with t ∈ [0, 1]. The key properties are:

t	Behavior
d(0) = 0	The path starts at the current iterate.
d'(0) = -∇f	The initial tangent is steepest descent.
d(1) = -H∇f	The endpoint is the L-BFGS direction.

Because the path starts tangent to -∇f, the beginning of the path always decreases f (when ∇f ≠ 0). This anchors global convergence, while the t = 1 endpoint recovers L-BFGS superlinear behavior near the optimum. The line search walks t directly and discovers the right blend — no manual tuning of a mixing coefficient.

Installation

pip install qqn-torch

Or from source:

git clone https://github.com/your-org/qqn-torch
cd qqn-torch
pip install -e .

Requires PyTorch.

Quick Start

QQN follows the same closure-based API as torch.optim.LBFGS:

import torch
from qqn_torch import QQN

# A simple quadratic objective.
x = torch.tensor([1.5, -2.0], requires_grad=True)

optimizer = QQN([x], max_iter=20)


def closure():
    optimizer.zero_grad()
    loss = (x[0] - 3.0) ** 2 + (x[1] + 1.0) ** 2
    loss.backward()
    return loss


for _ in range(10):
    loss = optimizer.step(closure)
    print(f"loss = {loss:.6e}, x = {x.detach().tolist()}")

The closure must:

1. Clear gradients (zero_grad()),
2. Compute the loss,
3. Call loss.backward(),
4. Return the loss.

This is identical to the torch.optim.LBFGS contract, so existing LBFGS training loops work unchanged.

Configuration

QQN(
    params,
    history_size=10,  # L-BFGS curvature-pair history
    line_search="armijo",  # "armijo" | "backtracking" | "strong_wolfe" | "fixed"
    oracle="lbfgs",  # "lbfgs" | "momentum" | "secant" | Oracle instance
    region=None,  # None | "box" | "trust" | Region instance
    max_iter=20,  # inner iterations per .step()
    tol_grad=1e-7,  # gradient-norm stopping tolerance
    tol_change=1e-9,  # step/objective change tolerance
    line_search_options=None  # dict forwarded to the line search (c1, c2, ...)
)

Four orthogonal, swappable components

QQN is built as a combiner of four independent pieces. Each can be changed without touching the rest.

1. Oracle — the t = 1 endpoint (-H∇f)

Name	Description
lbfgs	(default) Two-loop recursion over curvature pairs.
momentum	Heavy-ball direction -(β·v + (1-β)·∇f).
secant	Barzilai–Borwein scalar step (O(n) memory).

Because the steepest-descent contribution anchors convergence, the oracle is free to be aggressive — it need not guarantee descent on its own.

2. Line search — walks the path and picks t

Name	Conditions	Notes
armijo	Armijo sufficient decrease	(default) Backtracking.
backtracking	Armijo sufficient decrease	Aggressive contraction from t=1.
strong_wolfe	Armijo + strong curvature	Can over-restrict the path step.
fixed	None	Debug/baseline; constant t.

The line search is not an implementation detail — it is the glue that makes the gradient and oracle work together. Convergence quality is bounded by line-search quality.

3. Region — optional projection of candidate points

Name	Description
None	(default) Identity — zero overhead.
box	Elementwise clip to [lo, hi].
trust	Trust-region sphere with adaptive radius.

When a region is active, the line search navigates the projected path d_R(t) = project_R(x, x + d(t)) - x, so descent guarantees hold on the feasible set. Custom regions can be composed with SequentialRegion.

4. Gradient

The raw -∇f signal, the path's tangent at the origin.

Custom components

You can pass instances instead of string shortcuts for full control:

from qqn_torch import QQN
from qqn_torch.regions import TrustRegion
from qqn_torch.oracles import SecantOracle

optimizer = QQN(
    params,
    oracle=SecantOracle(alpha_init=0.5),
    region=TrustRegion(radius=2.0, max_radius=1e3),
    line_search="strong_wolfe",
    line_search_options={"c1": 1e-4, "c2": 0.9},
)

How it works (per inner iteration)

g       = flat_grad(closure)         # autograd on the closure
qn_dir  = oracle.direction(g, state) # the t=1 endpoint, -H g
grad_dir = -g                        # the path tangent at t=0
d(t)    = t(1-t)·grad_dir + t²·qn_dir # quadratic path
t*      = line_search(...)           # picks the blend AND the step
x      += project(d(t*))             # apply (optionally projected) step
oracle.update(s, y)                  # s = Δx, y = Δg
region.update(...)                   # e.g. adapt trust radius

Advantages

• Adaptive: automatically balances conservative vs. aggressive steps.
• Robust: d'(0) = -∇f plus line-search fallbacks ensure progress even when the oracle is poor.
• Efficient: L-BFGS acceleration when curvature is reliable.
• Modular: gradient, oracle, search, and region are independently swappable.

Limitations

• Memory: stores L-BFGS history (O(m·n)).
• Overhead: walking the curved path adds modest per-iteration cost.
• Tuning: sensitive to history size, line-search constants, region radii.
• Line-search sensitivity: a poor line search undermines convergence and the quality of the curvature updates.

Theoretical guarantees

Under standard assumptions (smooth objective, bounded gradients):

• Global convergence — anchored by the steepest-descent tangent.
• Superlinear convergence — inherited from L-BFGS when t → 1 near the optimum.
• Descent property — every accepted step decreases f, enforced by the line search's sufficient-decrease test.

All guarantees are contingent on the line search satisfying sufficient decrease. When a region is active, they hold on the projected path d_R(t).

Documentation

• algorithm.md — comprehensive algorithm reference.

Acknowledgements

The strong-Wolfe line search is adapted from PyTorch's _strong_wolfe helper (torch/optim/lbfgs.py, BSD-licensed). See qqn_torch/_vendor/strong_wolfe.py for attribution.

License

See the LICENSE file. Vendored code retains its original PyTorch BSD license.