Risk What You've Saved: Stream-Level Robustness Budgets for Classifiers

An adversarially robust classifier pays a permanent tax. It gives up clean accuracy on every input, all the time, so that it stays correct on the rare input an attacker has perturbed. Poker-playing agents faced a similar problem and found a different answer. An agent that plays a safe equilibrium strategy, meaning one no opponent can beat on average, earns more than its guaranteed minimum whenever the opponent makes mistakes. The agent can bank that surplus and spend it on riskier, more profitable play, while its long-run worst case never falls below the safe guarantee. We propose to bring this "risk what you've won" accounting to robust classification. A deployed classifier answers a stream of queries. Each time it does better than its robust guarantee, it banks the difference as risk capital. It then spends that capital by shifting toward a more accurate, less robust model. If an attack drains the capital, it moves back toward the robust model.

The result changes what is guaranteed, and that change is the point. The robustness-accuracy trade-off is usually defined per query: every input must survive the worst perturbation. We instead guarantee that the expected cumulative error over the whole stream never exceeds what the always-robust model would suffer under worst-case attack. This holds against any adaptive attacker, including one that behaves benignly for a long time and then strikes. Under that stream-level guarantee, most of the clean-accuracy tax should be recoverable on streams that are mostly benign. The gain disappears only when the stream really is under sustained attack.

Core Claim

The setup reuses the training-free mixed classifier of Mixing classifiers to alleviate the accuracy-robustness trade-off. That paper averages the output probabilities of an accurate standard model $g$ and a robust model $h$ with a fixed weight $\alpha$ and certifies a robustness radius for the mixture. Write $R(\alpha)$ for an upper bound on the expected error of the $\alpha$-mixture under any attack within the threat model. We compute it offline on calibration data, in two versions. One is sound, built from that paper's certified radius. The other is empirical, measured with AutoAttack. Let $\alpha_0$ be the operator's safe weight.

At round $t$ the classifier commits to $\alpha_t$ and answers the query. With probability $\rho$, chosen privately and independently of the attacker, the query is audited: its label arrives later and the loss $\ell_t$ is observed. Capital is the importance-weighted savings relative to the safe guarantee:

$$k_t = \sum_{s \le t} \Big( R(\alpha_0) - \tfrac{Z_s}{\rho}\,\ell_s \Big),$$

where $Z_s \in \{0,1\}$ indicates whether round $s$ was audited. The rule picks the most clean-accurate weight whose extra worst-case exposure is already paid for:

$$\alpha_t = \min\{\alpha : R(\alpha) - R(\alpha_0) \le \max(k_{t-1}, 0)\}.$$

Given past rounds, the expected loss at round $t$ is at most $R(\alpha_t)$, because $R$ bounds every admissible attack. The estimated loss is unbiased. The excess exposure is covered by existing capital. Together these imply that $k_t$ cannot decrease in conditional expectation below zero, so $\mathbb{E}[\sum_t \ell_t] \le T\,R(\alpha_0)$ for any adaptive attacker.

This is a direct translation of PRWYWE ("Prime Risk What You've Won in Expectation") from Safe Opponent Exploitation For Epsilon Equilibrium Strategies. There, risk is funded by "gifts" from opponent mistakes and anchored to the worst-case value of the agent's own approximate strategy, not an ideal game value. In our setting the anchor is $R(\alpha_0)$ of the deployed robust mixture. The gifts are benign queries and attacks too weak to cause errors.

On a clean stream, even playing $\alpha_0$ earns capital at a rate of roughly $R(\alpha_0)$ minus the clean error, which is large on CIFAR-10. The schedule should therefore move toward $g$ within a short burn-in. An attacker who baits by staying quiet only builds capital that the defender is entitled to spend. Its eventual strike can cost at most what the defender has saved.

The guarantee is cumulative and in expectation, not per query. A burst attack can still cause a cluster of errors bounded by the accumulated capital. We therefore also study a windowed variant that caps how much capital can be spent within any $W$ rounds, which trades recovered accuracy for a bound on bursts. We also study a high-probability variant that replaces the expectation argument with anytime-valid confidence sequences of the kind used in Agents That Certify Their Own Exploits.

Relation to Prior Work

Three papers motivate the mechanism. Bai et al. show that probability mixing gives a strong static trade-off curve but fix $\alpha$ offline, with no monitoring. Our contribution is the online schedule and the stream-level guarantee, not a better mixture. The PRWYWE accounting of Jeary and Turrini, and the related risk-capital idea in Accumulating Risk Capital Through Investing in Cooperation, supply the budget logic. Both use symbolic games where realized payoffs are always observed. We must handle partial, delayed labels, which forces the importance-weighted estimator and enlarges its variance by $1/\rho$.

Li and Huang's CS-RNR self-certifies candidate strategies before committing. It also shows that naive Bernoulli mixing of a best response with equilibrium play reaches exploitability 2.04, which is 13.6× its 0.15 budget, in Leduc Hold'em. That result constrains our design. We never randomize between $g$ and $h$ per query; we commit to a probability mixture whose worst-case error $R(\alpha)$ has been audited in advance.

Safe and Robust Subgame Exploitation in Imperfect Information Games contributes the principle we adopt as our safety notion: the adapted strategy must be no more exploitable than the deployed baseline. Here that becomes no worse cumulative worst-case error than the fixed $\alpha_0$ mixture.

On the robustness side, Theoretically Principled Trade-off between Robustness and Accuracy (TRADES) proves that a per-query trade-off is unavoidable on entangled distributions. We do not contradict that result. We change the quantity being guaranteed. TART reduces the tax through training-time geometry: it filters out adversarial perturbations that point off the data manifold. It is complementary, since a TART-trained model can serve as $h$.

Policy Smoothing for Provably Robust Reinforcement Learning certifies a lower bound on total episodic reward under smoothing noise but pays the clean cost on every episode. That makes it a natural second domain, because rewards are observed without labels. Finally, Best of Both Worlds: Regret Minimization versus Minimax Play gives online algorithms with constant regret to a safe comparator. It is the closest theoretical competitor, and we treat it as a baseline rather than a footnote.

Research Program

The work has three parts.

The first builds the worst-case error curve $R(\alpha)$ for mixtures of standard and robust CIFAR-10 models. It uses a certified version from Bai et al.'s radius and an empirical version from AutoAttack. We also measure how optimistic the empirical curve is against attacks adapted to the mixture.

The second proves the expected-value guarantee and its windowed and high-probability variants. Each guarantee is stated with its assumptions explicit. Queries are drawn from the deployment distribution before perturbation. The attacker cannot see which queries are audited. Perturbations stay within the radius that $R$ was certified for. We characterize how quickly capital accumulates as a function of $\rho$ and of the gap between clean and robust error, which tells us when the high-probability version starves for evidence. Li and Huang call this failure confirmation starvation.

The third part transfers the scheme to sequential control. There, $\alpha$ is replaced by the policy-smoothing noise level, the robust guarantee is Kumar et al.'s certified episodic-reward bound, and capital is the realized return above that bound.

Baselines

The do-nothing reference is the fixed Bai et al. mixture at $\alpha_0$, using the same two models. The most relevant reported number for this baseline is that paper's CIFAR-10 result with ResNet-18 and ConvNeXT-T: clean accuracy approaching 95% with PGD-attacked accuracy of 30–40% (Mixing classifiers). We report the fixed mixture at every $\alpha$ on a grid, so that our scheduled policy is compared against the entire static curve, not one point.

The standard-training reference is TRADES with tuned trade-off weight. Zhang et al. report 56.61% PGD robust accuracy on CIFAR-10, and the file reports natural accuracy values such as 88.64%. A TART model, reported at 83.73% clean and 36.58% AutoAttack accuracy, also serves as an alternative robust component. Our scheme beats the static methods if, at matched stream-level worst-case error, it achieves higher accuracy on benign and lightly attacked streams.

The strongest online competitor is a safe-anchored expert algorithm over the $\alpha$ grid in the style of Müller et al. It learns which weight to play from audited losses and keeps constant regret to the $\alpha_0$ comparator. With labels, every $\alpha$'s loss on an audited query is computable, so it receives full information on exactly the same audited rounds as our method.

A detector baseline routes queries to $g$ unless an adversarial-input detector fires. It uses the same labeled budget for calibration and a matched false-positive rate.

The key ablation keeps everything in our method but funds capital from "no attack detected" signals instead of realized audited losses. This isolates whether the realized-savings accounting is what buys safety against baiting.

All methods share models, streams, the audit rate $\rho$, and a hyperparameter search of equal size on a separate validation stream. Beating a baseline means one of two things. The first is higher benign-stream accuracy at equal or lower cumulative error under the strongest adaptive attacker. The second is a stated bound that holds where the baseline's does not.

Why not just…?

Why not just tune a fixed $\alpha$ lower? A fixed mixture's worst-case error is paid on every query, whether or not an attack occurs. To reach a stream-level target of $R(\alpha_0)$ with a fixed weight, you must play $\alpha_0$ itself. Our claim is that the scheduled policy reaches the same worst-case cumulative bound while sitting near $g$ on benign streams. The static-curve comparison tests this directly. If the scheduled policy's benign accuracy is not clearly above the fixed curve at matched worst-case error, the idea fails.

Why not just use an adversarial detector to switch models? Detectors carry no guarantee against an attacker who adapts to them. Input filters also reject rare benign inputs, as Baseline Defenses for Adversarial Attacks Against Aligned Language Models shows for perplexity filters. In the game setting, CS-RNR earned 6.2× the steady-state gain of a binary gate. Our bait-then-burst attacker, which evades the detector, should show unbounded cumulative damage for the detector and bounded damage for our method. The detector-funded ablation shows whether that difference comes from the accounting rather than the mixture.

Why not just run a safe-anchored no-regret learner over $\alpha$? This is a real threat. Müller et al.'s guarantee has a similar shape and may match us on stationary streams. The difference lies in timing. A regret learner raises robustness only after observing losses from the current attack. Our rule caps exposure before the round using the precomputed worst case $R$, so damage from a sudden burst is bounded by capital rather than by how fast the learner reacts. If the expert baseline matches us on burst attacks too, the honest conclusion is that stream-level guarantees, not our specific accounting rule, carry the benefit. We would report it that way.

Decisive Experiments

On CIFAR-10 we construct streams of 50,000 test queries drawn with replacement and play them against several attackers. The attackers are: none; a constant fraction perturbed with AutoAttack against the current mixture; a bait-then-burst attacker that stays benign until capital peaks and then attacks continuously; and a capital-aware attacker that knows $k_t$ and times its strikes for when $\alpha_t$ is smallest. We sweep the audit rate $\rho$ from 1% to 100% and the window cap $W$.

We report four quantities: cumulative error rate on the stream, accuracy on benign stretches, the largest number of errors within any window of $W$ rounds, and violations of the guarantee. A violation is a run whose cumulative error exceeds $T\,R(\alpha_0)$ plus the stated slack.

The outcome that would establish the claim has three parts. With the certified $R$, there are zero violations across all attackers. On benign streams, accuracy approaches that of $g$ after a burn-in whose length scales as predicted with $\rho$. Under the capital-aware attacker, cumulative error stays at or below the fixed-$\alpha_0$ worst case. The outcome that would refute it is either violations with the empirical $R$ that the certified $R$ does not repair, or no benign-accuracy gain over the fixed curve once $\rho$ falls below about 10%.

The secondary experiment on Cartpole and Pong schedules the policy-smoothing noise level from realized episodic return relative to Kumar et al.'s certified bound. No reported per-environment bound values are available on Lacuna, so we will recompute them. The test is whether clean return recovers on unattacked episodes while cumulative return under timed attacks stays above the certified total.