omnibias.core.line_search

0.5.0rc1Release candidatePython >=3.10Apache-2.0

Coefficient recurrences, activation contracts, jet algebra, and verified arithmetic shared by the numerical backends.

import omnibias.core.line_search

Module contract & mathematical conventions

Exact jet line-search algebra (theory 03-12).

A directional Taylor jet of a scalar phi(s) = L(theta + s d) turns the line-search subproblem into root-finding on a known polynomial. This module is the shared, backend-free half: Taylor coefficients, certified Lagrange remainder radii, Wolfe-as-interval, and model-step selection. Tensor evaluation of the jet lives in the torch / jax twins.

The jet comes from the founding bias collapse (delta -> 0) tower. No temperature collapse appears. The polynomial is a model, not the loss: truncation is real, the trust radius bounds it when a sound |phi^(N+1)| bound is supplied, and verify=True is the never-worse backstop.

omnibias.core cannot import omnibias.difference (that package depends on core). The remainder used here is the same Lagrange identity that certified_fd_error_general applies to stencils: if |phi^(N+1)| <= M on [0, r] then |R_N(s)| <= M |s|^(N+1) / (N+1)!.

Shared formulas do not imply universal floating-point identity. Verify dtype, shape, derivative-order support, and the stated numerical assumptions for the path you use.

Module source ↗Source revision 9a2d73df0573Running reference examples →

CLASS

GradientSecant

omnibias.core.GradientSecantSource ↗

class GradientSecant

Dataclass constructor fields; inherited fields, if any, are declared by the base class. A field(...) expression describes a default factory or field options, not a literal argument default.

Secant plane for a steepest step along -gradient.

previous_gradient and current_gradient are Euclidean gradients. previous_step is the accepted scalar along -previous_gradient. direction is the current search direction; the eigenstep is used only when it equals -current_gradient. used_curvatures are plane-Hessian eigenvalues already annihilated by earlier accepted steps.

The jet is the founding bias collapse (delta -> 0). No temperature collapse appears.

Parameters

Name	Type & default	Contract
`previous_gradient`dataclass field	`tuple[float, ...]`Required	See the operation contract and implementation below.
`previous_step`dataclass field	`float`Required	See the operation contract and implementation below.
`current_gradient`dataclass field	`tuple[float, ...]`Required	See the operation contract and implementation below.
`direction`dataclass field	`tuple[float, ...]`Required	See the operation contract and implementation below.
`used_curvatures`dataclass field	`tuple[float, ...]`Default: ()	See the operation contract and implementation below.

Regression example · secant ignored when direction is not negative gradient

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_secant_ignored_when_direction_is_not_negative_gradient() -> None:
    derivs = (1.0, -2.0, 6.0, -12.0, 48.0)
    plain = select_model_step(
        derivs,
        radius=1.0,
        config=JetLineSearchConfig(order=4, verify=False),
    )
    secant = GradientSecant(
        previous_gradient=(1.0, 0.0),
        previous_step=0.2,
        current_gradient=(0.0, 1.0),
        direction=(1.0, 0.0),
        used_curvatures=(),
    )
    result = run_model_line_search(
        derivs,
        config=JetLineSearchConfig(order=4, trust_radius=1.0, verify=False),
        secant=secant,
    )
    assert result.consumed_curvature is None
    assert result.step == pytest.approx(plain.step)

python -m pytest packages/omnibias-core/tests/test_line_search.py -k test_secant_ignored_when_direction_is_not_negative_gradient -q

Fields & methods

previous_gradientfield

previous_gradient: tuple[float, ...]

Declared tuple[float, ...] field on GradientSecant. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

previous_stepfield

previous_step: float

Declared float field on GradientSecant. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

current_gradientfield

current_gradient: tuple[float, ...]

Declared tuple[float, ...] field on GradientSecant. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

directionfield

direction: tuple[float, ...]

Declared tuple[float, ...] field on GradientSecant. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

used_curvaturesfield

used_curvatures: tuple[float, ...] = ()

Declared tuple[float, ...] field on GradientSecant. Default expression: ().

View source ↗

Read the implementation

class GradientSecant:
    """Secant plane for a steepest step along ``-gradient``.

    ``previous_gradient`` and ``current_gradient`` are Euclidean gradients.
    ``previous_step`` is the accepted scalar along ``-previous_gradient``.
    ``direction`` is the current search direction; the eigenstep is used only
    when it equals ``-current_gradient``. ``used_curvatures`` are plane-Hessian
    eigenvalues already annihilated by earlier accepted steps.

    The jet is the founding bias collapse (``delta -> 0``). No temperature
    collapse appears.
    """

    previous_gradient: tuple[float, ...]
    previous_step: float
    current_gradient: tuple[float, ...]
    direction: tuple[float, ...]
    used_curvatures: tuple[float, ...] = ()

Other public import paths

omnibias.core.GradientSecant
omnibias.jax.GradientSecant
omnibias.torch.GradientSecant
omnibias.core.line_search.GradientSecant
omnibias.jax.line_search.GradientSecant
omnibias.torch.line_search.GradientSecant

CLASS

JetLineSearchConfig

omnibias.core.JetLineSearchConfigSource ↗

class JetLineSearchConfig

Dataclass constructor fields; inherited fields, if any, are declared by the base class. A field(...) expression describes a default factory or field options, not a literal argument default.

Configuration for select_model_step and the backend drivers.

trust_radius="certified" uses a Lagrange radius only when next_derivative_bound is supplied to the driver. A bare float is an explicit (not certified) cap.

Parameters

Name	Type & default	Contract
`order`dataclass field	`int`Default: 4	See the operation contract and implementation below.
`trust_radius`dataclass field	`float \| Literal['certified']`Default: 'certified'	See the operation contract and implementation below.
`verify`dataclass field	`bool`Default: True	See the operation contract and implementation below.
`wolfe_c1`dataclass field	`float`Default: 0.0001	See the operation contract and implementation below.
`wolfe_c2`dataclass field	`float`Default: 0.9	See the operation contract and implementation below.
`max_step`dataclass field	`float`Default: 1.0	See the operation contract and implementation below.
`isolate_roots`dataclass field	`bool`Default: True	See the operation contract and implementation below.
`remainder_atol`dataclass field	`float`Default: 1e-08	See the operation contract and implementation below.
`require_wolfe`dataclass field	`bool`Default: False	See the operation contract and implementation below.

Executed regression · run model requires actual when verify

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_run_model_requires_actual_when_verify() -> None:
    with pytest.raises(ValueError, match="actual_fn"):
        run_model_line_search(_QUARTIC_DERIVS, config=JetLineSearchConfig(order=4))

python -m pytest "packages/omnibias-core/tests/test_line_search.py::test_run_model_requires_actual_when_verify" -q

Regression example · explicit cap with bound is certified

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_explicit_cap_with_bound_is_certified() -> None:
    radius, certified = resolve_trust_radius(
        JetLineSearchConfig(order=4, trust_radius=1.0),
        next_derivative_bound=0.0,
    )
    assert certified
    assert radius == 1.0

python -m pytest packages/omnibias-core/tests/test_line_search.py -k test_explicit_cap_with_bound_is_certified -q

Fields & methods

orderfield

order: int = 4

Declared int field on JetLineSearchConfig. Default expression: 4.

View source ↗

trust_radiusfield

trust_radius: float | Literal['certified'] = 'certified'

Declared float | Literal['certified'] field on JetLineSearchConfig. Default expression: 'certified'.

View source ↗

verifyfield

verify: bool = True

Declared bool field on JetLineSearchConfig. Default expression: True.

View source ↗

wolfe_c1field

wolfe_c1: float = 0.0001

Declared float field on JetLineSearchConfig. Default expression: 0.0001.

View source ↗

wolfe_c2field

wolfe_c2: float = 0.9

Declared float field on JetLineSearchConfig. Default expression: 0.9.

View source ↗

max_stepfield

max_step: float = 1.0

Declared float field on JetLineSearchConfig. Default expression: 1.0.

View source ↗

isolate_rootsfield

isolate_roots: bool = True

Declared bool field on JetLineSearchConfig. Default expression: True.

View source ↗

remainder_atolfield

remainder_atol: float = 1e-08

Declared float field on JetLineSearchConfig. Default expression: 1e-08.

View source ↗

require_wolfefield

require_wolfe: bool = False

Declared bool field on JetLineSearchConfig. Default expression: False.

View source ↗

__post_init__method

__post_init__(self) -> None

See the class contract above and the exact method implementation below.

Returns: None

Validation & failure cases

