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

doi:10.15960/j.cnki.issn.1007-6093.2025.03.005

运筹学学报（中英文） ›› 2025, Vol. 29 ›› Issue (3): 93-123.doi: 10.15960/j.cnki.issn.1007-6093.2025.03.005

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

• 第九届中国运筹学会科学技术奖获奖者专辑 • 上一篇下一篇

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

石旭¹, 王玖鳞², 江如俊¹^,*(), 宋维正³

1. 复旦大学大数据学院, 上海 200433
2. 南开大学数学科学学院, 天津 300071
3. 复旦大学数学科学学院, 上海 200433

收稿日期:2025-02-22 出版日期:2025-09-15 发布日期:2025-09-09
通讯作者: 江如俊 E-mail:rjjiang@fudan.edu.cn
基金资助:
国家自然科学基金(12171100)

Solving Stackelberg prediction games using inexact hyper-gradient methods

Xu SHI¹, Jiulin WANG², Rujun JIANG¹^,*(), Weizheng SONG³

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

摘要：

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

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

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

中图分类号:

O225

石旭, 王玖鳞, 江如俊, 宋维正. 斯塔克尔伯格预测博弈问题的非精确超梯度法[J]. 运筹学学报（中英文）, 2025, 29(3): 93-123.

Xu SHI, Jiulin WANG, Rujun JIANG, Weizheng SONG. Solving Stackelberg prediction games using inexact hyper-gradient methods[J]. Operations Research Transactions, 2025, 29(3): 93-123.

图/表 8

Fig.1

Fig.2

Fig.3

Fig.4

Fig.C1

Fig.C2

Fig.C3

Fig.C4

参考文献 26

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. doi: 10.1016/j.eswa.2015.09.047
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. doi: 10.1007/BF01586088
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. doi: 10.1137/S1052623497322735
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. doi: 10.1137/17M1145914
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. doi: 10.1214/aoms/1177729893
25	NesterovY.Lectures on Convex Optimization[M].Switzerland:Springer,2018.
26	JorgeN,StephenW J.Numerical Optimization[M].Heidelberg:Springer,2006.

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

Solving Stackelberg prediction games using inexact hyper-gradient methods

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 26

相关文章 1

编辑推荐

Metrics

本文评价