Information Preserving Line Search via Bayesian Optimization

Robin Labryga, Tomislav Prusina, Sören Laue

TL;DR

This paper introduces a novel line search method that leverages Bayesian optimization to preserve and utilize information from previous function and gradient evaluations, unlike traditional methods that discard it. This approach leads to more informed step-length decisions, resulting in improved convergence and efficiency, especially for expensive black-box optimization problems.

What Problem Does This Paper Address?

Line search is a crucial component of iterative optimization algorithms, responsible for determining the optimal step size in a given direction to ensure progress towards a solution. Traditional line search methods, such as those based on the Wolfe conditions, rely on iteratively refining an interval that contains a suitable step. However, a significant drawback of these methods is that they discard valuable information (function values and gradients) from previous evaluations once an interval is narrowed. This can lead to suboptimal step choices, particularly when the search space is complex or when function evaluations are computationally expensive. The paper addresses this by proposing a line search method that actively preserves and reuses all observed data to make better decisions.

Methods

The core of the proposed method is the application of Bayesian Optimization (BO) to the line search problem. Instead of discarding past evaluations, the authors maintain a dataset of all observed function values and gradients. This data is used to train a Gaussian Process (GP) surrogate model, which approximates the objective function within the search interval.

The key novelties are:

  • Information Preservation: Unlike traditional methods, all function and gradient evaluations are stored and used to update the GP model.
  • Gaussian Process Surrogate: A GP with a Matérn kernel (specifically v=5) is used to model the objective function and its uncertainty. This allows for more accurate predictions and better exploration of the search space.
  • Lower Confidence Bound (LCB) Acquisition Function: The LCB acquisition function is employed to select the next candidate step. LCB balances exploration (searching uncertain regions) and exploitation (focusing on promising regions), guided by the GP's mean and variance.
  • Interval Management: The method incorporates an interval selection and refinement strategy inspired by the Moré-Thuente approach. This ensures that the search remains within a bounded region and that a step satisfying the strong Wolfe conditions can be found. The interval is dynamically adjusted to guarantee convergence.

Datasets

The paper evaluates its method on the CUTEst test set, which contains 292 unconstrained and 163 bound-constrained optimization problems. The authors note that three unconstrained problems with unbounded optimal solutions were excluded from the experiments.

Key Insights and Ideas

  • Reusing Information is Key: The fundamental insight is that discarding past evaluations in line search is inefficient. By preserving and leveraging this information with a probabilistic model (GP), significantly better step-length decisions can be made.
  • Bayesian Optimization for Line Search is Viable: While BO is typically used for global optimization of expensive black-box functions, this paper demonstrates its effectiveness and potential for the more localized problem of line search.
  • GP Uncertainty Guides Better Steps: The GP's ability to quantify uncertainty is crucial. It allows the acquisition function to intelligently explore regions where the function's behavior is less understood, potentially leading to the discovery of better steps that traditional methods might miss.
  • Dynamic Interval Refinement is Necessary: For BO to be effectively applied to line search, a robust mechanism for managing and refining the search interval is essential, especially since line search often operates on unbounded intervals.

Key Results

The proposed Bayesian line search method, integrated into the GENO solver (named Bayesian GENO), demonstrated superior performance compared to state-of-the-art methods (Cubic GENO, Ipopt, and L-BFGS-B) on the CUTEst test set.

  • Convergence: Bayesian GENO solved the highest number of problems across all criteria (function value convergence, gradient convergence, or at least one criterion) for both unconstrained and bound-constrained problems.
  • Function Evaluations: The method generally required fewer function evaluations to reach a desired level of accuracy compared to Ipopt and Cubic GENO, and was competitive with or outperformed L-BFGS-B, especially on unconstrained problems.
  • Overhead: The Bayesian GENO solver incurs a higher computational overhead per function evaluation compared to Cubic GENO and L-BFGS-B, comparable to Ipopt. This is attributed to the complexity of Gaussian process regression.

Limitations and Future Work

  • Computational Overhead: The primary limitation identified is the increased computational overhead per function evaluation due to the GP modeling and acquisition function optimization. This makes the method most suitable for scenarios where function evaluations are significantly more expensive than the overhead.
  • Future Work: The authors suggest that this method is especially valuable in optimization scenarios where function evaluations are expensive. Future work could explore further optimizations to reduce the overhead or investigate its application in more complex optimization settings. The paper also mentions that the code is available on GitHub, encouraging further research and development.

Summary updated

Abstract

Line search is a fundamental part of iterative optimization methods for unconstrained and bound-constrained optimization problems to determine suitable step lengths that provide sufficient improvement in each iteration. Traditional line search methods are based on iterative interval refinement, where valuable information about function value and gradient is discarded in each iteration. We propose a line search method via Bayesian optimization, preserving and utilizing otherwise discarded information to improve step-length choices. Our approach is guaranteed to converge and shows superior performance compared to state-of-the-art methods based on empirical tests on the challenging unconstrained and bound-constrained optimization problems from the CUTEst test set.
BibTeX
@misc{labryga2025information,
  author = {Robin Labryga and Tomislav Prusina and Sören Laue},
  title = {{Information Preserving Line Search via Bayesian Optimization}},
  year = {2025},
  eprint = {2507.15485},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.15485},
}
Figure