REVIEW 3 major objections 5 minor 25 references
Enhancing finite-difference based derivative-free optimization methods with machine learning
T0 review · 3 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash
Pith's one-line read A surrogate-model wrapper around finite-difference derivative-free optimization reduces the worst-case function-evaluation count, and its leading term becomes $O(\epsilon^{-2})$, independent of dimension, when successful surrogate steps…
desk verdict A genuinely useful surrogate-acceleration paper for finite-difference DFO with a solid complexity theorem; the main caveat is that the numerical gains are measured in oracle calls, not wall-clock time, so the training overhead is unaccounted. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The carrying object is Algorithm 1, the surrogate step: after the base method computes a finite-difference gradient, the datasets $F$ and $G$ are updated and a surrogate $m_\theta$ is trained by minimizing the Sobolev-learning objective (2), which penalizes both mismatches to stored function values and mismatches of $\nabla m_\theta$ to stored finite-difference gradients. The decisive property is that each accepted surrogate step forces a decrease of at least $\epsilon^2/(2\gamma\sigma_{\max})$ in the true objective while costing one function evaluation, so the proof can add these decreases to the base method's own decrease. Proposition 3.1 identifies the geometric content of the Sobolev penalty: if the surrogate interpolates the finite-difference points exactly, the gradient-matching term equals a second-order Taylor remainder, so Sobolev learning with finite-difference gradients is a penalty on the surrogate's curvature.
What would settle it
A decisive experiment would count surrogate-training effort in the budget: on a cheap-to-evaluate problem, track total wall-clock time and total L-BFGS-iteration cost for Algorithm 3 with a neural-network surrogate versus Algorithm 2, both run until $\|\nabla f(x_k)\|_2 \le \epsilon$; if the accelerated method is slower once training is included, the practical efficiency claim fails even though Theorem 2.4 remains correct as an oracle-counting statement. A simpler version would repeat the data profiles with the x-axis measured in units that include surrogate training cost rather than simplex gradients.
Extended reading notes
Core claim
On its own terms, the paper's central claim is that a simple wrapper provably improves finite-difference DFO: train a continuously differentiable surrogate on the collected points and finite-difference gradients, then apply gradient descent with Armijo line search to the surrogate until it fails to ensure sufficient decrease of the true objective, and accept each such step as a new iterate. Theorem 2.4 bounds the number of function evaluations by $4\eta(S)(n+1)C_{\max}(f(x_0)-f_{\mathrm{low}})\epsilon^{-2} + \log_2(\sigma_{\max}/\sigma_0)(n+1) + T(\epsilon)$, where $\eta(S) = (1 + S/(2(n+1)))/(1+S)$ and $S$ is the average number of successful surrogate steps per outer iteration. Because $\eta(S)$ decreases with $S$, a surrogate that is accepted more often gives a strictly better oracle-complexity bound, and for $S \ge n$ the leading term becomes $O(\epsilon^{-2})$ with no factor of $n$. The paper also shows numerically, using radial-basis and shallow neural-network surrogates on 134 benchmark problems, that the accelerated method outperforms the base method, and that Sobolev learning, which includes approximate gradients in the training objective, strengthens the improvement.
Load-bearing premise
The practical acceleration rests on the assumption that training or updating the surrogate is negligible compared with one evaluation of $f$: the theorem counts only zeroth-order oracle calls, and the numerical plots count only simplex gradients, so surrogate training, which for neural networks is an L-BFGS solve of a nonconvex problem run up to 1000 iterations per outer step, is not part of the budget. If function evaluations are cheap relative to training, the apparent speedup can vanish.
Editorial extensions
If this is right
- Each attempted surrogate step consumes one function evaluation, and each accepted step contributes a fixed $\epsilon^2$-scale decrease in the objective, so more reliable surrogates translate directly into a smaller worst-case evaluation count.
- If the average number of successful surrogate steps per outer iteration reaches $n$, the leading term in the evaluation bound becomes $6C_{\max}(f(x_0)-f_{\mathrm{low}})\epsilon^{-2}$, independent of the dimension; only a logarithmic $n$-term from the unknown Lipschitz constant remains.
- The heuristic cannot worsen the theoretical worst case: if no surrogate step is ever accepted, the bound reduces to the base method's $O(n\epsilon^{-2})$ with the same constants.
- Including finite-difference gradients in surrogate training is numerically beneficial: Sobolev learning gives lower surrogate-gain values and better data profiles than training on function values alone.
- On the 134-problem benchmark, the surrogate-accelerated methods solve a larger proportion of problems within any fixed budget of simplex gradients than the base method, and the gap widens as the budget grows.
Reading between the lines
- My inference: the same wrapper should accelerate other finite-difference DFO methods, since the proof of Theorem 2.4 only needs the base method to supply a per-iteration decrease lower bound and bounded finite-difference stepsizes; any method satisfying those two inequalities inherits the $\eta(S)$ gain.
- My inference: Proposition 3.1 suggests a design rule the paper does not state explicitly; when interpolation is inexact, the surrogate's curvature along coordinate directions is still the quantity Sobolev learning controls, so choosing models with bounded second derivatives should make the accepted surrogate steps more reliable.
- My inference: because the complexity theorem and the data profiles count only function evaluations, an apples-to-apples comparison for cheap objectives should include surrogate-training work; the paper's own remark that RBF training is much cheaper than neural-network training implies that a wall-clock benchmark could shift the NN-versus-RBF ranking on problems where evaluations are fast.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper proposes a surrogate-based acceleration heuristic for finite-difference derivative-free optimization (DFO). The heuristic (Algorithm 1) trains a surrogate model using the accumulated dataset of function values and finite-difference gradient approximations (Sobolev learning, equation (2)), and then performs gradient descent with Armijo line search on the surrogate until a step fails to produce sufficient decrease on the true objective, at which point control returns to the base DFO method and the dataset is augmented. The authors integrate this heuristic with a simplified version of the derivative-free quadratic regularization method of Grapiglia (Algorithm 2), yielding Algorithm 3. The main theoretical result is Theorem 2.4, which bounds the number of function evaluations required to reach an epsilon-approximate stationary point by 4*eta(S)*(n+1)*C_max*(f(x0)-f_low)*epsilon^{-2} + log2(sigma_max/sigma0)*(n+1) + T(epsilon), where eta(S) = (1 + S/(2(n+1)))/(1+S) decreases with the average number of successful surrogate steps S; when S >= n, the leading term becomes independent of n. Numerical experiments on 134 CUTEst problems compare NN and RBF surrogates, with and without Sobolev learning, against the base method using data profiles measured in simplex gradients.
Significance. If Theorem 2.4 is correct, the paper provides a clean and honest oracle-complexity certification for a class of ML-accelerated DFO methods: the bound depends on the observed number of successful surrogate steps rather than assuming it, and each successful surrogate step provably costs only one function evaluation. The proof of the main theorem is mostly elementary and the accounting of function evaluations is consistent. Proposition 3.1 gives a neat interpretation of Sobolev training with finite-difference gradients as curvature regularization. The numerical section is thorough in its coverage of model families and ablations, and the reported median surrogate gains (eta approximately 0.3-0.4 with Sobolev learning) support the qualitative prediction of the theory. However, the practical significance of the acceleration depends on the assumption that oracle evaluations dominate the total computational cost, because the NN training cost (L-BFGS up to 1000 iterations per outer loop) is excluded from both the theory and the benchmarks. The paper would be substantially strengthened by a wall-clock-normalized comparison or at least a report of training costs.
major comments (3)
- [Section 4.2, Figures 1-4] The data profiles in Figures 1, 2, and 4 count only simplex gradients, and Theorem 2.4 counts only evaluations of f; the cost of training the surrogate by solving (2) with L-BFGS (up to 1000 iterations per call, Section 4.2) is invisible to both the theory and the benchmarks. Algorithm 3 invokes Surrogate at every outer iteration, so if function evaluations are cheap relative to training, the reported gains in simplex gradients may not translate into wall-clock speedups. The paper acknowledges this asymmetry only in the RBF-versus-NN comparison in Section 4.3, not in the accelerated-versus-base comparison that motivates the abstract's claim of 'significant performance improvements.' Please report training time per run, a wall-clock-normalized data profile, or at least the number of L-BFGS iterations and average training time per problem, so the reader can judge whether the motivating expensive-evaluation regime is represented.
- [Lemma 2.2] Lemma 2.2 is the foundation of the complexity analysis, but its proof is entirely delegated: 'It follows directly from Lemmas 1-4 in [13].' Since Algorithm 2 is a simplified version of the method in [13] (it sets B_k=0 and uses a particular Armijo backtracking), and since the constants C_f and sigma_max appear in Theorem 2.4, the manuscript should either restate the relevant lemmas from [13] and verify that their hypotheses hold for Algorithm 2, or provide a self-contained proof in an appendix. As written, a reader cannot verify the load-bearing estimates (4) and (5) without consulting [13].
- [Section 4.2] The neural network surrogate is trained with L-BFGS starting from He or Glorot random initialization, but the paper does not report the random seeds used, and the data profiles appear to be based on a single run per problem. Because the NN training problem (2) is nonconvex, the surrogate quality and hence the number of successful steps could vary across initializations. Please report the seeds and, ideally, show results over multiple runs with confidence bands, at least for a subset of the test problems, to confirm that the observed improvements are stable.
minor comments (5)
- [Section 4.3] The sentence 'To validate the worst-case complexity bounds derived in Section 2' overstates what is done; computing the empirical surrogate gain eta(S(T_max)) illustrates the factor in the bound but does not validate the bound, since C_max depends on the unknown Lipschitz constant L. Please rephrase, for example, 'To illustrate the behavior of the surrogate gain in the complexity bound.'
- [Algorithm 1] The initialization 'F + := empty set' uses a plus sign as a superscript that is inconsistent with the later notation F^+; please use a consistent symbol.
- [Proof of Theorem 2.4] The notation 'log' in the telescoping line should be 'log2' for consistency with the rest of the paper.
- [Theorem 2.4] The expression eta(S(T(epsilon)) is missing a closing parenthesis; it should be eta(S(T(epsilon))).
- [Section 4.2] The bullet point about the minimal-norm solution for RBF models is helpful, but it should state whether the least-squares solver uses a QR or SVD-based method to compute that solution.
Circularity Check
No significant circularity: Theorem 2.4 is a conditional counting bound, and the only self-citation (Lemma 2.2 from [13]) is an independent prior result about the base method.
full rationale
The central oracle-complexity claim (Theorem 2.4) is derived by counting function evaluations: each finite-difference outer iteration costs (i_k+1)(n+1) evaluations, each accepted surrogate step costs one evaluation of f, and the failed surrogate trial is accounted for by the +T(epsilon) term. The factor eta(S) is defined as a decreasing function of the observed average number of successful surrogate steps S(T(epsilon)); it is measured ex post from the run, not fitted to enforce a target improvement, so the bound is not circular. Lemma 2.2 is imported from Lemmas 1-4 of [13], a prior paper by one of the present authors; although this is a self-citation, [13] is an independent published analysis of the base finite-difference method and does not assume the surrogate acceleration whose complexity is being proved. The numerical comparison counts only zeroth-order oracle calls and excludes NN/RBF training time; the paper itself flags this in Section 4.3, noting that for cheap evaluations the RBF-accelerated method may become substantially faster than the NN-accelerated method. That asymmetry is a benchmarking limitation, not a circular derivation. Accordingly, no load-bearing step reduces to its own inputs.
Assumptions & free parameters
free parameters (4)
- gamma (surrogate decrease threshold constant) =
25/2
- lambda (Sobolev regularization weight) =
1e-4
- Dataset caps N <= 10(n+1), M <= 10 =
N cap 10(n+1), M cap 10
- Algorithmic constants (sigma0, sigma_min, rho, epsilon) =
sigma0=1, sigma_min=1e-2, rho=1e-4, epsilon=1e-5
assumptions (4)
- domain assumption f is differentiable and bounded below (Assumption A1)
- domain assumption nabla f is L-Lipschitz continuous (Assumption A2)
- ad hoc to paper The surrogate model m_theta is continuously differentiable
- domain assumption Oracle cost dominates surrogate training cost
Cite this review
Pith. "Pith review of Enhancing finite-difference based derivative-free optimization methods with machine learning." pith.science (2026). https://pith.science/paper/ZBSHFP3C
@misc{pith2026250207435,
author = {Pith},
title = {Pith review of: Enhancing finite-difference based derivative-free optimization methods with machine learning},
year = {2026},
howpublished = {\url{https://pith.science/paper/ZBSHFP3C}},
note = {Machine review of arXiv:2502.07435}
}
read the original abstract
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.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[9]
The limitation of neural nets for approximation and optimization
Tommaso Giovannelli, Oumaima Sohab, and Luis Nunes Vicente. The limitation of neural nets for approximation and optimization, 2023. arXiv:2311.12253
work page Pith review arXiv 2023
- [13]
-
[1]
Charles Audet and J. E. Dennis. Mesh Adaptive Direct Search Algorithms for Constrained Optimization. SIAM Journal on Optimization , 17(1):188–217, 2006. Publisher: Society for Industrial and Applied Mathematics
work page 2006
-
[2]
Derivative-Free and Blackbox Optimization
Charles Audet and Warren Hare. Derivative-Free and Blackbox Optimization . Springer Series in Operations Research and Financial Engineering. Springer International Publishing, Cham, 2017
work page 2017
-
[3]
A. S. Berahas, O. Sohab, and L. N. Vicente. Full-low evaluation methods for derivative-free optimization. Optimization Methods and Software , 38(2):386–411, 2023
work page 2023
-
[4]
Abdalla, Azizallah Izady, Mohammad Reza Nikoo, and Ali Al- Maktoumi
Mingjie Chen, Osman A. Abdalla, Azizallah Izady, Mohammad Reza Nikoo, and Ali Al- Maktoumi. Development and surrogate-based calibration of a CO2 reservoir model. Journal of Hydrology, 586(124798):124798, 2020
work page 2020
-
[5]
Conn, Katya Scheinberg, and Luis N
Andrew R. Conn, Katya Scheinberg, and Luis N. Vicente. Introduction to Derivative-Free Opti- mization. MOS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics, 2009
work page 2009
-
[6]
Conn, Katya Scheinberg, and Lu ´ ıs N
Andrew R. Conn, Katya Scheinberg, and Lu ´ ıs N. Vicente. Global Convergence of General Derivative-Free Trust-Region Algorithms to First- and Second-Order Critical Points. SIAM Journal on Optimization , 20(1):387–415, 2009
work page 2009
Show all 25 references
-
[7]
Sobolev Training for Neural Networks
Wojciech Marian Czarnecki, Simon Osindero, Max Jaderberg, Grzegorz ´Swirszcz, and Razvan Pascanu. Sobolev Training for Neural Networks. page arXiv:1706.04859, 2017
2017 arXiv
-
[8]
Frazier and Jialei Wang
Peter I. Frazier and Jialei Wang. Bayesian optimization for materials design. arXiv e-prints , 225:arXiv:1506.01349, 2016
2016 arXiv
-
[10]
Understanding the difficulty of training deep feedforward neural networks
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the Thirteenth International Conference on Artificial Intel- ligence and Statistics , pages 249–256. JMLR Workshop and Conference Proceedings, 2010
2010
-
[11]
Nicholas I. M. Gould, Dominique Orban, and Philippe L. Toint. CUTEst: a Constrained and Unconstrained Testing Environment with safe threads for mathematical optimization. Compu- tational Optimization and Applications , 60(3):545–557, 2015. 15
2015
-
[12]
Grapiglia
Geovani N. Grapiglia. Quadratic regularization methods with finite-difference gradient approx- imations. Computational Optimization and Applications , 85:683–703, 2023
2023
-
[14]
Serge Gratton and Philippe L. Toint. OPM, a collection of Optimization Problems in Matlab. arXiv e-prints , page arXiv:2112.05636, 2021
2021 arXiv
-
[15]
Temperature modeling of creep- feed grinding processes for nickel-based superalloys with variable heat flux distribution
Adina Grimmert, Florian Pachnek, and Petra Wiederkehr. Temperature modeling of creep- feed grinding processes for nickel-based superalloys with variable heat flux distribution. CIRP Journal of Manufacturing Science and Technology , 41:477–489, 2023
2023
-
[16]
Delving Deep into Rectifiers: Sur- passing Human-Level Performance on ImageNet Classification
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving Deep into Rectifiers: Sur- passing Human-Level Performance on ImageNet Classification. In 2015 IEEE International Conference on Computer Vision (ICCV) , pages 1026–1034, 2015
2015
-
[17]
Neural Network Accelerated Implicit Fil- tering: Integrating Neural Network Surrogates With Provably Convergent Derivative Free Op- timization Methods
Brian Irwin, Eldad Haber, Raviv Gal, and Avi Ziv. Neural Network Accelerated Implicit Fil- tering: Integrating Neural Network Surrogates With Provably Convergent Derivative Free Op- timization Methods. In Proceedings of the 40th International Conference on Machine Learning , p...
2023
-
[18]
C. T. Kelley. Implicit Filtering . Software, Environments, and Tools. Society for Industrial and Applied Mathematics, 2011
2011
-
[19]
ChemBO: Bayesian Optimization of Small Organic Molecules with Synthesizable Recommendations
Ksenia Korovina, Sailun Xu, Kirthevasan Kandasamy, Willie Neiswanger, Barnabas Poczos, Jeff Schneider, and Eric Xing. ChemBO: Bayesian Optimization of Small Organic Molecules with Synthesizable Recommendations. In Proceedings of the Twenty Third International Conference on Art...
2020
-
[20]
Jeffrey Larson, Matt Menickelly, and Stefan M. Wild. Derivative-free optimization methods. Acta Numerica, 28:287–404, 2019
2019
-
[21]
Benchmarking Derivative-Free Optimization Algorithms
Jorge Mor´ e and Stefan Wild. Benchmarking Derivative-Free Optimization Algorithms. SIAM Journal on Optimization , 20:172–191, 2009
2009
-
[22]
M. J. D. Powell. The NEWUOA software for unconstrained optimization without derivatives. In G. Di Pillo and M. Roma, editors, Large-Scale Nonlinear Optimization, pages 255–297. Springer US, Boston, MA, 2006
2006
-
[23]
On the numerical performance of finite-difference-based methods for derivative-free optimization
Hao-Jun Michael Shi, Melody Qiming Xuan, Figen Oztoprak, and Jorge Nocedal. On the numerical performance of finite-difference-based methods for derivative-free optimization. Op- timization Methods and Software , 38(2):289–311, 2023
2023
-
[24]
L. N. Vicente. Worst case complexity of direct search. EURO Journal on Computational Optimization, 1(1):143–153, 2013
2013
-
[25]
Accelerating Discovery of Polyimides with Intrinsic Microporosity for Membrane-Based Gas Separation: Synergizing Physics-Informed Performance Metrics and Active Learning
Mao Wang and Jianwen Jiang. Accelerating Discovery of Polyimides with Intrinsic Microporosity for Membrane-Based Gas Separation: Synergizing Physics-Informed Performance Metrics and Active Learning. Advanced Functional Materials, 34(23):2314683, 2024. 16 A Supplementary numeri...
2024
Reviewed August 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.