Drift-Aware Quadratic Hyperparameter Optimizer
Implementation & benchmark of arXiv:2608.18124 — TOBYQA: A Trust-Region Method for Derivative-Free Optimization on Time-Varying Functions
Source paper: TOBYQA: A Trust-Region Method for Derivative-Free Optimization on Time-Varying Functions arXiv:2608.18124 ⓘ · analyzed Sep 1, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Replace standard black-box hyperparameter search with a trust-region optimizer whose local quadratic surrogate includes an explicit linear dependence on wall-clock time or training-step age. Fit the model with ridge-regularized quadratic interpolation, then use a drift-compensated trust-region ratio to avoid rejecting useful moves merely because the validation distribution has deteriorated over time.
Formulas
Mathematical statement
The paper augments the classical interpolation constraint matrix with a temporal column: $$X_{\mathrm{aug}}=\begin{bmatrix}\mathbf{1}_{m}&D&\theta\end{bmatrix}\in\mathbb{R}^{m\times(n+2)},$$ where $m$ is the number of observations, $n$ is the dimension of the search variable $x$, $D$ has rows $d_i^{ op}$ with $d_i=x_i-x_k$ relative to the current trust-region center $x_k$, and $ heta=( heta_1,\ldots, heta_m)^ op$ contains the observation times. The local model is $$Q_k(x,t)=c+g^\top d+\frac12d^\top Gd+\gamma(t-t_k),\qquad d=x-x_k,$$ where $c$ is the center value, $g$ is a gradient-like vector, $G$ is a symmetric implicit Hessian, and $\gamma$ is the estimated temporal drift coefficient. The quadratic coefficients are represented by interpolation multipliers through $$G=\sum_{i=1}^{m}\lambda_i d_i d_i^\top,$$ with multiplier vector $\lambda$. The regularized KKT system has the structure $$\begin{bmatrix}\Phi+\rho I&X_{\mathrm{aug}}\\X_{\mathrm{aug}}^\top&0\end{bmatrix}\begin{bmatrix}\lambda\\c\\g\\\gamma\end{bmatrix}=\begin{bmatrix}F\\0\end{bmatrix},$$ where $F=(F_1,\ldots,F_m)^ op$ contains observed neural-network objective values, $\Phi_{ij}= frac12(d_i^ op d_j)^2$ is the quadratic-basis Gram matrix, $I$ is the $m imes m$ identity, and $\rho>0$ controls ridge regularization. The hard-constraint limit is $$\begin{bmatrix}\Phi&X_{\mathrm{aug}}\\X_{\mathrm{aug}}^\top&0\end{bmatrix}\begin{bmatrix}\lambda\\c\\g\\\gamma\end{bmatrix}=\begin{bmatrix}F\\0\end{bmatrix},$$ which enforces $Q_k(x_i,t_i)=F_i$. Stationarity gives $\xi_i=\lambda_i/\rho$ and an objective regularization equivalent to $$\frac12\|G^{(\rho)}\|_F^2+\frac{1}{2\rho}\|\lambda^{(\rho)}\|^2,$$ so the ridge term penalizes unstable curvature and yields a unique solution whenever $X_{\mathrm{aug}}$ has full column rank. For a candidate step $s$, use the drift-compensated ratio $$r=\frac{F_k-F_{\mathrm{new}}-\hat\gamma(t_{\mathrm{new}}-t_k)}{Q_k(x_k,t_k)-Q_k(x_k+s,t_{\mathrm{new}})},$$ where $F_k$ and $F_{\mathrm{new}}$ are observed validation losses and $\hat\gamma$ is the fitted temporal coefficient.
Implementation notes
Integrate this as a black-box optimizer around an expensive neural-network evaluation, not inside backpropagation. The optimization variable can be 6–20 continuous or transformed hyperparameters such as learning rate, weight decay, dropout, augmentation strength, LoRA rank scale, or distillation temperature. At iteration $k$, maintain a center $x_k$, radius $\Delta_k$, and the most recent $m\ge n+2$ trials $(x_i,t_i,F_i)$, where $F_i$ is validation loss or negative reward and $t_i$ is elapsed wall-clock time, global training step, or dataset-window index. Normalize each coordinate and form $d_i=x_i-x_k$ and $\theta_i=t_i-t_k$. Build $\Phi_{ij}=0.5(d_i^Td_j)^2$ and $X_{aug}=[1,D,\theta]$, then solve the displayed regularized KKT system for $(\lambda,c,g,\gamma)$ using a dense linear solver with a small diagonal jitter if needed. Construct $G=\sum_i\lambda_i d_i d_i^T$, symmetrize it, and compute a trial step by approximately minimizing $Q_k(x_k+s,t_{new})$ subject to $\|s\|_2\le\Delta_k$ and box constraints; a practical MVP uses projected gradient steps or truncated conjugate gradient on $g+Gs$, with the temporal term excluded from the step because it is constant in $s$. Evaluate the neural network at the proposed hyperparameters, compute the ratio $r$ above, accept if $r>0.1$, enlarge the radius when $r>0.75$, and shrink it when $r<0.1$. The formula supplies the surrogate, ridge solve, and drift correction; empirical choices are $\rho$, acceptance thresholds, initial radius, and the time coordinate. First test on CIFAR-10 with a small ResNet-18 and six hyperparameters, comparing against random search, Gaussian-process Bayesian optimization, and standard quadratic DFO under a fixed budget of 30 partial training runs. Measure best validation accuracy versus completed runs and robustness when the validation data are replaced or reweighted every few trials. Success is faster improvement at equal evaluations, fewer catastrophic trust-region updates under drift, and higher final accuracy when the objective changes monotonically over time.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.