mathtoolbox

The mathtoolbox library provides implementations of acquisition functions used in Bayesian optimization, including their derivatives with respect to the data point. This allows for efficient optimization of the acquisition function itself.

Supported acquisition functions:

• Expected improvement (EI)
• Gaussian process upper confidence bound (GP-UCB)

#include <mathtoolbox/acquisition-functions.hpp>

The gradient descent implementation in mathtoolbox includes the following configuration characteristics:

• Line Search: Uses backtracking-line-search to find appropriate step sizes.
• Initial Step Size: Must be specified using the default_alpha parameter.
• Bound Conditions: Supports simple lower and upper bound constraints on the optimization variables.

The library implements data normalization using simple standardization for each dimension $d$. For each data point $i$ in dimension $d$, the value is transformed as follows:

$$X_{i}^{(d)} \leftarrow \frac{X_{i}^{(d)} - \text{E}[X^{(d)}]}{\sigma(X^{(d)})}$$

The Self-Organizing Map (SOM) implementation in mathtoolbox is used for dimensionality reduction and low-dimensional embedding. It allows you to visualize high-dimensional data by mapping it onto a low-dimensional (typically 1D or 2D) latent space.

This library implements a batch-style SOM algorithm, meaning that in each update step, all data points contribute to the update of node coordinates simultaneously, rather than updating nodes one data point at a time (online-style).

When calling ComputeWeights, you can choose between two modes depending on your data quality:

Exact Interpolation

• Method: Set use_regularization = false in ComputeWeights.
• Behavior: The interpolated function passes through all scattered data points exactly.
• Use Case: Best for clean, noise-free datasets.

Scattered Data Approximation (Regularization)

• Method: Set use_regularization = true and provide a lambda value in ComputeWeights.
• Behavior: Solves a minimization problem that balances the error against the weight magnitude ($\min_{\mathbf{w}} { | \mathbf{\Phi} \mathbf{w} - \mathbf{y} |^2 + \lambda | \mathbf{w} |^2 }$). This results in a smoother function that does not necessarily pass through every point.
• Use Case: Best for noisy or dense datasets where exact interpolation would lead to overfitting or instability.

When working with the SOM implementation, the following terms are used:

• Data space: The high-dimensional space where the original data points exist.
• Latent space: The low-dimensional space where the map is constructed (restricted to one or two dimensions in this library).
• Node: An element of the map. Nodes have fixed coordinates in the latent space and learned coordinates in the data space.

The mathtoolbox::BayesianOptimizer is a black-box global optimization algorithm designed for maximization problems where the objective function $f(\mathbf{x})$ is expensive to evaluate.

Core Mechanics

• Problem Formulation: It solves $\mathbf{x}^{*} = \mathop{\rm arg~max}_{\mathbf{x} \in \mathcal{X}} : f(\mathbf{x})$, where the search space $\mathcal{X}$ is defined as a hyperrectangle (bounded by lower and upper limits for each dimension).
• Surrogate Model: It uses Gaussian Process Regression to model the latent function based on observed data.
• Acquisition Function: It currently uses the Expected Improvement (EI) function to determine the next sampling point.
• Workflow: The optimizer iteratively samples points to find the maximum of the objective function.

To use the gradient descent optimization method, include the corresponding header file in your C++ project. This implementation is a gradient-based local optimization method that utilizes backtracking line search to determine step sizes.

#include <mathtoolbox/gradient-descent.hpp>

To use the probability distribution functions and their derivatives in your C++ project, include the following header file:

#include <mathtoolbox/probability-distributions.hpp>

To use the line search method that finds a step size satisfying the strong Wolfe conditions (Armijo sufficient decrease and curvature conditions), include the following header in your C++ project:

#include <mathtoolbox/strong-wolfe-conditions-line-search.hpp>

This implementation follows Algorithm 3.5 from Nocedal and Wright (2006), Numerical Optimization.

The Limited-memory BFGS (L-BFGS) method is a quasi-Newton numerical optimization algorithm provided by mathtoolbox. It is designed for large-scale optimization problems where storing a full Hessian matrix is impractical.

Implementation Details

• Inverse Hessian Initialization: Uses the strategy from Nocedal and Wright (2006), Equation 7.20: $\mathbf{H}k^0 \leftarrow \frac{\mathbf{y}{k - 1}^T \mathbf{s}{k - 1}}{\mathbf{y}{k - 1}^T \mathbf{y}_{k - 1}} \mathbf{I}$.
• Line Search: Employs the strong-wolfe-conditions-line-search algorithm to determine appropriate step sizes.

C++ Integration

To use L-BFGS in your C++ project, include the following header:

#include <mathtoolbox/l-bfgs.hpp>