PaperlayerView exact revision on arXiv

Source-linked AI summary

Why and When Neural Networks Improve Local Approximation in Optimization

Chengkuo Bian, Pengcheng Xie

arXiv:2608.24963v1cs.LGmath.OC

TL;DR

Neural surrogates can improve derivative-free optimization in some settings but not others. The paper formalizes radius-aware local generalization and tests surrogate role, reliable radius, and remaining base-method room under controlled comparisons. Safeguarded assistance improves benchmark performance, whereas gradient replacement and attaching the same surrogate to a strong solver do not.

  • Problem

    Published results on neural surrogates in derivative-free optimization are contradictory, with models helping one solver while leaving another unchanged or worsening it.

  • Method

    The paper formalizes radius-aware local generalization, relates it to fully linear models, and varies surrogate role while holding the network class, training pipeline, and base method fixed.

  • Results

    67 to 84 instances solved: safeguarded assistance improved high-accuracy performance over 117 benchmarks, while gradient replacement lowered it to 65.

  • Takeaways & Limitations

    Surrogate value depends on safeguarded assistance, a reliable operating radius, and progress the base method still has available, rather than fit accuracy alone.

  • Takeaways & Limitations

    The main studies use n≤16, and the n=128 probe covers thirteen smooth unconstrained problems with one start each; broader high-dimensional claims remain unsupported.

Abstract

from arXiv · show

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.

1 Introduction

The paper argues that neural-surrogate gains in derivative-free optimization depend less on pointwise fit accuracy than on surrogate role, local-generalization radius, and remaining base-method progress.

  • Training and approximation: 0.703 to 0.148: removing the gradient term from the training loss sharply reduced surrogate acceptance.The paper attributes the benefit of gradient information to restraining curvature that value-only fitting can invent.
  • Main claim: Neural-surrogate benefit is determined by whether the model assists candidate generation or replaces a core algorithmic quantity, operates within its reliable radius, and has base-method room to help.Pointwise approximation accuracy alone poorly predicts optimization benefit.
  • Empirical findings: 65 instances solved: replacing the base method’s gradient with the surrogate degraded performance below the base method’s 67.The comparison isolates role while retaining safeguards and other experimental components.
  • Empirical findings: 67 to 84 instances solved: safeguarded assistance lifted high-accuracy performance over 117 benchmark instances.The improvement represented roughly a sixth of the benchmark, but released Py-BOBYQA still solved 103.
  • Limits and scope: 88 to 86: attaching the identical surrogate to a strong model-based trust-region solver reduced solved instances, indicating limited remaining room for assistance.The released interpolation solver remained ahead at 103.

2 Background and Problem Setting

The background distinguishes local surrogate construction from how models enter derivative-free optimization, emphasizing uniform, radius-dependent reliability and safeguarded use over ordinary regression fit.

  • Problem setting: Derivative-free optimization targets expensive black-box objectives where evaluations are costly and derivatives are unavailable, unreliable, or too expensive.Simulation runs supply objective values, making evaluation count the central currency.
  • Model-based optimization: Trust-region methods build local models around the current iterate, compute trial steps within a radius, and accept or reject them using true-versus-predicted decrease.This separates model quality from acceptance control.
  • Surrogate roles: Replacement substitutes a surrogate for a core quantity, whereas assistance proposes extra candidates while the true objective retains final acceptance.The paper tests this distinction while holding the surrogate class, training pipeline, and base method fixed.
  • Local model quality: Fully linear and fully quadratic models require uniform approximation on a neighborhood, including appropriate derivative accuracy rather than merely fitting sampled values.These conditions give trust-region methods a rigorous meaning for a good local model.
  • Local model quality: Assistance can tolerate an imperfect model because true-objective acceptance filters proposals, while replacement exposes search directions, updates, and globalization logic to surrogate derivative errors.This explains why the same approximation quality can have different optimization consequences under different embeddings.
  • Motivation for learned surrogates: Neural networks offer flexible, smooth surrogates for noisy or irregular data, but direct gradient replacement has not reliably improved optimization despite competitive value and gradient approximation.The paper therefore studies the interaction among coverage, training objectives, smoothness, and algorithmic role.

