Skip to content

Pathfinder

Pathfinder (Zhang et al., 2022b) is a variational method that follows an L-BFGS optimization path of the unconstrained log joint, forms a normal approximation at each iterate from the quasi-Newton inverse-Hessian estimate, and keeps the one with the largest estimated evidence lower bound (ELBO). Multi-path Pathfinder runs several independent paths and resamples their pooled draws with Pareto-smoothed importance weights (Vehtari et al., 2024). The formal statement gives the approximation, the ELBO estimate, and the resampling step.

Pathfinder takes CmdStan's argument names. It scores the same Jacobian-corrected PotentialFn as the Hamiltonian kernels, over the latents one recorded run reaches. Its result PathfinderDraws keeps the layout of independent draws, one pseudo-chain of num_samples draws, with each draw's target and approximation log densities (Stan's lp__ and lp_approx__), the path it came from, each path's ELBO and stopping reason, and the Pareto shape of the pooled importance ratios. PathfinderMethod applies it to a bound model, and fit(..., algorithm="pathfinder") to a formula.

import torch
from quivers.inference import Pathfinder
from quivers.modeling import Model, PathfinderMethod

source = """object Row : FinSet _
object Out : Real 1
program regression(x : Tensor[Real]([Row]), y : Tensor[Real]([Row])) : Row -> Out
    sample b <- Normal(loc=0.0, scale=1.0)
    let mu = b * x
    observe y : Row <- Normal(loc=mu, scale=1.0)
    return b
export regression
"""
x = torch.linspace(-1.0, 1.0, 12)
y = 0.6 * x + 0.1 * torch.sin(7.0 * x)
fitted = Model(source).fit(
    {"x": x, "y": y},
    method=PathfinderMethod(
        pathfinder=Pathfinder(num_paths=2, num_draws=200, num_psis_draws=400, seed=1)
    ),
)
draws = fitted.posterior
assert draws.samples["b"].shape == (1, 400)
assert draws.num_paths == 2 and draws.resampled

Cost per path: the L-BFGS evaluations, then for each of the L iterates O(N J^2 + J^3) to factor the approximation by a thin QR and a Cholesky decomposition, and K log-density evaluations at O(N J + J^2) per draw for the ELBO, with N the unconstrained dimension, J the history size, and K the ELBO draws. No N-by-N matrix is formed. Paths run one after another.

The line search enforces the strong Wolfe conditions with cubic interpolation (Nocedal and Wright, 2006). Near-zero Wolfe constants make it an exact line search, under which the approximation on a Gaussian target is the target itself once the history size reaches the dimension.

pathfinder

Pathfinder variational inference over the unconstrained log joint.

Pathfinder [@zhang2022pathfinder] runs L-BFGS on the Jacobian-corrected unconstrained log density of a program from a random initial point, forms a normal approximation at every iterate of the optimization path from the iterate, its gradient, and the L-BFGS inverse-Hessian estimate, selects the approximation with the largest Monte Carlo estimate of the evidence lower bound (ELBO), and draws from it. Multi-path Pathfinder runs several independent paths and resamples their pooled draws with replacement, with probabilities given by Pareto-smoothed importance weights.

The pieces follow the paper's algorithms:

  • lbfgs_path: L-BFGS (Algorithm 7) with a strong Wolfe line search and Stan's convergence tests, recording every iterate and gradient;
  • recover_diagonal: the diagonal inverse-Hessian estimate of Gilbert and Lemarechal along the path (Algorithm 3);
  • bfgs_approximation: the compact BFGS representation of [@byrd1994representations] at one iterate and its factorization by a thin QR and a Cholesky decomposition (Algorithm 4);
  • single_path: ELBO selection and draws (Algorithm 1);
  • psis_log_weights: Pareto-smoothed importance sampling as the loo package computes it [@vehtari2024psis];
  • Pathfinder: the driver over a compiled program (Algorithm 2), whose result PathfinderDraws the fit, prediction, and artifact machinery reads as independent draws.

Termination

Termination = Literal['absolute objective', 'relative objective', 'absolute gradient', 'relative gradient', 'parameter change', 'maximum iterations', 'line search failed']

Why an L-BFGS path stopped.

InitialValues

InitialValues = Mapping[str, Tensor | float]

Natural-scale starting values keyed by latent site.

PathfinderTarget

Bases: Protocol

A log density on a flat unconstrained vector.

PotentialFn is one, through Pathfinder.run; a test target can be any object with these members.

dtype property

dtype: dtype

Floating type the density is evaluated in.

log_density

log_density(z: Tensor) -> Tensor

Return the scalar log density at z.

PARAMETER DESCRIPTION
z

Position, shape (N,), in dtype.

TYPE: Tensor

RETURNS DESCRIPTION
Tensor

Scalar log density, -inf outside the support.

Source code in src/quivers/inference/pathfinder.py
def log_density(self, z: torch.Tensor) -> torch.Tensor:
    """Return the scalar log density at ``z``.

    Parameters
    ----------
    z : torch.Tensor
        Position, shape ``(N,)``, in `dtype`.

    Returns
    -------
    torch.Tensor
        Scalar log density, ``-inf`` outside the support.
    """
    ...

value_and_grad

value_and_grad(z: Tensor) -> tuple[Tensor, Tensor]

Return the log density and its gradient at z.

PARAMETER DESCRIPTION
z

Position, shape (N,), in dtype.

TYPE: Tensor

RETURNS DESCRIPTION
tuple[Tensor, Tensor]

Scalar log density and gradient of shape (N,).

Source code in src/quivers/inference/pathfinder.py
def value_and_grad(self, z: torch.Tensor) -> tuple[torch.Tensor, torch.Tensor]:
    """Return the log density and its gradient at ``z``.

    Parameters
    ----------
    z : torch.Tensor
        Position, shape ``(N,)``, in `dtype`.

    Returns
    -------
    tuple[torch.Tensor, torch.Tensor]
        Scalar log density and gradient of shape ``(N,)``.
    """
    ...

LBFGSSettings didactic-model

LBFGSSettings(*, history_size: int = 5, max_iterations: int = 1000, init_alpha: float = 0.001, tol_obj: float = 1e-12, tol_rel_obj: float = 10000.0, tol_grad: float = 1e-08, tol_rel_grad: float = 10000000.0, tol_param: float = 1e-08, wolfe_c1: float = 0.0001, wolfe_c2: float = 0.9, max_line_search: int = 40)

Bases: ValueModel

L-BFGS settings, named as CmdStan's optimizer and Pathfinder arguments.

PARAMETER DESCRIPTION
history_size

Number of position and gradient updates kept (CmdStan history_size, default 5).

TYPE: int DEFAULT: 5

max_iterations

Maximum L-BFGS iterations (max_lbfgs_iters, default 1000).

TYPE: int DEFAULT: 1000

init_alpha

Step length tried first on the first iteration (init_alpha).

TYPE: float DEFAULT: 0.001

tol_obj

Stop when the objective changes by less than this (tol_obj).

TYPE: float DEFAULT: 1e-12

tol_rel_obj

Stop when the relative objective change is below this many machine epsilons (tol_rel_obj).

TYPE: float DEFAULT: 10000.0

tol_grad

Stop when the gradient norm is below this (tol_grad).

TYPE: float DEFAULT: 1e-08

tol_rel_grad

Stop when g' H g / max(|f|, 1) is below this many machine epsilons, with H the inverse-Hessian estimate (tol_rel_grad).

TYPE: float DEFAULT: 10000000.0

tol_param

Stop when the position moves by less than this (tol_param).

TYPE: float DEFAULT: 1e-08

wolfe_c1

Sufficient decrease constant of the strong Wolfe conditions.

TYPE: float DEFAULT: 0.0001

wolfe_c2

Curvature constant of the strong Wolfe conditions. Near zero, the line search returns the exact minimizer along the direction, which cubic interpolation reaches in one step on a quadratic.

TYPE: float DEFAULT: 0.9

max_line_search

Maximum function evaluations of one line search.

TYPE: int DEFAULT: 40

OptimizationPath didactic-model

OptimizationPath(*, positions: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), log_densities: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), gradients: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), termination: Termination, num_evaluations: int)

