TOBYQA: A Time-Augmented Model-Based Method for Derivative-Free Optimization under Noise and Temporal Drift
Abstract
Derivative-free optimization (DFO) is challenging when the observation channel varies over time and evaluations are noisy. Conventional model-based methods assume stationary observations; under temporal drift, historical data biases gradient estimates and acceptance tests confound latent-objective decrease with temporal variation. We propose TOBYQA (Time-augmented Optimization BY Quadratic Approximation), a regularized model-based DFO framework that jointly incorporates spatial geometry and temporal variations within a single saddle-point interpolation system. TOBYQA augments the classical least-Frobenius-norm quadratic interpolation system with a linear-in-time drift term and a ridge regularization on the residual kernel, which accommodates noise and ensures well-posedness when the constraint block has full column rank, relaxing the geometric poisedness requirements of classical interpolation. We prove that under affine temporal drift, the recovered gradient is algebraically invariant to the drift rate for any noise scale and sample radius. This property leads to a drift-compensated acceptance test that subtracts the estimated temporal component from the observed reduction. Driven by an adaptive cubic regularization scheme with a closed-form step and a geometry-guarded statistical stationarity stopping rule, TOBYQA achieves an expected oracle complexity of O(ε−2). Benchmark evaluations across diverse temporal drift regimes show that, at tolerance τ=10−3, TOBYQA solves 71.0%, 60.8%, and 41.9% of instances at n=6, $10$, and $20$, respectively, compared with 25.1%, 18.5%, and 14.9% for the best-performing comparison method. These results demonstrate higher solve rates under temporal drift while retaining comparable performance in static environments.
Related
- An Adaptive Augmented Lagrangian Method for Deterministic and Stochastic Nonconvex Optimization
- A Feasible Direction Method with Active-Set Identification for Derivative-Free Optimization
- An Inexact Augmented Lagrangian Method for (L0, L1)-Smooth Convex Optimization
- Allen--Cahn Residual-Constrained Topology Optimization via an Augmented Lagrangian Method
- Optimal Control Under Signal Temporal Logic Constraints: A Robust Reformulation via Augmented Dynamics
BibTeX
@misc{yao2026tobyqa,
title = {{TOBYQA: A Time-Augmented Model-Based Method for Derivative-Free Optimization under Noise and Temporal Drift}},
author = {Haoyu Yao and Pengcheng Xie},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.18124},
eprint = {2608.18124},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.18124},
}
RIS
TY - UNPB
TI - TOBYQA: A Time-Augmented Model-Based Method for Derivative-Free Optimization under Noise and Temporal Drift
AU - Haoyu Yao
AU - Pengcheng Xie
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2608.18124
UR - https://arxiv.org/abs/2608.18124
AB - Derivative-free optimization (DFO) is challenging when the observation channel varies over time and evaluations are noisy. Conventional model-based methods assume stationary observations; under temporal drift, historical data biases gradient estimates and acceptance tests confound latent-objective decrease with temporal variation. We propose TOBYQA (Time-augmented Optimization BY Quadratic Approximation), a regularized model-based DFO framework that jointly incorporates spatial geometry and temporal variations within a single saddle-point interpolation system. TOBYQA augments the classical least-Frobenius-norm quadratic interpolation system with a linear-in-time drift term and a ridge regularization on the residual kernel, which accommodates noise and ensures well-posedness when the constraint block has full column rank, relaxing the geometric poisedness requirements of classical interpolation. We prove that under affine temporal drift, the recovered gradient is algebraically invariant to the drift rate for any noise scale and sample radius. This property leads to a drift-compensated acceptance test that subtracts the estimated temporal component from the observed reduction. Driven by an adaptive cubic regularization scheme with a closed-form step and a geometry-guarded statistical stationarity stopping rule, TOBYQA achieves an expected oracle complexity of O(ε^−2). Benchmark evaluations across diverse temporal drift regimes show that, at tolerance τ=10^−3, TOBYQA solves 71.0%, 60.8%, and 41.9% of instances at n=6, $10$, and $20$, respectively, compared with 25.1%, 18.5%, and 14.9% for the best-performing comparison method. These results demonstrate higher solve rates under temporal drift while retaining comparable performance in static environments.
ER -