3 Neural Networks for Local Approximation

Neural networks can improve local approximation through noise smoothing and directional guidance, but optimization gains depend on how the surrogate is embedded, the radius studied, and the approximation order required.

  • Approximation mechanisms: Smoothing across multiple data points can produce a more stable gradient field than noisy finite differences.Smaller finite-difference steps reduce truncation error but increase noise variance as O(h^-2).
  • Approximation mechanisms: Sobolev training matches function values and gradients, improving local directional fidelity for descent guidance.The surrogate is continuously differentiable and used with gradient descent and an Armijo-like condition.
  • Embedding constraints: High-quality value or gradient approximation does not reliably improve optimization when surrogate gradients replace a sensitive algorithmic component.This motivates careful embedding and safeguards.
  • Embedding constraints: Neural networks require continuously differentiable surrogate families when optimization relies on surrogate derivatives.Taminiau et al. therefore exclude ReLU, while Giovannelli et al. identify SiLU as best-performing in their approximation benchmarks.
  • Approximation order: Neural networks can be competitive for zero- and first-order approximation, whereas interpolation and regression models often perform better for second-order approximation.This distinction matters when trust-region methods require fully quadratic models.
  • Approximation order: Activation-enriched polynomial bases can replace some quadratic cross terms while maintaining approximation quality with fewer parameters.These models occupy an intermediate position between classical polynomials and full neural networks.
  • Model choice: The training objective and safeguarded embedding matter more than assuming neural networks are universally best among learned surrogates.RBF surrogates trained with the same Sobolev objective provide a direct comparison.

4 Training Data Selection for Local Models

Training data generated or selected near the optimization path determines local model coverage: geometry, redundancy, and radius jointly constrain generalization and usable surrogate steps.

  • Local data construction: Model-based DFO commonly samples within B(x_k; Δ_k) to support local geometry and stability.Alternative approximation studies sample training and testing data in B(x_0; 1) after shifting and scaling.
  • Local data construction: Online DFO-as-data-generator loops add function values and finite-difference gradient targets from the base method’s iterates.The surrogate is updated as the algorithm naturally explores the region of interest.
  • Geometry and coverage: Diversity-aware sampling and poisedness-improving repairs can improve coverage, reduce redundancy, and strengthen local generalization.The recommendations apply to uniform sampling and to polynomial, RBF, and neural surrogates as appropriate.
  • Geometry and coverage: Λ-poisedness means that an interpolation set yields a well-conditioned system with uniformly bounded Lagrange polynomials on the trust-region ball.This criterion supports classical fully linear and fully quadratic guarantees.
  • Geometry and coverage: Neural networks lack an analogous linear-system criterion, so coverage remains decisive when samples concentrate near a low-dimensional path.Poor orthogonal coverage can limit the surrogate’s local generalization radius.
  • Radius selection: Small trust regions improve locality, whereas large regions support exploration but may exceed the surrogate’s reliable range.The paper couples radius or stepsize scale with diagnostics and region-size sweeps.
  • Radius selection: The tested overlap, step-spacing, and singular-value diagnostics did not predict surrogate proposal acceptance over 3202 outer iterations.This limits their value as standalone acceptance predictors.

5 Offline and Online Learning Strategies