Bases: ValueModel

The iterates of one L-BFGS run on -log p.

PARAMETER DESCRIPTION
positions

Iterates theta(0..L), float64, shape (L + 1, N).

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

log_densities

log p at each iterate, shape (L + 1,).

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

gradients

grad log p at each iterate, shape (L + 1, N).

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

termination

Why the run stopped.

TYPE: Termination

num_evaluations

Log-density and gradient evaluations, line searches included.

TYPE: int

num_iterations property

num_iterations: int

Accepted L-BFGS steps L.

DiagonalRecovery didactic-model

DiagonalRecovery(*, alphas: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), accepted: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), steps: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), gradient_steps: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY))

Bases: ValueModel

Output of the paper's α-RECOVER (Algorithm 3).

PARAMETER DESCRIPTION
alphas

Diagonal initial inverse-Hessian estimate after each step, shape (L, N).

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

accepted

Boolean, whether step l enters the inverse-Hessian estimates, shape (L,).

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

steps

Position updates s(l) = theta(l) - theta(l-1), shape (L, N).

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

gradient_steps

Updates z(l) = grad log p(theta(l-1)) - grad log p(theta(l)) of the gradient of -log p, shape (L, N).

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

NormalApproximation didactic-model

NormalApproximation(*, mean: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), alpha: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), q: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), cholesky: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), beta: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), gamma: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), log_det: float)

Bases: ValueModel

The normal approximation at one iterate, in factored form.

The covariance is Sigma = diag(alpha) + beta gamma beta' (the compact BFGS inverse-Hessian estimate) and is held through the thin QR factorization Q R = diag(alpha)^(-1/2) beta and the Cholesky factor L of I + R gamma R', so Sigma = T T' with T = diag(alpha)^(1/2) (Q L Q' + I - Q Q'). Sampling and scoring cost O(N J + J^2) per draw for history size J.

PARAMETER DESCRIPTION
mean

theta + Sigma grad log p(theta), shape (N,).

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

alpha

Diagonal part, shape (N,).

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

q

Orthonormal factor, shape (N, k) with k = min(N, 2 J).

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

cholesky

Lower Cholesky factor of I + R gamma R', shape (k, k).

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

beta

[diag(alpha) Z, S], shape (N, 2 J).

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

gamma

Middle matrix of the compact representation, shape (2 J, 2 J).

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

log_det

log |Sigma|.

TYPE: float

sample

sample(noise: Tensor) -> Tensor

Map standard normal noise to draws (Algorithm 4, line 11).

PARAMETER DESCRIPTION
noise

Standard normal u, shape (M, N).

TYPE: Tensor

RETURNS DESCRIPTION
Tensor

mean + diag(alpha)^(1/2) (Q (L - I) Q' u + u), shape (M, N).

Source code in src/quivers/inference/pathfinder.py
def sample(self, noise: torch.Tensor) -> torch.Tensor:
    """Map standard normal noise to draws (Algorithm 4, line 11).

    Parameters
    ----------
    noise : torch.Tensor
        Standard normal ``u``, shape ``(M, N)``.

    Returns
    -------
    torch.Tensor
        ``mean + diag(alpha)^(1/2) (Q (L - I) Q' u + u)``, shape ``(M, N)``.
    """
    rotated = noise @ self.q
    eye = torch.eye(self.cholesky.shape[0], dtype=torch.float64)
    lifted = (rotated @ (self.cholesky - eye).T) @ self.q.T + noise
    return self.mean + lifted * self.alpha.sqrt()

log_prob

log_prob(draws: Tensor) -> Tensor

Score draws under the approximation.

The standard normal coordinates are recovered with the inverse of I + Q (L - I) Q', which is I + Q (L^(-1) - I) Q', so the cost is O(N J + J^2) per draw.

PARAMETER DESCRIPTION
draws

Points, shape (M, N).

TYPE: Tensor

RETURNS DESCRIPTION
Tensor

Log densities, shape (M,).

Source code in src/quivers/inference/pathfinder.py
def log_prob(self, draws: torch.Tensor) -> torch.Tensor:
    """Score draws under the approximation.

    The standard normal coordinates are recovered with the inverse of
    ``I + Q (L - I) Q'``, which is ``I + Q (L^(-1) - I) Q'``, so the cost
    is O(N J + J^2) per draw.

    Parameters
    ----------
    draws : torch.Tensor
        Points, shape ``(M, N)``.

    Returns
    -------
    torch.Tensor
        Log densities, shape ``(M,)``.
    """
    whitened = (draws - self.mean) / self.alpha.sqrt()
    rotated = whitened @ self.q
    solved = torch.linalg.solve_triangular(self.cholesky, rotated.T, upper=False).T
    noise = whitened + (solved - rotated) @ self.q.T
    dim = draws.shape[-1]
    return -0.5 * (
        self.log_det + (noise * noise).sum(-1) + dim * math.log(2 * math.pi)
    )

covariance

covariance() -> Tensor

Form the dense covariance; O(N^2 J), for inspection and tests.

RETURNS DESCRIPTION
Tensor

diag(alpha) + beta gamma beta', shape (N, N).

Source code in src/quivers/inference/pathfinder.py
def covariance(self) -> torch.Tensor:
    """Form the dense covariance; O(N^2 J), for inspection and tests.

    Returns
    -------
    torch.Tensor
        ``diag(alpha) + beta gamma beta'``, shape ``(N, N)``.
    """
    return torch.diag(self.alpha) + self.beta @ self.gamma @ self.beta.T

SinglePath didactic-model

SinglePath(*, path: OptimizationPath = field(opaque=True, extras=OPAQUE_BY_IDENTITY), elbo: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), best_iteration: int, draws: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), log_density: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), log_approx: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), failed: bool)

