Basis-Disagreement Trust-Region Training
Implementation & benchmark of arXiv:2608.18129 — Simulation-Optimization of Systems of Optimizers: Exploiting the Inner Optimization's Geometry
Source paper: Simulation-Optimization of Systems of Optimizers: Exploiting the Inner Optimization's Geometry arXiv:2608.18129 ⓘ · analyzed Sep 1, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Use active-basis changes as a cheap, solver-derived indicator that a policy update has crossed a nonsmooth decision boundary. Adapt the neural optimizer’s step size and gradient confidence using the fraction of trajectory decisions whose bases disagree between the current and proposed policy, preserving large steps in locally affine regions and damping updates near combinatorial switches.
Formulas
Mathematical statement
For each stochastic trajectory driven by common noise $\xi$, the paper defines a critical-region event in which every $(s_{i,t},\theta)$ remains in the interior of one LP region. Within that event, the LP action is affine and the pathwise derivative is exact; basis changes are the only obstructions. For two nearby policy parameters $\theta$ and $\theta'$, define the observable basis-disagreement count $D(\theta,\theta';\xi)=\sum_{i=1}^{N}\sum_{t=0}^{T-1}\mathbf{1}\{B_{i,t}(\theta,\xi)\ne B_{i,t}(\theta',\xi)\}$ and normalized disagreement $q=D/(NT)$. A trust-region rule can enforce $q\le q_{\max}$, so the analytic gradient is used only where most local affine assumptions persist. The proposed update is $\theta' = \theta-\eta(q)\widehat g$, with $\eta(q)=\eta_0\min(1,q_{\max}/(q+\varepsilon))$ and optional gradient attenuation $w(q)=\exp(-\alpha q)$. This is an implementable stability heuristic tied directly to the paper’s basis-change obstruction; $q_{\max}$, $\alpha$, and $\varepsilon$ are tunable engineering parameters.
Implementation notes
Attach this controller to AdamW, SGD, or a policy-gradient optimizer when the network generates parameters for one or more embedded LPs. At optimizer step $r$, save the current network parameters $\theta_r$ and the active basis IDs from a minibatch of stochastic rollouts. Compute the analytic LP-layer gradient $\widehat g_r$ using the basis formulas. Form a proposal $\theta_r^{\mathrm{trial}}=\theta_r-\eta_0\widehat g_r$ without committing it, rerun the same minibatch with identical random seeds and common exogenous noise, and record the new basis IDs. Calculate $D_r$ by counting unequal $(agent,time)$ basis IDs and $q_r=D_r/(NT)$. Apply $\eta_r=\eta_0\min(1,q_{\max}/(q_r+\varepsilon))$ and optionally multiply the gradient by $\exp(-\alpha q_r)$; then commit the update. To avoid doubling cost permanently, perform the proposal rollout every $K$ steps, estimate a moving average of $q_r$, and use a single cheap boundary diagnostic on intervening steps. Also log the minimum active slack, reduced-cost margin, and condition number of each basis, because a basis ID can change for numerical reasons. The math supplies the critical-region validity condition and disagreement statistic; $q_{\max}$, $\alpha$, and $K$ are empirical hyperparameters. Start with a 2-layer MLP controlling a small multi-period min-cost-flow LP on synthetic demand, comparing AdamW, fixed-step analytic differentiation, and this controller. Measure loss oscillation, number of failed or infeasible LP solves, basis-change rate, and final objective at equal solver calls. The expected signal is fewer catastrophic loss spikes and lower seed-to-seed variance, with no loss in progress when basis disagreement is already low.
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.