Offline and online learning serve different roles: offline transfer requires shared task structure, while the reviewed primary studies fit or update surrogates locally within individual optimization runs.

  • Offline learning: Offline pre-training can reuse transferable representations across repeated or parameterized optimization tasks with shared structure.Neither primary source assumes this distributional setting.
  • Offline learning: Within this synthesis, offline models are treated as warm starts or priors that bias online fitting toward smoothness.These roles preserve local adaptation rather than replacing it.
  • Offline learning: Cross-objective offline generalization differs fundamentally from local interpolation on a fixed objective and requires explicit testing.A systematic cross-task study is outside the paper’s scope.
  • Online learning: Online learning updates the surrogate as new points are evaluated.This keeps the model coupled to the current optimization run.
  • Online learning: Giovannelli et al. train feedforward neural networks on locally sampled data and evaluate them on separate data from the same ball.Their approximation pipeline compares activations across repeated training runs and reports SiLU as best-performing.
  • Online learning: In FLE-S, neural surrogates are trained online from accumulated data with only 5 initial epochs and 1 subsequent epoch to limit overhead.Learning rates and training thresholds are selected separately for surrogate classes.
  • Online learning: Taminiau et al. warm-start shallow-network retraining and cap dataset sizes at N≤10(n+1) and M≤10.Oldest points are removed when thresholds are exceeded, coupling the design to safeguarded assistance.
  • Hybrid learning: A hybrid strategy combines task-family pretraining, local online fine-tuning, and acceptance of surrogate steps only after sufficient true-objective decrease.This aligns offline priors with safeguarded online assistance.

6 Model Architecture and Complexity

Neural-network architecture trades approximation flexibility against parameter count, training cost, and data requirements; its value depends on oracle expense and the surrounding optimization budget.

  • Architecture: The shallow neural model uses width q=5n, while the approximation experiments use two hidden layers of width 4n each.These are the architectures associated with the two reviewed training pipelines.
  • Architecture: With q=5n, the shallow model has approximately 5n^2 + 10n + 1 parameters.This count makes dimension-dependent training burden explicit.
  • Architecture: The two-hidden-layer architecture has approximately 20n^2 + 12n + 1 parameters.Its parameter count is substantially larger than the shallow model’s.
  • Complexity: Deeper and wider networks may improve approximation while requiring larger datasets and longer training.Expressivity therefore carries a direct computational trade-off.
  • Complexity: Training cost should be compared with function-evaluation cost, because neural-network overhead can dominate when oracle evaluations are moderately priced.For very expensive simulations, higher training cost may still be worthwhile.
  • Regularization: Data normalization, weight decay λ=10^-4, and Sobolev gradient penalties are used to stabilize low-data training and regularize the fit.The gradient penalty can be interpreted as a curvature regularizer under finite differences.

7 Generalization and Error Analysis

The paper treats surrogate trustworthiness as a radius-dependent local property rather than a consequence of pointwise training accuracy. It formalizes this view, connects it to fully linear approximation, and states analytical qualifications and limitations.

  • Radius-aware local generalization: The effective generalization radius requires function- and gradient-error bounds throughout every smaller ball around the current point.The radius-aware definition uses local uniform error profiles and prescribed error envelopes.
  • Radius-aware local generalization: A nonzero gradient-error floor makes the radius zero under the classical fully linear condition, so useful learned-model radii require an explicit floor.The paper reports that the measured floor does not vanish for its fitted networks.
  • Radius-aware local generalization: Reducing the modeling region can improve approximation, but a solver operating beyond the learned model’s bounded reliable region can be misled.This motivates treating sample coverage and working radius as central determinants of surrogate usefulness.
  • Error bounds: Under strong smoothness, coverage, and training-accuracy assumptions, propositions connect sample fill distance and training errors to uniform gradient error.The authors present these propositions as analytical tools rather than verified certificates for trained networks.
  • Error bounds: If surrogate-gradient error is no larger than the true gradient norm, surrogate steps may fail to decrease the objective, whereas true-decrease validation can remain robust.The strict-descent result holds when the true gradient norm exceeds the surrogate-gradient error.
  • Scope and limitations: Finite-difference gradient targets amplify evaluation noise by h^-1, and cross-task generalization remains an explicitly untested direction.The paper notes problem-dependent mitigation trade-offs and leaves multi-objective-function testing for future work.

8 Algorithm Design