When self.order < 0, raises ValueError(f'order must be >= 0, got {self.order}').
When isinstance(self.trust_radius, float) and (self.trust_radius < 0.0 or not math.isfinite(self.trust_radius)), raises ValueError(f'trust_radius must be >= 0 and finite, got {self.trust_radius}').
When not 0.0 < self.wolfe_c1 < 1.0, raises ValueError(f'wolfe_c1 must be in (0, 1), got {self.wolfe_c1}').
When not self.wolfe_c1 < self.wolfe_c2 < 1.0, raises ValueError(f'need wolfe_c1 < wolfe_c2 < 1, got {self.wolfe_c1}, {self.wolfe_c2}').
When self.max_step < 0.0 or not math.isfinite(self.max_step), raises ValueError(f'max_step must be a finite number >= 0, got {self.max_step}').
When self.remainder_atol <= 0.0 or not math.isfinite(self.remainder_atol), raises ValueError(f'remainder_atol must be a positive finite number, got {self.remainder_atol}').

Executed regression · run model requires actual when verify

Full file, imports & fixtures ↗

def test_run_model_requires_actual_when_verify() -> None:
    with pytest.raises(ValueError, match="actual_fn"):
        run_model_line_search(_QUARTIC_DERIVS, config=JetLineSearchConfig(order=4))

python -m pytest "packages/omnibias-core/tests/test_line_search.py::test_run_model_requires_actual_when_verify" -q

Method implementation

    def __post_init__(self) -> None:
        if self.order < 0:
            raise ValueError(f"order must be >= 0, got {self.order}")
        if isinstance(self.trust_radius, float) and (
            self.trust_radius < 0.0 or not math.isfinite(self.trust_radius)
        ):
            raise ValueError(f"trust_radius must be >= 0 and finite, got {self.trust_radius}")
        if not 0.0 < self.wolfe_c1 < 1.0:
            raise ValueError(f"wolfe_c1 must be in (0, 1), got {self.wolfe_c1}")
        if not self.wolfe_c1 < self.wolfe_c2 < 1.0:
            raise ValueError(
                f"need wolfe_c1 < wolfe_c2 < 1, got {self.wolfe_c1}, {self.wolfe_c2}"
            )
        if self.max_step < 0.0 or not math.isfinite(self.max_step):
            raise ValueError(f"max_step must be a finite number >= 0, got {self.max_step}")
        if self.remainder_atol <= 0.0 or not math.isfinite(self.remainder_atol):
            raise ValueError(
                f"remainder_atol must be a positive finite number, got {self.remainder_atol}"
            )

View source ↗

Read the implementation

class JetLineSearchConfig:
    """Configuration for :func:`select_model_step` and the backend drivers.

    ``trust_radius="certified"`` uses a Lagrange radius only when
    ``next_derivative_bound`` is supplied to the driver. A bare float is an
    explicit (not certified) cap.
    """

    order: int = 4
    trust_radius: float | Literal["certified"] = "certified"
    verify: bool = True
    wolfe_c1: float = 1e-4
    wolfe_c2: float = 0.9
    max_step: float = 1.0
    isolate_roots: bool = True
    remainder_atol: float = 1e-8
    require_wolfe: bool = False

    def __post_init__(self) -> None:
        if self.order < 0:
            raise ValueError(f"order must be >= 0, got {self.order}")
        if isinstance(self.trust_radius, float) and (
            self.trust_radius < 0.0 or not math.isfinite(self.trust_radius)
        ):
            raise ValueError(f"trust_radius must be >= 0 and finite, got {self.trust_radius}")
        if not 0.0 < self.wolfe_c1 < 1.0:
            raise ValueError(f"wolfe_c1 must be in (0, 1), got {self.wolfe_c1}")
        if not self.wolfe_c1 < self.wolfe_c2 < 1.0:
            raise ValueError(
                f"need wolfe_c1 < wolfe_c2 < 1, got {self.wolfe_c1}, {self.wolfe_c2}"
            )
        if self.max_step < 0.0 or not math.isfinite(self.max_step):
            raise ValueError(f"max_step must be a finite number >= 0, got {self.max_step}")
        if self.remainder_atol <= 0.0 or not math.isfinite(self.remainder_atol):
            raise ValueError(
                f"remainder_atol must be a positive finite number, got {self.remainder_atol}"
            )

Other public import paths

omnibias.core.JetLineSearchConfig
omnibias.jax.JetLineSearchConfig
omnibias.torch.JetLineSearchConfig
omnibias.core.line_search.JetLineSearchConfig
omnibias.jax.line_search.JetLineSearchConfig
omnibias.jax.optim.JetLineSearchConfig
omnibias.torch.line_search.JetLineSearchConfig
omnibias.torch.optim.JetLineSearchConfig

CLASS

LineSearchResult

omnibias.core.LineSearchResultSource ↗

class LineSearchResult

Dataclass constructor fields; inherited fields, if any, are declared by the base class. A field(...) expression describes a default factory or field options, not a literal argument default.

Outcome of a jet line search (model step, optional verification).

Parameters

Name	Type & default	Contract
`step`dataclass field	`float`Required	See the operation contract and implementation below.
`model_value`dataclass field	`float`Required	See the operation contract and implementation below.
`actual_value`dataclass field	`float \| None`Required	See the operation contract and implementation below.
`model_error`dataclass field	`float \| None`Required	See the operation contract and implementation below.
`truncation_radius`dataclass field	`float`Required	See the operation contract and implementation below.
`fell_back`dataclass field	`bool`Required	See the operation contract and implementation below.
`wolfe_ok`dataclass field	`bool \| None`Default: None	See the operation contract and implementation below.
`truncation_certified`dataclass field	`bool`Default: False	See the operation contract and implementation below.
`isolated_root`dataclass field	`bool`Default: False	See the operation contract and implementation below.
`consumed_curvature`dataclass field	`float \| None`Default: None	See the operation contract and implementation below.

Fields & methods

stepfield

step: float

Declared float field on LineSearchResult. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

model_valuefield

model_value: float

Declared float field on LineSearchResult. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

actual_valuefield

actual_value: float | None

Declared float | None field on LineSearchResult. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

model_errorfield

model_error: float | None

Declared float | None field on LineSearchResult. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

truncation_radiusfield

truncation_radius: float

Declared float field on LineSearchResult. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

fell_backfield

fell_back: bool

Declared bool field on LineSearchResult. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

wolfe_okfield

wolfe_ok: bool | None = None

Declared bool | None field on LineSearchResult. Default expression: None.

View source ↗

truncation_certifiedfield

truncation_certified: bool = False

Declared bool field on LineSearchResult. Default expression: False.

View source ↗

isolated_rootfield

isolated_root: bool = False

Declared bool field on LineSearchResult. Default expression: False.

View source ↗

consumed_curvaturefield

consumed_curvature: float | None = None

Declared float | None field on LineSearchResult. Default expression: None.

View source ↗

Read the implementation

class LineSearchResult:
    """Outcome of a jet line search (model step, optional verification)."""

    step: float
    model_value: float
    actual_value: float | None
    model_error: float | None
    truncation_radius: float
    fell_back: bool
    wolfe_ok: bool | None = None
    truncation_certified: bool = False
    isolated_root: bool = False
    consumed_curvature: float | None = None

Other public import paths

omnibias.core.LineSearchResult
omnibias.jax.LineSearchResult
omnibias.torch.LineSearchResult
omnibias.core.line_search.LineSearchResult
omnibias.jax.line_search.LineSearchResult
omnibias.jax.optim.LineSearchResult
omnibias.torch.line_search.LineSearchResult
omnibias.torch.optim.LineSearchResult

FUNCTION

apply_verification

omnibias.core.line_search.apply_verificationSource ↗

apply_verification(result: LineSearchResult, actual_fn: Callable[[float], float], *, start_value: float) -> LineSearchResult

Never-worse backstop: shrink toward 0 if the true phi rose.

actual_fn(s) evaluates the true restriction. The returned step satisfies actual <= start_value (up to a tiny absolute slack for round-off). A reduction of the model step sets fell_back.

Parameters

Name	Type & default	Contract
`result`positional-or-keyword	`LineSearchResult`Required	See the operation contract and implementation below.
`actual_fn`positional-or-keyword	`Callable[[float], float]`Required	See the operation contract and implementation below.
`start_value`keyword-only	`float`Required	See the operation contract and implementation below.

ReturnsLineSearchResult

Executed regression · g3 never worse pathological

Full file, imports & fixtures ↗

