The power of an adversary in Glauber dynamics

Byron Chin, Ankur Moitra, Elchanan Mossel, Colin Sandon
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1102-1124, 2024.

Abstract

Glauber dynamics are a natural model of dynamics of dependent systems. While originally introduced in statistical physics, they have found important applications in the study of social networks, computer vision and other domains. In this work, we introduce a model of corrupted Glauber dynamics whereby instead of updating according to the prescribed conditional probabilities, some of the vertices and their updates are controlled by an adversary. We study the effect of such corruptions on global features of the system. Among the questions we study are: How many nodes need to be controlled in order to change the average statistics of the system in polynomial time? And how many nodes are needed to obstruct approximate convergence of the dynamics? Given a specific budget, how can the adversary choose nodes to control to maximize the overall effect? Our results can be viewed as studying the robustness of classical sampling methods and are thus related to robust inference. The proofs connect to classical theory of Glauber dynamics from statistical physics.

Cite this Paper

BibTeX
@InProceedings{pmlr-v247-chin24a, title = {The power of an adversary in Glauber dynamics}, author = {Chin, Byron and Moitra, Ankur and Mossel, Elchanan and Sandon, Colin}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {1102--1124}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/chin24a/chin24a.pdf}, url = {https://proceedings.mlr.press/v247/chin24a.html}, abstract = {Glauber dynamics are a natural model of dynamics of dependent systems. While originally introduced in statistical physics, they have found important applications in the study of social networks, computer vision and other domains. In this work, we introduce a model of corrupted Glauber dynamics whereby instead of updating according to the prescribed conditional probabilities, some of the vertices and their updates are controlled by an adversary. We study the effect of such corruptions on global features of the system. Among the questions we study are: How many nodes need to be controlled in order to change the average statistics of the system in polynomial time? And how many nodes are needed to obstruct approximate convergence of the dynamics? Given a specific budget, how can the adversary choose nodes to control to maximize the overall effect? Our results can be viewed as studying the robustness of classical sampling methods and are thus related to robust inference. The proofs connect to classical theory of Glauber dynamics from statistical physics. } }
Endnote
%0 Conference Paper %T The power of an adversary in Glauber dynamics %A Byron Chin %A Ankur Moitra %A Elchanan Mossel %A Colin Sandon %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-chin24a %I PMLR %P 1102--1124 %U https://proceedings.mlr.press/v247/chin24a.html %V 247 %X Glauber dynamics are a natural model of dynamics of dependent systems. While originally introduced in statistical physics, they have found important applications in the study of social networks, computer vision and other domains. In this work, we introduce a model of corrupted Glauber dynamics whereby instead of updating according to the prescribed conditional probabilities, some of the vertices and their updates are controlled by an adversary. We study the effect of such corruptions on global features of the system. Among the questions we study are: How many nodes need to be controlled in order to change the average statistics of the system in polynomial time? And how many nodes are needed to obstruct approximate convergence of the dynamics? Given a specific budget, how can the adversary choose nodes to control to maximize the overall effect? Our results can be viewed as studying the robustness of classical sampling methods and are thus related to robust inference. The proofs connect to classical theory of Glauber dynamics from statistical physics.
APA
Chin, B., Moitra, A., Mossel, E. & Sandon, C.. (2024). The power of an adversary in Glauber dynamics. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:1102-1124 Available from https://proceedings.mlr.press/v247/chin24a.html.

Related Material