We propose a new distributed algorithm that combines heavy-ball momentum and a consensus-based gradient method to find a Nash equilibrium (NE) in a class of non-cooperative convex games with unconstrained action sets. In this approach, each agent in the game has access to its own smooth local cost function and can exchange information with its neighbors over a communication network. The proposed method is designed to work on a general sequence of time-varying directed graphs and allows for non-identical step-sizes and momentum parameters. Our work is the first to incorporate heavy-ball momentum in the context of non-cooperative games, and we provide a rigorous proof of its geometric convergence to the NE under the common assumptions of strong convexity and Lipschitz continuity of the agents' cost functions. Moreover, we establish explicit bounds for the step-size values and momentum parameters based on the characteristics of the cost functions, mixing matrices, and graph connectivity structures. To showcase the efficacy of our proposed method, we perform numerical simulations on a Nash-Cournot game to demonstrate its accelerated convergence compared to existing methods.


翻译:我们提出了一种新的分布式算法,它结合了Heavy-Ball动量和基于共识的梯度方法,用于在一类具有非约束动作集的非合作凸博弈中寻找纳什均衡(NE)。在这种方法中,游戏中的每个智能体都可以访问自己的平滑局部成本函数,并可以在通信网络上与其邻居交换信息。所提出的方法是为了在一般的时变有向图上工作,并允许不同的步长和动量参数。我们的工作是首次将Heavy-Ball动量纳入非合作游戏的背景中,并在强凸性和Lipschitz连续性的普遍假设下证明了其几何收敛于NE。此外,我们根据成本函数,混合矩阵和图连接结构的特征为步长值和动量参数建立了显式上限。为了展示我们提出的方法的功效,我们在Nash-Cournot博弈上进行了数值模拟,以展示其相对于现有方法的加速收敛性。

0
下载
关闭预览

相关内容

动量方法 (Polyak, 1964) 旨在加速学习,特别是处理高曲率、小但一致的梯度,或是带噪声的梯度。 动量算法积累了之前梯度指数级衰减的移动平均,并且继续沿该方向移动。
机器学习组合优化
专知会员服务
108+阅读 · 2021年2月16日
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
【泡泡一分钟】基于运动估计的激光雷达和相机标定方法
泡泡机器人SLAM
25+阅读 · 2019年1月17日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
【泡泡一分钟】动态环境下稳健的单目SLAM
泡泡机器人SLAM
13+阅读 · 2018年3月22日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
2+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
Arxiv
19+阅读 · 2020年7月13日
VIP会员
相关VIP内容
机器学习组合优化
专知会员服务
108+阅读 · 2021年2月16日
相关资讯
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
【泡泡一分钟】基于运动估计的激光雷达和相机标定方法
泡泡机器人SLAM
25+阅读 · 2019年1月17日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
【泡泡一分钟】动态环境下稳健的单目SLAM
泡泡机器人SLAM
13+阅读 · 2018年3月22日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
2+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员