Bases: ValueModel

One Pathfinder run (Algorithm 1).

PARAMETER DESCRIPTION
path

The L-BFGS iterates.

TYPE: OptimizationPath DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

elbo

ELBO estimate at iterates 1..L, -inf where the approximation is not positive definite or a draw has a nonfinite log density.

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

best_iteration

Iterate l* of the largest ELBO, zero when the path failed.

TYPE: int

draws

Unconstrained draws from the selected approximation, shape (M, N).

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

log_density

Target log density at each draw (NaN without calculate_lp).

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

log_approx

Approximation log density at each draw.

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

failed

Whether no iterate gave a usable approximation. A failed path keeps its last iterate as its draws with log_approx = inf, so that it receives zero importance weight.

TYPE: bool

PathfinderDraws didactic-model

PathfinderDraws(*, samples: Mapping[str, Tensor] = field(opaque=True, extras=OPAQUE_BY_IDENTITY), num_samples: int, log_density: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), log_approx: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), path_index: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), path_elbo: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), path_iterations: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), path_best_iteration: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), path_termination: tuple[str, ...] = (), num_evaluations: Tensor = field(opaque=True, extras=OPAQUE_BY_IDENTITY), pareto_k: float = nan, resampled: bool = False, single_paths: Mapping[str, Tensor] = field(default_factory=dict, opaque=True, extras=OPAQUE_BY_IDENTITY))

Bases: PriorDraws

Pathfinder draws, read by the fit machinery as independent draws.

The samples share PriorDraws's layout (1, draw, *event_shape): importance-resampled draws are not a Markov chain and carry no chain diagnostics. draw_provenance names them variational.

PARAMETER DESCRIPTION
samples

Constrained draws (1, draw, *event_shape).

TYPE: Mapping[str, Tensor] DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

num_samples

Number of draws.

TYPE: int

log_density

