2 Search Results for "Lauritzen, Steffen"

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/DagSemProc.09401.1
09401 Abstracts Collection – Machine learning approaches to statistical dependences and causality

Authors: Dominik Janzing, Steffen Lauritzen, and Bernhard Schölkopf

Published in: Dagstuhl Seminar Proceedings, Volume 9401, Machine learning approaches to statistical dependences and causality (2010)

Abstract
From 27.09.2009 to 02.10.2009, the Dagstuhl Seminar 09401 ``Machine learning approaches to statistical dependences and causality'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Dominik Janzing, Steffen Lauritzen, and Bernhard Schölkopf. 09401 Abstracts Collection – Machine learning approaches to statistical dependences and causality. In Machine learning approaches to statistical dependences and causality. Dagstuhl Seminar Proceedings, Volume 9401, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{janzing_et_al:DagSemProc.09401.1,
  author =	{Janzing, Dominik and Lauritzen, Steffen and Sch\"{o}lkopf, Bernhard},
  title =	{{09401 Abstracts Collection – Machine learning approaches to statistical dependences and causality }},
  booktitle =	{Machine learning approaches to statistical dependences and causality},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9401},
  editor =	{Dominik Janzing and Steffen Lauritzen and Bernhard Sch\"{o}lkopf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09401.1},
  URN =		{urn:nbn:de:0030-drops-23636},
  doi =		{10.4230/DagSemProc.09401.1},
  annote =	{Keywords: Machine learning, statistical dependences, causality}
}
  • Refine by Author
  • 1 Galanis, Andreas
  • 1 Janzing, Dominik
  • 1 Kalavasis, Alkis
  • 1 Kandiros, Anthimos Vardis
  • 1 Lauritzen, Steffen
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Generating random combinatorial structures
  • 1 Theory of computation → Problems, reductions and completeness
  • 1 Theory of computation → Random walks and Markov chains

  • Refine by Keyword
  • 1 Glauber dynamics
  • 1 Ising model
  • 1 Machine learning
  • 1 causality
  • 1 mean-field Ising
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2010
  • 1 2024

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact