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

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*, 宋维正³

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

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

Solving Stackelberg prediction games using inexact hyper-gradient methods

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

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 Published:2025-09-09

摘要/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.

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

参考文献

[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] Zhou Y, Kantarcioglu M, Xi B. 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 II, of the 20th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, 2016: 350-362.
[6] Wahab O A, Bentahar J, Otrok H, 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] Jeroslow R 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] Gould N I M, Lucidi S, Roma M, 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] Zhang L-H, Shen C. 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 37th 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] Conn A R, Gould N I M, Toint P L. Trust Region Methods [M]. Philadelphia: SIAM, 2000.
[24] Sherman J, Morrison W 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] Nesterov Y. Lectures on Convex Optimization [M]. Switzerland: Springer, 2018.
[26] Jorge N, Stephen W J. Numerical Optimization [M]. Heidelberg: Springer, 2006.

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

Solving Stackelberg prediction games using inexact hyper-gradient methods

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价