Results 31 - 40 of 24254
Eldan’s stochastic localization is a probabilistic construction that has proved instrumental to the analysis of diffusion models, and more generally, modern breakthroughs in high-dimensional geometry and the design of sampling algorithms. Motivated by sampling under non-Euclidean geometries and the mirror descent algorithm in optimization, we develop a functional generalization of Eldan's process that replaces Gaussian regularization with regularization by any positive integer multiple of a log-Laplace transform. This talk introduces the process, its basic properties and analysis, and outlines applications and open questions.
We study \emph{learning-to-sample} -- a basic algorithmic task underlying generative modeling -- for Ising models, a standard testbed for algorithmic ideas in both theoretical computer science and machine learning. Given i.i.d. samples of an unknown target distribution, the goal of learning-to-sample is to learn a computationally efficient generation procedure that produces new samples following approximately the same distribution. While this task is related to classical problems such as parameter learning and sampling given the model parameters, it is fundamentally distinct from both. We show that for Ising models, learning- to-sample undergoes a computational phase transition at the spectral threshold \lambda_{\max}(J)-\lambda_{\min}(J)=1 where Jis the interaction matrix. Specifically, we show that Ising models with \lambda_{\max}(J)-\lambda_{\min}(J)<1, admit a simple and efficient learning-to-sample algorithm: we run the classical Glauber dynamics initialized from the empirical distribution, using transition probabilities learned from the provided samples. In contrast, we show that when \lambda_{\max}(J)-\lambda_{\min}(J)>1, learning-to-sample is cryptographically hard. We construct a family of Ising models of constantly bounded-width which lie just beyond the spectral threshold \lambda_{\max}(J)-\lambda_{\min}(J)=1, and show that learning-to-sample for this family is computationally hard under standard cryptographic assumptions, even when the learner is given both polynomially many i.i.d. samples from the model and explicit access to its parameters.Together with prior results on parameter learning for bounded-width Ising models [KM17,WSD19,VML20], this shows that learning-to-sample can be more difficult than parameter learning. Finally, we show that any efficient learner for these hard instances exhibits a natural memorization-hallucination dichotomy: the learner must either output configurations that, after a simple transformation, match the (transformed) training data or place substantial mass on configurations of negligible probability under the target distribution.
Based on joint work with Frederic Koehler, Holden Lee and Andrej Risteski.
Nalini Anantharaman's research focuses on the geometric description of wave propagation. It combines dynamical systems theory, partial differential equations, symplectic and Riemannian geometry, and probability theory. In particular, the aim is to...
We consider the problem of algorithmically sampling from the Gibbs measure of a mean field spin glass, a prototypical model of a "disordered" probability measure. We prove that two algorithms succeed at temperatures above a ''stochastic localization threshold'' temperature.
1) Our first result shows that a denoising diffusions-based algorithm samples from the Gibbs measure. This improves the guarantee of this algorithm over previous work, from vanishing Wasserstein to total variation error.
2) Our second result shows that simulated annealing of Langevin dynamics also succeeds, and is proved by a new local-to-global principle for analyzing simulated annealing. This is the first guarantee for a Markov chain in this problem beyond the ''uniqueness threshold,'' where the Langevin dynamics mix slowly from a worst-case initialization.
For the pure p-spin models, the temperature we achieve is within an absolute (p-independent) constant of the ''shattering transition,'' which is the conjectured computational threshold of this problem. Based on joint works with Andrea Montanari, Huy Tuan Pham, Sidhanth Mohanty, Amit Rajaraman, and David X. Wu.
Research used to hold a sacred place in human society. As we are all seeing firsthand, research is being automated by machines at a rapid pace. I will share some recent experiences and discuss what will remain valuable, what we should do differently, and what research will look like. I don't know the answers, so this will be more of a discussion.
Estimating the ground-state energy of quantum many-body systems is a leading application of quantum computing. For general Hamiltonians, however, the problem is QMA-complete and is therefore unlikely to admit an efficient quantum algorithm. This motivates the search for natural classes of Hamiltonians whose ground-energy problem lies in BQP but is not known to lie in BPP.
In this talk, we identify quantum impurity Hamiltonians as one such class. These Hamiltonians are central to dynamical mean-field theory (DMFT), widely regarded as a gold-standard framework for studying strongly interacting quantum systems. Specifically, by explicitly constructing a guiding state, we give a polynomial-time quantum algorithm that estimates the ground-state energy of quantum impurity Hamiltonians to any inverse polynomial precision. Previously, the best unconditional upper bounds were a quasi-polynomial-time classical algorithm and containment of the corresponding decision problem in QCMA [Bravyi&Gosset arxiv:1609.00735].
Pseudoentangled states are quantum states whose entanglement structure is computationally hard to determine. In particular, given copies of such states, or in some cases even the circuits preparing them, no polynomial-time quantum algorithm can estimate their entanglement entropy across a specified cut. In this talk, I'll discuss a recent result showing that pseudoentangled states can be constructed by 2D-local constant-depth circuits. This gives a strong separation with respect to pseudoerandom states, which cannot be constructed from local constant-depth circuits, and strengthens previous results on the hardness of learning the entanglement structure of local Hamiltonian ground-states.
I will also discuss the backstory for this result, in particular how I used AI tools in order to improve upon my original construction and write the paper.
Based on: https://arxiv.org/abs/2605.31448