The algorithm-design section embeds learned models as safeguarded assistance, combines diagnostics into adaptive gating, and analyzes convergence without claiming a better asymptotic rate. Its design preserves the base method when assistance is disabled, while practical benefit depends on acceptance and available headroom.

  • Role-based embedding: The role taxonomy distinguishes replacing a core DFO ingredient from assisting the base method with safeguarded surrogate proposals.This distinction is the section’s organizing design choice.
  • Training and interfaces: Value-only and Sobolev training differ in whether they fit function values alone or jointly use finite-difference gradient targets.Removing the value term leaves the model identifiable only up to an additive constant, which matters for predicted-decrease acceptance.
  • Safeguarded assistance: Safeguarded assistance evaluates each surrogate proposal on the true objective and retains it only after a true-decrease test.The procedure returns the best point, successful surrogate-step count, and newly evaluated points.
  • Implementation boundary: The reproduced surrogate loop lacks an intrinsic termination test, so the implementation adds an inner-index cap, stall exit, and evaluation-budget bound.The source analysis covers iterations before the hitting time T(epsilon), not behavior near stationarity.
  • ARAS framework: ARAS gates surrogate influence using a computable scale-disagreement diagnostic and a training residual, both available without extra oracle cost.The framework adapts the surrogate’s influence to estimated trustworthiness instead of fixing its role in advance.
  • ARAS framework: Acceptance rates across kappa quartiles fall from 0.484 to 0.045, an elevenfold drop from the lowest to highest quartile.The quartiles are based on the ratio of surrogate to finite-difference gradient norms over 3196 outer iterations.
  • Convergence analysis: ARAS retains the base method’s O(n epsilon^-2) evaluation order and cannot worsen its bound when alpha_k is identically zero.The theorem certifies convergence preservation, not an improved asymptotic rate.

9 Numerical Experiments

Across fixed surrogate and solver configurations, safeguarded assistance improves a weak base method, gradient replacement degrades it, and attaching the surrogate to an already strong interpolation solver adds no benefit. The experiments also show that fit quality, implementation quality, and remaining optimization headroom delimit the observed gains.

  • Benchmark scoring: Using released Py-BOBYQA as the reference value changes the benchmark comparison from assistance leading 99 to 94 to trailing 84 against 88.The reported scoring uses the best value attained by any method.
  • Safeguarded assistance: Safeguarded assistance lifts the base method from 67 to 84 instances solved at τ=10^-5, with smaller gains at looser tolerances.It rises from 93 to 100 at 10^-3 and from 109 to 113 at 10^-1.
  • Training configuration: The trained width-6n, 900-iteration network reaches 84 instances, whereas the earlier width-3n, 300-iteration setting reaches 75, showing that undertraining limits measured performance.All subsequent surrogate results use the trained setting.
  • Remaining headroom: Attaching the identical trained network to the trust-region solver reduces solved instances from 88 to 86, indicating little remaining room for surrogate-driven progress.That solver already builds a quadratic model from the same evaluations.
  • Problem dependence: On extended Wood, assistance solves 7 of 9 instances at τ=10^-5 versus 4 for Py-BOBYQA, but analogous curved-valley problems do not reproduce the win.The network’s local gradient-error advantage also fails to explain this isolated result.
  • Interpolation comparison: Released Py-BOBYQA solves 12 of 13 problems at n=64, compared with 7 for assistance and 5 for the authors’ implementation, separating interpolation quality from implementation degradation.At n=128, it solves 10 of 13 at τ=10^-5, while assistance solves 8 and the finite-difference base solves 6.
  • Gradient replacement: Gradient replacement solves 65 instances versus 67 for its base at τ=10^-5 and accepts no surrogate-gradient step that survives the true-objective test.It triggers 678 finite-difference fallbacks, consistent with the observed loss.

9.3 Region Size and the Generalization Radius

