{"id":"51be2fae-1770-4ed6-b7cc-40f2da398f37","arxiv_id":"2502.07435","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A surrogate trained with Sobolev learning accelerates a finite-difference derivative-free method, with a complexity bound that improves with the average number of successful surrogate steps.","lead":"This paper adds a machine-learning surrogate step to a finite-difference derivative-free optimization method, training a model on function values and approximate gradients and taking fast model-based steps until they stop improving the true function. If the surrogate steps work often, the worst-case number of function evaluations drops, and tests on 134 optimization problems show gains over the base method.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The oracle-complexity bound in Theorem 2.4 is internally consistent, but the practical speedup claim depends on excluding surrogate training costs from the comparison; a wall-clock-normalized benchmark would settle whether the acceleration survives for cheap evaluations.","rationale":"I read the paper as making two related claims: a theoretical worst-case oracle-complexity guarantee for Algorithm 3, and a practical claim that adding surrogate steps improves performance. The theoretical claim is well supported. The proof of Theorem 2.4 is algebraically consistent: substituting the bound on T(epsilon) from Lemma 2.3 into the evaluation count gives the stated leading term, and the separate +T(epsilon) term is legitimate because the step count is not replaced by an upper bound. The numerical claim, however, is benchmarked exclusively in terms of function evaluations, while the surrogate training effort, especially the L-BFGS solve for the NN surrogate, is not counted. This is exactly the reader's weakest assumption, and it is load-bearing because the paper's headline is about performance improvement, not merely about oracle complexity in an expensive-evaluation limit. The authors partially acknowledge the issue when comparing NN and RBF surrogates, but they do not quantify when training cost dominates. A wall-clock-normalized experiment would directly test whether the claimed improvements survive outside the expensive-oracle regime. Since the reader's conditional verdict already captures this uncertainty, I do not propose changing the verdict.","tokens_in":11366,"tokens_out":7517,"duration_ms":74987,"concrete_test":"Re-run the 134-problem benchmark with a wall-clock budget instead of a fixed simplex-gradient budget. For each problem, record cumulative CPU time spent in surrogate training (NN and RBF separately) and in f evaluations, then build data profiles with total CPU time on the x-axis for several assumed per-evaluation costs (e.g., 1 ms, 10 ms, 1 s). If the NN-accelerated method is slower than the base method for cheap evaluations on a substantial fraction of problems, the practical improvement claim is limited to expensive-evaluation regimes. Additionally, fix random seeds and rerun Figure 1 at least three times to confirm that the reported advantage is not an artifact of a single stochastic training run.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim has two parts: (i) the worst-case oracle complexity bound in Theorem 2.4, and (ii) the numerical claim that Algorithm 3 significantly outperforms Algorithm 2. Part (i) is sound: FE counts only evaluations of f, the accounting in the proof of Theorem 2.4 is consistent (the +T term absorbs the otherwise missing +1), and the final bound follows from Lemma 2.3. Part (ii) is less secure. In Algorithm 1, Step 1 trains the surrogate by approximately solving (2) with L-BFGS, allowed up to 1000 iterations each time it is called, and Algorithm 3 calls this surrogate routine at every outer iteration. Theorem 2.4 and the data profiles in Section 4 count only zeroth-order oracle calls; the time spent training the surrogate, including warm-starting, backpropagation, and L-BFGS iterations, is invisible to both the theory and the benchmark. The paper acknowledges the training-cost asymmetry only between NN and RBF surrogates in Section 4.3, not between the accelerated method and the base method. If evaluating f is cheap relative to training the surrogate, the apparent gain measured in simplex gradients can be eroded or reversed in wall-clock time. Thus the load-bearing assumption is that oracle evaluations dominate total computational cost; this is plausible for the motivating expensive-simulation setting but is not controlled in the reported experiments.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":11703,"tokens_out":21502,"duration_ms":176528,"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":[{"comment":"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.","section":"Section 4.2, Figures 1-4"},{"comment":"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":"Lemma 2.2"},{"comment":"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.","section":"Section 4.2"}],"minor_comments":[{"comment":"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.'","section":"Section 4.3"},{"comment":"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.","section":"Algorithm 1"},{"comment":"The notation 'log' in the telescoping line should be 'log2' for consistency with the rest of the paper.","section":"Proof of Theorem 2.4"},{"comment":"The expression eta(S(T(epsilon)) is missing a closing parenthesis; it should be eta(S(T(epsilon))).","section":"Theorem 2.4"},{"comment":"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.","section":"Section 4.2"}],"recommendation":"major_revision","confidential_remarks":"The reader's report flagged inequality (9) as undercounting trial-point evaluations; on my reading, (9) is a valid upper bound: each inner-loop index i costs n finite-difference evaluations plus one Armijo trial evaluation, so the bound is conservative. The more substantive weakness is the exclusion of training costs from the numerical comparison, which I have raised as a major comment. The paper's reliance on [13] for Lemma 2.2 is a legitimate dependency, but given that [13] is the first author's own paper and the simplified Algorithm 2 is not identical, a self-contained proof would increase confidence. Overall, the theoretical contribution is sound and the numerical study is reasonably extensive, but the practical claim requires additional evidence."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this paper does what it says. It adds a Sobolev-trained surrogate (using finite-difference gradients) to a finite-difference DFO method, with a step-until-failure rule, and proves an oracle-complexity bound that improves with the observed average number of successful surrogate steps. That is a real, new contribution relative to NNAIF and the negative result in [9]. The theory is clean; the reader's worry about undercounting in inequality (9) does not survive inspection. Each gradient computation uses n perturbations, and the Armijo trial is the single extra evaluation, so the (i_k+1)(n+1) count is an upper bound, not an undercount. The stress-test note is right: the accounting is consistent. The complexity theorem is the strongest part, and it is honest in that the surrogate gain eta(S) is an a posteriori quantity, not an assumed condition. The numerical experiments on CUTEst show consistent improvement, and the Sobolev variant is clearly better. So the core is solid. The real soft spot is practical: the benchmarks count simplex gradients, not wall-clock time. Training the surrogate with L-BFGS up to 1000 iterations per outer loop is excluded from both the theory and the data profiles. For the motivating expensive-simulation setting, oracle calls dominate, so this is reasonable, but the paper only acknowledges this for NN-versus-RBF, not for accelerated-versus-base. A wall-clock comparison, or at least a sensitivity analysis with cheap test functions, would settle whether the acceleration survives. Minor issues: no seeds for the stochastic NN training and no code shipped, which limits reproducibility. The citation of the first author's earlier paper for the base-method lemmas is standard dependency, not circularity. Overall, this is a worthwhile paper for the DFO community. It deserves a serious referee, but the referee should press for a clearer statement that the method targets expensive-oracle settings and ideally for wall-clock results or code. I'd send it to peer review.","headline":"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.","tokens_in":12209,"tokens_out":6727,"would_cite":true,"duration_ms":61662,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C56","90C30","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["derivative-free optimization","finite-difference gradients","surrogate models","Sobolev learning","worst-case complexity","neural networks","radial basis functions","data profiles"],"falsifier":"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.","tokens_in":11176,"feed_emoji":"⚙️","tokens_out":11223,"duration_ms":91586,"temperature":0.7,"pith_summary":"Derivative-free optimization methods that replace gradients by finite differences automatically accumulate a dataset of points, function values, approximate gradients, and step sizes. The paper's proposal is to train a surrogate model on that dataset, including the approximate gradients through Sobolev learning, and then take cheap surrogate-driven gradient steps until they stop decreasing the true objective, at which point the base method resumes. Integrated with a finite-difference method from the literature, the heuristic finds an $\\epsilon$-approximate stationary point with at most $O(n\\epsilon^{-2})$ function evaluations, and when the average number of successful surrogate steps per outer iteration is at least $n$, the leading term becomes $O(\\epsilon^{-2})$, independent of dimension. Each attempted surrogate step costs one function evaluation, which is why a surrogate that is accepted more often shrinks the constant in the worst-case bound. Numerical data profiles on 134 problems from the OPM/CUTEst benchmark show that neural-network and radial-basis surrogates solve more problems within a fixed budget than the base method, especially when approximate gradients are used in training.","feed_headline":"Surrogate steps make derivative-free optimization cost independent of n","feed_subtitle":"Each surrogate step tried costs one function evaluation; tests on 134 CUTEst problems confirm the speedup.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the base finite-difference DFO method (Algorithm 2) whose per-iteration decrease and stepsize bounds underpin the complexity analysis.","marker":"[13]"},{"why":"Introduces the neural-network surrogate-acceleration idea for implicit filtering that this paper adapts, including the loss formulation (1).","marker":"[17]"},{"why":"Provides the Sobolev-training formulation used in the surrogate objective (2).","marker":"[7]"},{"why":"Provides the OPM benchmark set whose 134 problems are used for the numerical comparisons.","marker":"[14]"},{"why":"Provides the CUTEst environment from which the benchmark problems are drawn.","marker":"[11]"},{"why":"Defines the data profiles and the convergence test used to compare methods.","marker":"[21]"},{"why":"Earlier surrogate variants of a finite-difference method failed to outperform their base method, motivating the gradient-augmented design.","marker":"[9]"}],"fun_headline_variants":["Surrogate wrapper kills n-dependence in finite-difference DFO","Surrogate steps give derivative-free optimization a cost bonus","Surrogate-based acceleration removes n factor in DFO complexity","Machine-learned surrogates speed up finite-difference DFO"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Surrogate wrapper kills n-dependence in finite-difference DFO","Surrogate steps give derivative-free optimization a cost bonus","Surrogate-based acceleration removes n factor in DFO complexity","Machine-learned surrogates speed up finite-difference DFO"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000651,"raw_usage":{"total_tokens":3014,"prompt_tokens":1003,"completion_tokens":2011,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":619,"completion_tokens_details":{"reasoning_tokens":1941}},"tokens_in":619,"tokens_out":2011,"duration_ms":12519,"temperature":1.0,"reasoning_tokens":1941,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T12:46:33.825059+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Grapiglia","cited_arxiv_id":null,"evidence_quote":"Supplies the base finite-difference DFO method (Algorithm 2) whose per-iteration decrease and stepsize bounds underpin the complexity analysis."},{"cited_title":"Neural Network Accelerated Implicit Fil- tering: Integrating Neural Network Surrogates With Provably Convergent Derivative Free Op- timization Methods","cited_arxiv_id":null,"evidence_quote":"Introduces the neural-network surrogate-acceleration idea for implicit filtering that this paper adapts, including the loss formulation (1)."},{"cited_title":"OPM, a collection of Optimization Problems in Matlab","cited_arxiv_id":"2112.05636","evidence_quote":"Provides the OPM benchmark set whose 134 problems are used for the numerical comparisons."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the CUTEst environment from which the benchmark problems are drawn."},{"cited_title":"Benchmarking Derivative-Free Optimization Algorithms","cited_arxiv_id":null,"evidence_quote":"Defines the data profiles and the convergence test used to compare methods."},{"cited_title":"The limitation of neural nets for approximation and optimization","cited_arxiv_id":"2311.12253","evidence_quote":"Earlier surrogate variants of a finite-difference method failed to outperform their base method, motivating the gradient-augmented design."}],"review_version":1}