def test_g3_never_worse_pathological() -> None:
    def sharp_bowl(p: jax.Array) -> jax.Array:
        s = p[0]
        return 1.0 - 2.0 * s + 50.0 * s**2

    result = jet_line_search(
        sharp_bowl,
        jnp.zeros(1),
        jnp.ones(1),
        config=JetLineSearchConfig(order=1, trust_radius=1.0, verify=True),
    )
    assert result.actual_value is not None
    assert result.actual_value <= 1.0 + 1e-14
    assert result.fell_back

python -m pytest "packages/omnibias-jax/tests/test_line_search.py::test_g3_never_worse_pathological" -q

Regression example · verify never worse on pathological direction

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_verify_never_worse_on_pathological_direction() -> None:
    # Model wants a large step; true phi rises immediately (ascent).
    derivs = (1.0, -1.0, 0.0, 0.0, 0.0)
    model = select_model_step(
        derivs,
        radius=1.0,
        config=JetLineSearchConfig(order=4, verify=False),
    )
    assert model.step > 0.0

    def actual(s: float) -> float:
        return 1.0 + 10.0 * s

    verified = apply_verification(model, actual, start_value=1.0)
    assert verified.fell_back
    assert verified.actual_value is not None
    assert verified.actual_value <= 1.0 + 1e-14
    assert verified.step >= 0.0

python -m pytest packages/omnibias-core/tests/test_line_search.py -k test_verify_never_worse_on_pathological_direction -q

Read the implementation

def apply_verification(
    result: LineSearchResult,
    actual_fn: Callable[[float], float],
    *,
    start_value: float,
) -> LineSearchResult:
    """Never-worse backstop: shrink toward 0 if the true ``phi`` rose.

    ``actual_fn(s)`` evaluates the true restriction. The returned step
    satisfies ``actual <= start_value`` (up to a tiny absolute slack for
    round-off). A reduction of the model step sets ``fell_back``.
    """
    step = float(result.step)
    actual = float(actual_fn(step))
    fell = False
    if (not math.isfinite(actual)) or actual > start_value + 1e-15:
        trial = step
        actual = float("inf")
        for _ in range(40):
            trial *= 0.5
            if trial < 1e-16:
                trial = 0.0
                actual = float(start_value)
                break
            trial_val = float(actual_fn(trial))
            if math.isfinite(trial_val) and trial_val <= start_value + 1e-15:
                actual = trial_val
                break
        step = trial
        fell = True
        if not math.isfinite(actual):
            step = 0.0
            actual = float(start_value)
    model_error = abs(actual - result.model_value) if step == result.step else None
    # If we fell back, re-evaluate the *model* at the accepted step so the
    # recorded model_value matches the returned step.
    model_value = result.model_value
    return LineSearchResult(
        step=step,
        model_value=model_value,
        actual_value=actual,
        model_error=model_error,
        truncation_radius=result.truncation_radius,
        fell_back=fell,
        wolfe_ok=result.wolfe_ok,
        truncation_certified=result.truncation_certified,
        isolated_root=result.isolated_root and not fell,
        consumed_curvature=None if fell else result.consumed_curvature,
    )

FUNCTION

certified_truncation_radius

omnibias.core.certified_truncation_radiusSource ↗

certified_truncation_radius(next_derivative_bound: float, order: int, *, atol: float=1e-08, max_step: float=1.0) -> float

Largest r in [0, max_step] with remainder.hi <= atol.

Binary search returns the *lower* endpoint of the last feasible split, so the Lagrange enclosure is guaranteed (the float r is never rounded upward past the bound).

Parameters

Name	Type & default	Contract
`next_derivative_bound`positional-or-keyword	`float`Required	See the operation contract and implementation below.
`order`positional-or-keyword	`int`Required	See the operation contract and implementation below.
`atol`keyword-only	`float`Default: 1e-08	See the operation contract and implementation below.
`max_step`keyword-only	`float`Default: 1.0	See the operation contract and implementation below.

Returnsfloat

Explicit validation & failure cases

When atol <= 0.0 or not math.isfinite(atol), raises ValueError(f'atol must be a positive finite number, got {atol}').
When max_step < 0.0 or not math.isfinite(max_step), raises ValueError(f'max_step must be a finite number >= 0, got {max_step}').

These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.

Executed regression · explicit cap with bound is certified

Full file, imports & fixtures ↗

def test_explicit_cap_with_bound_is_certified() -> None:
    radius, certified = resolve_trust_radius(
        JetLineSearchConfig(order=4, trust_radius=1.0),
        next_derivative_bound=0.0,
    )
    assert certified
    assert radius == 1.0

python -m pytest "packages/omnibias-core/tests/test_line_search.py::test_explicit_cap_with_bound_is_certified" -q

Regression example · g2 polynomial remainder is zero

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_g2_polynomial_remainder_is_zero() -> None:
    """Degree-4 model of a degree-4 polynomial: M = 0, radius is the cap."""
    radius = certified_truncation_radius(0.0, order=4, atol=1e-8, max_step=2.5)
    assert radius == 2.5
    bound = lagrange_remainder_bound(0.0, 2.5, 4)
    assert bound.hi == 0.0

python -m pytest packages/omnibias-core/tests/test_line_search.py -k test_g2_polynomial_remainder_is_zero -q

Read the implementation

def certified_truncation_radius(
    next_derivative_bound: float,
    order: int,
    *,
    atol: float = 1e-8,
    max_step: float = 1.0,
) -> float:
    """Largest ``r`` in ``[0, max_step]`` with ``remainder.hi <= atol``.

    Binary search returns the *lower* endpoint of the last feasible split, so
    the Lagrange enclosure is guaranteed (the float ``r`` is never rounded
    upward past the bound).
    """
    if atol <= 0.0 or not math.isfinite(atol):
        raise ValueError(f"atol must be a positive finite number, got {atol}")
    if max_step < 0.0 or not math.isfinite(max_step):
        raise ValueError(f"max_step must be a finite number >= 0, got {max_step}")
    if next_derivative_bound == 0.0:
        return float(max_step)
    lo = 0.0
    hi = float(max_step)
    for _ in range(80):
        mid = 0.5 * (lo + hi)
        if lagrange_remainder_bound(next_derivative_bound, mid, order).hi <= atol:
            lo = mid
        else:
            hi = mid
    return lo

Other public import paths

omnibias.core.certified_truncation_radius
omnibias.core.line_search.certified_truncation_radius

FUNCTION

derivatives_from_taylor_coeffs

omnibias.core.line_search.derivatives_from_taylor_coeffsSource ↗

derivatives_from_taylor_coeffs(coeffs: Sequence[float]) -> list[float]

Inverse of taylor_coeffs_from_derivatives.

Parameters

Name	Type & default	Contract
`coeffs`positional-or-keyword	`Sequence[float]`Required	See the operation contract and implementation below.

Returnslist[float]

Explicit validation & failure cases

When not coeffs, raises ValueError('coeffs must be non-empty').
When not math.isfinite(val), raises ValueError(f'coeff[{k}] must be finite, got {raw!r}').

These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.

Read the implementation

def derivatives_from_taylor_coeffs(coeffs: Sequence[float]) -> list[float]:
    """Inverse of :func:`taylor_coeffs_from_derivatives`."""
    if not coeffs:
        raise ValueError("coeffs must be non-empty")
    out: list[float] = []
    fact = 1
    for k, raw in enumerate(coeffs):
        if k >= 1:
            fact *= k
        val = float(raw)
        if not math.isfinite(val):
            raise ValueError(f"coeff[{k}] must be finite, got {raw!r}")
        out.append(val * float(fact))
    return out

FUNCTION

factorial_int

omnibias.core.line_search.factorial_intSource ↗

factorial_int(n: int) -> int

n! as an int (exact).

Parameters

Name	Type & default	Contract
`n`positional-or-keyword	`int`Required	See the operation contract and implementation below.

Returnsint

Explicit validation & failure cases

When n < 0, raises ValueError(f'factorial is undefined for n < 0, got {n}').

These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.

Executed regression · certified local error exp

Full file, imports & fixtures ↗

def test_certified_local_error_exp() -> None:
    # exp on [0, 0.1]; order-3 model, M = |phi^(4)(0)| = 1 under-bounds
    # the true max e^{0.1}; still a well-defined remainder number.
    derivs = tuple(1.0 for _ in range(5))
    bound = certified_local_error(derivs, 0.1)
    remainder = abs(math.exp(0.1) - sum((0.1**k) / math.factorial(k) for k in range(4)))
    # Using M=1 < e^{0.1} is not sound; the API is only as sound as M.
    # With the true max M the bound must cover the remainder:
    sound = certified_local_error((1.0, 1.0, 1.0, 1.0, math.exp(0.1)), 0.1)
    assert sound >= remainder - 1e-15
    assert bound > 0.0

