DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.70

On Sampling from Ising Models with Spectral Constraints

Authors: Andreas Galanis, Alkis Kalavasis, and Anthimos Vardis Kandiros

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract

We consider the problem of sampling from the Ising model when the underlying interaction matrix has eigenvalues lying within an interval of length γ. Recent work in this setting has shown various algorithmic results that apply roughly when γ < 1, notably with nearly-linear running times based on the classical Glauber dynamics. However, the optimality of the range of γ was not clear since previous inapproximability results developed for the antiferromagnetic case (where the matrix has entries ≤ 0) apply only for γ > 2. To this end, Kunisky (SODA'24) recently provided evidence that the problem becomes hard already when γ > 1 based on the low-degree hardness for an inference problem on random matrices. Based on this, he conjectured that sampling from the Ising model in the same range of γ is NP-hard. Here we confirm this conjecture, complementing in particular the known algorithmic results by showing NP-hardness results for approximately counting and sampling when γ > 1, with strong inapproximability guarantees; we also obtain a more refined hardness result for matrices where only a constant number of entries per row are allowed to be non-zero. The main observation in our reductions is that, for γ > 1, Glauber dynamics mixes slowly when the interactions are all positive (ferromagnetic) for the complete and random regular graphs, due to a bimodality in the underlying distribution. While ferromagnetic interactions typically preclude NP-hardness results, here we work around this by introducing in an appropriate way mild antiferromagnetism, keeping the spectrum roughly within the same range. This allows us to exploit the bimodality of the aforementioned graphs and show the target NP-hardness by adapting suitably previous inapproximability techniques developed for antiferromagnetic systems.

Cite as

Andreas Galanis, Alkis Kalavasis, and Anthimos Vardis Kandiros. On Sampling from Ising Models with Spectral Constraints. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{galanis_et_al:LIPIcs.APPROX/RANDOM.2024.70,
  author =	{Galanis, Andreas and Kalavasis, Alkis and Kandiros, Anthimos Vardis},
  title =	{{On Sampling from Ising Models with Spectral Constraints}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{70:1--70:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.70},
  URN =		{urn:nbn:de:0030-drops-210638},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.70},
  annote =	{Keywords: Ising model, spectral constraints, Glauber dynamics, mean-field Ising, random regular graphs}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2024.5

On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games

Authors: Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm, and Manolis Zampetakis

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract

Characterizing the performance of no-regret dynamics in multi-player games is a foundational problem at the interface of online learning and game theory. Recent results have revealed that when all players adopt specific learning algorithms, it is possible to improve exponentially over what is predicted by the overly pessimistic no-regret framework in the traditional adversarial regime, thereby leading to faster convergence to the set of coarse correlated equilibria (CCE) - a standard game-theoretic equilibrium concept. Yet, despite considerable recent progress, the fundamental complexity barriers for learning in normal- and extensive-form games are poorly understood. In this paper, we make a step towards closing this gap by first showing that - barring major complexity breakthroughs - any polynomial-time learning algorithms in extensive-form games need at least 2^{log^{1/2 - o(1)} |𝒯|} iterations for the average regret to reach below even an absolute constant, where |𝒯| is the number of nodes in the game. This establishes a superpolynomial separation between no-regret learning in normal- and extensive-form games, as in the former class a logarithmic number of iterations suffices to achieve constant average regret. Furthermore, our results imply that algorithms such as multiplicative weights update, as well as its optimistic counterpart, require at least 2^{(log log m)^{1/2 - o(1)}} iterations to attain an O(1)-CCE in m-action normal-form games under any parameterization. These are the first non-trivial - and dimension-dependent - lower bounds in that setting for the most well-studied algorithms in the literature. From a technical standpoint, we follow a beautiful connection recently made by Foster, Golowich, and Kakade (ICML '23) between sparse CCE and Nash equilibria in the context of Markov games. Consequently, our lower bounds rule out polynomial-time algorithms well beyond the traditional online learning framework, capturing techniques commonly used for accelerating centralized equilibrium computation.

Cite as

Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm, and Manolis Zampetakis. On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 5:1-5:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{anagnostides_et_al:LIPIcs.ITCS.2024.5,
  author =	{Anagnostides, Ioannis and Kalavasis, Alkis and Sandholm, Tuomas and Zampetakis, Manolis},
  title =	{{On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{5:1--5:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.5},
  URN =		{urn:nbn:de:0030-drops-195334},
  doi =		{10.4230/LIPIcs.ITCS.2024.5},
  annote =	{Keywords: No-regret learning, extensive-form games, multiplicative weights update, optimism, lower bounds}
}

Search Results

Documents authored by Kalavasis, Alkis

On Sampling from Ising Models with Spectral Constraints

Abstract

Cite as

On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games

Abstract

Cite as

Thanks for your feedback!

Could not send message