Operations Research Transactions ›› 2025, Vol. 29 ›› Issue (3): 93-123.doi: 10.15960/j.cnki.issn.1007-6093.2025.03.005

Special Issue: 第九届中国运筹学会科学技术奖获奖者专辑

• Research Article • Previous Articles     Next Articles

Solving Stackelberg prediction games using inexact hyper-gradient methods

Xu SHI1, Jiulin WANG2, Rujun JIANG1,*(), Weizheng SONG3   

  1. 1. School of Data Science, Fudan University, Shanghai 200433, China
    2. School of Mathematical Sciences, Nankai University, Tianjin 300071, China
    3. School of Mathematical Sciences, Fudan University, Shanghai 200433, China
  • Received:2025-02-22 Online:2025-09-15 Published:2025-09-09
  • Contact: Rujun JIANG E-mail:rjjiang@fudan.edu.cn

Abstract:

The Stackelberg prediction game (SPG) is a bilevel optimization framework for modeling strategic interactions between a learner and a follower. Existing methods for solving this problem with general loss functions are computationally expensive and scarce. We propose a novel hyper-gradient type method with a warm-start strategy to address this challenge. Particularly, we first use a Taylor expansion-based approach to obtain a good initial point. Then we apply a hyper-gradient descent method with an explicit approximate hyper-gradient. We establish the convergence results of our algorithm theoretically. Furthermore, when the follower employs the least squares loss function, our method is shown to reach an ε-stationary point by solving quadratic subproblems. Numerical experiments show our algorithms are empirically orders of magnitude faster than the state-of-the-art.

Key words: Stackelberg prediction game, approximate hyper-gradient, bilevel optimization

CLC Number: