Fraud detectors, bot filters and credit models face attackers who pay real money to change their features. Buying aged accounts, faking transaction metadata, or piggybacking on someone else's credit history all cost something. Such an attacker evades only when the profit beats the cost. That means a defender does not need to make every input unflippable. It needs to make flipping too expensive for the attackers who would otherwise profit. Yet today's tabular defenses never optimize this quantity directly. They either train against examples from a slow discrete attack search, or they replace the attacker's true cost structure with a crude geometric ball. Neither tells the defender how a change to the model changes the attacker's cheapest route to evasion.
We propose to learn that missing signal. A small neural network, the surrogate, predicts the minimum cost an attacker must pay to flip a given input under the current model. It is trained, as the defense evolves, on the outputs of an exact discrete attack. Because the surrogate's prediction depends on the defender's own scores, gradients flow from "how expensive is evasion for this fraudster" back into the defender's weights. Training can then push up the price of evasion where attackers are near the profit line and leave clean accuracy alone elsewhere. We study this in a sequential deployment setting where the attacker population drifts round by round. In that setting the surrogate itself becomes something the training process can fool, and keeping it honest is half the problem.
Core Claim
A cost- and profit-bounded attacker does not maximize the defender's loss. The attacker minimizes its own cost subject to flipping the decision, and attacks only if its gain exceeds that cost. The defender's true objective therefore has two parts. The first is the fraction of malicious inputs whose minimum evasion cost $c^*(x;\theta)$ exceeds their gain $g(x)$, where $\theta$ are the defender's weights. The second is clean accuracy. Formally the defender minimizes
$$ \mathbb{E}_{x \sim \text{malicious}}\big[\sigma\big((g(x) - c^*(x;\theta))/\tau\big)\big] + \lambda\, \mathcal{L}_{\text{clean}}(\theta), $$
with $\sigma$ a sigmoid, $\tau$ a temperature, and $\lambda$ a trade-off weight.
The key term is the derivative of $c^*$ with respect to $\theta$. We call it the deterrence gradient: it says how a model change raises or lowers the attacker's cheapest evasion. Standard adversarial training discards this term. Danskin's theorem justifies ignoring the attacker's response only when the attacker maximizes the defender's own loss, and here it does not. Our claim is that a learned surrogate of $c^*$ supplies a usable deterrence gradient for nonlinear tabular models with discrete, asymmetric, interacting feature costs. We further claim that this beats both relaxation-based and augmentation-based defenses in realized attacker success at equal clean accuracy. The claim must hold under truthful verification by the exact attack, not by the surrogate's own estimate.
Where This Sits
Three prior strands motivate the proposal, each from a different direction.
Adversarial Robustness for Tabular Data through Cost and Utility Awareness defines cost-bounded and utility-bounded attackers. It gives an exact-ish discrete attack, the Universal Greedy search over a cost-weighted graph of feature edits. It trains defenses through a "convex cover" that projects costs onto a weighted $L_1$ ball. That relaxation ignores feature interactions and discrete cost jumps, and its own authors flag dependent costs as open. We reuse their attack as our oracle and their datasets as our testbed, and we replace the relaxation.
Strategic Classification Made Practical differentiates through a smoothed best response using a convex-concave procedure inside a convex optimization layer. This is exactly the deterrence gradient, but it requires known convex costs and continuous features. Our surrogate targets the regime where those assumptions fail.
Landscape Surrogate supplies the training method. Its method, LANCER, alternates between fitting a neural surrogate of a non-differentiable solver's objective from a replay buffer and taking gradient steps through that surrogate. It was tested only on static, non-adversarial problems. Here the "solver" is the attacker.
Two strands constrain the design. Deep Incentive Design with Differentiable Equilibrium Blocks reports that upstream optimizers exploit surrogate inaccuracies. In our setting the defender's optimizer will learn to inflate predicted evasion cost without raising true cost, so verification against the exact attack is mandatory rather than optional.
The online view of adversarial training in A Closer Look at Curriculum Adversarial Training shows that generalization depends on how far the adversarial distribution moves between steps. This argues for bounding each defender update so the surrogate's training data stays relevant. The tracking results of Incrementally Learning Time-Varying Half Planes motivate the sequential evaluation. Against a greedy adversary, mistake rate scales as the square root of the drift rate, and proactive trackers beat conservative ones. That is the gap we expect reactive retraining to show.
Research Program
The surrogate. For an input $x$, the Universal Greedy search under the current model yields a frontier of candidate edits. We take the $K$ cheapest partial edit paths and evaluate the defender's score at each edited point. The surrogate $M_w$ receives $x$, the edit costs, and these $K$ defender scores, and predicts $c^*(x;\theta)$. Because the defender scores are differentiable in $\theta$, so is the prediction. This sidesteps conditioning a network on raw weight vectors. It also restricts the method to differentiable defenders, such as MLPs and TabNet; gradient-boosted trees appear only as non-differentiable reference points.
Alternating training. Each round runs the exact attack on a sampled batch under the current $\theta$ and stores the pairs (surrogate inputs, true minimum cost) in a replay buffer. It refits $w$ on that buffer, then takes a bounded number of $\theta$ steps on the objective above.
Anti-gaming. We add three safeguards against the defender fooling the surrogate. The first is a trust region on how far defender scores at frontier points may move per round, following the curriculum argument. The second is an ensemble of surrogates whose disagreement is penalized. The third is a held-out exact-attack audit each round. If true and predicted deterrence diverge beyond a threshold, the audit rolls the round back and doubles the oracle batch.
Sequential deployment. The program then moves to sequential deployment rounds. Between rounds the attacker population shifts in two ways: the gain distribution $g$ rises, and the cost table changes, for example when a feature becomes cheaper to fake. The defender sees only attacks against its deployed model.
Baselines
The naive reference is a strategy-blind model trained by ordinary empirical risk minimization on clean data. On the strategic spam data, Strategic Classification Made Practical reports that such a model falls to about 54% accuracy under gaming. Any method must clear this easily.
The strongest existing tabular defense is the convex-cover adversarial training of Adversarial Robustness for Tabular Data through Cost and Utility Awareness. On HomeCredit it reports reducing attack success rate by 40% relative to standard models while keeping competitive clean accuracy. For TwitterBot and IEEECIS there is no reported numeric result found on Lacuna for convex-cover defense. We run it ourselves with the same architecture, data splits, cost tables and hyperparameter search budget as our method. Beating it means lower attack success and lower attacker profit under the utility-bounded Universal Greedy attack, at clean accuracy within one point.
The strongest differentiable strategic method is the smoothed best-response training of Strategic Classification Made Practical, which restores about 80% accuracy on spam. We reproduce it on spam as a sanity anchor, where our method should match it. We also run it on the tabular cost datasets using the best convex approximation of their costs. Our method should beat it there, because the costs are discrete and interacting.
The ablation that isolates our key ingredient is augmentation-only training. It uses the same exact-attack examples and the same oracle budget, but trains on them as ordinary adversarial examples, with no surrogate and no deterrence gradient. If it matches our method, the surrogate adds nothing. A second ablation removes the anti-gaming safeguards, to measure how much surrogate exploitation occurs. In the sequential setting we add reactive retraining on each round's observed attacks. All methods receive the same number of exact-attack oracle calls per round.
Why not just…?
Why not just do adversarial training on Universal Greedy examples? This is the most serious threat. It is exactly our augmentation-only ablation. Training on the attacker's chosen examples teaches the model to classify those points. It does not tell the model which changes would make other attackers' cheapest route cross the profit line, because the attacker optimizes cost rather than the defender's loss. We expect the gap to show mainly in attacker profit and deterrence rate, not in accuracy on attacked points. If no gap appears on HomeCredit, IEEECIS and TwitterBot, we will report that the deterrence gradient is not worth its cost.
Why not just keep the convex-cover relaxation, which already works? It works with additive costs. The reported 40% reduction on HomeCredit says nothing about interacting costs, such as changing occupation shifting the plausible income range, which its authors list as open. We will build cost tables with explicit feature dependencies. The relaxation should degrade as dependence strength grows, while the surrogate, trained on exact attacks, should not. If the relaxation holds up, the proposal's scope narrows to the sequential setting.
Why not just use derivative-free search over defender weights? Landscape Surrogate reports about 100 solver calls for its surrogate against up to 50,000 for a competing method. Each "call" for us is a full discrete attack, so derivative-free search over a neural model's weights is impractical. We will nonetheless include a small evolutionary-search baseline on an MLP with an equal oracle budget, to make the comparison explicit.
Why not just retrain reactively each round? Reactive retraining always defends against last round's attacker. The half-plane tracking results suggest it lags by an amount that grows with drift rate. Our sequential experiment varies drift speed directly to test whether the surrogate-based defender's advantage widens as drift accelerates.
Proposed Experiments and Decisive Checks
The experiments use HomeCredit, IEEECIS and TwitterBot with the cost tables of the tabular-cost paper, including the darknet-derived costs for bots. We use spam as a cross-check against the strategic-classification results, and Drebin with binary feature-addition costs as a stretch domain.
All evaluation uses the exact utility-bounded Universal Greedy attack against the final deployed model, never the surrogate. We measure clean accuracy, attack success rate, mean attacker profit, deterred fraction (malicious inputs whose true minimum cost exceeds their gain), and oracle calls.
The first decisive check is that our method beats both convex cover and augmentation-only on profit and deterred fraction at matched clean accuracy. The second is surrogate fidelity. We track rank correlation between predicted and true minimum cost on points the defender has recently moved, with and without the anti-gaming safeguards. A large drop without safeguards confirms that defender-side gaming is real; recovery with safeguards shows it is controlled. The third check runs the sequential protocol with gain drift and cost-table shocks at several speeds. We plot cumulative attacker profit over rounds against reactive retraining and static strategic training, and expect the gap to grow with drift speed.
If the first check fails while the third succeeds, the contribution is a sequential tracking method rather than a better static defense, and we will report it that way.
References
- Adversarial Robustness for Tabular Data through Cost and Utility Awareness
- Strategic Classification Made Practical
- Landscape Surrogate: Learning Decision Losses for Mathematical Optimization Under Partial Information
- Deep Incentive Design with Differentiable Equilibrium Blocks
- A Closer Look at Curriculum Adversarial Training: From an Online Perspective
- Incrementally Learning Time-Varying Half Planes