DS606 – Game Theory for Machine Learning (IIT Bombay)
Author: Anurag Deshpande · Paper: paper.pdf · Slides: Deck.pdf
We formulate adversarial ML robustness as a finite zero-sum imperfect-information extensive-form game (EFG) between an adversary and a defender. Both players choose strategies—attacks and classifiers—across T = 3 rounds, with a public loss-magnitude signal s ∈ {H, M, L} revealed after each round. Solving via Counterfactual Regret Minimization (CFR), cross-validated with Double Oracle and Stackelberg LP, yields mixed-strategy Nash Equilibria with provable minimax accuracy guarantees.
- Two-game threat-model separation — Adversarial (L∞-bounded) and corruption attacks occupy separate payoff matrices with separate NE solutions, avoiding conflation of fundamentally different threat models.
- Gradient-obfuscation accountability — BoundaryAttack provides a gradient-free worst-case bound for non-differentiable defenders (KNN, RandomForest), complementing surrogate-gradient APGD.
- Multi-round strategic value — Value of Information VoI = V*_EFG − V*_stage quantifies the benefit of T = 3 rounds of public loss signalling over a single-shot game.
- EoT adaptive attack — Expectation-over-Transformations PGD against the known NE mixture tests whether the NE survives an attacker who knows the defender's mixed strategy.
- Statistical rigor — Clopper-Pearson exact binomial 95% CIs (not bootstrap); signal threshold sensitivity across 5 (τ_L, τ_H) configurations.
| Game | Attacks | Nature |
|---|---|---|
| Adversarial | APGD, BoundaryAttack, SquareAttack, CW | L∞-bounded worst-case perturbations |
| Corruption | Rotation, GaussianBlur, PixelCorrupt | Common image corruptions (not L∞-bounded) |
Each game produces its own payoff matrix and NE solution. Results are never mixed across games.
| Model | Type | Notes |
|---|---|---|
| MLP | Neural (sklearn) | 256→128 hidden, early stopping |
| SVM | Kernel (sklearn) | RBF, C=10, gamma=scale |
| RandomForest | Ensemble (sklearn) | 150 trees, max_depth=10 |
| KNN | Instance-based (sklearn) | k=5, Euclidean, brute-force |
| ConvNet | Neural (PyTorch) | 3-layer CNN, Adam |
| WideResNet-16-4 | Neural (PyTorch) | ~2.7M params, CPU-feasible |
| Dataset | L∞ budget | Source |
|---|---|---|
| MNIST | ε = 0.3 | Madry challenge; Cohen et al. 2019 |
| CIFAR-10 | ε = 8/255 ≈ 0.0314 | RobustBench; Madry et al. 2018 |
| File | Role |
|---|---|
config.py |
Central hyperparameter registry. Set QUICK_RUN = False for the full paper run. |
data.py |
Loaders for full MNIST (60k/10k) and native RGB CIFAR-10 (50k/10k via torchvision). |
models.py |
6 defenders + NumpySurrogate distillation for gradient-based attacks. |
wideresnet.py |
WideResNet-16-4 architecture with optional PGD adversarial training. |
attacks.py |
APGD, BoundaryAttack, SquareAttack, CW, corruption attacks, EoT-PGD, Clopper-Pearson CIs. |
game.py |
CFR solver, Double Oracle LP, Stackelberg LP, VoI, sensitivity sweep, prior-work comparison. |
analysis.py |
9-panel 3×3 visualization; prints full EFG behavioral strategies. |
main.py |
Orchestration: multi-seed loop, two-game payoff construction, all solvers, EoT evaluation. |
| File | Role |
|---|---|
run_capture.py |
Runs main.py and writes stdout to results/output.txt. Recommended for paper runs. |
spawn.py |
Spawns main.py as a detached background process on Windows. |
run.bat |
Windows batch launcher. |
pip install numpy scipy scikit-learn torch torchvision matplotlibCIFAR-10 is downloaded automatically by torchvision on first run (~170 MB to ~/.torch/).
MNIST is fetched via sklearn.datasets.fetch_openml.
cd "DS606 Project"
python run_capture.py # stdout → results/output.txt
# or directly:
python main.pyPlots are saved to:
results/mnist/robust_ml_v4.png
results/cifar10/robust_ml_v4.png
Set QUICK_RUN = True in config.py. Runs MNIST only in ~5 minutes with minimal budgets.
| Parameter | Value | Notes |
|---|---|---|
PGD_EPS |
0.3 (MNIST), 8/255 (CIFAR-10) | Community-standard L∞ budgets |
PGD_ALPHA |
0.030 (MNIST), 2/255 (CIFAR-10) | Step size ≈ ε/10 |
APGD_STEPS |
50 | Adaptive step schedule |
APGD_N_RESTARTS |
2 | Random restarts |
SQUARE_N_QUERIES |
1,000 | Score-based queries (RobustBench uses 5,000) |
BOUNDARY_STEPS |
100 | Decision-boundary refinement steps |
BOUNDARY_INIT_TRIES |
100 | Nearest-opposite-class initialisations |
CW_STEPS |
100 | CW L2 inner iterations |
CW_BINARY_STEPS |
6 | Binary search steps on confidence |
EOT_PGD_STEPS |
100 | EoT-PGD adaptive attack steps |
CFR_ITER |
50,000 | Targets exploitability < 1e-4 |
N_TRAIN_SUBSET |
10,000 | Training subset for classical models |
N_TEST_SAMPLES |
2,000 | Evaluation subset (CI width ≈ ±2.2%) |
RANDOM_SEEDS |
[42] | Single seed (3-seed adds ~3× compute) |
_convnet_epochs |
30 | ConvNet epochs (Adam, lr=1e-3) |
_wrn_epochs |
20 | WideResNet-16-4 epochs (SGD, cosine LR) |
use_adv_train |
False | PGD-AT disabled on CPU; enable for GPU runs |
CFR_ITER |
50,000 | ε-Nash certificate: exploitability ~1e-4 |
SENSITIVITY_CONFIGS |
5 configs | (τ_L, τ_H) sweep: (0.35,0.60)…(0.55,0.80) |
ROTATION_ANGLE |
25° | Max rotation (corruption game) |
PIXEL_CORRUPT_P |
0.25 | Salt-and-pepper probability |
GAUSSIAN_SIGMA |
2.0 (28px), 2.5 (32px) | Blur sigma per image size |
| Phase | MNIST | CIFAR-10 |
|---|---|---|
| Data loading | ~15 s | ~30 s (first run) |
| Train 6 defenders | ~15 min | ~25 min |
| Train surrogates (20 epochs) | ~2 min | ~3 min |
| APGD (50 steps, 6 models) | ~2 min | ~3 min |
| BoundaryAttack (100 steps, 6 models) | ~10 min | ~15 min |
| SquareAttack (1k queries, 6 models) | ~20 min | ~35 min |
| CW (100 steps, 6 models) | ~5 min | ~8 min |
| Corruption attacks (3 types, 6 models) | ~3 min | ~4 min |
| EoT-PGD adaptive evaluation | ~5 min | ~8 min |
| CFR (50k iterations) × 2 (main + VoI) | ~15 min | ~18 min |
| Signal sensitivity (5 configs) | ~5 min | ~6 min |
| Total | ~100 min | ~120 min |
Full paper run (both datasets): ~3–4 hours on CPU.
For GPU runs with WideResNet-28-10 and PGD-AT, set _WRN_ARCH["cifar10"] = (28, 10) in wideresnet.py and use_adv_train=True in config.py.
- Players: Adversary A (chooses attack a ∈ A_adv or A_cor), Defender D (chooses classifier d ∈ D)
- Rounds: T = 3, simultaneous moves per round
- Signal: s_t ∈ {H, M, L} after round t; public to both players
- H (high loss): accuracy < 45% (attacker winning)
- M (medium): 45% ≤ accuracy < 70%
- L (low loss): accuracy ≥ 70% (defender winning)
- Payoff: Adversarial accuracy (defender accuracy = 1 − adversary payoff)
- Information sets: (player, round, own-action history, signal history)
CFR recurses over the EFG tree with information-set keys (player, round, action_tuple, signal_tuple). At 50,000 iterations, regret matching converges to exploitability < 10⁻⁴, constituting a formal ε-Nash certificate. Three solvers (CFR, Double Oracle, Stackelberg LP) are cross-validated for consistency.
VoI = V*_EFG − V*_stage
V*_EFG is the T = 3 round EFG game value (with public signals). V*_stage is the one-shot stage-game NE value. VoI > 0 indicates that multi-round signalling benefits the defender.
Expectation-over-Transformations PGD against the NE mixture σ_D*:
∇_x L^EoT = Σ_d σ_d · ∇_x L(f_d(x), y)
This is the critical adaptive-attack evaluation (Tramèr et al. NeurIPS 2020): does the NE mixture survive an attacker who knows the defender's mixed strategy and can exploit it?
For non-differentiable classifiers (SVM, RF, KNN), a NumpySurrogate (3-layer numpy MLP) is trained via knowledge distillation with squared-normalised soft targets. APGD runs on surrogate gradients. BoundaryAttack provides a complementary gradient-free bound that is immune to gradient masking.
Clopper-Pearson exact binomial 95% CIs are computed for each (attack, model) cell. At n = 2,000 test samples, the expected half-width is ≈ ±2.2 percentage points. The CI is conservative (actual coverage ≥ 95%) and does not rely on normal approximation.
Signal threshold sensitivity sweeps over 5 (τ_L, τ_H) configurations:
(0.35, 0.60), (0.40, 0.65), (0.45, 0.70), (0.50, 0.75), (0.55, 0.80)
The base setting is (0.45, 0.70). NE support qualitative structure is reported across all configs.
- Attack class restriction — The game-value certificate V* is a minimax guarantee within the defined attack set A. It is not a pointwise L∞-certified guarantee (as in randomised smoothing).
- Surrogate-gradient limitation — APGD via surrogate may underestimate adversary payoff against KNN/RF due to gradient obfuscation (Athalye et al. ICML 2018). BoundaryAttack provides a complementary gradient-free bound.
- CPU scale — WideResNet-16-4 (~2.7M params) is used for CPU feasibility. WideResNet-28-10 (~36M params) with full PGD-AT gives higher robustness but requires a GPU.
- KNN scalability — KNN predict_proba is O(N_train × d) per call; 10k training samples, 784/3072 features. SquareAttack and BoundaryAttack are slow against KNN.
- Single seed — Paper run uses seed 42. Full 3-seed replication [42, 123, 789] would add ~3× compute.
- Not comparable to RobustBench — RobustBench evaluates WRN-28-10 with PGD-AT at 5,000 Square queries on the full 10k test set. Our game-theoretic framework uses different scope.
| Symptom | Cause | Fix |
|---|---|---|
| CIFAR-10 download fails | Network issue | Set TORCH_HOME to a writable path and retry |
| WideResNet training > 1 hr | GPU not available; WRN-28-10 selected | Ensure _WRN_ARCH["cifar10"] = (16, 4) in wideresnet.py |
| BoundaryAttack very slow | 100 steps × 6 models × 2k samples | Reduce BOUNDARY_STEPS to 20 for development |
| SquareAttack vs KNN slow | O(N_train) per predict_proba call | Reduce SQUARE_N_QUERIES to 100 for development |
| CFR exploitability not < 1e-4 | Too few iterations | Increase CFR_ITER to 100,000 (GPU recommended) |
UnicodeEncodeError on Windows |
Terminal encoding | main.py calls sys.stdout.reconfigure(encoding="utf-8") at startup |
torch.cuda.is_available() = False |
No CUDA GPU | Code falls back to CPU automatically; training is slower |
- Madry et al. (2018). Towards Deep Learning Models Resistant to Adversarial Attacks. ICLR.
- Croce & Hein (2020). Reliable Evaluation of Adversarial Robustness with an Ensemble of Diverse Parameter-Free Attacks. ICML.
- Andriushchenko et al. (2020). Square Attack: A Query-Efficient Black-Box Adversarial Attack via Random Search. ECCV.
- Carlini & Wagner (2017). Towards Evaluating the Robustness of Neural Networks. IEEE S&P.
- Brendel et al. (2018). Decision-Based Adversarial Attacks: Reliable Attacks Against Black-Box Machine Learning Models. ICLR.
- Athalye et al. (2018). Obfuscated Gradients Give a False Sense of Security. ICML.
- Tramèr et al. (2020). On Adaptive Attacks to Adversarial Example Defenses. NeurIPS.
- Zinkevich et al. (2007). Regret Minimization in Games with Incomplete Information. NIPS.
- Zagoruyko & Komodakis (2016). Wide Residual Networks. BMVC.
- Hendrycks & Dietterich (2019). Benchmarking Neural Network Robustness to Common Corruptions. ICLR.
@misc{deshpande2026robustml,
author = {Deshpande, Anurag},
title = {Robust ML as an Imperfect-Information Extensive-Form Game},
year = {2026},
note = {Course project, DS606 -- Game Theory for Machine Learning, IIT Bombay}
}Anurag Deshpande · anuragdeshpande31@gmail.com · github.com/anurag-add