English

运筹学学报 >

2025 , Vol. 29 >Issue 3: 93 - 123

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2025.03.005

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

斯塔克尔伯格预测博弈问题的非精确超梯度法

  • 石旭 ,
  • 王玖鳞 ,
  • 江如俊 ,
  • 宋维正
展开
  • 1. 复旦大学大数据学院, 上海 200433
    2. 南开大学数学科学学院, 天津 300071
    3. 复旦大学数学科学学院, 上海 200433

收稿日期: 2025-02-22

  网络出版日期: 2025-09-09

基金资助

国家自然科学基金(12171100)

版权

运筹学学报编辑部, 2025, 版权所有，未经授权，不得转载。
收起

Solving Stackelberg prediction games using inexact hyper-gradient methods

  • Xu SHI ,
  • Jiulin WANG ,
  • Rujun JIANG ,
  • Weizheng SONG
Expand
  • 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
江如俊   E-mail: rjjiang@fudan.edu.cn

Received date: 2025-02-22

  Online published: 2025-09-09

Copyright

, 2025, All rights reserved. Unauthorized reproduction is prohibited.
Fold

摘要

斯塔克尔伯格预测博弈是一种双层优化框架, 旨在建模学习者与追随者之间的交互。现有方法在处理具有一般损失函数的问题时, 计算代价高昂且方法较少。为了解决这一挑战, 我们提出了一种结合热启动策略的全新的基于超梯度的方法。具体而言, 我们首先采用基于泰勒展开的方法来获取一个良好的初始点, 然后利用具有显式近似超梯度的超梯度下降方法对问题进行求解。我们从理论上证明了该算法的收敛性。此外, 当追随者采用最小二乘损失函数时, 我们的方法仅通过求解二次子问题即可达到$\varepsilon$-稳定点。数值实验表明, 与当前最先进的方法相比, 我们的算法在时间上快了若干个数量级。

关键词： 斯塔克尔伯格预测博弈; 近似超梯度; 双层优化

本文引用格式

石旭 , 王玖鳞 , 江如俊 , 宋维正 . 斯塔克尔伯格预测博弈问题的非精确超梯度法[J]. 运筹学学报, 2025 , 29(3) : 93 -123 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.03.005

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

参考文献

1 Brückner M, Scheffer T. Stackelberg games for adversarial prediction problems[C]//Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2011: 547-555.
2 ZhouY,KantarciogluM,XiB.A survey of game theoretic approach for adversarial machine learning[J].Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery,2019,20(3):e1259.
3 Shokri R, Theodorakopoulos G, Troncoso C, et al. Protecting location privacy: Optimal strategy against localization attacks[C]//Proceedings of the 2012 ACM Conference on Computer and Communications Security, 2012: 617-627.
4 Balcan M-F, Blum A, Haghtalab N, et al. Commitment without regrets: Online learning in Stackelberg security games[C]//Proceedings of the 16th ACM Conference on Economics and Computation, 2015: 61-78.
5 Zhou Y, Kantarcioglu M. Modeling adversarial learning as nested Stackelberg games[C]//Proceedings, Part Ⅱ, of the 20th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, 2016: 350-362.
6 WahabO A,BentaharJ,OtrokH,et al.A Stackelberg game for distributed formation of business-driven services communities[J].Expert Systems with Applications,2016,45,359-372.
7 Bishop N, Tran-Thanh L, Gerding E. Optimal learning from verified training data[C]//Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020: 9520-9529.
8 JeroslowR G.The polynomial hierarchy and a simple model for competitive analysis[J].Mathematical Programming,1985,32(2):146-164.
9 Wang J, Chen H, Jiang R, et al. Fast algorithms for Stackelberg prediction game with least squares loss[C]//Proceedings of the 38th International Conference on Machine Learning, 2021: 10708-10716.
10 Wang J, Huang W, Jiang R, et al. Solving Stackelberg prediction game with least squares loss via spherically constrained least squares reformulation[C]//Proceedings of the 39th International Conference on Machine Learning, 2022: 22665-22679.
11 GouldN I M,LucidiS,RomaM,et al.Solving the trust-region subproblem using the Lanczos method[J].SIAM Journal on Optimization,1999,9(2):504-525.
12 Carmon Y, Duchi J C. Analysis of krylov subspace solutions of regularized non-convex quadratic problems[C]//Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018: 10728-10738.
13 ZhangL-H,ShenC.A nested Lanczos method for the trust-region subproblem[J].SIAM Journal on Scientific Computing,2018,40(4):A2005-A2032.
14 Pedregosa F. Hyperparameter optimization with approximate gradient[C]//Proceedings of the 33rd International Conference on Machine Learning, 2016: 737-746.
15 Franceschi L, Donini M, Frasconi P, et al. Forward and reverse gradient-based hyperparameter optimization[C]//Proceedings of the 34th International Conference on Machine Learning, 2017: 1165-1173.
16 Ghadimi S, Wang M. Approximation methods for bilevel programming[EB/OL]. [2024-12-16] arXiv: 1802.02246.
17 Shaban A, Cheng C-A, Hatch N, et al. Truncated back-propagation for bilevel optimization[C]//Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019: 1723-1732.
18 Grazzi R, Franceschi L, Pontil M, et al. On the iteration complexity of hypergradient computation[C]//Proceedings of the 37 $th International Conference on Machine Learning, 2020: 3748-3758.
19 Ji K, Yang J, Liang Y. Bilevel optimization: Convergence analysis and enhanced design[C]//Proceedings of the 38th International Conference on Machine Learning, 2021: 4882-4892.
20 Ji K, Liu M, Liang Y, et al. Will bilevel optimizers benefit from loops[C]//Proceedings of the 36th International Conference on Neural Information Processing Systems, 2022: 3011-3023.
21 Domke J. Generic methods for optimization-based modeling[C]//Proceedings of the 15th International Conference on Artificial Intelligence and Statistics, 2012: 318-326.
22 Ji K, Lee J D, Liang Y, et al. Convergence of meta-learning with task-specific adaptation over partial parameters[C]//Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020: 11490-11500.
23 ConnA R,GouldN I M,TointP L.Trust Region Methods[M].Philadelphia:SIAM,2000.
24 ShermanJ,MorrisonW J.Adjustment of an inverse matrix corresponding to a change in one element of a given matrix[J].The Annals of Mathematical Statistics,1950,21(1):124-127.
25 NesterovY.Lectures on Convex Optimization[M].Switzerland:Springer,2018.
26 JorgeN,StephenW J.Numerical Optimization[M].Heidelberg:Springer,2006.
Options
文章导航

/

〈 〉