Results 511 - 520 of 24757

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. 

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.

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.

Recent years have seen tremendous progress in AI-driven robotics. These advancements have been attributed not only to increased data and improved hardware, but also to fundamental algorithmic innovations in the way robots are trained.

In this talk, we focus on one specific innovation: the introduction of ""generative control policies"" (GCPs), such as diffusion- and flow-based generative models as parameterizations of robot policies (policies being the mapping from observations to actions). The prevailing wisdom has been that GCPs enable robot policies to fit complex, often-multimodal action distributions that arise from diversely collected data. Through careful experimental and theoretical analysis, we suggest that GCPs routinely do not capture multi-modality in action data. Rather, we demonstrate that the increased performance afforded by GCPs are mediated through specific ""on-manifold"" inductive biases afforded by iterative computation and the incorporation of noise at training. In sum, our findings suggest that flow-based generative modeling offers algorithmic benefits unrelated to distribution matching, and point to the possibility of novel learning formalisms that achieve the same by more direct means.

I'll present how we can use diffusion models and closely related energy-based models to solve different reasoning tasks. I'll talk about how these models naturally enable us to implement search at inference time, and how these models can be composed together to solve more complex reasoning questions. Finally, I'll empirically illustrate how such a reasoning system allows us to solve a number of complex symbolic reasoning and decision-making/planning tasks.

In this talk, I'll discuss how diffusion and flow models transformed continuous-action policies in RL and robotic control. While in principle learning-based control methods (imitation learning and RL) are largely agnostic to the particular representation used for the action distribution, in practice diffusion and flow models have significantly improved the performance of learned policies across various learning-based control domains. By modeling complex distributions over high-dimensional spaces, these models made it possible to represent large "action chunks" (sequences of actions), which greatly improved imitation learning performance and, most recently, the performance of offline RL and offline-to-online RL methods. In this talk, I'll discuss algorithms that use diffusion and flow for RL and IL, as well as some of the large-scale models built on these principles.