python -m pytest "packages/omnibias-core/tests/test_refine.py::test_certified_local_error_exp" -q

Read the implementation

def factorial_int(n: int) -> int:
    """``n!`` as an ``int`` (exact)."""
    if n < 0:
        raise ValueError(f"factorial is undefined for n < 0, got {n}")
    acc = 1
    for k in range(2, n + 1):
        acc *= k
    return acc

FUNCTION

interval_poly_eval

omnibias.core.line_search.interval_poly_evalSource ↗

interval_poly_eval(coeffs: Sequence[float], s: Interval) -> Interval

Outward-rounded Horner evaluation of a real polynomial on an interval.

Parameters

Name	Type & default	Contract
`coeffs`positional-or-keyword	`Sequence[float]`Required	See the operation contract and implementation below.
`s`positional-or-keyword	`Interval`Required	See the operation contract and implementation below.

ReturnsInterval

Executed regression · run model requires actual when verify

Full file, imports & fixtures ↗

def test_run_model_requires_actual_when_verify() -> None:
    with pytest.raises(ValueError, match="actual_fn"):
        run_model_line_search(_QUARTIC_DERIVS, config=JetLineSearchConfig(order=4))

python -m pytest "packages/omnibias-core/tests/test_line_search.py::test_run_model_requires_actual_when_verify" -q

Read the implementation

def interval_poly_eval(coeffs: Sequence[float], s: Interval) -> Interval:
    """Outward-rounded Horner evaluation of a real polynomial on an interval."""
    acc = Interval.point(0.0)
    for a in reversed(coeffs):
        acc = acc * s + Interval.point(float(a))
    return acc

FUNCTION

isolate_real_roots

omnibias.core.line_search.isolate_real_rootsSource ↗

isolate_real_roots(coeffs: Sequence[float], lo: float, hi: float, *, n_grid: int=_GRID_POINTS) -> list[Interval]

Certified enclosures of simple real roots on [lo, hi].

Sign-change cells that pass the interval-Newton uniqueness test are returned. Multiple / clustered roots may fail uniqueness; those stay out of this list (the float candidates from real_roots_on_interval are still usable as uncertified seeds).

Parameters

Name	Type & default	Contract
`coeffs`positional-or-keyword	`Sequence[float]`Required	See the operation contract and implementation below.
`lo`positional-or-keyword	`float`Required	See the operation contract and implementation below.
`hi`positional-or-keyword	`float`Required	See the operation contract and implementation below.
`n_grid`keyword-only	`int`Default: _GRID_POINTS	See the operation contract and implementation below.

Returnslist[Interval]

Executed regression · run model requires actual when verify

Full file, imports & fixtures ↗

def test_run_model_requires_actual_when_verify() -> None:
    with pytest.raises(ValueError, match="actual_fn"):
        run_model_line_search(_QUARTIC_DERIVS, config=JetLineSearchConfig(order=4))

python -m pytest "packages/omnibias-core/tests/test_line_search.py::test_run_model_requires_actual_when_verify" -q

Read the implementation

def isolate_real_roots(
    coeffs: Sequence[float],
    lo: float,
    hi: float,
    *,
    n_grid: int = _GRID_POINTS,
) -> list[Interval]:
    """Certified enclosures of simple real roots on ``[lo, hi]``.

    Sign-change cells that pass the interval-Newton uniqueness test are
    returned. Multiple / clustered roots may fail uniqueness; those stay
    out of this list (the float candidates from
    :func:`real_roots_on_interval` are still usable as uncertified seeds).
    """

    def g(x: Interval) -> Interval:
        return interval_poly_eval(coeffs, x)

    def gp(x: Interval) -> Interval:
        return interval_poly_eval(poly_derivative(coeffs), x)

    span = hi - lo
    if span <= 0.0:
        return []
    cells: list[Interval] = []
    for i in range(n_grid):
        a = lo + span * i / n_grid
        b = lo + span * (i + 1) / n_grid
        if not certified_sign_change(g, a, b):
            continue
        result = interval_newton(g, gp, (a, b), max_iter=80, tol=1e-14)
        if result["unique"]:
            enc = result["enclosure"]
            cells.append(Interval(enc[0], enc[1]))
    return cells

FUNCTION

lagrange_remainder_bound

omnibias.core.line_search.lagrange_remainder_boundSource ↗

lagrange_remainder_bound(next_derivative_bound: float, step: float, order: int) -> Interval

Sound enclosure of |R_N(s)| <= M |s|^(N+1) / (N+1)!.

next_derivative_bound is a claimed upper bound on |phi^(N+1)| on the segment from 0 to step. The bound is only as sound as M.

Parameters

Name	Type & default	Contract
`next_derivative_bound`positional-or-keyword	`float`Required	See the operation contract and implementation below.
`step`positional-or-keyword	`float`Required	See the operation contract and implementation below.
`order`positional-or-keyword	`int`Required	See the operation contract and implementation below.

ReturnsInterval

Explicit validation & failure cases

When order < 0, raises ValueError(f'order must be >= 0, got {order}').
When next_derivative_bound < 0.0, raises ValueError(f'next_derivative_bound must be >= 0, got {next_derivative_bound}').

These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.

Executed regression · g2 polynomial remainder is zero

Full file, imports & fixtures ↗

def test_g2_polynomial_remainder_is_zero() -> None:
    """Degree-4 model of a degree-4 polynomial: M = 0, radius is the cap."""
    radius = certified_truncation_radius(0.0, order=4, atol=1e-8, max_step=2.5)
    assert radius == 2.5
    bound = lagrange_remainder_bound(0.0, 2.5, 4)
    assert bound.hi == 0.0

python -m pytest "packages/omnibias-core/tests/test_line_search.py::test_g2_polynomial_remainder_is_zero" -q

Regression example · g2 exp remainder encloses grid and sample

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_g2_exp_remainder_encloses_grid_and_sample() -> None:
    """On [0, r] for exp, |R_N| <= e^r r^{N+1}/(N+1)! is sound."""
    order = 4
    cap = 0.5
    m = math.exp(cap)
    radius = certified_truncation_radius(m, order, atol=1e-6, max_step=cap)
    assert 0.0 < radius <= cap
    enclosure = lagrange_remainder_bound(m, radius, order)
    assert enclosure.hi <= 1e-6 + 1e-15

    def remainder(s: float) -> float:
        # exp(s) - Taylor_N(s) at 0
        model = sum((s**k) / math.factorial(k) for k in range(order + 1))
        return abs(math.exp(s) - model)

    grid = [radius * i / 40.0 for i in range(41)]
    rng_vals = [radius * ((i * 17 + 3) % 97) / 97.0 for i in range(20)]
    for s in grid + rng_vals:
        err = remainder(s)
        assert err <= enclosure.hi + 1e-14

python -m pytest packages/omnibias-core/tests/test_line_search.py -k test_g2_exp_remainder_encloses_grid_and_sample -q

Read the implementation

def lagrange_remainder_bound(
    next_derivative_bound: float,
    step: float,
    order: int,
) -> Interval:
    r"""Sound enclosure of ``|R_N(s)| <= M |s|^(N+1) / (N+1)!``.

    ``next_derivative_bound`` is a claimed upper bound on ``|phi^(N+1)|`` on
    the segment from ``0`` to ``step``. The bound is only as sound as ``M``.
    """
    if order < 0:
        raise ValueError(f"order must be >= 0, got {order}")
    if next_derivative_bound < 0.0:
        raise ValueError(
            f"next_derivative_bound must be >= 0, got {next_derivative_bound}"
        )
    if next_derivative_bound == 0.0:
        return Interval.point(0.0)
    m = Interval.point(float(next_derivative_bound))
    s_abs = Interval.point(abs(float(step)))
    fact = Interval.from_rational(factorial_int(order + 1))
    return m * s_abs.pow_int(order + 1) / fact

FUNCTION

plane_hessian_eigenvalues

omnibias.core.line_search.plane_hessian_eigenvaluesSource ↗

plane_hessian_eigenvalues(previous_gradient: Sequence[float], previous_step: float, current_gradient: Sequence[float], gradient_curvature: float) -> tuple[float, float] | None

Eigenvalues of the secant Hessian on span(g_prev, g).