The region-size sweep supports a bounded effective generalization radius: enlarging the fitted neighborhood eventually makes gradient error too large, while shrinking it leaves a training-error floor. Sobolev training improves errors but does not remove either boundary, and greater depth does not improve assisted optimization here.

  • Region-size effects: Relative gradient error rises from 0.055 at Δ=10^-2 to 1.57 at Δ=3.2, where descent can no longer be guaranteed.The reported intervals are [0.050, 0.063] and [0.89, 2.60], respectively.
  • Region-size effects: With fixed sample budget, the surrogate has a finite effective generalization radius because fill distance scales with Δ and the coverage term eventually dominates.This connects sample coverage to radius-aware local generalization.
  • Small-radius floor: Across the smallest three radii, relative error changes only from 0.055 to 0.075, while the median fitted exponent is β=0.87 and 69% of pairs grow sublinearly.The small-radius training-error floor prevents automatic satisfaction of the fully linear condition.
  • Training loss: Sobolev training reduces relative error by a factor of 1.16 to 1.66 across radii but leaves both the small-radius floor and large-radius wall unchanged.Its largest improvement occurs at moderate Δ.
  • Network depth: Two hidden layers worsen small-radius relative gradient error, with two-layer-to-one-layer ratios of 1.069 at Δ=10^-2 and 1.042 at Δ=2.6 × 10^-2.Both intervals exclude one.
  • Network depth: At τ=10^-5, the deeper network solves 97 instances versus 101 for the one-layer network, with acceptance rates of 0.199 and 0.204.At τ=10^-3, the depths are indistinguishable at 111 versus 112 instances.

9.4 Sobolev versus Value-Only Training

Sobolev training preserves gradient information that value-only training lacks, substantially improving surrogate acceptance and benchmark performance. Noise experiments show that apparent thresholds arise from the base method’s acceptance mechanism stopping early, while repairing that interface—not adding the surrogate—produces the inventory-model gain.

  • Training signal: 0.703 versus 0.148: surrogate acceptance falls sharply when the gradient term is removed from the training loss.Both arms use the same width-6n, 900-iteration network, so the comparison isolates the loss term.
  • Noise and room: 0.70 to 0.15: the fraction of helped problem–dimension pairs declines across the noise sweep, but the bootstrap intervals overlap throughout.The largest noise level at which pairs remain helped varies by problem over four decades, so no common noise threshold appears.
  • Noise and room: 62.3% to 21.7%: the fraction of budget consumed before stopping falls with noise, while base and assistance stop within three percentage points of each other.Surrogate proposals fall by a factor of 123, but acceptance only falls by a factor of 1.6, locating the main failure in the base method’s Armijo test.
  • Simulation testbed: The resulting ordering is to make the acceptance test noise-tolerant before asking what a surrogate adds.The paper identifies replication, common random numbers, or statistical acceptance tests as possible repairs.
  • Simulation testbed: 10.40 versus 0.00 cost units: repairing the stochastic acceptance interface helps the inventory model, whereas safeguarded surrogate assistance adds no measurable improvement.The repaired method leads on 73 of 90 runs; the surrogate remains almost never invoked.

9.7 Do the Redundancy Diagnostics Predict Anything?

The study tests whether coverage and model-quality diagnostics predict surrogate acceptance. Model-quality measures are substantially stronger signals, while redundancy measures are too weak to serve as practical gates.

  • Coverage diagnostics: 77%: N_sp equals 1 at most iterations, and directional rank is nearly full, leaving little variation for these coverage measures to explain.Directional rank reaches its maximum at 92%, 90%, and 81% of iterations for dimensions 4, 8, and 16.
  • Coverage diagnostics: −0.097 and −0.063: overlap and step-spacing diagnostics have statistically distinguishable but much smaller effects than model-quality statistics.Their effects are five to eight times smaller, making them unsuitable as practical acceptance gates.
  • Model-quality diagnostics: −0.492, +0.465, and −0.394: gradient-scale ratio, previous acceptance rate, and training residual show the strongest reported associations with acceptance.The signs match the proposed mechanism: over-confident or poorly fitted models produce proposals that fail.
  • Model-quality diagnostics: 0.415 below versus 0.076 above κ_k=2: acceptance separates strongly when iterations are split by the gradient-scale ratio.Across κ_k quartiles, acceptance falls monotonically from 0.484 to 0.343, 0.106, and 0.045.
  • Gate calibration: The calibrated gate does not improve safeguarded assistance because the surrogate is already cheap enough while the model is merely imperfect.The proposed break-even condition is acceptance below 1/(n+1).

9.8 Is the Network the Problem?

