Pith. sign in

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 →

arxiv 1908.06901 v3 pith:UXDLRW33 submitted 2019-08-19 cs.GT stat.COstat.ML

classification cs.GTstat.COstat.ML MSC 91A6590C3065K05
keywords Stackelberggamesbileveloptimizationadversarialmachinelearninggradientascentadjointmethodautomaticdifferentiationcontinuoushigh-dimensional
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Stackelberg games with continuous, high-dimensional decisions—the situation that arises when both players are machine-learning algorithms—cannot generally be solved in closed form, and classical bilevel solvers do not scale. This paper argues that gradient ascent can solve them numerically if the defender can compute the gradient of her utility with respect to her own decision, and it proposes two ways to obtain that gradient. The backward method approximates the attacker's best response by a gradient flow truncated at time $T$ and differentiates through it with an adjoint equation; the forward method propagates derivatives through $T$ steps of gradient ascent. The paper claims that the backward method scales well in time with the defender's decision dimension while the forward method scales well in memory, so together they cover the regimes that arise in adversarial machine learning. On an adversarial regression problem, the backward method yields a defender whose error stays flat as attacks grow stronger, which is what a correct Stackelberg solution should do.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

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)
  1. [§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.
  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. [§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. [§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)
  1. [§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).
  2. [§4.2] The text says the data generator aims to 'confuse the data generator'; presumably this should be 'confuse the learner'.
  3. [§4.2] In the last paragraph, the defender's decisions are denoted ω after previously being denoted w; unify the notation.
  4. [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. [§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

0 steps flagged · score 0.0 of 10

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 3 free parameters · 5 assumptions · 0 invented entities

The method inherits the standard bilevel assumptions: uniqueness of the inner solution, common knowledge of the attacker utility, plus Bottou-type convergence conditions. No new physical or mathematical entities are introduced.

free parameters (3)
  • Number of inner iterations T (horizon) = 40 (conceptual), 100 (wine)
    T controls how closely β(α,T) approximates β*(α); the paper sets it by hand and asserts T ≫ 1 without error control. The reported results are conditional on these choices.
  • Inner learning rate η = 0.1 (conceptual), 0.01 (wine)
    Inner gradient step size in Algorithms 1 and 2; must satisfy the convergence assumptions and is selected by hand.
  • Outer learning rate = 0.1 (conceptual), 1e-6 (wine)
    Gradient ascent or descent step for the defender; chosen by hand and affects convergence of the outer loop.
assumptions (5)
  • domain assumption Inner problem (attacker's utility) has a unique global maximum β*(α) for every defender action α
    Invoked throughout Sections 2 and 3 to justify backward induction; excludes optimistic and pessimistic equilibria.
  • domain assumption Gradient dominance condition: for every ε>0 and α, ⟨β - β*(α), ∂β uA[α, β]⟩ > 0 outside the ε-ball around β*(α)
    Assumed in Propositions 1 and 2 to prove convergence of gradient flow and gradient ascent to β*(α); not verified in the AML experiment.
  • domain assumption Quadratic growth bound: ||∂β uA||^2 ≤ A + B||β - β*(α)||^2 for some A,B > 0
    Condition 3 in Proposition 2, required for the discrete-time convergence rate; the paper states it without checking it for the wine experiment.
  • domain assumption Common knowledge: the defender knows the attacker's utility uA(α, β)
    Stated in Section 2 as the common knowledge hypothesis; the whole Stackelberg solution rests on it.
  • domain assumption Automatic differentiation libraries compute Hessian-vector products with the stated complexity
    The complexity analysis in Sections 3.1 and 3.2 relies on standard AD complexity results, which may fail for custom or non-differentiable operations.

how reviews work

0 comments
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

Figures reproduced from arXiv: 1908.06901 by the authors.

Figure 1
Figure 1. The two-player sequential decision game with certain outcom [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Backward and Forward running times versus the dimension of [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 4
Figure 4. Convergence for several initial points. Finally, to illustrate convergence of the proposed approach, we solve (8) using gradient descent with the backward method for 20 different random initializa￾tions of the defender’s decisions ω. Results are depicted in [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 27 canonical work pages

  1. [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)

  2. [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)

  3. [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)

  4. [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)

  5. [5]

    In: Proceedings of the 17th ACM SIGKDD international c onfer- ence on Knowledge discovery and data mining

    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. [6]

    Dheeru, D., Karra Taniskidou, E.: UCI machine learning repository (2017), http://archive.ics.uci.edu/ml

  7. [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)

  8. [8]

    Wiley (2000)

    French, S., Insua, D.R.: Statistical decision theory. Wiley (2000)

Show all 28 references
  1. [9]

    Friedman, J., Hastie, T., Tibshirani, R.: The elements of statistical learning, vol. 1. Springer series in statistics New York (2001)

  2. [10]

    Harvester Wheatsheaf (1 992)

    Gibbons, R.: A Primer in Game Theory. Harvester Wheatsheaf (1 992)

  3. [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)

  4. [12]

    105 (2008)

    Griewank, A., Walther, A.: Evaluating derivatives: principles and t echniques of algorithmic differentiation, vol. 105 (2008)

  5. [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)

  6. [14]

    Routledge (2004)

    Heap, S.H., Varoufakis, Y.: Game Theory. Routledge (2004)

  7. [15]

    Hinze, M., Pinnau, R., Ulbrich, M., Ulbrich, S.: Optimization with PDE constraints, vol. 23. Springer Science & Business Media (2008)

  8. [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)

  9. [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)

  10. [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)

  11. [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)

  12. [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)

  13. [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)

  14. [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)

  15. [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)

  16. [24]

    Routledge (2018)

    Pontryagin, L.S.: Mathematical theory of optimal processes. Routledge (2018)

  17. [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)

  18. [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

  19. [27]

    Cambridge University Press (2011)

    Tambe, M.: Security and game theory: algorithms, deployed sys tems, lessons learned. Cambridge University Press (2011)

  20. [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...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.