For a quadratic, H g_prev = (g_prev - g) / s_prev when the previous step was along -g_prev. gradient_curvature is g^T H g, which the order-2 directional jet supplies as phi''(0) along -g.

Parameters

Name	Type & default	Contract
`previous_gradient`positional-or-keyword	`Sequence[float]`Required	See the operation contract and implementation below.
`previous_step`positional-or-keyword	`float`Required	See the operation contract and implementation below.
`current_gradient`positional-or-keyword	`Sequence[float]`Required	See the operation contract and implementation below.
`gradient_curvature`positional-or-keyword	`float`Required	See the operation contract and implementation below.

Returnstuple[float, float] | None

Executed regression · secant eigenstep hits named quadratic in three steps

Full file, imports & fixtures ↗

def test_secant_eigenstep_hits_named_quadratic_in_three_steps() -> None:
    """G4 suite: polynomial minimizer, then two unused inverse eigenvalues."""
    for cond in (50.0, 100.0, 200.0, 400.0, 800.0):
        theta = [-1.2, 0.8]
        prev: tuple[tuple[float, float], float] | None = None
        used: tuple[float, ...] = ()
        steps = 0
        for _ in range(6):
            value = theta[0] ** 2 + cond * theta[1] ** 2
            if value <= 1e-8:
                break
            grad = (2.0 * theta[0], 2.0 * cond * theta[1])
            step, consumed, _new = _illcond_step(theta, cond, prev=prev, used=used)
            if consumed is not None:
                used = (*used, consumed)
            theta = [theta[0] - step * grad[0], theta[1] - step * grad[1]]
            prev = (grad, step)
            steps += 1
        final = theta[0] ** 2 + cond * theta[1] ** 2
        assert steps == 3
        assert final <= 1e-8
        assert len(used) == 2

python -m pytest "packages/omnibias-core/tests/test_line_search.py::test_secant_eigenstep_hits_named_quadratic_in_three_steps" -q

Read the implementation

def plane_hessian_eigenvalues(
    previous_gradient: Sequence[float],
    previous_step: float,
    current_gradient: Sequence[float],
    gradient_curvature: float,
) -> tuple[float, float] | None:
    """Eigenvalues of the secant Hessian on ``span(g_prev, g)``.

    For a quadratic, ``H g_prev = (g_prev - g) / s_prev`` when the previous
    step was along ``-g_prev``. ``gradient_curvature`` is ``g^T H g``, which
    the order-2 directional jet supplies as ``phi''(0)`` along ``-g``.
    """
    if previous_step <= 0.0 or not math.isfinite(previous_step):
        return None
    if len(previous_gradient) != len(current_gradient) or len(current_gradient) < 2:
        return None
    if not math.isfinite(gradient_curvature):
        return None
    prev = [float(v) for v in previous_gradient]
    curr = [float(v) for v in current_gradient]
    if any(not math.isfinite(v) for v in prev + curr):
        return None
    prev_norm = _norm(prev)
    curr_norm = _norm(curr)
    if prev_norm < 1e-18 or curr_norm < 1e-18:
        return None
    secant = [(prev[i] - curr[i]) / float(previous_step) for i in range(len(prev))]
    unit_prev = [v / prev_norm for v in prev]
    along = _dot(curr, unit_prev)
    ortho = [curr[i] - along * unit_prev[i] for i in range(len(curr))]
    ortho_norm = _norm(ortho)
    if ortho_norm < 1e-12 * max(curr_norm, 1.0):
        return None
    unit_ortho = [v / ortho_norm for v in ortho]
    hessian_prev = [v / prev_norm for v in secant]
    auu = _dot(unit_prev, hessian_prev)
    auw = _dot(unit_ortho, hessian_prev)
    projected = _dot(curr, unit_ortho)
    if abs(projected) < 1e-18:
        return None
    aww = (
        float(gradient_curvature) - auu * along * along - 2.0 * auw * along * projected
    ) / (projected * projected)
    disc = (auu - aww) ** 2 + 4.0 * auw * auw
    if disc < 0.0 or not math.isfinite(disc):
        return None
    root = math.sqrt(disc)
    first = 0.5 * (auu + aww + root)
    second = 0.5 * (auu + aww - root)
    if not (math.isfinite(first) and math.isfinite(second)):
        return None
    return first, second

FUNCTION

poly_derivative

omnibias.core.line_search.poly_derivativeSource ↗

poly_derivative(coeffs: Sequence[float]) -> list[float]

Formal derivative of sum_k coeffs[k] s^k.

Parameters

Name	Type & default	Contract
`coeffs`positional-or-keyword	`Sequence[float]`Required	See the operation contract and implementation below.

Returnslist[float]

Executed regression · run model requires actual when verify

Full file, imports & fixtures ↗

def test_run_model_requires_actual_when_verify() -> None:
    with pytest.raises(ValueError, match="actual_fn"):
        run_model_line_search(_QUARTIC_DERIVS, config=JetLineSearchConfig(order=4))

python -m pytest "packages/omnibias-core/tests/test_line_search.py::test_run_model_requires_actual_when_verify" -q

Read the implementation

def poly_derivative(coeffs: Sequence[float]) -> list[float]:
    """Formal derivative of ``sum_k coeffs[k] s^k``."""
    if len(coeffs) <= 1:
        return [0.0]
    return [float(k) * float(coeffs[k]) for k in range(1, len(coeffs))]

FUNCTION

poly_eval

omnibias.core.line_search.poly_evalSource ↗

poly_eval(coeffs: Sequence[float], s: float) -> float

Horner evaluation of sum_k coeffs[k] s^k.

Parameters

Name	Type & default	Contract
`coeffs`positional-or-keyword	`Sequence[float]`Required	See the operation contract and implementation below.
`s`positional-or-keyword	`float`Required	See the operation contract and implementation below.

Returnsfloat

Executed regression · run model requires actual when verify

Full file, imports & fixtures ↗

def test_run_model_requires_actual_when_verify() -> None:
    with pytest.raises(ValueError, match="actual_fn"):
        run_model_line_search(_QUARTIC_DERIVS, config=JetLineSearchConfig(order=4))

python -m pytest "packages/omnibias-core/tests/test_line_search.py::test_run_model_requires_actual_when_verify" -q

Regression example · poly eval matches hand

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_poly_eval_matches_hand() -> None:
    coeffs = [1.0, -2.0, 3.0, -2.0, 2.0]
    # p(1) = 1 - 2 + 3 - 2 + 2 = 2
    assert poly_eval(coeffs, 1.0) == pytest.approx(2.0)
    # p(0.5) = 1 - 1 + 0.75 - 0.25 + 0.125 = 0.625 (spec backtracking point)
    assert poly_eval(coeffs, 0.5) == pytest.approx(0.625)

python -m pytest packages/omnibias-core/tests/test_line_search.py -k test_poly_eval_matches_hand -q

Read the implementation

def poly_eval(coeffs: Sequence[float], s: float) -> float:
    """Horner evaluation of ``sum_k coeffs[k] s^k``."""
    acc = 0.0
    for a in reversed(coeffs):
        acc = acc * s + float(a)
    return acc

FUNCTION

polynomial_wolfe

omnibias.core.polynomial_wolfeSource ↗

polynomial_wolfe(coeffs: Sequence[float], *, c1: float=0.0001, c2: float=0.9, bracket: tuple[float, float]=_DEFAULT_BRACKET) -> Interval | None

Hull of steps in bracket that satisfy the strong Wolfe conditions.

coeffs are Taylor coefficients of p(s) = sum a_k s^k. Armijo is p(s) <= p(0) + c1 s p'(0); strong curvature is |p'(s)| <= c2 |p'(0)|. The returned interval is the hull of the feasible components, or None if the feasible set is empty.

This is an exact statement about the *polynomial model*, not about the true phi.

Parameters

Name	Type & default	Contract
`coeffs`positional-or-keyword	`Sequence[float]`Required	See the operation contract and implementation below.
`c1`keyword-only	`float`Default: 0.0001	See the operation contract and implementation below.
`c2`keyword-only	`float`Default: 0.9	See the operation contract and implementation below.
`bracket`keyword-only	`tuple[float, float]`Default: _DEFAULT_BRACKET	See the operation contract and implementation below.

ReturnsInterval | None

Explicit validation & failure cases

When not 0.0 < c1 < 1.0, raises ValueError(f'c1 must be in (0, 1), got {c1}').
When not c1 < c2 < 1.0, raises ValueError(f'need c1 < c2 < 1, got {c1}, {c2}').
When hi < lo, raises ValueError(f'bracket must satisfy lo <= hi, got {bracket}').

These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.

