Convergence Analysis of Gradient-Based Learning with Non-Uniform Learning Rates in Non-Cooperative Multi-Agent Settings
Considering a class of gradient-based multi-agent learning algorithms in non-cooperative settings, we provide local convergence guarantees to a neighborhood of a stable local Nash equilibrium. In particular, we consider continuous games where agents learn in (i) deterministic settings with oracle ac...
I tiakina i:
| Ngā kaituhi matua: | , , , |
|---|---|
| Hōputu: | Tuhinga |
| I whakaputaina: |
2019
|
| Ngā marau: | |
| Urunga tuihono: | https://arxiv.org/abs/1906.00731 http://arxiv.org/abs/1906.00731 |
| Ngā Tūtohu: |
Kāore He Tūtohu, Me noho koe te mea tuatahi ki te tūtohu i tēnei pūkete!
|
| _version_ | 1879176118501638144 |
|---|---|
| author | Chasnov, Benjamin Ratliff, Lillian J. Mazumdar, Eric Burden, Samuel A. |
| author_browse | Burden, Samuel A. Chasnov, Benjamin Mazumdar, Eric Ratliff, Lillian J. |
| author_facet | Chasnov, Benjamin Ratliff, Lillian J. Mazumdar, Eric Burden, Samuel A. |
| author_sort | Chasnov, Benjamin |
| building | arXiv |
| collection | Acceso abierto |
| description | Considering a class of gradient-based multi-agent learning algorithms in non-cooperative settings, we provide local convergence guarantees to a neighborhood of a stable local Nash equilibrium. In particular, we consider continuous games where agents learn in (i) deterministic settings with oracle access to their gradient and (ii) stochastic settings with an unbiased estimator of their gradient. Utilizing the minimum and maximum singular values of the game Jacobian, we provide finite-time convergence guarantees in the deterministic case. On the other hand, in the stochastic case, we provide concentration bounds guaranteeing that with high probability agents will converge to a neighborhood of a stable local Nash equilibrium in finite time. Different than other works in this vein, we also study the effects of non-uniform learning rates on the learning dynamics and convergence rates. We find that much like preconditioning in optimization, non-uniform learning rates cause a distortion in the vector field which can, in turn, change the rate of convergence and the shape of the region of attraction. The analysis is supported by numerical examples that illustrate different aspects of the theory. We conclude with discussion of the results and open questions. |
| first_indexed | 2026-10-16T00:39:49Z |
| format | Article |
| fullrecord | <oai_dc:dc xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ https://www.openarchives.org/OAI/2.0/oai_dc.xsd"><identifier>arxiv-1906.00731</identifier><datestamp>2024-09-23</datestamp>
<dc:title>Convergence Analysis of Gradient-Based Learning with Non-Uniform Learning Rates in Non-Cooperative Multi-Agent Settings</dc:title>
<dc:creator>Chasnov, Benjamin</dc:creator>
<dc:creator>Ratliff, Lillian J.</dc:creator>
<dc:creator>Mazumdar, Eric</dc:creator>
<dc:creator>Burden, Samuel A.</dc:creator>
<dc:subject>Optimization and Control</dc:subject>
<dc:subject>Computer Science and Game Theory</dc:subject>
<dc:subject>Machine Learning</dc:subject>
<dc:subject>Systems and Control</dc:subject>
<dc:description>Considering a class of gradient-based multi-agent learning algorithms in non-cooperative settings, we provide local convergence guarantees to a neighborhood of a stable local Nash equilibrium. In particular, we consider continuous games where agents learn in (i) deterministic settings with oracle access to their gradient and (ii) stochastic settings with an unbiased estimator of their gradient. Utilizing the minimum and maximum singular values of the game Jacobian, we provide finite-time convergence guarantees in the deterministic case. On the other hand, in the stochastic case, we provide concentration bounds guaranteeing that with high probability agents will converge to a neighborhood of a stable local Nash equilibrium in finite time. Different than other works in this vein, we also study the effects of non-uniform learning rates on the learning dynamics and convergence rates. We find that much like preconditioning in optimization, non-uniform learning rates cause a distortion in the vector field which can, in turn, change the rate of convergence and the shape of the region of attraction. The analysis is supported by numerical examples that illustrate different aspects of the theory. We conclude with discussion of the results and open questions. </dc:description>
<dc:date>2019-05-30</dc:date>
<dc:type>text</dc:type>
<dc:identifier>https://arxiv.org/abs/1906.00731</dc:identifier>
<dc:identifier>http://arxiv.org/abs/1906.00731</dc:identifier>
</oai_dc:dc> |
| id | arxiv-1906.00731 |
| institution | arXiv |
| last_indexed | 2026-10-16T00:39:49Z |
| publishDate | 2019 |
| publishDateRange | 2019 |
| publishDateSort | 2019 |
| record_format | oai_dc |
| spelling | arxiv-1906.007312024-09-23 Convergence Analysis of Gradient-Based Learning with Non-Uniform Learning Rates in Non-Cooperative Multi-Agent Settings Chasnov, Benjamin Ratliff, Lillian J. Mazumdar, Eric Burden, Samuel A. Optimization and Control Computer Science and Game Theory Machine Learning Systems and Control Considering a class of gradient-based multi-agent learning algorithms in non-cooperative settings, we provide local convergence guarantees to a neighborhood of a stable local Nash equilibrium. In particular, we consider continuous games where agents learn in (i) deterministic settings with oracle access to their gradient and (ii) stochastic settings with an unbiased estimator of their gradient. Utilizing the minimum and maximum singular values of the game Jacobian, we provide finite-time convergence guarantees in the deterministic case. On the other hand, in the stochastic case, we provide concentration bounds guaranteeing that with high probability agents will converge to a neighborhood of a stable local Nash equilibrium in finite time. Different than other works in this vein, we also study the effects of non-uniform learning rates on the learning dynamics and convergence rates. We find that much like preconditioning in optimization, non-uniform learning rates cause a distortion in the vector field which can, in turn, change the rate of convergence and the shape of the region of attraction. The analysis is supported by numerical examples that illustrate different aspects of the theory. We conclude with discussion of the results and open questions. 2019-05-30 text https://arxiv.org/abs/1906.00731 http://arxiv.org/abs/1906.00731 |
| spellingShingle | Optimization and Control Computer Science and Game Theory Machine Learning Systems and Control Chasnov, Benjamin Ratliff, Lillian J. Mazumdar, Eric Burden, Samuel A. Convergence Analysis of Gradient-Based Learning with Non-Uniform Learning Rates in Non-Cooperative Multi-Agent Settings |
| title | Convergence Analysis of Gradient-Based Learning with Non-Uniform Learning Rates in Non-Cooperative Multi-Agent Settings |
| title_full | Convergence Analysis of Gradient-Based Learning with Non-Uniform Learning Rates in Non-Cooperative Multi-Agent Settings |
| title_fullStr | Convergence Analysis of Gradient-Based Learning with Non-Uniform Learning Rates in Non-Cooperative Multi-Agent Settings |
| title_full_unstemmed | Convergence Analysis of Gradient-Based Learning with Non-Uniform Learning Rates in Non-Cooperative Multi-Agent Settings |
| title_short | Convergence Analysis of Gradient-Based Learning with Non-Uniform Learning Rates in Non-Cooperative Multi-Agent Settings |
| title_sort | convergence analysis of gradient based learning with non uniform learning rates in non cooperative multi agent settings |
| topic | Optimization and Control Computer Science and Game Theory Machine Learning Systems and Control |
| url | https://arxiv.org/abs/1906.00731 http://arxiv.org/abs/1906.00731 |
| work_keys_str_mv | AT chasnovbenjamin convergenceanalysisofgradientbasedlearningwithnonuniformlearningratesinnoncooperativemultiagentsettings AT ratlifflillianj convergenceanalysisofgradientbasedlearningwithnonuniformlearningratesinnoncooperativemultiagentsettings AT mazumdareric convergenceanalysisofgradientbasedlearningwithnonuniformlearningratesinnoncooperativemultiagentsettings AT burdensamuela convergenceanalysisofgradientbasedlearningwithnonuniformlearningratesinnoncooperativemultiagentsettings |