Source-linked AI summary
Enhancing finite-difference based derivative-free optimization methods with machine learning
Timothé Taminiau, Estelle Massart, Geovani Nunes Grapiglia
TL;DR
Finite-difference DFO methods collect data that can be reused to address the cost of black-box optimization, but prior surrogate variants did not outperform the base method. The paper adds a surrogate-search heuristic using function values and approximate gradients, and reports significant performance improvements, especially when gradient information is used through Sobolev learning.
Problem
Finite-difference-based DFO generates rich data, but leveraging those data to improve black-box optimization performance remains a central challenge.
Method
The heuristic trains a surrogate from collected function values and approximate gradients, applies gradient descent with Armijo line search, and returns to the base method when true-objective decrease is insufficient.
Results
Numerical experiments demonstrate significant performance improvements over the base method, particularly when approximate-gradient data are leveraged through Sobolev learning.
Takeaways & Limitations
Surrogate steps can improve finite-difference DFO efficiency, with the theoretical complexity constant decreasing as the average number of successful surrogate steps increases.
Takeaways & Limitations
The analysis assumes the objective is bounded from below, and its complexity results use an additional assumption for the surrogate-accelerated method.
Abstract
from arXiv · showhide
Derivative-Free Optimization (DFO) involves methods that rely solely on evaluations of the objective function. One of the earliest strategies for designing DFO methods is to adapt first-order methods by replacing gradients with finite-difference approximations. The execution of such methods generates a rich dataset about the objective function, including iterate points, function values, approximate gradients, and successful step sizes. In this work, we propose a simple auxiliary procedure to leverage this dataset and enhance the performance of finite-difference-based DFO methods. Specifically, our procedure trains a surrogate model using the available data and applies the gradient method with Armijo line search to the surrogate until it fails to ensure sufficient decrease in the true objective function, in which case we revert to the original algorithm and improve our surrogate based on the new available information. As a proof of concept, we integrate this procedure with the derivative-free method proposed in (Optim. Lett. 18: 195--213, 2024). Numerical results demonstrate significant performance improvements, particularly when the approximate gradients are also used to train the surrogates.
1 Introduction
Finite-difference-based DFO methods generate reusable data about black-box objectives, motivating surrogate models that can propose low-cost search points. This work introduces a heuristic that uses these data, including approximate gradients, to enhance such methods.
- Motivation: Finite-difference-based DFO methods can exploit iterates, function values, step sizes, and gradient approximations collected during optimization.These data support surrogate models that identify promising candidate points or search directions with few additional objective evaluations.
- Related work: Earlier surrogate variants using neural networks, polynomials, and radial basis functions did not outperform the finite-difference base method.The reported experiments used a subset of CUTEst problems.
- Contribution: The proposed heuristic trains a surrogate from function-value data augmented with approximate-gradient pairs, then applies gradient descent with Armijo line search to it.The surrogate search continues until sufficient decrease in the true objective is not ensured, after which the best point found is returned and the original method resumes.
- Contribution: The heuristic is designed to enhance virtually any finite-difference-based DFO method and is demonstrated by integration with the derivative-free method proposed by.The paper presents this integration as a proof of concept.
- Results: Numerical experiments with radial basis functions and neural-network surrogates demonstrate significant performance improvements over the base method.The proposed procedure is positioned as an auxiliary enhancement rather than a replacement for the underlying DFO algorithm.
2 Surrogate-based heuristic
The heuristic integrates surrogate steps into finite-difference DFO while retaining the base method when surrogate progress is insufficient. Under the stated assumptions, successful surrogate steps reduce the theoretical evaluation complexity.
- Algorithm: The heuristic trains a continuously differentiable surrogate, performs surrogate steps, and stops when the sufficient-decrease condition is no longer met.It returns the best surrogate point and uses it as the next iterate; otherwise, the base method continues with newly collected data.
- Theory: Under A1, Algorithm 1 terminates finitely, while additional assumptions ensure Algorithm 3 is well defined when ∥∇f(xk)∥2 > ϵ.The analysis also bounds the step-size parameter over the relevant iterations.
- Algorithm: Algorithm 3 integrates the surrogate heuristic into a finite-difference gradient-descent DFO method with Armijo line search.The integration requires only small changes to the base method and retains the original algorithmic structure.
- Complexity: The complexity bound retains O(nϵ−2) function evaluations, with its constant factor inversely proportional to the average number of successful surrogate steps.When no surrogate step succeeds, the bound matches the base method; successful steps yield a smaller surrogate gain.
- Complexity: If the average number of successful surrogate steps is positive, the surrogate gain is below one and the worst-case oracle-complexity bound improves.In the ideal case S(T(ϵ)) ≥ n, the dimension dependence is reduced to the term involving log2(σmax/σ0)(n + 1).
3 Surrogate models of the objective
The paper uses shallow neural networks and radial basis functions as surrogate families, training them with function values and finite-difference gradient information. Sobolev learning is interpreted as curvature-related regularization under exact interpolation.
- Sobolev learning: The surrogate is trained with errors on both model values and model derivatives, a procedure known as Sobolev learning [7].The derivative targets are finite-difference approximations obtained from evaluations at each reference point and its coordinate perturbations.
- Sobolev learning: When all relevant points are exactly interpolated, Sobolev learning with forward finite differences penalizes a term related to surrogate curvature.This interpretation follows from the finite-difference gradient error and a second-order Taylor expansion.
- Model families: The paper considers two surrogate families: shallow neural networks and radial basis functions.For radial basis functions, setting λ = 0 permits efficient least-squares solution of the model parameters.
- Model families: The neural-network surrogate is a one-hidden-layer model with an activation function, weight matrices, and biases.Training its parameters generally requires an iterative optimization algorithm and can incur substantial additional cost.
4 Numerical results
Across the CUTEst-based benchmark, surrogate-accelerated methods outperform the finite-difference base method, with Sobolev learning generally improving both neural-network and RBF surrogates. SoftPlus neural networks outperform Gaussian RBFs numerically, although RBFs may be faster when function evaluations are inexpensive.
- Neural-network surrogates: The SoftPlus NN-accelerated method outperforms the base method, and Sobolev learning further improves its performance.The data profile uses a budget of 100 simplex gradients and compares standard learning with Sobolev learning.
- Radial-basis-function surrogates: Gaussian RBF surrogates also outperform the base method, with further improvement when Sobolev learning uses finite-difference gradients.The comparison is presented in the Gaussian-RBF data profile for a budget of 100 simplex gradients.
- Surrogate gain: Median surrogate gains are approximately 0.4 for Sobolev-trained NN surrogates and 0.3 for Sobolev-trained RBF surrogates, versus 0.7 and 0.6 without Sobolev learning.The surrogate gain measures improvement captured by the worst-case complexity bound; smaller values indicate more efficient surrogate steps.
- Comparison of surrogate models: The NN-accelerated method outperforms the RBF-accelerated method, although RBF steps may be accepted more often while producing smaller objective reductions.The gap relative to the base method increases overall with the maximum function-evaluation budget.
- Computational cost: RBF acceleration may be substantially faster than NN acceleration when objective evaluations are relatively inexpensive because RBF models cost less to train.When function evaluations are very costly, surrogate-training cost has less impact on total runtime.
5 Concluding remarks
The paper introduces a surrogate-based heuristic for finite-difference DFO methods and establishes complexity and numerical-performance benefits for the integrated scheme.
- 5 Concluding remarks: O(nϵ−2) function evaluations suffice to find an ϵ-approximate stationary point, with the constant inversely proportional to average surrogate steps.Each outer iteration costs O(n) evaluations, while each surrogate step costs one evaluation.
- 5 Concluding remarks: The heuristic yields significant performance improvements over the base method, particularly when approximate-gradient data are incorporated through Sobolev learning.The numerical tests covered different surrogate models and learning strategies.
A Supplementary numerical results
Supplementary experiments compare neural-network and radial-basis surrogate choices under Sobolev learning using data profiles with a tolerance of 10−4 and a budget of 100 simplex gradients.
- A Supplementary numerical results: Surrogate-accelerated performance is largely insensitive to the chosen activation or radial basis function, with Sobolev learning remaining robust across choices.Figures 5 and 6 compare the corresponding neural-network and radial-basis alternatives.
- A Supplementary numerical results: The neural-network comparison uses data profiles at tolerance 10−4 and a budget of 100 simplex gradients under Sobolev learning.The tested alternatives differ by activation function.
- A Supplementary numerical results: The radial-basis comparison uses data profiles at tolerance 10−4 and a budget of 100 simplex gradients under Sobolev learning.The tested alternatives differ by radial basis function.