Sample Recycling in Derivative-Free Optimization

25 concepts17 papers

In derivative-free (or zeroth-order) optimization, we navigate an objective landscape $f(x)$ without direct access to its analytical gradients. To find a descent direction, standard algorithms rely on finite differences or random perturbations: they query the function at several nearby points, compute an empirical slope, take a step, and then discard every single query.

This practice is highly inefficient. In a $d$-dimensional parameter space, estimating a local gradient or Hessian requires $O(d)$ or $O(d^2)$ function evaluations per step. When each query involves an expensive black-box operation—such as running a climate simulation, executing a quantum circuit, or evaluating a large language model—throwing away past evaluations creates a massive computational bottleneck.

A rapidly growing body of research challenges this "amnesiac" paradigm. The core insight is simple: optimization trajectories are continuous, and loss landscapes change slowly. A function evaluation from a previous iteration still contains rich geometric information about the local neighborhood. By maintaining a persistent memory or surrogate model of historical queries, we can drastically reduce the number of new samples required to estimate gradients and curvature.


The Geometry of Proximity: Local History Buffers

Why can we safely reuse a sample from three iterations ago? The answer lies in the local Taylor expansion of continuous landscapes. If the optimization step size is small, a historical sample point $x_{past}$ remains within a valid radius of the current state $x_{current}$.

Standard Zeroth-Order:
Step t:   [Query Points] ---> Estimate Gradient ---> Discard Queries
Step t+1: [New Queries]  ---> Estimate Gradient ---> Discard Queries

Sample Recycling:
Step t:   [Query Points] ---> Save to Buffer
Step t+1: [Buffer Points] + [Minimal New Queries] ---> Estimate Gradient

Instead of generating a completely fresh batch of perturbations at every step, we can maintain a history buffer and filter for points that fall within a strict distance bound. For instance, Xiaoxing Wang et al. introduce this mechanism in ReLIZO: Sample Reusable Linear Interpolation-based Zeroth-order Optimization. They frame gradient estimation as a quadratically constrained linear program (QCLP) over a buffer of nearby historical points, effectively decoupling the required sample size from the variable dimension $d$.

This local stability applies equally to higher-order curvature estimation. Estimating a Hessian matrix is notoriously expensive in black-box settings, but Junbin Qiu et al. demonstrate in Revisiting Zeroth-Order Hessian Approximation: A Single-Step Policy Optimization Lens that a history buffer can store previous evaluations to provide high-accuracy curvature estimates. Because local loss landscapes evolve slowly along the optimization path, these recycled samples act as a high-precision proxy for fresh forward passes. Similarly, in multi-objective optimization, Aboozar Mohammadi et al. utilize a trust-region framework in A trust-region approach for computing Pareto fronts in multiobjective derivative-free optimization to reuse previously evaluated points when constructing local surrogate models, minimizing the total computational budget required to map Pareto fronts.


Trajectory-Informed Surrogates: Turning History into a Map

Rather than treating historical points as isolated constraints, another powerful approach aggregates the entire query history into a continuous statistical surrogate model, such as a Gaussian Process (GP) or a Neural Network. Here, the optimization trajectory is re-envisioned as a cumulative dataset that progressively refines a global map of the objective function.

In federated learning environments where communication and queries are strictly constrained, Yao Shu et al. propose FZooS in Federated Zeroth-Order Optimization using Trajectory-Informed Surrogate Gradients. Instead of performing finite-difference queries at every communication round, the authors use a GP to model the local function landscape based on the cumulative history of previous queries, yielding accurate gradient estimates with minimal new client interactions. This global perspective is also highly effective for security auditing; Shudong Zhang et al. show in Black-box Bayesian adversarial attack with transferable priors that retaining all previous query results within a global statistical surrogate maximizes the utility of every single interaction, allowing adversarial attacks to succeed with an order of magnitude fewer attempts than local gradient estimators.

This paradigm is particularly vital in noisy, high-dimensional engineering domains. Brian Irwin demonstrates in Neural Network Accelerated Implicit Filtering: Integrating Neural Network Surrogates With Provably Convergent Derivative Free Optimization Methods that training a neural network surrogate on the entire history of sampled points transforms past evaluations into a robust global map, allowing implicit filtering methods to navigate noisy environments efficiently.

Application to Quantum and Differential Models