Unconstrained log joint (Stan's lp__) at each draw, shape (1, draw); NaN without calculate_lp.

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

log_approx

Approximation log density (lp_approx__), shape (1, draw).

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

path_index

Path each draw came from, shape (draw,).

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

path_elbo

Largest ELBO estimate of each path, -inf for a failed path.

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

path_iterations

L-BFGS iterations of each path.

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

path_best_iteration

Selected iterate of each path.

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

path_termination

Why each path's L-BFGS run stopped.

TYPE: tuple[str, ...] DEFAULT: ()

num_evaluations

Log-density evaluations of each path.

TYPE: Tensor DEFAULT: field(opaque=True, extras=OPAQUE_BY_IDENTITY)

pareto_k

Pareto shape of the pooled importance ratios; NaN without resampling.

TYPE: float DEFAULT: nan

resampled

Whether the draws were importance resampled.

TYPE: bool DEFAULT: False

single_paths

With save_single_paths, each path's draws (path, draw, ...) before resampling; empty otherwise.

TYPE: Mapping[str, Tensor] DEFAULT: field(default_factory=dict, opaque=True, extras=OPAQUE_BY_IDENTITY)

num_paths property

num_paths: int

Number of Pathfinder runs.

Pathfinder didactic-model

Pathfinder(*, num_paths: int = 4, num_draws: int = 1000, num_psis_draws: int = 1000, num_elbo_draws: int = 25, psis_resample: bool = True, calculate_lp: bool = True, save_single_paths: bool = False, lbfgs: LBFGSSettings = field(default_factory=LBFGSSettings), init_radius: float = 2.0, init_strategy: Literal['uniform', 'zero'] = 'uniform', initial_values: InitialValues | tuple[InitialValues, ...] | None = field(default=None, opaque=True, extras=OPAQUE_BY_IDENTITY), seed: int = 0)

Bases: ValueModel

Single- and multi-path Pathfinder over a compiled program.

Parameter names follow CmdStan's pathfinder method; brms maps chains to num_paths. With one path the draws are that path's num_draws draws. With several, the num_paths * num_draws pooled draws are resampled with replacement to num_psis_draws draws with Pareto-smoothed importance weights p / q (Algorithm 2), unless psis_resample or calculate_lp is False, in which case every pooled draw is returned. Paths run one after another, each from its own stream derived from seed.

PARAMETER DESCRIPTION
num_paths

Independent runs I (CmdStan num_paths, default 4).

TYPE: int DEFAULT: 4

num_draws

Draws per path M (num_draws; cmdstanr single_path_draws).

TYPE: int DEFAULT: 1000

num_psis_draws

Draws after resampling R (num_psis_draws; cmdstanr draws).

TYPE: int DEFAULT: 1000

num_elbo_draws

Draws per ELBO estimate K (num_elbo_draws, default 25).

TYPE: int DEFAULT: 25

psis_resample

Whether to importance resample across paths.

TYPE: bool DEFAULT: True

calculate_lp

Whether to evaluate the target at the returned draws.

TYPE: bool DEFAULT: True

save_single_paths

Whether to keep each path's draws in the result.

TYPE: bool DEFAULT: False

lbfgs

L-BFGS settings (history_size, max_lbfgs_iters, init_alpha, and the tolerances).

TYPE: LBFGSSettings DEFAULT: field(default_factory=LBFGSSettings)

init_radius

Initial points are uniform on (-init_radius, init_radius) in every unconstrained coordinate (CmdStan's init radius).

TYPE: float DEFAULT: 2.0

init_strategy

Uniform initial points, or the origin.

TYPE: ('uniform', 'zero') DEFAULT: "uniform"

initial_values

Natural-scale values replacing the named sites' initial coordinates, shared or one mapping per path.

TYPE: Mapping or Sequence of Mapping or None DEFAULT: field(default=None, opaque=True, extras=OPAQUE_BY_IDENTITY)

seed

Base seed of every path's streams.

TYPE: int DEFAULT: 0

run

run(model: MonadicProgram, x: Tensor, observations: dict[str, Tensor]) -> PathfinderDraws

Run Pathfinder on a program's unconstrained log joint.

The latents are those one recorded run of the program reaches, as for MCMC, and the target is the same Jacobian-corrected PotentialFn the Hamiltonian kernels use.

PARAMETER DESCRIPTION
model

The program.

TYPE: MonadicProgram

x

One-row program input.

TYPE: Tensor

observations

Observed values and data.

TYPE: dict[str, Tensor]

RETURNS DESCRIPTION
PathfinderDraws

Constrained draws and per-path diagnostics.

RAISES DESCRIPTION
ValueError

If the input has several rows, the data lie outside their support, an initial value is invalid, an initial point has a nonfinite log density, or every path fails.

Source code in src/quivers/inference/pathfinder.py
def run(
    self,
    model: MonadicProgram,
    x: torch.Tensor,
    observations: dict[str, torch.Tensor],
) -> PathfinderDraws:
    """Run Pathfinder on a program's unconstrained log joint.

    The latents are those one recorded run of the program reaches, as
    for `MCMC`, and the target is the same Jacobian-corrected
    `PotentialFn` the Hamiltonian kernels use.

    Parameters
    ----------
    model : MonadicProgram
        The program.
    x : torch.Tensor
        One-row program input.
    observations : dict[str, torch.Tensor]
        Observed values and data.

    Returns
    -------
    PathfinderDraws
        Constrained draws and per-path diagnostics.

    Raises
    ------
    ValueError
        If the input has several rows, the data lie outside their
        support, an initial value is invalid, an initial point has a
        nonfinite log density, or every path fails.
    """
    _require_one_run(x, "Pathfinder.run")
    _check_observed_support(model, observations, "Pathfinder.run")
    with (
        torch.random.fork_rng(devices=[]),
        latent_structure_recording(),
    ):
        torch.random.set_rng_state(stream(self.seed, -2).get_state())
        recorded = trace(model, x, observations=observations)
    registry = LatentRegistry.from_trace(model, recorded)
    potential = PotentialFn(model, registry, x, observations)
    unconstrained = self.run_target(
        _PotentialTarget(potential),
        registry.total_unconstrained_dim,
        registry=registry,
    )
    return unconstrained

run_target

run_target(target: PathfinderTarget, dim: int, *, registry: LatentRegistry | None = None) -> PathfinderDraws

Run Pathfinder on a log density over R^dim.

PARAMETER DESCRIPTION
target

The log density.

TYPE: PathfinderTarget

dim

Dimension N.

TYPE: int

registry

The program's registry; its sites name the result's samples. Without one, the result holds the unconstrained draws as site "theta".

TYPE: LatentRegistry or None DEFAULT: None

RETURNS DESCRIPTION
PathfinderDraws

Draws and per-path diagnostics.

RAISES DESCRIPTION
ValueError

If every path fails.

Source code in src/quivers/inference/pathfinder.py
def run_target(
    self,
    target: PathfinderTarget,
    dim: int,
    *,
    registry: LatentRegistry | None = None,
) -> PathfinderDraws:
    """Run Pathfinder on a log density over ``R^dim``.

    Parameters
    ----------
    target : PathfinderTarget
        The log density.
    dim : int
        Dimension ``N``.
    registry : LatentRegistry or None
        The program's registry; its sites name the result's samples.
        Without one, the result holds the unconstrained draws as site
        ``"theta"``.

    Returns
    -------
    PathfinderDraws
        Draws and per-path diagnostics.

    Raises
    ------
    ValueError
        If every path fails.
    """
    paths = [
        single_path(
            target,
            self._initial_point(dim, path, registry),
            seed=int(stream(self.seed, 2 * path + 1).initial_seed()),
            settings=self.lbfgs,
            num_elbo_draws=self.num_elbo_draws,
            num_draws=self.num_draws,
            calculate_lp=self.calculate_lp,
        )
        for path in range(self.num_paths)
    ]
    usable = [index for index, path in enumerate(paths) if not path.failed]
    if not usable:
        raise ValueError(
            "Pathfinder: every path failed to produce a positive definite "
            "approximation with a finite ELBO; reasons: "
            + ", ".join(path.path.termination for path in paths)
        )
    pooled = torch.cat([paths[index].draws for index in usable])
    log_p = torch.cat([paths[index].log_density for index in usable])
    log_q = torch.cat([paths[index].log_approx for index in usable])
    origin = torch.cat(
        [
            torch.full((paths[index].draws.shape[0],), index, dtype=torch.long)
            for index in usable
        ]
    )
    resample = self.num_paths > 1 and self.psis_resample and self.calculate_lp
    pareto_k = math.nan
    if resample:
        log_weights, pareto_k = psis_log_weights(log_p - log_q)
        chosen = torch.multinomial(
            log_weights.exp(),
            self.num_psis_draws,
            replacement=True,
            generator=stream(self.seed, -3),
        )
        pooled, log_p, log_q, origin = (
            pooled[chosen],
            log_p[chosen],
            log_q[chosen],
            origin[chosen],
        )
    count = int(pooled.shape[0])
    samples = _constrained_samples(pooled, registry)
    single: dict[str, torch.Tensor] = {}
    if self.save_single_paths:
        per_path = [
            None if path.failed else _constrained_samples(path.draws, registry)
            for path in paths
        ]
        for name, value in samples.items():
            filler = torch.full(
                (self.num_draws, *value.shape[2:]), math.nan, dtype=value.dtype
            )
            single[name] = torch.stack(
                [filler if drawn is None else drawn[name][0] for drawn in per_path]
            )
    return PathfinderDraws(
        samples=samples,
        num_samples=count,
        log_density=log_p.reshape(1, count),
        log_approx=log_q.reshape(1, count),
        path_index=origin,
        path_elbo=torch.tensor(
            [
                -math.inf if path.failed else float(path.elbo.max())
                for path in paths
            ],
            dtype=torch.float64,
        ),
        path_iterations=torch.tensor(
            [path.path.num_iterations for path in paths], dtype=torch.long
        ),
        path_best_iteration=torch.tensor(
            [path.best_iteration for path in paths], dtype=torch.long
        ),
        path_termination=tuple(path.path.termination for path in paths),
        num_evaluations=torch.tensor(
            [
                path.path.num_evaluations
                + path.path.num_iterations * self.num_elbo_draws
                + (0 if path.failed or not self.calculate_lp else self.num_draws)
                for path in paths
            ],
            dtype=torch.long,
        ),
        pareto_k=pareto_k,
        resampled=resample,
        single_paths=single,
    )

lbfgs_path

lbfgs_path(target: PathfinderTarget, initial: Tensor, settings: LBFGSSettings) -> OptimizationPath

Maximize log p by L-BFGS, recording every iterate.

The search direction is the two-loop recursion over the last history_size pairs with the scaled identity (s'y / y'y) I as the initial inverse Hessian; a pair enters the history when s'y > eps |y|^2. The first step tries length init_alpha along the gradient, later steps length one. The line search enforces the strong Wolfe conditions by bracketing and cubic interpolation [@nocedal2006numerical]. The run stops on the first of Stan's tests that holds, in Stan's order: absolute and relative objective change, absolute and relative gradient, and parameter change.

PARAMETER DESCRIPTION
target

The log density.

TYPE: PathfinderTarget

initial

Starting position, shape (N,).

TYPE: Tensor

settings

Optimizer settings.

TYPE: LBFGSSettings

RETURNS DESCRIPTION
OptimizationPath

Iterates, log densities, gradients, and the stopping reason. Cost is O(L J N) besides the evaluations.

RAISES DESCRIPTION
ValueError

If the log density or its gradient at initial is not finite.

Source code in src/quivers/inference/pathfinder.py
def lbfgs_path(
    target: PathfinderTarget, initial: torch.Tensor, settings: LBFGSSettings
) -> OptimizationPath:
    """Maximize ``log p`` by L-BFGS, recording every iterate.

    The search direction is the two-loop recursion over the last
    ``history_size`` pairs with the scaled identity
    ``(s'y / y'y) I`` as the initial inverse Hessian; a pair enters the
    history when ``s'y > eps |y|^2``. The first step tries length
    ``init_alpha`` along the gradient, later steps length one. The line
    search enforces the strong Wolfe conditions by bracketing and cubic
    interpolation [@nocedal2006numerical]. The run stops on the first of
    Stan's tests that holds, in Stan's order: absolute and relative objective
    change, absolute and relative gradient, and parameter change.

    Parameters
    ----------
    target : PathfinderTarget
        The log density.
    initial : torch.Tensor
        Starting position, shape ``(N,)``.
    settings : LBFGSSettings
        Optimizer settings.

    Returns
    -------
    OptimizationPath
        Iterates, log densities, gradients, and the stopping reason. Cost is
        O(L J N) besides the evaluations.

    Raises
    ------
    ValueError
        If the log density or its gradient at ``initial`` is not finite.
    """
    evaluations = [0]

    def evaluate(z: torch.Tensor) -> tuple[torch.Tensor, float, torch.Tensor]:
        """Round ``z`` to the target's dtype and return ``-log p`` there.

        Parameters
        ----------
        z : torch.Tensor
            Position.

        Returns
        -------
        tuple
            The rounded position, objective, and objective gradient.
        """
        rounded = z.to(target.dtype).to(torch.float64)
        evaluations[0] += 1
        value, gradient = target.value_and_grad(rounded.to(target.dtype))
        return rounded, -float(value), -gradient.detach().to(torch.float64)

    x, f, g = evaluate(initial.to(torch.float64))
    if not (math.isfinite(f) and bool(torch.isfinite(g).all())):
        raise ValueError(
            "Pathfinder: the log density or its gradient at the initial point "
            "is not finite"
        )
    positions, objectives, gradients = [x], [f], [g]
    pairs: deque[tuple[torch.Tensor, torch.Tensor]] = deque(
        maxlen=settings.history_size
    )
    termination: Termination = "maximum iterations"
    for iteration in range(settings.max_iterations):
        direction = -_two_loop(g, pairs)
        slope = float(g @ direction)
        if not slope < 0:
            pairs.clear()
            direction = -g
            slope = -float(g @ g)
        start = settings.init_alpha if iteration == 0 else 1.0
        step = _line_search(evaluate, x, f, g, direction, slope, start, settings)
        if step is None:
            termination = "line search failed"
            break
        x_new, f_new, g_new = step
        s, y = x_new - x, g_new - g
        if float(s @ y) > _EPSILON * float(y @ y):
            pairs.append((s, y))
        positions.append(x_new)
        objectives.append(f_new)
        gradients.append(g_new)
        change = abs(f - f_new)
        reason: Termination | None = None
        if change < settings.tol_obj:
            reason = "absolute objective"
        elif change / max(abs(f), abs(f_new), 1.0) < settings.tol_rel_obj * _EPSILON:
            reason = "relative objective"
        elif float(g_new.norm()) < settings.tol_grad:
            reason = "absolute gradient"
        elif (
            float(g_new @ _two_loop(g_new, pairs)) / max(abs(f_new), 1.0)
            < settings.tol_rel_grad * _EPSILON
        ):
            reason = "relative gradient"
        elif float(s.norm()) < settings.tol_param:
            reason = "parameter change"
        x, f, g = x_new, f_new, g_new
        if reason is not None:
            termination = reason
            break
    return OptimizationPath(
        positions=torch.stack(positions),
        log_densities=-torch.tensor(objectives, dtype=torch.float64),
        gradients=-torch.stack(gradients),
        termination=termination,
        num_evaluations=evaluations[0],
    )

recover_diagonal

recover_diagonal(path: OptimizationPath) -> DiagonalRecovery

Recover the diagonal inverse-Hessian estimates along a path.

Algorithm 3 of [@zhang2022pathfinder]: starting from alpha = 1, each step with s'z > 1e-12 |z|^2 updates alpha elementwise by the diagonal BFGS formula of Gilbert and Lemarechal, 1 / alpha_n = a / (b alpha_n) + z_n^2 / b - a s_n^2 / (b c alpha_n^2) with a = z' diag(alpha) z, b = z' s, c = s' diag(alpha)^(-1) s [@gilbert1989numerical], and is marked accepted. The paper's printed condition has its inequality reversed; the condition here is the one its text states, which keeps steps whose gradient change is not 10^12 times larger than the position change along it.

PARAMETER DESCRIPTION
path

L-BFGS iterates and gradients.

TYPE: OptimizationPath

RETURNS DESCRIPTION
DiagonalRecovery

Per-step diagonals, acceptance marks, and updates; O(L N).

Source code in src/quivers/inference/pathfinder.py
def recover_diagonal(path: OptimizationPath) -> DiagonalRecovery:
    """Recover the diagonal inverse-Hessian estimates along a path.

    Algorithm 3 of [@zhang2022pathfinder]: starting from ``alpha = 1``, each
    step with ``s'z > 1e-12 |z|^2`` updates ``alpha`` elementwise by the
    diagonal BFGS formula of Gilbert and Lemarechal,
    ``1 / alpha_n = a / (b alpha_n) + z_n^2 / b - a s_n^2 / (b c alpha_n^2)``
    with ``a = z' diag(alpha) z``, ``b = z' s``, ``c = s' diag(alpha)^(-1) s``
    [@gilbert1989numerical], and is marked accepted. The paper's printed condition has its
    inequality reversed; the condition here is the one its text states,
    which keeps steps whose gradient change is not 10^12 times larger than
    the position change along it.

    Parameters
    ----------
    path : OptimizationPath
        L-BFGS iterates and gradients.

    Returns
    -------
    DiagonalRecovery
        Per-step diagonals, acceptance marks, and updates; O(L N).
    """
    positions, gradients = path.positions, path.gradients
    steps = positions[1:] - positions[:-1]
    changes = gradients[:-1] - gradients[1:]
    dim = positions.shape[1]
    alpha = torch.ones(dim, dtype=torch.float64)
    alphas, accepted = [], []
    for s, z in zip(steps, changes, strict=True):
        b = float(s @ z)
        if b > 1e-12 * float(z @ z):
            a = float(z @ (alpha * z))
            c = float(s @ (s / alpha))
            alpha = 1.0 / (a / (b * alpha) + z * z / b - a * s * s / (b * c * alpha**2))
            accepted.append(True)
        else:
            accepted.append(False)
        alphas.append(alpha)
    return DiagonalRecovery(
        alphas=torch.stack(alphas) if alphas else torch.empty(0, dim),
        accepted=torch.tensor(accepted, dtype=torch.bool),
        steps=steps,
        gradient_steps=changes,
    )

compact_factors

compact_factors(alpha: Tensor, s: Tensor, z: Tensor) -> tuple[Tensor, Tensor]

Compact BFGS representation of the inverse Hessian.

Equation (2) of [@zhang2022pathfinder], after Byrd, Nocedal and Schnabel (1994, eq. 2.6): beta = [diag(alpha) Z, S] and gamma = [[0, -E^(-1)], [-E^(-T), E^(-T) (diag(eta) + Z' diag(alpha) Z) E^(-1)]] with E the upper triangle of S'Z and eta its diagonal, so that diag(alpha) + beta gamma beta' equals the BFGS updates of diag(alpha) by the pairs in order.

PARAMETER DESCRIPTION
alpha

Initial diagonal, shape (N,).

TYPE: Tensor

s

Position updates as columns, shape (N, m).

TYPE: Tensor

z

Gradient updates of -log p as columns, shape (N, m).

TYPE: Tensor

RETURNS DESCRIPTION
tuple[Tensor, Tensor]

beta of shape (N, 2m) and gamma of shape (2m, 2m); O(N m^2 + m^3).

Source code in src/quivers/inference/pathfinder.py
def compact_factors(
    alpha: torch.Tensor, s: torch.Tensor, z: torch.Tensor
) -> tuple[torch.Tensor, torch.Tensor]:
    """Compact BFGS representation of the inverse Hessian.

    Equation (2) of [@zhang2022pathfinder], after Byrd, Nocedal and Schnabel
    (1994, eq. 2.6): ``beta = [diag(alpha) Z, S]`` and
    ``gamma = [[0, -E^(-1)], [-E^(-T), E^(-T) (diag(eta) + Z' diag(alpha) Z) E^(-1)]]``
    with ``E`` the upper triangle of ``S'Z`` and ``eta`` its diagonal, so that
    ``diag(alpha) + beta gamma beta'`` equals the BFGS updates of
    ``diag(alpha)`` by the pairs in order.

    Parameters
    ----------
    alpha : torch.Tensor
        Initial diagonal, shape ``(N,)``.
    s : torch.Tensor
        Position updates as columns, shape ``(N, m)``.
    z : torch.Tensor
        Gradient updates of ``-log p`` as columns, shape ``(N, m)``.

    Returns
    -------
    tuple[torch.Tensor, torch.Tensor]
        ``beta`` of shape ``(N, 2m)`` and ``gamma`` of shape ``(2m, 2m)``;
        O(N m^2 + m^3).
    """
    m = s.shape[1]
    inner = s.T @ z
    upper = torch.triu(inner)
    eta = torch.diagonal(inner)
    eye = torch.eye(m, dtype=torch.float64)
    inverse = torch.linalg.solve_triangular(upper, eye, upper=True)
    beta = torch.cat([alpha[:, None] * z, s], dim=1)
    lower_right = inverse.T @ (torch.diag(eta) + z.T @ (alpha[:, None] * z)) @ inverse
    gamma = torch.cat(
        [
            torch.cat([torch.zeros(m, m, dtype=torch.float64), -inverse], dim=1),
            torch.cat([-inverse.T, lower_right], dim=1),
        ],
        dim=0,
    )
    return beta, gamma

normal_approximation

normal_approximation(position: Tensor, gradient: Tensor, alpha: Tensor, s: Tensor, z: Tensor) -> NormalApproximation | None

Factor the normal approximation at one iterate (Algorithm 4).

PARAMETER DESCRIPTION
position

Iterate theta, shape (N,).

TYPE: Tensor

gradient

grad log p(theta), shape (N,).

TYPE: Tensor

alpha

Diagonal estimate, shape (N,).

TYPE: Tensor

s

Selected update pairs as columns, shape (N, m), oldest first.

TYPE: Tensor

z

Selected update pairs as columns, shape (N, m), oldest first.

TYPE: Tensor

RETURNS DESCRIPTION
NormalApproximation or None

The factored approximation, or None when the estimate is not positive definite. Cost O(N m^2 + m^3).

Source code in src/quivers/inference/pathfinder.py
def normal_approximation(
    position: torch.Tensor,
    gradient: torch.Tensor,
    alpha: torch.Tensor,
    s: torch.Tensor,
    z: torch.Tensor,
) -> NormalApproximation | None:
    """Factor the normal approximation at one iterate (Algorithm 4).

    Parameters
    ----------
    position : torch.Tensor
        Iterate ``theta``, shape ``(N,)``.
    gradient : torch.Tensor
        ``grad log p(theta)``, shape ``(N,)``.
    alpha : torch.Tensor
        Diagonal estimate, shape ``(N,)``.
    s, z : torch.Tensor
        Selected update pairs as columns, shape ``(N, m)``, oldest first.

    Returns
    -------
    NormalApproximation or None
        The factored approximation, or None when the estimate is not
        positive definite. Cost O(N m^2 + m^3).
    """
    if not bool((alpha > 0).all() and torch.isfinite(alpha).all()):
        return None
    dim = position.shape[0]
    if s.shape[1] == 0:
        empty = torch.zeros(dim, 0, dtype=torch.float64)
        return NormalApproximation(
            mean=position + alpha * gradient,
            alpha=alpha,
            q=empty,
            cholesky=torch.zeros(0, 0, dtype=torch.float64),
            beta=empty,
            gamma=torch.zeros(0, 0, dtype=torch.float64),
            log_det=float(alpha.log().sum()),
        )
    beta, gamma = compact_factors(alpha, s, z)
    q, r = torch.linalg.qr(beta / alpha.sqrt()[:, None], mode="reduced")
    inner = torch.eye(q.shape[1], dtype=torch.float64) + r @ gamma @ r.T
    cholesky, info = torch.linalg.cholesky_ex(0.5 * (inner + inner.T))
    if int(info) != 0 or not bool(torch.isfinite(cholesky).all()):
        return None
    mean = position + alpha * gradient + beta @ (gamma @ (beta.T @ gradient))
    log_det = float(alpha.log().sum() + 2 * torch.diagonal(cholesky).log().sum())
    if not (math.isfinite(log_det) and bool(torch.isfinite(mean).all())):
        return None
    return NormalApproximation(
        mean=mean,
        alpha=alpha,
        q=q,
        cholesky=cholesky,
        beta=beta,
        gamma=gamma,
        log_det=log_det,
    )

bfgs_approximation

bfgs_approximation(path: OptimizationPath, recovery: DiagonalRecovery, iteration: int, history_size: int) -> NormalApproximation | None

The normal approximation at iterate iteration of a path.

It uses the last history_size accepted pairs among steps 1..iteration and the diagonal recovered at that iterate.

PARAMETER DESCRIPTION
path

The L-BFGS iterates.

TYPE: OptimizationPath

recovery

α-RECOVER output for the path.

TYPE: DiagonalRecovery

iteration

Iterate l in 1..L.

TYPE: int

history_size

Number J of pairs.

TYPE: int

RETURNS DESCRIPTION
NormalApproximation or None

The approximation, or None when it is not positive definite.

Source code in src/quivers/inference/pathfinder.py
def bfgs_approximation(
    path: OptimizationPath,
    recovery: DiagonalRecovery,
    iteration: int,
    history_size: int,
) -> NormalApproximation | None:
    """The normal approximation at iterate ``iteration`` of a path.

    It uses the last ``history_size`` accepted pairs among steps
    ``1..iteration`` and the diagonal recovered at that iterate.

    Parameters
    ----------
    path : OptimizationPath
        The L-BFGS iterates.
    recovery : DiagonalRecovery
        α-RECOVER output for the path.
    iteration : int
        Iterate ``l`` in ``1..L``.
    history_size : int
        Number ``J`` of pairs.

    Returns
    -------
    NormalApproximation or None
        The approximation, or None when it is not positive definite.
    """
    chosen = [index for index in range(iteration) if bool(recovery.accepted[index])][
        -history_size:
    ]
    return normal_approximation(
        path.positions[iteration],
        path.gradients[iteration],
        recovery.alphas[iteration - 1],
        recovery.steps[chosen].T,
        recovery.gradient_steps[chosen].T,
    )

stream

stream(seed: int, index: int) -> Generator

Derive an independent generator from a seed by SplitMix64.

The mixing is the one MCMC uses to give each chain its stream.

PARAMETER DESCRIPTION
seed

Base seed.

TYPE: int

index

Stream index.

TYPE: int

RETURNS DESCRIPTION
Generator

A CPU generator seeded with the mixed value.

Source code in src/quivers/inference/pathfinder.py
def stream(seed: int, index: int) -> torch.Generator:
    """Derive an independent generator from a seed by SplitMix64.

    The mixing is the one `MCMC` uses to give each chain its stream.

    Parameters
    ----------
    seed : int
        Base seed.
    index : int
        Stream index.

    Returns
    -------
    torch.Generator
        A CPU generator seeded with the mixed value.
    """
    value = (seed + (index + 1) * 0x9E3779B97F4A7C15) & _MASK
    value = ((value ^ (value >> 30)) * 0xBF58476D1CE4E5B9) & _MASK
    value = ((value ^ (value >> 27)) * 0x94D049BB133111EB) & _MASK
    value ^= value >> 31
    return torch.Generator().manual_seed(value)

single_path

single_path(target: PathfinderTarget, initial: Tensor, *, seed: int, settings: LBFGSSettings, num_elbo_draws: int, num_draws: int, calculate_lp: bool = True) -> SinglePath

Run single-path Pathfinder from one initial point.

The ELBO at iterate l averages log p(phi) - log q(phi) over num_elbo_draws draws of stream stream(seed, l); the returned draws come from stream stream(seed, -1).

PARAMETER DESCRIPTION
target

The log density.

TYPE: PathfinderTarget

initial

Starting position, shape (N,).

TYPE: Tensor

seed

Base of the path's random streams.

TYPE: int

settings

L-BFGS settings, including the history size.

TYPE: LBFGSSettings

num_elbo_draws

Draws per ELBO estimate K.

TYPE: int

num_draws

Draws returned M.

TYPE: int

calculate_lp

Whether to evaluate the target at the returned draws.

TYPE: bool DEFAULT: True

RETURNS DESCRIPTION
SinglePath

The path, its ELBO profile, and the draws. Cost is the L-BFGS evaluations plus L K + M log-density evaluations and O(L (N J^2 + J^3 + K (N J + J^2))) arithmetic.

Source code in src/quivers/inference/pathfinder.py
def single_path(
    target: PathfinderTarget,
    initial: torch.Tensor,
    *,
    seed: int,
    settings: LBFGSSettings,
    num_elbo_draws: int,
    num_draws: int,
    calculate_lp: bool = True,
) -> SinglePath:
    """Run single-path Pathfinder from one initial point.

    The ELBO at iterate ``l`` averages ``log p(phi) - log q(phi)`` over
    ``num_elbo_draws`` draws of stream ``stream(seed, l)``; the returned
    draws come from stream ``stream(seed, -1)``.

    Parameters
    ----------
    target : PathfinderTarget
        The log density.
    initial : torch.Tensor
        Starting position, shape ``(N,)``.
    seed : int
        Base of the path's random streams.
    settings : LBFGSSettings
        L-BFGS settings, including the history size.
    num_elbo_draws : int
        Draws per ELBO estimate ``K``.
    num_draws : int
        Draws returned ``M``.
    calculate_lp : bool
        Whether to evaluate the target at the returned draws.

    Returns
    -------
    SinglePath
        The path, its ELBO profile, and the draws. Cost is the L-BFGS
        evaluations plus ``L K + M`` log-density evaluations and
        O(L (N J^2 + J^3 + K (N J + J^2))) arithmetic.
    """
    path = lbfgs_path(target, initial, settings)
    recovery = recover_diagonal(path)
    elbo = torch.full((path.num_iterations,), -math.inf, dtype=torch.float64)
    best: NormalApproximation | None = None
    best_iteration = 0
    for iteration in range(1, path.num_iterations + 1):
        approximation = bfgs_approximation(
            path, recovery, iteration, settings.history_size
        )
        if approximation is None:
            continue
        draws, log_q = _draw(
            approximation, num_elbo_draws, stream(seed, iteration), target.dtype
        )
        log_p = _score(target, draws)
        estimate = float((log_p - log_q).mean())
        if not math.isfinite(estimate):
            continue
        elbo[iteration - 1] = estimate
        if best is None or estimate > float(elbo[best_iteration - 1]):
            best, best_iteration = approximation, iteration
    if best is None:
        last = path.positions[-1:]
        return SinglePath(
            path=path,
            elbo=elbo,
            best_iteration=0,
            draws=last,
            log_density=path.log_densities[-1:],
            log_approx=torch.full((1,), math.inf, dtype=torch.float64),
            failed=True,
        )
    draws, log_q = _draw(best, num_draws, stream(seed, -1), target.dtype)
    log_p = (
        _score(target, draws)
        if calculate_lp
        else torch.full((num_draws,), math.nan, dtype=torch.float64)
    )
    return SinglePath(
        path=path,
        elbo=elbo,
        best_iteration=best_iteration,
        draws=draws,
        log_density=log_p,
        log_approx=log_q,
        failed=False,
    )

psis_log_weights

psis_log_weights(log_ratios: Tensor) -> tuple[Tensor, float]

Pareto-smooth importance log ratios as loo's psis with r_eff = 1.

The largest M = ceil(min(0.2 S, 3 sqrt(S))) ratios are replaced by the quantiles (i - 1/2) / M of a generalized Pareto distribution fit to their exceedances over the next largest ratio, and every ratio is truncated at the largest raw ratio [@vehtari2024psis]. Ratios of -inf keep zero weight.

PARAMETER DESCRIPTION
log_ratios

Log importance ratios log p - log q, shape (S,).

TYPE: Tensor

RETURNS DESCRIPTION
tuple[Tensor, float]

Normalized smoothed log weights and the Pareto shape k (inf when the tail cannot be fit). Cost O(S log S).

RAISES DESCRIPTION
ValueError

If no ratio is finite.

Source code in src/quivers/inference/pathfinder.py
def psis_log_weights(log_ratios: torch.Tensor) -> tuple[torch.Tensor, float]:
    """Pareto-smooth importance log ratios as loo's ``psis`` with ``r_eff = 1``.

    The largest ``M = ceil(min(0.2 S, 3 sqrt(S)))`` ratios are replaced by
    the quantiles ``(i - 1/2) / M`` of a generalized Pareto distribution fit
    to their exceedances over the next largest ratio, and every ratio is
    truncated at the largest raw ratio [@vehtari2024psis]. Ratios of
    ``-inf`` keep zero weight.

    Parameters
    ----------
    log_ratios : torch.Tensor
        Log importance ratios ``log p - log q``, shape ``(S,)``.

    Returns
    -------
    tuple[torch.Tensor, float]
        Normalized smoothed log weights and the Pareto shape ``k`` (``inf``
        when the tail cannot be fit). Cost O(S log S).

    Raises
    ------
    ValueError
        If no ratio is finite.
    """
    ratios = log_ratios.detach().to(torch.float64)
    finite = torch.isfinite(ratios)
    if not bool(finite.any()):
        raise ValueError("Pathfinder: no draw has a finite importance ratio")
    count = int(finite.sum())
    peak = float(ratios[finite].max())
    weights = torch.where(finite, ratios - peak, -math.inf)
    tail = math.ceil(min(0.2 * count, 3 * math.sqrt(count)))
    k = math.inf
    if tail >= 5:
        values, order = torch.sort(weights[finite])
        indices = torch.nonzero(finite).flatten()[order]
        tail_values = values[-tail:]
        if abs(float(tail_values[-1] - tail_values[0])) >= _EPSILON / 100:
            cutoff = float(values[-tail - 1])
            k, sigma = _gpd_fit(torch.exp(tail_values) - math.exp(cutoff))
            if math.isfinite(k):
                p = (torch.arange(1, tail + 1, dtype=torch.float64) - 0.5) / tail
                quantiles = sigma * torch.expm1(-k * torch.log1p(-p)) / k
                weights[indices[-tail:]] = torch.log(quantiles + math.exp(cutoff))
    weights = torch.clamp(weights, max=0.0)
    return weights - torch.logsumexp(weights, 0), k

draw_provenance

draw_provenance(posterior: MCMCResult | PriorDraws | Guide) -> Literal['mcmc', 'variational', 'prior']

Name where retained draws come from.

PARAMETER DESCRIPTION
posterior

A fit's posterior.

TYPE: MCMCResult or PriorDraws or Guide

RETURNS DESCRIPTION
{'mcmc', 'variational', 'prior'}

"mcmc" for recorded chains, "variational" for a guide or Pathfinder draws, "prior" for independent prior draws.

Source code in src/quivers/inference/pathfinder.py
def draw_provenance(
    posterior: MCMCResult | PriorDraws | Guide,
) -> Literal["mcmc", "variational", "prior"]:
    """Name where retained draws come from.

    Parameters
    ----------
    posterior : MCMCResult or PriorDraws or Guide
        A fit's posterior.

    Returns
    -------
    {"mcmc", "variational", "prior"}
        ``"mcmc"`` for recorded chains, ``"variational"`` for a guide or
        Pathfinder draws, ``"prior"`` for independent prior draws.
    """
    if isinstance(posterior, MCMCResult):
        return "mcmc"
    if isinstance(posterior, PathfinderDraws):
        return "variational"
    return "prior" if isinstance(posterior, PriorDraws) else "variational"

Cited sources

Lu Zhang, Bob Carpenter, Andrew Gelman, and Aki Vehtari. Pathfinder: Parallel quasi-Newton variational inference. Journal of Machine Learning Research, 23(306):1–49, 2022b. URL: https://jmlr.org/papers/v23/21-0889.html.

Aki Vehtari, Daniel Simpson, Andrew Gelman, Yuling Yao, and Jonah Gabry. Pareto Smoothed Importance Sampling. Journal of Machine Learning Research, 25(72):1–58, 2024. URL: https://www.jmlr.org/papers/v25/19-556.html.

Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Springer Series in Operations Research and Financial Engineering. Springer, 2 edition, 2006. doi:10.1007/978-0-387-40065-5.