ganesh 0.28.0

Minimization and sampling in Rust, simplified
Documentation

ganesh (/ɡəˈneɪʃ/), named after the Hindu god of wisdom, provides minimization and sampling algorithms through scalar- and linear-algebra-generic Rust interfaces. Most users implement CostFunction, optionally implement Gradient, and run an algorithm. Default finite differences keep analytic derivatives optional.

Table of Contents

Key Features

  • Algorithms that are simple to use with sensible defaults.
  • Traits which make developing future algorithms simple and consistent.
  • A simple interface that lets new users get started quickly.
  • A pure Rust implementation of the L-BFGS-B algorithm.
  • Scalar- and linear-algebra-generic Rust APIs with f64/nalgebra defaults, native f32, and optional ndarray support.
  • Composable scaling, bounds, and periodic parameter transforms with first- and second-order derivative propagation.

Rust precision is selected through type parameters, so f32 and f64 can coexist without feature switching. The default build remains Python-free. Downstream extension crates can enable the optional python feature to reuse typed PyO3 configuration, initialization, callback, transform, and result objects without Ganesh publishing a Python package of its own.

The backend-ndarray feature deliberately does not choose an ndarray-linalg LAPACK source. Applications using it should depend on ndarray-linalg directly and enable exactly one of its source features before linking an executable that uses those operations.

Quick Start

This crate provides some common test functions in the test_functions module. Consider the following implementation of the Rosenbrock function:

use ganesh::traits::*;
use ganesh::{LinearAlgebra, RealScalar, Vector};
use std::convert::Infallible;

pub struct Rosenbrock {
    pub n: usize,
}
impl<T, B> CostFunction<T, B> for Rosenbrock
where
    T: RealScalar,
    B: LinearAlgebra<T>,
{
    fn evaluate(&self, x: &Vector<T, B>, _args: &()) -> Result<T, Infallible> {
        Ok((0..(self.n - 1)).fold(T::zero(), |sum, i| {
            sum + T::literal(100.0) * (x.get(i + 1) - x.get(i).powi(2)).powi(2)
                + (T::one() - x.get(i)).powi(2)
        }))
    }
}

To minimize this function, we could consider using the Nelder-Mead algorithm:

use ganesh::algorithms::gradient_free::NelderMead;
use ganesh::traits::*;
use ganesh::test_functions::Rosenbrock;
use std::convert::Infallible;

fn main() -> Result<(), Infallible> {
    let problem = Rosenbrock { n: 2 };
    let mut nm: NelderMead = Default::default();
    let result = nm.process_default(&problem, &(), [2.0, 2.0])?;
    println!("{}", result);
    Ok(())
}

We could also use some more verbose syntax if we wanted additional customization:

use ganesh::algorithms::gradient_free::{NelderMead, NelderMeadConfig};
use ganesh::traits::*;
use ganesh::test_functions::Rosenbrock;
use std::convert::Infallible;

fn main() -> Result<(), Infallible> {
    let problem = Rosenbrock { n: 2 };
    let mut nm: NelderMead = Default::default();
    let config = NelderMeadConfig::default();
    let result = nm.process(
        &problem,
        &(),
        vec![2.0, 2.0],
        config,
        NelderMead::default_callbacks(),
    )?;
    println!("{}", result);
    Ok(())
}

The same program is available as cargo run --example readme. It outputs