Executed regression · polynomial wolfe contains descent step

Full file, imports & fixtures ↗

def test_polynomial_wolfe_contains_descent_step() -> None:
    coeffs = taylor_coeffs_from_derivatives(_QUARTIC_DERIVS)
    hull = polynomial_wolfe(coeffs, c1=1e-4, c2=0.9, bracket=(0.0, 1.0))
    assert hull is not None
    result = select_model_step(_QUARTIC_DERIVS, radius=1.0)
    assert hull.contains(result.step) or result.step == 0.0

python -m pytest "packages/omnibias-core/tests/test_line_search.py::test_polynomial_wolfe_contains_descent_step" -q

Read the implementation

def polynomial_wolfe(
    coeffs: Sequence[float],
    *,
    c1: float = 1e-4,
    c2: float = 0.9,
    bracket: tuple[float, float] = _DEFAULT_BRACKET,
) -> Interval | None:
    r"""Hull of steps in ``bracket`` that satisfy the strong Wolfe conditions.

    ``coeffs`` are Taylor coefficients of ``p(s) = sum a_k s^k``. Armijo is
    ``p(s) <= p(0) + c1 s p'(0)``; strong curvature is
    ``|p'(s)| <= c2 |p'(0)|``. The returned interval is the hull of the
    feasible components, or ``None`` if the feasible set is empty.

    This is an exact statement about the *polynomial model*, not about the
    true ``phi``.
    """
    if not 0.0 < c1 < 1.0:
        raise ValueError(f"c1 must be in (0, 1), got {c1}")
    if not c1 < c2 < 1.0:
        raise ValueError(f"need c1 < c2 < 1, got {c1}, {c2}")
    lo, hi = bracket
    if hi < lo:
        raise ValueError(f"bracket must satisfy lo <= hi, got {bracket}")
    p0 = poly_eval(coeffs, 0.0)
    dcoeffs = poly_derivative(coeffs)
    dp0 = poly_eval(dcoeffs, 0.0)
    # Armijo residual h(s) = p(s) - p0 - c1 s p'(0)
    h_coeffs = list(coeffs)
    h_coeffs[0] = h_coeffs[0] - p0
    if len(h_coeffs) < 2:
        h_coeffs.append(0.0)
    h_coeffs[1] = h_coeffs[1] - c1 * dp0
    # Curvature: p'(s) - c2 |p'(0)| = 0 and p'(s) + c2 |p'(0)| = 0
    bound = c2 * abs(dp0)
    crit = real_roots_on_interval(h_coeffs, lo, hi)
    if dcoeffs:
        upper = list(dcoeffs)
        upper[0] = dcoeffs[0] - bound
        crit.extend(real_roots_on_interval(upper, lo, hi))
        lower = list(dcoeffs)
        lower[0] = dcoeffs[0] + bound
        crit.extend(real_roots_on_interval(lower, lo, hi))
    cuts = _dedup_sorted([lo, hi, *crit])
    feasible: list[float] = []
    for i in range(len(cuts) - 1):
        a, b = cuts[i], cuts[i + 1]
        mid = 0.5 * (a + b)
        if _wolfe_holds(coeffs, mid, c1=c1, c2=c2):
            feasible.extend([a, b, mid])
    for x in cuts:
        if _wolfe_holds(coeffs, x, c1=c1, c2=c2):
            feasible.append(x)
    if not feasible:
        return None
    return Interval(min(feasible), max(feasible))

Other public import paths

omnibias.core.polynomial_wolfe
omnibias.core.line_search.polynomial_wolfe

FUNCTION

real_roots_on_interval

omnibias.core.line_search.real_roots_on_intervalSource ↗

real_roots_on_interval(coeffs: Sequence[float], lo: float, hi: float, *, n_grid: int=_GRID_POINTS) -> list[float]

Approximate real roots of a polynomial on [lo, hi] (grid + Newton).

Parameters

Name	Type & default	Contract
`coeffs`positional-or-keyword	`Sequence[float]`Required	See the operation contract and implementation below.
`lo`positional-or-keyword	`float`Required	See the operation contract and implementation below.
`hi`positional-or-keyword	`float`Required	See the operation contract and implementation below.
`n_grid`keyword-only	`int`Default: _GRID_POINTS	See the operation contract and implementation below.

Returnslist[float]

Explicit validation & failure cases

When hi < lo, raises ValueError(f'need lo <= hi, got {lo}, {hi}').
When n_grid < 2, raises ValueError(f'n_grid must be >= 2, got {n_grid}').

These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.

Executed regression · run model requires actual when verify

Full file, imports & fixtures ↗

def test_run_model_requires_actual_when_verify() -> None:
    with pytest.raises(ValueError, match="actual_fn"):
        run_model_line_search(_QUARTIC_DERIVS, config=JetLineSearchConfig(order=4))

python -m pytest "packages/omnibias-core/tests/test_line_search.py::test_run_model_requires_actual_when_verify" -q

Read the implementation

def real_roots_on_interval(
    coeffs: Sequence[float],
    lo: float,
    hi: float,
    *,
    n_grid: int = _GRID_POINTS,
) -> list[float]:
    """Approximate real roots of a polynomial on ``[lo, hi]`` (grid + Newton)."""
    if hi < lo:
        raise ValueError(f"need lo <= hi, got {lo}, {hi}")
    if n_grid < 2:
        raise ValueError(f"n_grid must be >= 2, got {n_grid}")
    if all(abs(float(c)) < 1e-30 for c in coeffs):
        return []
    span = hi - lo
    if span == 0.0:
        return [lo] if abs(poly_eval(coeffs, lo)) < 1e-12 else []
    roots: list[float] = []
    xs = [lo + span * i / n_grid for i in range(n_grid + 1)]
    vals = [poly_eval(coeffs, x) for x in xs]
    for i in range(len(xs) - 1):
        a, b = xs[i], xs[i + 1]
        fa, fb = vals[i], vals[i + 1]
        if abs(fa) < 1e-14:
            roots.append(a)
            continue
        if fa * fb < 0.0:
            mid = 0.5 * (a + b)
            found = _newton_real_root(coeffs, mid)
            if found is None:
                # Bisection fallback when Newton leaves the bracket.
                lo_b, hi_b = a, b
                flo = fa
                for _ in range(60):
                    mid_b = 0.5 * (lo_b + hi_b)
                    fmid = poly_eval(coeffs, mid_b)
                    if flo * fmid <= 0.0:
                        hi_b = mid_b
                    else:
                        lo_b = mid_b
                        flo = fmid
                found = 0.5 * (lo_b + hi_b)
            if lo - 1e-12 <= found <= hi + 1e-12:
                roots.append(min(max(found, lo), hi))
    return _dedup_sorted(roots)

FUNCTION

resolve_trust_radius

omnibias.core.line_search.resolve_trust_radiusSource ↗

resolve_trust_radius(config: JetLineSearchConfig, *, next_derivative_bound: float | None) -> tuple[float, bool]

Return (radius, certified) honouring the config and optional M.

Parameters

Name	Type & default	Contract
`config`positional-or-keyword	`JetLineSearchConfig`Required	See the operation contract and implementation below.
`next_derivative_bound`keyword-only	`float \| None`Required	See the operation contract and implementation below.

Returnstuple[float, bool]

Executed regression · run model requires actual when verify

Full file, imports & fixtures ↗

def test_run_model_requires_actual_when_verify() -> None:
    with pytest.raises(ValueError, match="actual_fn"):
        run_model_line_search(_QUARTIC_DERIVS, config=JetLineSearchConfig(order=4))

python -m pytest "packages/omnibias-core/tests/test_line_search.py::test_run_model_requires_actual_when_verify" -q

Regression example · explicit cap with bound is certified

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_explicit_cap_with_bound_is_certified() -> None:
    radius, certified = resolve_trust_radius(
        JetLineSearchConfig(order=4, trust_radius=1.0),
        next_derivative_bound=0.0,
    )
    assert certified
    assert radius == 1.0

python -m pytest packages/omnibias-core/tests/test_line_search.py -k test_explicit_cap_with_bound_is_certified -q

Read the implementation

def resolve_trust_radius(
    config: JetLineSearchConfig,
    *,
    next_derivative_bound: float | None,
) -> tuple[float, bool]:
    """Return ``(radius, certified)`` honouring the config and optional ``M``."""
    cap = float(config.max_step)
    if isinstance(config.trust_radius, float):
        cap = min(float(config.trust_radius), cap)
    if next_derivative_bound is None:
        return cap, False
    radius = certified_truncation_radius(
        next_derivative_bound,
        config.order,
        atol=config.remainder_atol,
        max_step=cap,
    )
    return radius, True

