probabilistic_bisector

Probabilistic Bisector

probabilistic_bisector provides a probabilistic bisection algorithm for locating roots of scalar objective functions observed in noise.

Classical bisection assumes that evaluating an objective function gives an exact sign. In many numerical, simulation, and experimental settings this is not true: repeated evaluations at the same point may produce different values, and the sign of the objective may only be inferable statistically.

This crate is designed for that setting.

Motivation

Suppose we want to find a root x* of a scalar objective function

text f(x*) = 0

but each call to the objective produces a noisy observation. A single evaluation may not reliably tell us whether f(x) is positive or negative.

Instead of treating each sign observation as exact, this crate maintains a posterior distribution over the possible root location. Each observation updates that distribution, and the algorithm returns a confidence interval for the root.

Theoretical basis

The implementation follows the probabilistic bisection framework described by Waeber.

The algorithm maintains a posterior distribution over the root location on a fixed internal domain. At each step:

A query point is selected from the current posterior.
The objective is evaluated repeatedly at that point.
A curved-boundary sign test determines the sign of the objective to the requested confidence level.
The posterior mass is updated according to whether the root is expected to lie to the left or right of the query point.
A sequential confidence interval is updated by intersecting the previous interval with the current Waeber-style confidence region.

Internally, posterior mass is stored over a partition of the search domain. The posterior is represented in log-space for numerical stability.

Coordinate scaling

The posterior is represented on a numerically convenient internal domain, usually [0, 1]. User objective functions are evaluated on their original raw domain.

A Scaler maps between these coordinate systems. For strictly positive domains spanning several orders of magnitude, logarithmic scaling may be used so that posterior resolution is distributed multiplicatively rather than linearly.

Implementing an objective

Problems are represented by implementing [RootOracle].

The oracle provides noisy evaluations of the objective. Implementations may be deterministic or stochastic.

use confi::ConfidenceLevel;
use probabilistic_bisector::{run, BisectorConfig, RootOracle};

struct Linear {
    root: f64,
}

impl RootOracle<f64> for Linear {
    fn evaluate(&mut self, x: f64) -> f64 {
        x - self.root
    }
}


fn main() -> Result<(), Box<dyn std::error::Error>> {
    let config = BisectorConfig {
        max_observations: 10000,      // Maximum observations in the loop
        max_knots: 1000,              // Maximum knots in the posterior distribution
        max_sign_evaluations: 1000,   // Maximum function calls in evaluating the objective sign
        rel_tol: 1e-5,                // Target relative tolerance
        tolerance_window: 10,         // Number of evaluations relative tolerance should be stable
    };

    let result = run(
        0.0..10.0,                    // Search range
        ConfidenceLevel::new(0.8)?,   // Required confidence level
        Linear { root: 2.5 },         // Problem
        config,
    )?;

    println!("root interval: {:?}", result.interval);
    println!("termination: {:?}", result.termination);
    Ok(())
}

Stochastic objectives

A RootOracle may use internal randomness. Since [RootOracle::evaluate] takes &mut self, objectives can store their own random number generator, allowing reproducible seeded tests.

`rust use probabilistic_bisector::RootOracle;

struct NoisyLinear { root: f64, index: usize, }

impl RootOracle for NoisyLinear { fn evaluate(&mut self, x: f64) -> f64 { let noise = if self.index % 2 == 0 { 0.001 } else { -0.001 }; self.index += 1; x - self.root + noise } } `

Termination

The solver may terminate because:

the requested tolerance was reached,
the maximum iteration budget was reached,
or the objective sign became indeterminate at all useful query points.

Sign indeterminacy is not necessarily an error. It usually means that the algorithm has reached the noise floor of the objective: additional samples at nearby points do not determine the sign reliably within the configured evaluation budget -> Given the noise in the objective function the requested tolerance might be unachievable.

Output

Successful runs return a result containing:

a confidence interval for the root,
execution summary information,
and the reason the solver terminated.

Exceptional failures are reserved for invalid inputs, invalid oracle values, or internal invariant violations.

License: MIT

probabilistic_bisector 0.2.0

probabilistic_bisector