Many models are trained first on an easy loss and then switched to the loss that actually matters. A common case is predict-then-optimize pipelines, where a network predicts costs that a solver then uses to make a decision. These are almost always pre-trained on squared error before being fine-tuned on decision regret, meaning how much worse the chosen decision is than the best one in hindsight. The switch point is set by hand: "a few epochs" of squared-error training, chosen by trial and error. This proposal replaces that guess with a measurement. During warm-up, we periodically probe the target loss in a small neighbourhood of the model's current predictions. We ask two questions. Does the target loss respond at all within a radius $\delta$? Do the directions it suggests agree, or do they cancel? We switch when the answer to both is yes. During the target phase we shrink $\delta$, and we stop when the neighbourhood's gradients do cancel. That cancellation is the certificate that optimization theory calls Goldstein stationarity.
The key observation makes this cheap. The non-smooth part of the pipeline, the solver, takes as input a cost vector with tens to hundreds of entries. It does not take the millions of network weights. Smoothing and probing in that small output space sidesteps the dimension penalty that makes parameter-space randomized smoothing impractical for neural networks. The result is a switching rule, a schedule for the smoothing radius, and a stopping test that all come from one quantity. We will test whether this rule matches an expensive oracle-tuned switch point at a fraction of the cost, and whether it holds up where hand-tuned schedules break.
Background and the Gap
Staged training is the standard fix for target losses that give useless gradients near initialization. Smart Predict-and-Optimize for Hard Combinatorial Optimization Problems trains scheduling and knapsack predictors on a linear-programming relaxation of regret (SPO-relax), and it "warmstarts" with squared error for a fixed number of epochs. The benchmark of Benchmarking PtO and PnO Methods in the Predictive Combinatorial Optimization Regime finds that perturbation- and interpolation-based decision losses (Blackbox, DFL) essentially require warm-up from a squared-error model. Its pre-training length is still arbitrary. Task-Based Learning via Task-Oriented Prediction Network with Applications in Finance reports that warm-up alone gives "a significant 14% performance boost" in its learned-surrogate setup, again with the duration as a manual hyperparameter. These papers motivate the proposal: they show warm-up matters and that nobody measures when it is done.
DFF: Decision-Focused Fine-tuning for Smarter Predict-then-Optimize with Limited Data takes a different route. It keeps the squared-error backbone and fine-tunes only a bias-correction layer, constrained to a fixed trust region around the backbone's predictions. That trust region is a fixed radius around the warm-up predictions. Our $\delta$ is also a radius around predictions, but it is chosen by measuring the target loss rather than set in advance.
The Goldstein side supplies the method. The $\delta$-Goldstein subdifferential is the convex hull of all gradients found within distance $\delta$ of a point. A point is $(\delta,\epsilon)$-stationary when some average of those nearby gradients has norm at most $\epsilon$. This concept stays meaningful at kinks where ordinary gradient norms never shrink. Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization shows that the gradient of the function averaged over a $\delta$-ball lies in this hull. Driving the smoothed gradient to zero therefore certifies Goldstein stationarity, though at a query cost that grows as $d^{3/2}$ in the dimension.
Online-to-nonconvex conversion gives optimal first-order rates for reaching these points. See Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion and General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization; the latter shows schedule-free SGD removes learning-rate schedules. Both assume one fixed objective throughout training, so they say nothing about switching losses. Testing Approximate Stationarity Concepts for Piecewise Affine Functions shows that exact stationarity testing for piecewise-linear functions is NP-hard. It gives a polynomial-time verifier for a near-approximate version, used only post hoc. We borrow it only as an offline sanity check on small instances.
There is one constraint the proposal must respect. Goldstein theory needs a locally Lipschitz function, but true discrete regret is piecewise constant in the predicted costs, and it jumps between those flat pieces. We therefore always work with the $\delta$-perturbed regret, which is Lipschitz for any $\delta>0$, or with a relaxation that is already Lipschitz, such as SPO-relax.
Core Claim
During warm-up, the readiness of the target loss can be read from two statistics, both computed in prediction space. The first is activity, the fraction of random output perturbations of radius $\delta$ that change the solver's decision. The second is coherence, which says whether the resulting parameter-space signals point the same way.
For training example $i$ with prediction $\hat y_i$, draw perturbations $u_{ik}$ uniformly from the unit sphere in output space. Form the two-point estimate $g_{ik}$ of the perturbed-regret gradient at $\hat y_i$, in the style of the estimator in Lin et al. Map it back to parameters as $G_{ik}=J_i^\top g_{ik}$, where $J_i$ is the network's output Jacobian for example $i$, which backpropagation computes. Coherence over a minibatch of $N$ examples with $K$ perturbations each is
$$\rho_\delta=\frac{\big\|\tfrac{1}{NK}\sum_{i,k}G_{ik}\big\|}{\tfrac{1}{NK}\sum_{i,k}\|G_{ik}\|},$$
which is near 1 when the target loss offers a consistent descent direction. It is near 0 when the neighbourhood's signals cancel.
Cancellation has two causes that must be told apart. The model may already sit at a stationary point, or the target loss may simply be noise at this stage. Activity separates them, and so does the minimum-norm convex combination of the $G_{ik}$. That minimum-norm vector is a sampled upper bound on the distance from zero to the Goldstein hull. Note that this hull lives in output space, pulled back through $J$; it is not the parameter-space hull.
The rule has three parts. During warm-up, keep raising $\delta$ until activity crosses a threshold. Switch to the target loss once activity is high and $\rho_\delta$ is high at that radius. During the target phase, shrink $\delta$ geometrically. Stop when the minimum-norm element falls below $\epsilon$ at the smallest $\delta$ still showing nonzero activity.
The novelty claim is concrete. No existing staged method measures anything about the target loss before switching to it. No existing Goldstein method treats the choice of loss as part of the schedule.
Research Program
The first strand is analysis. Suppose the network output is $L_g$-Lipschitz in parameters, as in Lipschitz-continuous network maps. Then a parameter ball of radius $\delta/L_g$ maps into an output ball of radius $\delta$. We will make precise when output-space stationarity of the perturbed regret implies parameter-space $(\delta/L_g,\epsilon')$-Goldstein stationarity of the composite. We expect a rough form of $\epsilon'$ to scale with the largest Jacobian norm. We will state plainly where this fails, notably for very sharp networks. We will also prove the easier direction: when activity is zero at radius $\delta$, every target-loss update of a perturbation method is exactly zero. This explains, rather than merely observes, why Blackbox and DFL stall without warm-up.
The second strand is the estimator. We will measure how many perturbations $K$ and how many probed examples $N$ make the switch decision stable across random seeds. Probes can run every few hundred steps on a held-out subsample, so the extra solver calls during warm-up should be a small fraction of one target-phase epoch. We will report this overhead directly, because it is the price of the rule.
The third strand is the full method, run on top of existing decision losses rather than replacing them. It covers SPO-relax, Blackbox, and DFL as implemented in the Geng et al. benchmark, with the $\delta$ schedule controlling the perturbation radius of the methods that have one.
Baselines
The naive reference is training on the target loss from random initialization, with no warm-up. Geng et al. report that this fails for perturbation-based methods, so it marks the floor. The standard practice is a fixed warm-up of a few epochs, as in Mandi et al., using the epoch counts from those papers. Both run on identical data splits, solvers, and architectures.
The strongest competitor on the switching question is an oracle grid. We sweep the switch epoch over a dense grid and pick it on validation regret. This is what a careful practitioner would do, and it upper-bounds what any switching rule can achieve on in-distribution regret. We report it twice: once with its full cost of many training runs, and once restricted to the same total solver-call budget as our method. Beating it means matching its test regret within seed noise while using a single run. Alternatively, it means beating it outright under capacity shift, where validation-tuned switch points may not transfer.
A second strong competitor is a blended loss, squared error plus a weighted regret term, with the weight tuned under the same budget. A third is switching when validation squared error plateaus. On the synthetic network-flow task the strongest published method is DFF. It reports a normalized decision regret of 4.39%, against 5.99% for SPO Forest and 5.86% for Dboost (DFF); beating it means a lower normalized regret on the same data-generating settings. For energy scheduling and knapsack we found no reported regret numbers on Lacuna, so all comparisons there are run by us. The file's only quantitative statement for the Geng benchmark is that PnO beats PtO on 7 of 8 problems.
Three ablations isolate the key ingredient. The first keeps the probe schedule but switches on plain smoothed-gradient norm instead of activity plus coherence; this cannot tell a plateau from a stationary point. The second fixes $\delta$ instead of adapting it. The third switches at random times drawn from the distribution of times our rule chooses, which tests whether the rule picks the right moment or merely the right average duration.
Why not just…?
Why not just tune the warm-up length on validation data? This is the real threat. On in-distribution regret the oracle grid may well match us, since it optimizes the same quantity directly. Our argument is not that it is worse but that it costs many runs, each paying full solver costs. The file stresses that solver costs dominate PnO training (Benchmarking PtO and PnO Methods). The equal-budget comparison settles this. If the grid wins at equal compute on most problems, the switching rule has no reason to exist and we will say so. The capacity-shift test is a secondary chance for the rule to add value beyond compute.
Why not just blend the two losses with a fixed weight and never switch? Blending keeps the squared-error term in charge early, much like warm-up. At initialization, however, its regret component contributes exactly zero for perturbation methods when activity is zero, so the weight sets nothing until predictions improve. Late in training the residual squared-error term pulls against regret, which is the accuracy–decision tension Geng et al. document. The tuned-blend baseline measures whether this matters in practice.
Why not just use a convex surrogate like SPO+ that needs no warm-up? Where the objective is linear and SPO+ applies, it may indeed remove the need for staging. We include it as a two-stage-free baseline and report the problems where it suffices. The proposal targets the methods the benchmark finds dependent on warm-up, Blackbox and DFL, and problems where convex surrogates are not available.
Why not just anneal the perturbation temperature on a fixed schedule? A fixed annealing schedule has the same hand-tuning problem as a fixed warm-up length, moved to a different knob. The fixed-$\delta$ and random-timing ablations show whether measuring activity adds anything over a good fixed schedule.
Proposed Experiments
The testbeds are the problems in the Geng et al. benchmark. These are energy-cost-aware scheduling on SEMO electricity data (200 tasks, 10 machines), knapsack with the training-capacity-30, test-capacity-90 shift, and the combinatorial advertising dataset. We add 5x5 shortest-path and 50-asset portfolio tasks from Smart "Predict, then Optimize", plus the DFF synthetic network-flow tasks. The metrics are normalized test regret, total solver calls and wall-clock time including probes, regret degradation under capacity shift, and the gap between our chosen switch epoch and the oracle's.
The decisive check is a sweep over switch epochs. For each problem we train across the full grid of switch points, and we record coherence and activity at each candidate switch moment alongside the final regret. The rule is justified only if a high-activity, high-coherence state at switch time predicts low final regret across problems, with one fixed threshold rather than one tuned per problem. If the correlation is weak, or the threshold must be retuned for each problem, the claim fails.
A second check uses the Tian–So verifier on the smallest shortest-path instances with a linear predictor, where the relaxed regret is piecewise linear. There we test whether our sampled stopping certificate agrees with a provable near-stationarity test.
References
- Smart Predict-and-Optimize for Hard Combinatorial Optimization Problems
- Benchmarking PtO and PnO Methods in the Predictive Combinatorial Optimization Regime
- Task-Based Learning via Task-Oriented Prediction Network with Applications in Finance
- DFF: Decision-Focused Fine-Tuning for Smarter Predict-Then-Optimize with Limited Data
- Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization
- Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion
- General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization
- Testing Approximate Stationarity Concepts for Piecewise Affine Functions
- Smart "Predict, then Optimize"