FUNCTION

run_model_line_search

omnibias.core.run_model_line_searchSource ↗

run_model_line_search(derivatives: Sequence[float], *, config: JetLineSearchConfig | None=None, next_derivative_bound: float | None=None, actual_fn: Callable[[float], float] | None=None, secant: GradientSecant | None=None) -> LineSearchResult

Shared driver: radius -> model step -> optional eigenstep -> verify.

Parameters

Name	Type & default	Contract
`derivatives`positional-or-keyword	`Sequence[float]`Required	See the operation contract and implementation below.
`config`keyword-only	`JetLineSearchConfig \| None`Default: None	See the operation contract and implementation below.
`next_derivative_bound`keyword-only	`float \| None`Default: None	See the operation contract and implementation below.
`actual_fn`keyword-only	`Callable[[float], float] \| None`Default: None	See the operation contract and implementation below.
`secant`keyword-only	`GradientSecant \| None`Default: None	See the operation contract and implementation below.

ReturnsLineSearchResult

Explicit validation & failure cases

When len(derivatives) < cfg.order + 1, raises ValueError(f'need derivatives 0..{cfg.order} ({cfg.order + 1} values), got {len(derivatives)}').
When actual_fn is None, raises ValueError('verify=True requires actual_fn').

These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.

Executed regression · run model requires actual when verify

Full file, imports & fixtures ↗

def test_run_model_requires_actual_when_verify() -> None:
    with pytest.raises(ValueError, match="actual_fn"):
        run_model_line_search(_QUARTIC_DERIVS, config=JetLineSearchConfig(order=4))

python -m pytest "packages/omnibias-core/tests/test_line_search.py::test_run_model_requires_actual_when_verify" -q

Regression example · polynomial wolfe contains descent step

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_polynomial_wolfe_contains_descent_step() -> None:
    coeffs = taylor_coeffs_from_derivatives(_QUARTIC_DERIVS)
    hull = polynomial_wolfe(coeffs, c1=1e-4, c2=0.9, bracket=(0.0, 1.0))
    assert hull is not None
    result = select_model_step(_QUARTIC_DERIVS, radius=1.0)
    assert hull.contains(result.step) or result.step == 0.0

python -m pytest packages/omnibias-core/tests/test_line_search.py -k test_polynomial_wolfe_contains_descent_step -q

Read the implementation

def run_model_line_search(
    derivatives: Sequence[float],
    *,
    config: JetLineSearchConfig | None = None,
    next_derivative_bound: float | None = None,
    actual_fn: Callable[[float], float] | None = None,
    secant: GradientSecant | None = None,
) -> LineSearchResult:
    """Shared driver: radius -> model step -> optional eigenstep -> verify."""
    cfg = config if config is not None else JetLineSearchConfig()
    if len(derivatives) < cfg.order + 1:
        raise ValueError(
            f"need derivatives 0..{cfg.order} ({cfg.order + 1} values), "
            f"got {len(derivatives)}"
        )
    used = [float(v) for v in derivatives[: cfg.order + 1]]
    radius, certified = resolve_trust_radius(
        cfg, next_derivative_bound=next_derivative_bound
    )
    result = select_model_step(used, radius=radius, config=cfg)
    if secant is not None and cfg.order >= 2:
        picked = select_secant_eigenstep(used, secant, radius=radius)
        if picked is not None:
            step, consumed = picked
            coeffs = taylor_coeffs_from_derivatives(used)
            result = LineSearchResult(
                step=step,
                model_value=poly_eval(coeffs, step),
                actual_value=None,
                model_error=None,
                truncation_radius=float(radius),
                fell_back=False,
                wolfe_ok=_wolfe_holds(coeffs, step, c1=cfg.wolfe_c1, c2=cfg.wolfe_c2),
                truncation_certified=False,
                isolated_root=False,
                consumed_curvature=consumed,
            )
    result = LineSearchResult(
        step=result.step,
        model_value=result.model_value,
        actual_value=result.actual_value,
        model_error=result.model_error,
        truncation_radius=result.truncation_radius,
        fell_back=result.fell_back,
        wolfe_ok=result.wolfe_ok,
        truncation_certified=certified,
        isolated_root=result.isolated_root,
        consumed_curvature=result.consumed_curvature,
    )
    if cfg.verify:
        if actual_fn is None:
            raise ValueError("verify=True requires actual_fn")
        result = apply_verification(result, actual_fn, start_value=used[0])
        result = LineSearchResult(
            step=result.step,
            model_value=result.model_value,
            actual_value=result.actual_value,
            model_error=result.model_error,
            truncation_radius=result.truncation_radius,
            fell_back=result.fell_back,
            wolfe_ok=result.wolfe_ok,
            truncation_certified=certified,
            isolated_root=result.isolated_root,
            consumed_curvature=result.consumed_curvature,
        )
    return result

Other public import paths

omnibias.core.run_model_line_search
omnibias.core.line_search.run_model_line_search

FUNCTION

select_model_step

omnibias.core.select_model_stepSource ↗

select_model_step(derivatives: Sequence[float], *, radius: float, config: JetLineSearchConfig | None=None) -> LineSearchResult

Minimise the degree-N Taylor model on [0, radius].

Stationary points of the model are roots of p'. Certified isolation is attempted when config.isolate_roots is true; a unique interval Newton cell upgrades isolated_root. The returned step is never negative and never larger than radius.

Parameters

Name	Type & default	Contract
`derivatives`positional-or-keyword	`Sequence[float]`Required	See the operation contract and implementation below.
`radius`keyword-only	`float`Required	See the operation contract and implementation below.
`config`keyword-only	`JetLineSearchConfig \| None`Default: None	See the operation contract and implementation below.

ReturnsLineSearchResult

Explicit validation & failure cases

When radius < 0.0 or not math.isfinite(radius), raises ValueError(f'radius must be a finite number >= 0, got {radius}').

These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.

Executed regression · run model requires actual when verify

Full file, imports & fixtures ↗

def test_run_model_requires_actual_when_verify() -> None:
    with pytest.raises(ValueError, match="actual_fn"):
        run_model_line_search(_QUARTIC_DERIVS, config=JetLineSearchConfig(order=4))

python -m pytest "packages/omnibias-core/tests/test_line_search.py::test_run_model_requires_actual_when_verify" -q

Regression example · polynomial wolfe contains descent step

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_polynomial_wolfe_contains_descent_step() -> None:
    coeffs = taylor_coeffs_from_derivatives(_QUARTIC_DERIVS)
    hull = polynomial_wolfe(coeffs, c1=1e-4, c2=0.9, bracket=(0.0, 1.0))
    assert hull is not None
    result = select_model_step(_QUARTIC_DERIVS, radius=1.0)
    assert hull.contains(result.step) or result.step == 0.0

python -m pytest packages/omnibias-core/tests/test_line_search.py -k test_polynomial_wolfe_contains_descent_step -q

Read the implementation

def select_model_step(
    derivatives: Sequence[float],
    *,
    radius: float,
    config: JetLineSearchConfig | None = None,
) -> LineSearchResult:
    """Minimise the degree-``N`` Taylor model on ``[0, radius]``.

    Stationary points of the model are roots of ``p'``. Certified isolation
    is attempted when ``config.isolate_roots`` is true; a unique interval
    Newton cell upgrades ``isolated_root``. The returned step is never
    negative and never larger than ``radius``.
    """
    cfg = config if config is not None else JetLineSearchConfig()
    if radius < 0.0 or not math.isfinite(radius):
        raise ValueError(f"radius must be a finite number >= 0, got {radius}")
    coeffs = taylor_coeffs_from_derivatives(derivatives)
    p0 = poly_eval(coeffs, 0.0)
    dcoeffs = poly_derivative(coeffs)
    ddcoeffs = poly_derivative(dcoeffs)
    candidates = [0.0, float(radius)]
    isolated = False
    if cfg.isolate_roots and radius > 0.0:
        cells = isolate_real_roots(dcoeffs, 0.0, float(radius))
        if cells:
            isolated = True
            candidates.extend(cell.mid for cell in cells)
    candidates.extend(real_roots_on_interval(dcoeffs, 0.0, float(radius)))
    best_s = 0.0
    best_p = p0
    for raw in _dedup_sorted(candidates):
        s = min(max(raw, 0.0), float(radius))
        ps = poly_eval(coeffs, s)
        if not math.isfinite(ps):
            continue
        if cfg.require_wolfe and not _wolfe_holds(
            coeffs, s, c1=cfg.wolfe_c1, c2=cfg.wolfe_c2
        ):
            continue
        # Prefer local minima; still accept a boundary if it is the lowest.
        curvature = poly_eval(ddcoeffs, s) if ddcoeffs else 0.0
        if s not in (0.0, float(radius)) and curvature < -1e-14:
            continue
        if ps < best_p - 1e-16 or (abs(ps - best_p) <= 1e-16 and s < best_s):
            best_s = s
            best_p = ps
    wolfe = _wolfe_holds(coeffs, best_s, c1=cfg.wolfe_c1, c2=cfg.wolfe_c2)
    return LineSearchResult(
        step=best_s,
        model_value=best_p,
        actual_value=None,
        model_error=None,
        truncation_radius=float(radius),
        fell_back=False,
        wolfe_ok=wolfe,
        truncation_certified=False,
        isolated_root=isolated,
    )

Other public import paths

omnibias.core.select_model_step
omnibias.core.line_search.select_model_step

FUNCTION

select_secant_eigenstep

omnibias.core.line_search.select_secant_eigenstepSource ↗

select_secant_eigenstep(derivatives: Sequence[float], secant: GradientSecant, *, radius: float) -> tuple[float, float] | None

Inverse-eigenvalue step on the secant plane, or None.

The single-ray minimizer stays select_model_step. This schedule is the multi-step partner: after one previous steepest step, unused positive eigenvalues of the plane Hessian become candidate steps 1/λ inside (0, radius]. A candidate is eligible only when the directional Taylor model decreases and the current direction is -gradient. The lowest model value wins. phi''(0) is the jet curvature g^T H g.

Parameters

Name	Type & default	Contract
`derivatives`positional-or-keyword	`Sequence[float]`Required	See the operation contract and implementation below.
`secant`positional-or-keyword	`GradientSecant`Required	See the operation contract and implementation below.
`radius`keyword-only	`float`Required	See the operation contract and implementation below.

Returnstuple[float, float] | None

Executed regression · secant ignored when direction is not negative gradient

Full file, imports & fixtures ↗

def test_secant_ignored_when_direction_is_not_negative_gradient() -> None:
    derivs = (1.0, -2.0, 6.0, -12.0, 48.0)
    plain = select_model_step(
        derivs,
        radius=1.0,
        config=JetLineSearchConfig(order=4, verify=False),
    )
    secant = GradientSecant(
        previous_gradient=(1.0, 0.0),
        previous_step=0.2,
        current_gradient=(0.0, 1.0),
        direction=(1.0, 0.0),
        used_curvatures=(),
    )
    result = run_model_line_search(
        derivs,
        config=JetLineSearchConfig(order=4, trust_radius=1.0, verify=False),
        secant=secant,
    )
    assert result.consumed_curvature is None
    assert result.step == pytest.approx(plain.step)

python -m pytest "packages/omnibias-core/tests/test_line_search.py::test_secant_ignored_when_direction_is_not_negative_gradient" -q

Read the implementation

def select_secant_eigenstep(
    derivatives: Sequence[float],
    secant: GradientSecant,
    *,
    radius: float,
) -> tuple[float, float] | None:
    """Inverse-eigenvalue step on the secant plane, or ``None``.

    The single-ray minimizer stays :func:`select_model_step`. This schedule
    is the multi-step partner: after one previous steepest step, unused
    positive eigenvalues of the plane Hessian become candidate steps
    ``1/λ`` inside ``(0, radius]``. A candidate is eligible only when the
    directional Taylor model decreases and the current direction is
    ``-gradient``. The lowest model value wins. ``phi''(0)`` is the jet
    curvature ``g^T H g``.
    """
    if radius <= 0.0 or not math.isfinite(radius):
        return None
    if len(derivatives) < 3:
        return None
    if not _direction_is_negative_gradient(secant.direction, secant.current_gradient):
        return None
    curvature = float(derivatives[2])
    spectrum = plane_hessian_eigenvalues(
        secant.previous_gradient,
        secant.previous_step,
        secant.current_gradient,
        curvature,
    )
    if spectrum is None:
        return None
    coeffs = taylor_coeffs_from_derivatives(derivatives)
    base = poly_eval(coeffs, 0.0)
    best: tuple[float, float, float] | None = None
    for lam in spectrum:
        if lam <= 1e-14 or _curvature_consumed(lam, secant.used_curvatures):
            continue
        step = 1.0 / lam
        if not (0.0 < step <= float(radius)) or not math.isfinite(step):
            continue
        model = poly_eval(coeffs, step)
        if not math.isfinite(model) or model >= base - 1e-18:
            continue
        if best is None or model < best[0]:
            best = (model, step, lam)
    if best is None:
        return None
    return best[1], best[2]

FUNCTION

taylor_coeffs_from_derivatives

omnibias.core.taylor_coeffs_from_derivativesSource ↗

taylor_coeffs_from_derivatives(derivatives: Sequence[float]) -> list[float]

Convert phi^(k)(0) into Taylor coefficients a_k = phi^(k)(0) / k!.

Parameters

Name	Type & default	Contract
`derivatives`positional-or-keyword	`Sequence[float]`Required	See the operation contract and implementation below.

Returnslist[float]

Explicit validation & failure cases

When not derivatives, raises ValueError('derivatives must be non-empty').
When not math.isfinite(val), raises ValueError(f'derivative[{k}] must be finite, got {raw!r}').

These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.

Executed regression · boundary layer local scale

Full file, imports & fixtures ↗

def test_boundary_layer_local_scale() -> None:
    scale = local_scale_from_derivatives(_BL_DERIVS)
    assert scale == pytest.approx(_BL_SCALE, rel=1e-12)

python -m pytest "packages/omnibias-core/tests/test_refine.py::test_boundary_layer_local_scale" -q

Regression example · poly eval matches hand

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_poly_eval_matches_hand() -> None:
    coeffs = [1.0, -2.0, 3.0, -2.0, 2.0]
    # p(1) = 1 - 2 + 3 - 2 + 2 = 2
    assert poly_eval(coeffs, 1.0) == pytest.approx(2.0)
    # p(0.5) = 1 - 1 + 0.75 - 0.25 + 0.125 = 0.625 (spec backtracking point)
    assert poly_eval(coeffs, 0.5) == pytest.approx(0.625)

python -m pytest packages/omnibias-core/tests/test_line_search.py -k test_poly_eval_matches_hand -q

Read the implementation

def taylor_coeffs_from_derivatives(derivatives: Sequence[float]) -> list[float]:
    r"""Convert ``phi^(k)(0)`` into Taylor coefficients ``a_k = phi^(k)(0) / k!``."""
    if not derivatives:
        raise ValueError("derivatives must be non-empty")
    out: list[float] = []
    fact = 1
    for k, raw in enumerate(derivatives):
        if k >= 1:
            fact *= k
        val = float(raw)
        if not math.isfinite(val):
            raise ValueError(f"derivative[{k}] must be finite, got {raw!r}")
        out.append(val / float(fact))
    return out

Other public import paths

omnibias.core.taylor_coeffs_from_derivatives
omnibias.core.line_search.taylor_coeffs_from_derivatives

← Package overview Runnable learning examples →

omnibias.core.line_search

GradientSecant​

Parameters

Fields & methods

JetLineSearchConfig​

Parameters

Fields & methods

LineSearchResult​

Parameters

Fields & methods

apply_verification​

Parameters

certified_truncation_radius​

Parameters

derivatives_from_taylor_coeffs​

Parameters

factorial_int​

Parameters

interval_poly_eval​

Parameters

isolate_real_roots​

Parameters

lagrange_remainder_bound​

Parameters

plane_hessian_eigenvalues​

Parameters

poly_derivative​

Parameters

poly_eval​

Parameters

polynomial_wolfe​

Parameters

real_roots_on_interval​

Parameters

resolve_trust_radius​

Parameters

run_model_line_search​

Parameters

select_model_step​

Parameters

select_secant_eigenstep​

Parameters

taylor_coeffs_from_derivatives​

Parameters

GradientSecant

JetLineSearchConfig

LineSearchResult

apply_verification

certified_truncation_radius

derivatives_from_taylor_coeffs

factorial_int

interval_poly_eval

isolate_real_roots

lagrange_remainder_bound

plane_hessian_eigenvalues

poly_derivative

poly_eval

polynomial_wolfe

real_roots_on_interval

resolve_trust_radius

run_model_line_search

select_model_step

select_secant_eigenstep

taylor_coeffs_from_derivatives