Buchumschlag

A computational phase transition for learning-to-sample from Ising models

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Risteski, Andrej, Vuong, Thuy-Duong
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Machine Learning Computational Complexity Data Structures and Algorithms Probability
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Efficiently learning and sampling multimodal distributions with data-based initialization
von: Koehler, Frederic, et al.
Veröffentlicht: (2024)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
von: Huang, Neng, et al.
Veröffentlicht: (2024)

Sparsifying Suprema of Gaussian Processes
von: De, Anindya, et al.
Veröffentlicht: (2024)

Detection of local geometry in random graphs: information-theoretic and computational limits
von: Bok, Jinho, et al.
Veröffentlicht: (2026)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
von: Dhawan, Abhishek, et al.
Veröffentlicht: (2024)

Low-degree phase transitions for detecting a planted clique in sublinear time
von: Mardia, Jay, et al.
Veröffentlicht: (2024)

The tractability landscape of diffusion alignment: regularization, rewards, and computational primitives
von: Moitra, Ankur, et al.
Veröffentlicht: (2026)

Tensor cumulants for statistical inference on invariant distributions
von: Kunisky, Dmitriy, et al.
Veröffentlicht: (2024)

Fit Like You Sample: Sample-Efficient Generalized Score Matching from Fast Mixing Diffusions
von: Qin, Yilong, et al.
Veröffentlicht: (2023)

Sharp Thresholds for the Overlap Gap Property: Ising $p$-Spin Glass and Random $k$-SAT
von: Kızıldağ, Eren C.
Veröffentlicht: (2023)

Steering diffusion models with quadratic rewards: a fine-grained analysis
von: Moitra, Ankur, et al.
Veröffentlicht: (2026)

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
von: Moka, Sarat, et al.
Veröffentlicht: (2026)

Random tensor isomorphism under orthogonal and unitary actions
von: Chizewer, Jeremy, et al.
Veröffentlicht: (2026)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
von: Li, Tiange, et al.
Veröffentlicht: (2026)

Samplability makes learning easier
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

Parallel Sampling via Autospeculation
von: Anari, Nima, et al.
Veröffentlicht: (2025)

Polynomial-time sampling despite disorder chaos
von: Ma, Eric, et al.
Veröffentlicht: (2025)

Fast decision tree learning solves hard coding-theoretic problems
von: Koch, Caleb, et al.
Veröffentlicht: (2024)

On approximating the $f$-divergence between two Ising models
von: Feng, Weiming, et al.
Veröffentlicht: (2025)

Trickle-Down in Localization Schemes and Applications
von: Anari, Nima, et al.
Veröffentlicht: (2024)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
von: Kunisky, Dmitriy, et al.
Veröffentlicht: (2024)

Some easy optimization problems have the overlap-gap property
von: Li, Shuangping, et al.
Veröffentlicht: (2024)

Entropic independence via sparse localization
von: Jain, Vishesh, et al.
Veröffentlicht: (2026)

Computational-Statistical Tradeoffs from NP-hardness
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

Hardness of Learning Boolean Functions from Label Proportions
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2024)

A Distributional-Lifting Theorem for PAC Learning
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

Fast parallel sampling under isoperimetry
von: Anari, Nima, et al.
Veröffentlicht: (2024)

Exact and Approximate Algorithms for Polytree Learning
von: Harviainen, Juha, et al.
Veröffentlicht: (2026)

Differentially Private Verification of Distribution Properties
von: Du, Elbert, et al.
Veröffentlicht: (2026)

Low-Degree Method Fails to Predict Robust Subspace Recovery
von: Jia, He, et al.
Veröffentlicht: (2026)

The Sample Complexity of Replicable Realizable PAC Learning
von: Larsen, Kasper Green, et al.
Veröffentlicht: (2026)

Active Learning for Decision Trees with Provable Guarantees
von: Moakhar, Arshia Soltani, et al.
Veröffentlicht: (2026)

On the Hardness of Approximation of the Fair k-Center Problem
von: Thejaswi, Suhas
Veröffentlicht: (2026)

Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
von: Allcock, Jonathan, et al.
Veröffentlicht: (2025)

Superconstant Inapproximability of Decision Tree Learning
von: Koch, Caleb, et al.
Veröffentlicht: (2024)

Efficient and Private Property Testing via Indistinguishability
von: Dwork, Cynthia, et al.
Veröffentlicht: (2025)

Adaptive and oblivious statistical adversaries are equivalent
von: Blanc, Guy, et al.
Veröffentlicht: (2024)

Private graphon estimation via sum-of-squares
von: Chen, Hongjie, et al.
Veröffentlicht: (2024)

Feature Selection and Junta Testing are Statistically Equivalent
von: Beretta, Lorenzo, et al.
Veröffentlicht: (2025)

Omnipredictors for Regression and the Approximate Rank of Convex Functions
von: Gopalan, Parikshit, et al.
Veröffentlicht: (2024)