╭─────────────────────────────────────────────────────────────╮
│                    MINIMIZATION SUMMARY                     │
├───────────┬─────────┬─────────────┬─────────┬───────────────┤
│ Status    │ f(x)    │ # f(x)      │ # ∇f(x) │ # H(x)        │
├───────────┼─────────┼─────────────┼─────────┼───────────────┤
│ Converged │ 0.00009 │ 80          │ 0       │ 0             │
├───────────┼─────────┴─────────────┴─────────┴───────────────┤
│ Message   │ Success: term_f = STDDEV                        │
├───────────┴─────────────────────────────────┬───────────────┤
│ Parameters                                  │ Bounds        │
├───────────┬─────────┬─────────────┬─────────┼───────┬───────┤
│ Name      │ Value   │ Uncertainty │ Initial │ Lower │ Upper │
│ x_0       │ 1.00410 │ NaN         │ 2.00000 │ −∞    │ ∞     │
│ x_1       │ 1.00909 │ NaN         │ 2.00000 │ −∞    │ ∞     │
╰───────────┴─────────┴─────────────┴─────────┴───────┴───────╯

The ganesh crate uses algorithm methods such as Algorithm::process, Algorithm::process_with_default_callbacks, and Algorithm::process_default as the primary entrypoints for running optimizers and samplers.

Algorithms

At the moment, ganesh contains the following Algorithms:

All algorithms are written in pure Rust, including L-BFGS-B, which is typically a binding to FORTRAN code in other crates.

Examples

The examples directory contains a compact generic numeric example and polished showcase examples for optimization, fitting, multistart minimization, swarms, and ensemble sampling. In particular, periodic_fit combines scaling, positivity, and cyclic phase coordinates, while multistart searches the local basins of the Rastrigin function. Run any Rust example directly:

cargo run --release --example pso

Each showcase directory also contains a .justfile. For example, just --justfile examples/pso/.justfile show runs the Rust code and renders the visualization with a standalone uv script whose Python dependencies are pinned inline.

Python Bindings for Downstream Crates

Enable Ganesh's helper feature alongside PyO3 in the downstream extension crate:

[lib]
crate-type = ["cdylib"]

[dependencies]
ganesh = { version = "0.27", features = ["python"] }
pyo3 = { version = "0.29", features = ["extension-module"] }

Re-export the declarative submodule from the downstream module. This preserves PyO3's introspection metadata, so maturin generate-stubs can generate type hints for both the Ganesh objects and the downstream API:

#[pyo3::pymodule]
mod my_extension {
    #[pymodule_export]
    use ganesh::python::ganesh;
}

Python users can then construct fully validated settings without the downstream crate duplicating Ganesh's option surface:

from my_extension.ganesh import (
    AIESConfig,
    AIESMove,
    ChainStorage,
    MaxSteps,
    MoreThuenteLineSearch,
    ConjugateGradientConfig,
)

cg = ConjugateGradientConfig(
    update="hager_zhang",
    line_search=MoreThuenteLineSearch(c1=1e-4, c2=0.8),
)
aies = AIESConfig(
    moves=[AIESMove.stretch(scale=2.5, weight=0.8), AIESMove.walk(weight=0.2)],
    chain_storage=ChainStorage.sampled(keep_every=10, max_samples=5000),
)
limit = MaxSteps(20_000)

Each Rust wrapper exposes to_rust (or an Into/TryInto conversion) for downstream bindings. PythonCallbackBundle starts from an algorithm's normal Rust callbacks, accepts any downstream Rust Observer or Terminator, and can also append Python callables with (step, status) signatures. Use process_with_python_callbacks to run the algorithm and propagate Python callback exceptions correctly. The helper layer currently targets Ganesh's default f64/nalgebra backend; downstream crates remain free to expose additional numeric specializations and custom status data.

Parameter Transforms

All Algorithms in ganesh can be constructed to have access to a feature which allows algorithms which usually function in unbounded parameter spaces to only return results inside a bounding box. This is done via a parameter transformation, similar to that used by LMFIT and MINUIT. This transform is not directly useful with algorithms which already have bounded implementations, like L-BFGS-B, but it can be combined with other transformations which may be useful to algorithms with bounds. While the user inputs parameters within the bounds, unbounded algorithms can (and in practice will) convert those values to a set of unbounded "internal" parameters. When functions are called, however, these internal parameters are converted back into bounded "external" parameters, via the following transformations:

