Why and When Neural Networks Improve Local Approximation in Optimization

Chengkuo Bian; Pengcheng Xie

cs.LGAug 25, 2026

Why and When Neural Networks Improve Local Approximation in Optimization

Authors: Chengkuo Bian, Pengcheng Xie

Organizations: University of California, Berkeley, CA 94720, USA. · Applied Mathematics and Computational Research Division, Lawrence Berkeley National Laboratory, University of California, 1 Cyclotron Road, Berkeley, CA 94720, USA.

Abstract

Published experience with neural surrogates in derivative-free optimisation is contradictory: the same family of models that cuts the evaluation count of one solver leaves another unchanged, or makes it worse. We show that the contradiction dissolves once three factors are stated, and that these, rather than the fit accuracy a training curve reports, are what delimit when a learned local model pays. Role: a surrogate that proposes candidates the true objective must still approve helps, while one that replaces a gradient the solver depends on hurts. Radius: a model fitted to an optimisation path is reliable only inside a bounded neighbourhood, and its error neither vanishes as that neighbourhood shrinks nor survives its growth. Room: a surrogate can only accelerate progress the base method is still able to make. We formalise radius-aware local generalisation, relate it to the classical fully linear condition, and test each factor with the surrogate class, training pipeline and base method held fixed. Over 117 benchmark instances safeguarded assistance raises the instances solved to high accuracy from 67 to 84 while gradient replacement lowers them to 65; removing the gradient term from the training loss cuts surrogate acceptance from 0.703 to 0.148; and 1000 paired comparisons over ten noise levels show no noise threshold, only a base method that stops early. The same factors bound the gain: a model-based trust-region solver, which leaves little room, drops from 88 to 86 when the identical surrogate is attached, and released interpolation software stays ahead at 103, and on a Monte-Carlo inventory model repairing the acceptance interface is worth 10.40 cost units against 0.00 for the surrogate.

Figures & tables

m_{\theta}(v_{t})-m_{\theta}(\hat{v}_{t})\ \geq\ \frac{\rho}{2^{\ell_{t}}L_{t}}\,\left\lVert\nabla m_{\theta}(v_{t})\right\rVert_{2}^{2}

Algorithm 1 Safeguarded surrogate steps ( assist ), adapted from Algorithm 1 in [ 12 ]

Method	$\tau=10^{-1}$	$10^{-3}$	$10^{-5}$	lowest $f$
FD base method	109	93	67	8
NN assist (Sobolev)	113	100	84	7
NN assist (value-only)	109	94	66	1
NN replace	110	100	65	0
DFO-TR (ours)	113	102	88	33
DFO-TR $+$ NN assist	113	103	86	10

Table 1: Extended benchmark,

117

instances solved to accuracy

\tau

within

100

simplex gradients, with

f_{L}

taken over all eight variants below, released Py-BOBYQA included. The last column counts instances on which a method returns the lowest final value of the eight. Surrogate variants use the width-

6n

900

-iteration network of Section 9.8 ; the last row repeats safeguarded assistance at the width-

3n

300

-iteration setting to show what undertraining costs.

Figure 1: Data profiles

\delta_{a}(\beta)

over the

117

instances, with

f_{L}

taken over all six methods, all surrogate variants at the width-

6n

900

-iteration setting. Safeguarded assistance separates from its own base method as the tolerance tightens and tracks the model-based trust-region solver, gradient replacement is the weakest embedding, and attaching the surrogate to the trust-region solver does not help.

Figure 2: Region-size sweep,

273

cells. (a) Uniform gradient error relative to the median gradient norm in the same ball, median over cells with a bootstrap band over problems; the dotted line is the slope a fully linear model would have. (b) Distribution over the

39

problem–dimension pairs of the fitted exponent

\beta

e_{g}\sim\Delta^{\beta}

;

69\%

fall below the fully linear rate

\beta=1

, and those above it still carry a nonzero floor at small

\Delta

Figure 3: Noise sweep,

200

cells. (a) The fraction of problem–dimension pairs on which safeguarded assistance still ends at least

1.26\times

lower, with a bootstrap band over problems; the decline is real but the band is wide throughout. (b) On the same runs, the fraction of the evaluation budget consumed before the run stops, and the acceptance rate of surrogate proposals. The runs get shorter; the proposals do not get worse.

Method	median	IQR	paired diff. vs FD base		wins
FD base method	222.3	$[219.3,226.1]$	—		—
NN assist (Sobolev)	222.3	$[218.4,226.1]$	$+0.00$	$[+0.00,+0.00]$	21/90
NN replace	226.1	$[222.3,239.3]$	$+2.32$	$[+0.00,+5.69]$	5/90
Noise-aware base	211.6	$[209.2,215.0]$	$\mathbf{-10.40}$	$\mathbf{[-12.74,-8.84]}$	73/90
Noise-aware $+$ NN assist	212.2	$[208.6,217.1]$	$-10.47$	$[-12.24,-8.28]$	71/90
Adaptive-sampling TR	211.4	$[210.6,212.4]$	—		—

