Fast Rank-1 Lattice Targeted Sampling for Black-box Optimization

Yueming LyuNeurIPS 2023 · OpenReview

Overview

Researchers have developed Rank-1 Lattice Targeted Sampling (RLTS), a novel technique that brings the query efficiency of Bayesian Optimization to high-dimensional problems typically reserved for Evolution Strategies. By utilizing structured "rank-1 lattices" for sampling, the computational cost of Gaussian Process (GP) training is reduced from a sluggish $O(n^3)$ to a lightning-fast $O(n \log n)$. This breakthrough enables up to 300x speedups over state-of-the-art high-dimensional optimizers.

The Challenge in Black-Box Optimization

In black-box optimization—where the goal is to find the minimum of a function without knowing its internal mathematical structure (e.g., tuning a massive language model or a robot controller)—there is a classic trade-off:

  • Bayesian Optimization (BO) is highly sample-efficient because it builds a surrogate model (a Gaussian Process) to predict promising search areas. However, it is computationally expensive ($O(n^3)$ complexity) and typically struggles to scale beyond a few dozen dimensions.
  • Stochastic Optimization methods (like Evolution Strategies or CMA-ES) are fast and can scale to thousands of dimensions. However, they act as "dumb" samplers, often just spraying random Gaussian noise around the current best guess. This leads to poor query efficiency, requiring thousands of extra function evaluations to find the optimum.

The authors aim to bridge this gap, seeking a way to leverage the "intelligence" of Gaussian Processes in high-dimensional spaces without the crippling computational overhead.

Methods: Rank-1 Lattice Targeted Sampling

The core of the proposed solution is Rank-1 Lattice Targeted Sampling (RLTS), which relies on three main innovations:

  1. Structured Sampling with Rank-1 Lattices: Instead of picking random points (i.i.d. Gaussian sampling), the authors use a specific type of Quasi-Monte Carlo sampling called a Rank-1 Lattice. These points are much more evenly distributed than random noise, providing better coverage of the search space.
Comparison of Rank-1 Lattice Sampling vs. i.i.d. Gaussian Sampling.
  1. The FFT Speedup: Because the lattice points possess a highly regular structure, the "kernel matrix" used in Gaussian Processes becomes a circulant matrix. This structural property is a massive computational advantage. By utilizing Fast Fourier Transforms (FFT), the authors can perform GP training and inference in $O(n \log n)$ time instead of $O(n^3)$.
  2. Fast Coordinate Search: To find the next "targeted" point to sample, the authors developed a coordinate descent method that also leverages the lattice structure and FFTs, keeping the search phase equally fast at $O(n \log n)$.

By plugging this targeted sampler into an existing stochastic optimizer (like INGO), they create a hybrid method that uses a local GP to "nudge" the search toward more promising regions at every step.

Experimental Setup

The authors evaluated RLTS against two main types of challenges:

  • Synthetic Benchmarks: Classic optimization "torture tests," including the Rosenbrock, Rastrigin, and Nesterov functions, evaluated in 50 and 500 dimensions.
  • Real-World LLM Tuning: Black-box prompt fine-tuning for Large Language Models (LLMs). They used six benchmark datasets for different NLP tasks: DBpedia and AG’s News (topic classification), SST2 (sentiment analysis), SNLI and RTE (natural language inference), and MRPC (paraphrasing).

Key Insights and Results

  • Structure is Speed: The most profound insight is that by constraining how we sample (using lattices), we actually liberate the math. The circulant property of the resulting matrices allows the use of 1D signal processing tricks (FFTs) to solve complex 500-dimensional optimization problems.
  • Local Intelligence Beats Global Complexity: Instead of trying to build one giant, expensive GP for the whole search space, RLTS builds a fast, local GP at each step. This provides just enough guidance to improve query efficiency without the overhead of global BO.
  • 300x Speedup: When compared to TuRBO (a state-of-the-art high-dimensional BO method), RLTS achieved a roughly 300x speedup in wall-clock running time while reaching better optimization results.
  • Superior Query Efficiency: On 500-dimensional benchmark functions, RLTS converged significantly faster and to lower objective values than standard CMA-ES and INGO.
Convergence comparison showing RLTS achieving superior query efficiency over INGO and CMAES.
  • LLM Performance: In the prompt-tuning experiments, RLTS consistently reduced the hinge loss faster than its competitors across all six NLP datasets, proving its utility in modern machine learning pipelines.

Limitations and Future Work

While RLTS is a major step forward, some areas remain open for future exploration:

  • Local vs. Global Optima: The paper focuses on local GP models. While excellent for high-dimensional fine-tuning, the method might still be susceptible to getting stuck in local optima if the initial starting point is very poor.
  • Kernel Limitations: The computational speedup relies on shift-invariant kernels (like RBF or Matern) to maintain the circulant matrix property. It remains unclear how RLTS would adapt to more exotic, non-stationary kernels.
  • Downstream Applications: The authors suggest their new closed-form rank-1 lattice construction could have applications in other fields, such as numerical integration or complex simulations, which have yet to be explored.

Summary updated

Abstract

Black-box optimization has gained great attention for its success in recent applications. However, scaling up to high-dimensional problems with good query efficiency remains challenging. This paper proposes a novel Rank-1 Lattice Targeted Sampling (RLTS) technique to address this issue. Our RLTS benefits from random rank-1 lattice Quasi-Monte Carlo, which enables us to perform fast local exact Gaussian processes (GP) training and inference with $O(n \log n)$ complexity w.r.t. $n$ batch samples. Furthermore, we developed a fast coordinate searching method with $O(n \log n)$ time complexity for fast targeted sampling. The fast computation enables us to plug our RLTS into the sampling phase of stochastic optimization methods. This improves the query efficiency while scaling up to higher dimensional problems than Bayesian optimization. Moreover, to construct rank-1 lattices efficiently, we proposed a closed-form construction. Extensive experiments on challenging benchmark test functions and black-box prompt fine-tuning for large language models demonstrate the query efficiency of our RLTS technique.
BibTeX
@inproceedings{lyu2023fast,
  author = {Yueming Lyu},
  title = {{Fast Rank-1 Lattice Targeted Sampling for Black-box Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=M8CYKLHoEN},
}
Figure