Module subspace_embed 

Subspace Embedding Optimization

Reduces the dimensionality of a large-scale optimization problem by projecting the search space into a random low-dimensional subspace and optimising there.

Algorithm sketch

For each restart:

1. Sample a random projection matrix P of shape (subspace_dim × full_dim).
2. Optimize the surrogate g(y) = f(P^T y) in the subspace via coordinate descent.
3. Recover the full-dimensional point x = P^T y.
4. Clip to bounds if provided.

The method is particularly effective when the objective has a low intrinsic dimensionality (e.g., the effective subspace spanned by the gradient is small).

References

• Wang, Z. et al. (2016). “Bayesian Optimization in a Billion Dimensions via Random Embeddings”. JAIR 55.
• Choromanski, K. et al. (2022). “Geometry-Aware Structured Transformations”.

Structs

SubspaceConfig

Configuration for the subspace embedding optimizer.

SubspaceEmbeddingOptimizer

Optimizer that works in a random low-dimensional subspace.

Enums

SketchType

Type of random projection matrix to use for subspace embedding.

Functions

coord_descent_subspace

Coordinate descent in the subspace.

count_sketch

Generate a count-sketch matrix of shape (sub_dim × full_dim).

gaussian_sketch

Generate a Gaussian sketch matrix of shape (sub_dim × full_dim).

rademacher_sketch

Generate a Rademacher sketch matrix of shape (sub_dim × full_dim).