Optimal sample set selection for the simplex gradient
File(s)
Author(s)
Lengyel, Daniel
Type
Thesis
Abstract
This thesis addresses the challenge of estimating the gradient of a potentially noisy black-box function. Accurate gradient estimation is critical in various domains, with applications ranging from parameter assessment of biological processes to trajectory control. In all of these applications, function evaluations are costly and should be minimized when possible. However, there remains only a restricted understanding of the optimal sample set—i.e., the ideal black-box evaluation locations. This understanding is limited to severely constrained structures or heuristic stochastic sampling strategies. This thesis aims to make progress toward filling this gap, with the goal of retaining accuracy while reducing the number of function evaluations, and hence minimizing the cost of gradient estimation.
We focus on the simplex gradient, the gradient of the best linear approximation of the black-box function. The simplex gradient is a robust and accurate estimator that generalizes many finite difference methods and can be seen as the deterministic counterpart to likelihood ratios. We focus on the two most common forms: the fully-determined simplex gradient, the generalization of forward differences, and the centered simplex gradient, a generalization of central differences.
For the fully-determined simplex gradient, Chapter 3 derives optimal, non-orthogonal sampling structures that exploit low-curvature regions, resulting in significant performance gains. The proposed CASG method achieves accuracy comparable to central differences at half the cost. Chapter 4 extends this work to the centered simplex gradient, connecting optimal sample sets to orthogonal roots of homogeneous polynomials. The ORCAS method developed here offers improved worst-case guarantees and shows numerical performance converging to theoretical optima, providing orders of magnitude improvement over existing methods.
Together, these contributions deepen our understanding of optimal sets for gradient estimation, offering practical methodologies to improve accuracy and reduce costs across diverse applications.
We focus on the simplex gradient, the gradient of the best linear approximation of the black-box function. The simplex gradient is a robust and accurate estimator that generalizes many finite difference methods and can be seen as the deterministic counterpart to likelihood ratios. We focus on the two most common forms: the fully-determined simplex gradient, the generalization of forward differences, and the centered simplex gradient, a generalization of central differences.
For the fully-determined simplex gradient, Chapter 3 derives optimal, non-orthogonal sampling structures that exploit low-curvature regions, resulting in significant performance gains. The proposed CASG method achieves accuracy comparable to central differences at half the cost. Chapter 4 extends this work to the centered simplex gradient, connecting optimal sample sets to orthogonal roots of homogeneous polynomials. The ORCAS method developed here offers improved worst-case guarantees and shows numerical performance converging to theoretical optima, providing orders of magnitude improvement over existing methods.
Together, these contributions deepen our understanding of optimal sets for gradient estimation, offering practical methodologies to improve accuracy and reduce costs across diverse applications.
Version
Open Access
Date Issued
2024-07-25
Date Awarded
01/02/2025
License URL
Advisor
Parpas, Panos
Kantas, Nikolas
Jennings, Nicholas Robert
Publisher Department
Department of Computing
Department of Mathematics
Publisher Institution
Imperial College London
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)