REVIEW 4 major objections 5 minor 28 references
Gradient Methods for Solving Stackelberg Games
T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Two gradient methods make Stackelberg games solvable when decision spaces are continuous and high-dimensional.
desk verdict A useful adaptation of hyperparameter optimization to Stackelberg games, but the main convergence proofs have a sign error and the finite-horizon surrogate error is never bounded. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central mechanism is the adjoint method, a backward-in-time integration that computes the total derivative of the defender's utility under the gradient-flow constraint without forming the expensive Jacobian $d_\alpha\beta(\alpha,t)$ directly. The adjoint function $\lambda(t)$ solves $d_t\lambda(t)=-\lambda(t)\,\partial^2_\beta u_A[\alpha,\beta(\alpha,t)]$ with terminal condition $\lambda(T)=-\partial_\beta u_D[\alpha,\beta(\alpha,T)]$, and yields $d_\alpha u_D[\alpha,\beta(\alpha,T)] = \partial_\alpha u_D[\alpha,\beta(\alpha,T)] - \int_0^T \lambda(t)\,\partial_\alpha\partial_\beta u_A[\alpha,\beta(\alpha,t)]\,dt$. The forward solution uses the complementary mechanism of propagating the Jacobian $d_\alpha\beta_t(\alpha)$ through the $T$-step recurrence. Both rest on Propositions 1 and 2, which guarantee that the inner trajectory converges to the unique best response $\beta^*(\alpha)$ at rate $O(1/t)$ under a strict angle condition on the attacker's utility gradient.
What would settle it
On a game with a known closed-form equilibrium (like the conceptual example in Section 4.1), compare the gradient returned by either algorithm at a non-optimal defender action $\alpha$ with a finite-difference estimate of $d_\alpha u_D[\alpha,\beta^*(\alpha)]$ obtained from the exact best response; if the two do not converge as $T$ grows, or if outer gradient ascent from many random starting points does not approach the known equilibrium, the paper's central claim is false.
Extended reading notes
Core claim
The paper's central claim is that the bilevel Stackelberg problem can be replaced, to good effect, by a finite-horizon approximation in which the attacker's exact best response $\beta^*(\alpha)$ is replaced by the endpoint $\beta(\alpha,T)$ of a gradient flow (backward solution) or of a $T$-step gradient ascent (forward solution). For this replacement, the paper shows how to compute the total derivative $d_\alpha u_D[\alpha,\beta(\alpha,T)]$ exactly: the backward solution uses an adjoint equation and requires time $O(T\tau(n,m))$ and space $O(T\sigma(n,m))$; the forward solution differentiates the update recurrence directly and requires time $O(mT\tau(m,n))$ and space $O(\sigma(m,n))$. Under a uniqueness condition on the attacker's utility and a monotone-angle condition, Propositions 1 and 2 give convergence of $\beta(\alpha,t)$ to $\beta^*(\alpha)$ at rate $O(1/t)$ as $t\to\infty$, which is the theoretical justification for taking $T$ large. In the adversarial regression experiment, the backward solution produces a defender whose RMSE remains nearly constant as the attacker's incentive $c_d$ increases, while a non-adversarial ridge regression degrades; the paper also reports about 2.66 seconds per outer epoch on a laptop.
Load-bearing premise
The finite-horizon approximation replaces the attacker's exact best response with the endpoint of a $T$-step gradient trajectory, and the paper never bounds how much error this replacement introduces into the defender's objective, so the algorithms could be optimizing a different problem if $T$ is not large enough.
Editorial extensions
If this is right
- A defender with a moderate-dimensional decision and a very high-dimensional attacker can solve the Stackelberg game with the backward method in minutes on a laptop, as the adversarial regression experiment demonstrates.
- The forward method provides a memory-light alternative for settings where storing the full attacker trace across $T$ steps is infeasible, at the price of runtime that grows with the attacker's dimension $m$.
- Because both gradient computations are composed of automatic-differentiation primitives, they can be implemented directly on top of standard deep-learning libraries without a custom bilevel solver.
- The $O(1/t)$ inner convergence rate means the finite-horizon approximation bias shrinks only polynomially in $T$, so applications should choose $T$ by monitoring stabilization of the defender's outer objective.
Reading between the lines
- A natural diagnostic, not tested in the paper, is to run the outer gradient ascent for several increasing values of $T$ and check whether the resulting defender action stabilizes; if it does not, $T$ is too small and the algorithm is likely optimizing the wrong surface.
- The memory-saving trick of reversing or checkpointing the stored trace, mentioned as future work in the discussion, would make the backward method dominant in both time and memory if it can be implemented without destroying the gradient accuracy.
- The same adjoint-plus-gradient-flow construction should transfer to other continuous-action sequential games, such as security resource-allocation games, where the attacker response is also a smooth optimization problem.
- For neural-network utilities, where the trace storage cost can dominate, a hybrid strategy that checkpoints the trace at intervals and recomputes between checkpoints would interpolate between the paper's two methods; the paper does not explore this.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes two gradient-based methods for solving continuous Stackelberg games in adversarial machine learning: a backward/adjoint method and a forward method. Both methods replace the attacker's exact best response β*(α) by a finite-horizon gradient ascent/flow trajectory β(α,T), then perform gradient ascent on the resulting surrogate objective. The authors analyze time and space complexity and report experiments on a conceptual scalability example and on an adversarial regression problem. The paper adapts techniques from hyperparameter optimization (Franceschi et al., 2017) to the Stackelberg setting and provides reproducible code.
Significance. If the proposed methods were rigorously justified, they would provide a practical way to attack Stackelberg games with continuous, high-dimensional decision spaces, which are common in adversarial machine learning and beyond. The paper's complexity analysis and the empirical demonstration on an adversarial regression problem with O(10^4)-dimensional attacker decisions are valuable. The code is publicly available. However, the theoretical support for the central approximation is flawed: the key convergence propositions contain a sign error, and no bound is given for the finite-horizon truncation error. Without repair, the algorithms are heuristics whose convergence to a Stackelberg equilibrium is unsupported.
major comments (4)
- [§3.1, Proposition 1; §3.2, Proposition 2] Assumption 2 in both propositions has the wrong inequality sign. For the ODE ∂tβ = ∂βuA with β*(α) a maximizer, the natural Lyapunov function V(t) = ½‖β(t) − β*(α)‖² satisfies dV/dt = ⟨β − β*, ∂βuA⟩. Convergence requires this inner product to be negative, not positive, for β away from β*. The paper's own Section 4.1 example contradicts the stated condition: at α=0, β=1, β*=0, ∂βuA = −6β, so ⟨β − β*, ∂βuA⟩ = −6 < 0, yet the flow converges to β*. Thus Proposition 1 is false as written; the same sign error appears in Proposition 2.
- [§3.1–§3.2, Eqs. (2) and (6)] Even after correcting the sign, Propositions 1 and 2 only assert β(α,T) → β*(α) as T→∞. They do not establish convergence of dαβ(α,T) to dαβ*(α), nor convergence of the gradient dαuD[α,β(α,T)] to dαuD[α,β*(α)], which is the quantity actually used in the outer gradient ascent. Without such a result, Algorithms 1 and 2 optimize the finite-horizon surrogate (2)/(6), not the stated Stackelberg problem (1). A quantitative or qualitative bound on the truncation error |uD[α,β(α,T)] − uD[α,β*(α)]| and on the corresponding gradient error is needed to justify the algorithms.
- [§3.2, complexity discussion] The forward method's space complexity is stated as O(σ(m,n)), claiming that β_t values are overwritten. However, Algorithm 2 also maintains the Jacobian dαβ_t, which is an n×m matrix (or m×n depending on convention). Storing this matrix requires O(nm) memory, which is not reflected in the stated complexity. This omission affects the claimed 'scales well in space' advantage and the comparison in Figure 2, where n=m and memory growth would be quadratic rather than constant.
- [§4.2 and §5] The experimental section does not provide evidence that the computed solution is close to a true Stackelberg equilibrium. The hyperparameters T=40 and T=100 are chosen 'enough to reach convergence' without a convergence diagnostic, and no comparison to an exact or independently computed equilibrium is reported for the adversarial regression problem. At minimum, a sensitivity analysis over T and the inner learning rate η, or a verification on a small instance where the exact bilevel solution can be computed, would be needed to support the claim that the method solves the actual Stackelberg problem.
minor comments (5)
- [§4.1] The utility definitions contain inconsistent subscript use: uA(α,β) = −Σ_i 3(β_i − α_j)² and uD(α,β) = −Σ_i(7α_i + β²_j) use both i and j; this should be fixed (likely all i).
- [§4.2] The text says the data generator aims to 'confuse the data generator'; presumably this should be 'confuse the learner'.
- [§4.2] In the last paragraph, the defender's decisions are denoted ω after previously being denoted w; unify the notation.
- [Algorithm 1] The initialization β0(α)=0 may be unrealistic for the attacker's best response when β*(α) is nonzero; the paper does not discuss the effect of this initialization, and a non-zero starting point would change the surrogate objective.
- [§5] The discussion of extending the backward method with reversible learning [19] is a useful pointer, but it is not developed; this is fine as future work.
Circularity Check
No circularity: the two gradient methods are adaptations of external hyperparameter-optimization techniques, and the experimental benchmark uses an external data set; the finite-horizon approximation is acknowledged as an approximation, not presented as a fitted prediction of the exact best response.
full rationale
I checked the claimed derivation chain. The paper's central claim is that forward and backward differentiation of the finite-horizon surrogate (2)/(6) yields usable gradients for the Stackelberg problem (1). This is not circular: the surrogate replaces the exact best response beta*(alpha) with a finite-horizon trajectory beta_T, and the adjoint/forward differentiation formulas are obtained by direct calculus and automatic differentiation arguments, not by defining the target quantity in terms of itself. The convergence propositions cite the external standard reference [3] (Bottou), not the current authors' own prior work, so there is no self-citation chain forcing the conclusion. The adopted approximations are explicitly labelled as approximations ('approximate problem (1)' and 'T \gg 1'), and no fitted constant is later renamed as a prediction. Section 4 compares the proposed Nash solution against a non-adversarial baseline on the UCI white wine dataset, with hyperparameters selected by inspection; this is an external empirical benchmark, not a self-validating construction. The paper's self-citations ([11], [22], [25]) appear in background and future-work contexts and are not load-bearing for the gradient derivation. Any concern about the inequality sign in Propositions 1 and 2, or about whether convergence of beta_T implies convergence of d_alpha beta_T, is a correctness or rigor gap, not circularity. Therefore the appropriate circularity score is 0.
Assumptions & free parameters
free parameters (3)
- Number of inner iterations T (horizon) =
40 (conceptual), 100 (wine)
- Inner learning rate η =
0.1 (conceptual), 0.01 (wine)
- Outer learning rate =
0.1 (conceptual), 1e-6 (wine)
assumptions (5)
- domain assumption Inner problem (attacker's utility) has a unique global maximum β*(α) for every defender action α
- domain assumption Gradient dominance condition: for every ε>0 and α, ⟨β - β*(α), ∂β uA[α, β]⟩ > 0 outside the ε-ball around β*(α)
- domain assumption Quadratic growth bound: ||∂β uA||^2 ≤ A + B||β - β*(α)||^2 for some A,B > 0
- domain assumption Common knowledge: the defender knows the attacker's utility uA(α, β)
- domain assumption Automatic differentiation libraries compute Hessian-vector products with the stated complexity
Cite this review
Pith. "Pith review of Gradient Methods for Solving Stackelberg Games." pith.science (2026). https://pith.science/paper/UXDLRW33
@misc{pith2026190806901,
author = {Pith},
title = {Pith review of: Gradient Methods for Solving Stackelberg Games},
year = {2026},
howpublished = {\url{https://pith.science/paper/UXDLRW33}},
note = {Machine review of arXiv:1908.06901}
}
read the original abstract
Stackelberg Games are gaining importance in the last years due to the raise of Adversarial Machine Learning (AML). Within this context, a new paradigm must be faced: in classical game theory, intervening agents were humans whose decisions are generally discrete and low dimensional. In AML, decisions are made by algorithms and are usually continuous and high dimensional, e.g. choosing the weights of a neural network. As closed form solutions for Stackelberg games generally do not exist, it is mandatory to have efficient algorithms to search for numerical solutions. We study two different procedures for solving this type of games using gradient methods. We study time and space scalability of both approaches and discuss in which situation it is more appropriate to use each of them. Finally, we illustrate their use in an adversarial prediction problem.
Figures
Reference graph
Works this paper leans on
-
[1]
J ournal of optimization theory and applications 68(2), 371–378 (1991)
Bard, J.F.: Some properties of the bilevel programming problem. J ournal of optimization theory and applications 68(2), 371–378 (1991)
work page 1991
-
[2]
Pattern Recognition 84, 317–331 (2018)
Biggio, B., Roli, F.: Wild patterns: Ten years after the rise of adver sarial machine learning. Pattern Recognition 84, 317–331 (2018)
work page 2018
-
[3]
On-line learning in neural networks 17(9), 142 (1998)
Bottou, L.: Online learning and stochastic approximations. On-line learning in neural networks 17(9), 142 (1998)
work page 1998
-
[4]
Interfaces 36(6), 530–544 (2006)
Brown, G., Carlyle, M., Salmer´ on, J., Wood, K.: Defending critical in fras- tructure. Interfaces 36(6), 530–544 (2006)
work page 2006
-
[5]
Br¨ uckner, M., Scheffer, T.: Stackelberg games for adversaria l prediction problems. In: Proceedings of the 17th ACM SIGKDD international c onfer- ence on Knowledge discovery and data mining. pp. 547–555. ACM (20 11)
-
[6]
Dheeru, D., Karra Taniskidou, E.: UCI machine learning repository (2017), http://archive.ics.uci.edu/ml
work page 2017
-
[7]
In: Proceedings o f the 34th 14 R
Franceschi, L., Donini, M., Frasconi, P., Pontil, M.: Forward and rev erse gradient-based hyperparameter optimization. In: Proceedings o f the 34th 14 R. Naveiro and D. R ´ ıos Insua International Conference on Machine Learning-Volume 70. pp. 11 65–1173. JMLR. org (2017)
work page 2017
- [8]
Show all 28 references
-
[9]
Friedman, J., Hastie, T., Tibshirani, R.: The elements of statistical learning, vol. 1. Springer series in statistics New York (2001)
2001
-
[10]
Harvester Wheatsheaf (1 992)
Gibbons, R.: A Primer in Game Theory. Harvester Wheatsheaf (1 992)
-
[11]
European Jour nal of Operational Research 273(3), 1085–1096 (2019)
Gonz´ alez-Ortega, J., Insua, D.R., Cano, J.: Adversarial risk a nalysis for bi- agent influence diagrams: An algorithmic approach. European Jour nal of Operational Research 273(3), 1085–1096 (2019)
2019
-
[12]
105 (2008)
Griewank, A., Walther, A.: Evaluating derivatives: principles and t echniques of algorithmic differentiation, vol. 105 (2008)
2008
-
[13]
In: International Conferenc e on Machine Learning
Großhans, M., Sawade, C., Br¨ uckner, M., Scheffer, T.: Bayesia n games for adversarial regression problems. In: International Conferenc e on Machine Learning. pp. 55–63 (2013)
2013
-
[14]
Routledge (2004)
Heap, S.H., Varoufakis, Y.: Game Theory. Routledge (2004)
2004
-
[15]
Hinze, M., Pinnau, R., Ulbrich, M., Ulbrich, S.: Optimization with PDE constraints, vol. 23. Springer Science & Business Media (2008)
2008
-
[16]
Mathematical programming 32(2), 146–164 (1985)
Jeroslow, R.G.: The polynomial hierarchy and a simple model for co mpeti- tive analysis. Mathematical programming 32(2), 146–164 (1985)
1985
-
[17]
Computational statistics & da ta analysis 53(11), 3735–3745 (2009)
Kim, J.H.: Estimating classification error rate: Repeated cross- validation, repeated hold-out and bootstrap. Computational statistics & da ta analysis 53(11), 3735–3745 (2009)
2009
-
[18]
Journal of opt imization theory and applications 65(3), 485–499 (1990)
Kolstad, C.D., Lasdon, L.S.: Derivative evaluation and computatio nal ex- perience with large bilevel mathematical programs. Journal of opt imization theory and applications 65(3), 485–499 (1990)
1990
-
[19]
In: International Confe rence on Machine Learning
Maclaurin, D., Duvenaud, D., Adams, R.: Gradient-based hyperp arameter optimization through reversible learning. In: International Confe rence on Machine Learning. pp. 2113–2122 (2015)
2015
-
[20]
IEEE Security & Privacy 14(3), 68–72 (2016)
McDaniel, P., Papernot, N., Celik, Z.B.: Machine learning in adversar ial settings. IEEE Security & Privacy 14(3), 68–72 (2016)
2016
-
[21]
arXiv preprint arXiv:1901.08511 (2019)
Mokhtari, A., Ozdaglar, A., Pattathil, S.: A unified analysis of extr a- gradient and optimistic gradient methods for saddle point problems: Prox- imal point approach. arXiv preprint arXiv:1901.08511 (2019)
2019 arXiv
-
[22]
International Journ al of Ap- proximate Reasoning 113, 133–148 (2019)
Naveiro, R., Redondo, A., Insua, D.R., Ruggeri, F.: Adversarial c lassifica- tion: An adversarial risk analysis approach. International Journ al of Ap- proximate Reasoning 113, 133–148 (2019)
2019
-
[23]
Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., DeVito, Z., Lin, Z., Desmaison, A., Antiga, L., Lerer, A.: Automatic differentiation in pyto rch (2017)
2017
-
[24]
Routledge (2018)
Pontryagin, L.S.: Mathematical theory of optimal processes. Routledge (2018)
2018
-
[25]
Jou rnal of the American Statistical Association 104(486), 841–854 (2009)
Rios Insua, D., Rios, J., Banks, D.: Adversarial risk analysis. Jou rnal of the American Statistical Association 104(486), 841–854 (2009)
2009
-
[26]
IEEE Transact ions on Evolutionary Computation 22(2), 276–295 (2018) Gradient Methods for Solving Stackelberg Games 15
Sinha, A., Malo, P., Deb, K.: A review on bilevel optimization: from cla s- sical to evolutionary approaches and applications. IEEE Transact ions on Evolutionary Computation 22(2), 276–295 (2018) Gradient Methods for Solving Stackelberg Games 15
2018
-
[27]
Cambridge University Press (2011)
Tambe, M.: Security and game theory: algorithms, deployed sys tems, lessons learned. Cambridge University Press (2011)
2011
-
[28]
Syn- thesis Lectures on Artificial Intelligence and Machine Learning 12(3), 1–169 (2018)
Vorobeychik, Y., Kantarcioglu, M.: Adversarial machine learning . Syn- thesis Lectures on Artificial Intelligence and Machine Learning 12(3), 1–169 (2018). https://doi.org/10.2200/S00861ED1V01Y201806 AIM039, https://doi.org/10.2200/S00861ED1V01Y201806AIM039 A Proof of the adjoi...
2018 doi
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.