Table 2: Joint-replenishment

(s,S)

system: expected cost of the returned design over

90

runs (

30

seeds

\times

3

starting designs). Paired differences are taken against the FD base method at the same seed and start, with bootstrap

95\%

intervals for the median; “wins” counts runs in which the method beats that base.

Statistic	What it measures	$\rho$	95% CI	Usable
$\kappa_{k}=\\|\nabla m_{k}\\|/\\|g_{k}^{\mathrm{FD}}\\|$	gradient-scale disagreement	$-0.492$	$[-0.532,-0.439]$	yes
acceptance rate at $k-1$	recent track record	$+0.465$	$[+0.392,+0.522]$	yes
$\varrho_{k}$ , training residual	fit quality on own data	$-0.394$	$[-0.467,-0.307]$	yes
$\cos(\nabla m_{k},g_{k}^{\mathrm{FD}})$	gradient-direction agreement	$+0.186$	$[+0.132,+0.232]$	weak
decrease ratio at $k-1$	overshoot of the last failed proposal	$-0.155$	$[-0.234,-0.065]$	mislabelled
$r_{k}$ , overlap ratio	across-iteration redundancy	$-0.097$	$[-0.176,-0.020]$	negligible

Table 3: Candidate gate statistics against the surrogate acceptance rate:

3202

outer iterations on

116

instances at the width-

6n

900

-iteration setting. Spearman

\rho

with mid-ranks; intervals from

800

bootstrap replicates resampling instances rather than iterations.

Surrogate-Assisted Optimization

Surrogate-assisted optimization uses learned approximations to find strong solutions when experiments or simulations are costly.

See all 106 papers

Joint Surrogate Learning of Objectives, Constraints, and Sensitivities for Efficient Multi-objective Optimization of Neural Dynamical Systems
Mar 22, 2026Frithjof Gressmann, Ivan Georgiev Raikov, Seung Hyun Kim +3Neural Surrogate Modeling Surrogate-Assisted Optimization
Siebel School of Computing and Data Science, University of Illinois Urbana-Champaign, Urbana, IL · The Grainer College of Engineering, University of Illinois Urbana-Champaign, Urbana, IL · Department of Neurosurgery, Stanford University, Stanford, CA +3
Input convex neural networks as surrogates in mathematical optimisation
Aug 10, 2026Yu Liu, Jan Kronqvist, Fabricio OliveiraSurrogate-Assisted Optimization Mixed-Integer Linear Programming
Department of Mathematics and Systems Analysis, School of Science, Aalto University, Espoo, Finland · Department of Mathematics, KTH Royal Institute of Technology, Stockholm, Sweden · DTU Management, Technical University of Denmark, Lyngby, Denmark
Performance of Neural and Polynomial Operator Surrogates
Apr 1, 2026Josephine Westermann, Benno Huber, Thomas O'Leary-Roseberry +1Surrogate Modeling PDE Surrogate Modeling
Heidelberg University · The Ohio State University

Mar 22, 2026J/K move · Enter open · S save

Joint Surrogate Learning of Objectives, Constraints, and Sensitivities for Efficient Multi-objective Optimization of Neural Dynamical Systems

Frithjof Gressmann, Ivan Georgiev Raikov, Seung Hyun Kim, Mattia Gazzola+2

Siebel School of Computing and Data Science, University of Illinois Urbana-Champaign, Urbana, IL · The Grainer College of Engineering, University of Illinois Urbana-Champaign, Urbana, IL · Department of Neurosurgery, Stanford University, Stanford, CA+3

Neural Surrogate Modeling Surrogate-Assisted Optimization Multi-Objective Optimization Sensitivity Analysis

Open paper AskPDF arXiv

Gaussian process surrogates dominate constrained multi-objective optimization because they are effective in data-scarce regimes, but their cubic scaling in training samples limits their ability to capture shared structure between objectives and constraints as problems grow in dimensionality. We show that deterministic neural network surrogates, equipped with feature tokenization and adaptive output normalization, match or exceed Gaussian process accuracy, while scaling to high-dimensional output spaces and training on all data including infeasible samples. Jointly training a single Feature Tokenizer Transformer to predict objectives, constraint satisfaction, and parameter sensitivities yields a unified gradient that simultaneously improves objective values, steers toward feasibility, and identifies the most influential parameters: a coherent search signal that disjoint per-output models cannot provide. We validate this on biophysical neural optimization problems of increasing complexity. In the hardest regime, with wide, uninformed parameter bounds where random sampling finds zero feasible solutions, descending the surrogate's learned constraint gradient steers the search into the feasible region and recovers near-optimal solutions where standard surrogate optimization and constrained Bayesian optimization find none.

Abstract

Surrogate-Assisted Optimization

Explore similar work

Joint Surrogate Learning of Objectives, Constraints, and Sensitivities for Efficient Multi-objective Optimization of Neural Dynamical Systems

Input convex neural networks as surrogates in mathematical optimisation

Performance of Neural and Polynomial Operator Surrogates