The network’s capacity is not the principal bottleneck; training convergence matters more, while surrogate timing benefits depend on oracle cost. The study remains bounded by small dimensions and does not match released interpolation software.

  • Architecture and training: 6 of 13 at 300 iterations versus 8–9 of 13 at 900: training length matters more than width for benchmark performance.Widths from n to 12n change little, and widths 6n and 12n are indistinguishable at 900 iterations.
  • Architecture and training: 75 versus 84 instances: the earlier width-3n, 300-iteration setting understated performance relative to the adopted setting.The paper reports that the correction accounts for a third of the measured gap between assistance and a model-based solver.
  • Timing: 43, 57, and 111 ms: median training-call times at dimensions 4, 8, and 16 in the pure-NumPy implementation.Surrogate-gradient evaluation costs about 18 μs, so training dominates surrogate overhead.
  • Timing: 16.7 ms, 12.4 ms, and 14.7 ms: the estimated oracle-cost break-even thresholds at dimensions 4, 8, and 16.These thresholds follow from accepted surrogate steps displacing finite-difference gradients while every proposal still costs one true evaluation.
  • Scope boundary: Released interpolation software remains ahead at every tested dimension, including the n=128 probe.The main studies use n≤16, with one-start n=128 tests on thirteen problems.

10 Discussion

The experiments show that surrogate benefit depends on algorithmic role, local radius, and available base-method headroom rather than pointwise fit accuracy alone. They also expose training, wall-clock, and simulation-interface costs that constrain when assistance pays.

  • Safeguarded assistance improved evaluation efficiency, whereas gradient replacement degraded it, confirming that surrogate role matters beyond approximation quality.The acceptance interface preserves true-objective validation, while replacement inserts surrogate error into core updates.
  • Uniform error grew quickly with sampling radius and did not shrink proportionally at small radii, supporting radius-aware local generalisation.The effective generalisation radius can be estimated through radius sweeps and used to control learning-augmented regions.
  • Removing the gradient term from the loss cut surrogate acceptance from 0.703 to 0.148.Sobolev training encodes trend information and stabilises local surrogate descent under finite-difference stencils.
  • Noise produced no universal threshold; instead, stochastic runs shortened until they used a fifth of their budget, reducing proposals by 123-fold while acceptance fell 1.6-fold.The experiments attribute the disappearing contribution to the base method’s early stopping rather than a comparable collapse in surrogate acceptance.
  • At higher dimensions, training overhead and finite-difference targets constrain economics: training reached 31 s at n=128, while ten targets consumed 1290 of 6450 evaluations.The tested width scaling makes parameter count grow quadratically, and the measured break-even oracle cost rose to 104.4 ms at n=128.

11 Conclusion

The paper explains contradictory neural-surrogate results through role, radius, and room: safeguarded assistance can help, but only when local reliability and base-method headroom exist. It further argues that repairing noisy acceptance machinery must precede surrogate deployment.

  • A neural surrogate improves local approximation by reusing paid evaluations, averaging differencing noise, and using gradient information to restrain invented curvature.Removing the gradient term lowers acceptance from 0.703 to 0.148 and returns high-accuracy solves to the base method’s count.
  • Role, radius, and room delimit optimisation benefit: assistance raises high-accuracy solves from 67 to 84, while gradient replacement lowers them to 65.The paper treats radius at the approximation level and distinguishes headroom from whether the acceptance test functions.
  • Under stochastic oracles, no noise threshold separates helped from unhelped regimes; increasing noise shortens the base run rather than consistently reducing surrogate success.The largest helpful noise level varies over four decades.
  • On the Monte-Carlo inventory model, replication repairs the acceptance interface and restores improvement, whereas safeguarding alone cannot overcome an interface that cannot detect real decreases.With a deterministic oracle interface every tested variant stalled at its starting design; the paper therefore places interface repair first.
  • The evidence stops at n=128, leaving the thousands-dimensional regime where interpolation is expected to break down untested.The discussion identifies the derivative-free budget’s available points, rather than network capacity alone, as the predicted obstacle there.
Loading 2608.24963v1…