The benefits of surrogate-based sample recycling are vividly apparent in fields where function evaluations are exceptionally expensive, such as Variational Quantum Eigensolvers (VQEs) and differential equation calibration.

  • Quantum Shot Optimization: In VQEs, evaluating an energy landscape requires thousands of quantum measurements ("shots"). Samuele Pedrielli et al. introduce the Bayesian Parameter Shift Rule in Bayesian Parameter Shift Rules in Variational Quantum Eigensolvers, using a persistent surrogate model to accumulate all historical measurement data. This eliminates the need to treat each optimization step as an independent measurement task. To further optimize this process, Christopher J. Anders develops SubsCoRe in Adaptive Observation Cost Control for Variational Quantum Eigensolvers, which leverages a GP surrogate of the energy landscape to dynamically control the shot budget, ensuring that the algorithm only spends quantum resources when the historical data is insufficient to guarantee progress.
  • Differential Equation Calibration: Calibrating complex differential equations requires repeatedly solving the underlying systems to calculate sensitivities. Jon Cockayne et al. address this in Probabilistic Gradients for Fast Calibration of Differential Equation Models by modeling the gradient globally across the parameter space using a surrogate model. Reusing information gathered during previous optimization iterations drastically reduces the number of expensive model evaluations required to reach convergence.

Memory Vectors and Temporal Alignment

Sample recycling can also be implemented through lightweight memory structures that track specific search directions or exploit temporal correlations between successive iterations.

Instead of storing an unstructured cloud of points, an algorithm can maintain a persistent vector of the most recent cost evaluations for a fixed set of perturbation directions. Guido Carnevale et al. formalize this in Accelerating Model-Free Optimization via Averaging of Cost Samples, demonstrating that an auxiliary memory vector can serve as a proxy for current function values. This simple mechanism effectively bridges the performance gap between single-point and multi-point sampling methods without increasing the query burden. In evolution strategies, Zhengfei Zhang et al. show in An invariant information geometric method for high-dimensional online optimization that integrating historical sample data through exponential decay significantly enhances sample efficiency, matching the performance of Bayesian optimization in high dimensions while maintaining low computational overhead.

Directional Memory Vector:
[ Direction v1: Last Cost = 4.2 ]  <-- Reused as proxy in step t+1
[ Direction v2: Last Cost = 1.8 ]
[ Direction v3: Last Cost = 5.1 ]

In scenarios where explicit history storage is prohibited by memory constraints, the temporal correlation between steps can still be leveraged. For instance, Gil Goldshlager et al. introduce SPRING in A Kaczmarz-inspired approach to accelerate the optimization of neural network wavefunctions. By treating the parameter update as an underdetermined linear least-squares problem, their optimizer selects a solution that minimizes the distance to the previous iteration's update. This exploits the slow evolution of the underlying system to stabilize optimization without storing large datasets. For reinforcement learning and direct policy search, Yi-Qi Hu et al. demonstrate in Sequential Classification-Based Optimization for Direct Policy Search that maintaining a persistent memory of historical evaluations categorized into positive and negative sets allows the search model to continuously adapt to the objective landscape.


Reusing History Across Tasks and Environments

The utility of historical data extends beyond immediate step-to-step recycling; it can guide optimization across entirely different tasks or through dynamic environment shifts.

In sequential optimization settings, information about low-performing regions in past tasks is just as valuable as information about high-performing regions. Matthias Poloczek et al. demonstrate this in Warm Starting Bayesian Optimization by constructing a joint Gaussian Process model that captures the differences between past and current tasks. Utilizing the full evaluation history of past tasks drastically reduces the number of evaluations needed to find optimal solutions for new, related problems.

Furthermore, when optimizing in dynamic environments where the data distribution shifts in response to the optimizer's decisions (performative prediction), Yuya Hikima et al. show in Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependent Distributions that guidance directions for gradient estimation can be derived directly from historical samples collected in previous iterations. This strategy leverages past data to refine the search direction without requiring fresh, expensive environment interactions at every optimization step.

Conclusion

Sample recycling shifts derivative-free optimization from a series of isolated, amnesiac steps into a cumulative learning process. Whether through local proximity buffers, global surrogate models, or directional memory vectors, reusing historical evaluations exploits the underlying continuity of physical and mathematical landscapes. By transforming the optimization trajectory into a persistent dataset, these methods bridge the efficiency gap between zeroth-order and first-order optimization, unlocking scalable performance for computationally intensive black-box problems.

Key Foundational Work

Warm Starting Bayesian Optimization (2016) — contributed 1 concept elements to this direction.
Memory-based Stochastic Optimization (1995) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_historical_sample_reuse_d405bd96,
  title = {historical sample reuse},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/historical-sample-reuse/rdr_d405bd9651bd4037b5437aaab7f70810},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_historical_sample_reuse_d405bd96_v1,
  title = {historical sample reuse},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/historical-sample-reuse/rdr_d405bd9651bd4037b5437aaab7f70810/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}

See something wrong? Report a mistake