Upper and lower bounds:

x_\text{int} = \frac{u}{\sqrt{1 - u^2}}

x_\text{ext} = c + w \frac{x_\text{int}}{\sqrt{x_\text{int}^2 + 1}}

where

u = \frac{x_\text{ext} - c}{w},\ c = \frac{x_\text{min} + x_\text{max}}{2},\ w = \frac{x_\text{max} - x_\text{min}}{2}

Upper bound only:

x_\text{int} = \frac{1}{2}\left(\frac{1}{(x_\text{max} - x_\text{ext})} - (x_\text{max} - x_\text{ext}) \right)

x_\text{ext} = x_\text{max} - (\sqrt{x_\text{int}^2 + 1} - x_\text{int})

Lower bound only:

x_\text{int} = \frac{1}{2}\left((x_\text{ext} - x_\text{min}) - \frac{1}{(x_\text{ext} - x_\text{min})} \right)

x_\text{ext} = x_\text{min} + (\sqrt{x_\text{int}^2 + 1} + x_\text{int})

While MINUIT and LMFIT recommend caution in interpreting covariance matrices obtained from fits with bounds transforms, ganesh does not, since it implements higher-order derivatives on these bounds while these other libraries use linear approximations.

Transforms can be composed in application order with Transform::then. For example, a scaling transform can be followed by periodic canonicalization and then a bounds transform.

Periodic parameters

PeriodicTransform represents cyclic coordinates on a canonical half-open interval [a, b) while leaving the optimizer's internal coordinate unbounded:

x_\text{ext} = a + (x_\text{int} - a) \mathbin{\operatorname{rem\_euclid}} (b-a)

Away from the displayed seam, the transform has an identity Jacobian and zero component Hessians. The objective must be genuinely periodic: its value and derivatives must agree across the seam. This repeated unbounded lift is intended for minimization, not MCMC; using it as a sampling transform repeats the target density infinitely and therefore produces an improper internal target.

Future Plans

  • Eventually, I would like to implement some more modern gradient-free optimization techniques.
  • There are probably many optimizations and algorithm extensions that I'm missing right now.
  • There should be more tests and documentation (as usual).

Citations

While this project does not currently have an associated paper, most of the algorithms it implements do, and they should be cited appropriately. Citations are also generally available in the documentation.

ESS MCMC Sampler

@article{karamanis2020ensemble,
  title = {Ensemble slice sampling: Parallel, black-box and gradient-free inference for correlated & multimodal distributions},
  author = {Karamanis, Minas and Beutler, Florian},
  journal = {arXiv preprint arXiv: 2002.06212},
  year = {2020}
}

scikit-learn (used in constructing a Bayesian Mixture Model in the Global ESS step)

@article{scikit-learn,
  title={Scikit-learn: Machine Learning in {P}ython},
  author={Pedregosa, F. and Varoquaux, G. and Gramfort, A. and Michel, V.
          and Thirion, B. and Grisel, O. and Blondel, M. and Prettenhofer, P.
          and Weiss, R. and Dubourg, V. and Vanderplas, J. and Passos, A. and
          Cournapeau, D. and Brucher, M. and Perrot, M. and Duchesnay, E.},
  journal={Journal of Machine Learning Research},
  volume={12},
  pages={2825--2830},
  year={2011}
}

AIES MCMC Sampler

@article{Goodman2010,
  title = {Ensemble samplers with affine invariance},
  volume = {5},
  ISSN = {1559-3940},
  url = {http://dx.doi.org/10.2140/camcos.2010.5.65},
  DOI = {10.2140/camcos.2010.5.65},
  number = {1},
  journal = {Communications in Applied Mathematics and Computational Science},
  publisher = {Mathematical Sciences Publishers},
  author = {Goodman,  Jonathan and Weare,  Jonathan},
  year = {2010},
  month = jan,
  pages = {65–80}
}