Results 521 - 530 of 24760

Diffusion models rely on reversing a forward diffusion process modeled by a stochastic differential equation, a non-equilibrium process at its core. In this talk, I will outline an alternative formulation that relies solely on Langevin MCMC at a fixed noise level. In this framework, the effective noise is reduced through the accumulation of noisy measurements. Furthermore, by choosing an appropriate noise level, one can guarantee that the measurement accumulation remains within the class of log-concave sampling problems. Time permitting, I will discuss new extensions of Langevin MCMC for discrete data that are related to discrete diffusion models.

We consider classifying labelled data in the interpolation regime where there exist linear classifiers (with possibly negative margin) correctly classifying all points in the dataset. Under two idealized data-generating distributions, we establish a large deviation principle on the event that a point chosen uniformly at random from the set of interpolators achieves a given generalization error. This allows us to describe the proportion of interpolators having any desired performance and establish a concentration result regarding the most typical performance. We remark that this typical performance is inferior to that of ERM by gradient descent, indicating that most interpolators are ‘bad’. Sampling such typical interpolators is an interesting open problem.

This is based on joint work with August Chen.

Modern generative AI is often viewed through two dominant paradigms: autoregressive models, which underpin much of language modeling, and diffusion models, which have set the standard for high-quality image and video synthesis. These paradigms are usually treated as fundamentally different: autoregressive models are associated with compression and sequential computation, while diffusion models are associated with perceptual sample quality and parallel generation.

In this talk, I will argue that this divide is less fundamental than it may appear. I will use masked diffusion models (MDMs) as a lens: this class of discrete diffusion models is theoretically equivalent to random-order autoregressive models. From this perspective, many empirical differences between autoregression and diffusion, such as parallelism and perceptual quality, arise not from a fundamental distinction between the model classes themselves, but from details of model specification and training techniques. For example, I will present evidence that the loss reweighting technique from diffusion, when applied to any-order MDM/AR models, can yield perceptual sample quality comparable to strong continuous diffusion models.

Next, I will talk about moving beyond both (fixed-order) autoregression and (random-order) diffusion to find new powerful ways of generation. Specifically, I will focus on models that adaptively determine their generation order based on partial context. I will highlight the important role of insertion in flexible generation and planning, and a principled framework we established for scalable maximum likelihood learning of insertion-based generative models.

We give a polynomial-time algorithm to sample from the Gibbs measure of the Sherrington-Kirkpatrick (SK) model--a key model arising from statistical physics--with negligible total-variation distance up to inverse temperature β<1/2. The algorithm is based on algorithmic stochastic localization (a.k.a. a diffusion model) and Jarzynski's equality with rejection sampling. The proof is based on the potential Hessian ascent framework previously developed for optimization, combining a covariance estimate of tilted Gibbs distribution via Gaussian integration by parts, overlap concentration, and precise cavity estimates; a free probability argument controlling the diagonal sub-algebra of the Hessian; and functional inequalities for the localized distributions. Prior work obtained TV distance error guarantees only up to β ≈ 0.295, while results covering the entire replica-symmetric regime β < 1 gave guarantees only in non-trivial Wasserstein distance. We then show how to use regularity properties of the diffusion process in order to conclude a weak Poincare inequality for the SK model and simplify the algorithm. Our work shows how the theory of diffusion models can be used to solve challenging problems about sampling. Joint work with Ewan Davies, Juspreet Singh Sandhu, and Jonathan Shi.

"Modern AI systems are increasingly built by placing trained models inside larger computational loops. Inference-time algorithms are a basic instance of this idea: they use one or more trained models at test time to incorporate new information, exploit pretrained models as priors, and trade computational effort for accuracy, sample quality, or control. Examples include generator-verifier search for reasoning, diffusion models for solving inverse problems, and reward-guided generation. Theoretically, this revisits a classical question from optimization and theoretical computer science: what can be done with access to an oracle? Here, however, the oracles are new and non-standard: they model the capabilities of large pretrained models, making them powerful, but also imperfect because they are learned. This combination leads to new questions about algorithm design and error propagation.

This talk studies two central aspects of this paradigm: computational efficiency and error propagation. The first vignette considers generator-verifier systems, and shows how stochastic backtracking can trade additional computation for accuracy, giving a principled version of test-time scaling even with imperfect learned oracles. The second vignette studies diffusion steering: when can we efficiently bias a pretrained diffusion model toward higher-reward samples while staying close to the original model? We show that tractability depends strongly on both the reward structure and the alignment objective, and that simple primitives—such as sampling from linear tilts—can be surprisingly useful for handling richer reward classes."

Let μ(dx) ∝ e^(−U(x)) dx on ℝ^d, where U is m-strongly convex and L-smooth, and denote by κ = L/m the condition number. We consider windowed thinning, an exact simulation method for the bouncy particle sampler and the coordinate Zigzag process. The method divides a trajectory into deterministic windows and uses a gradient evaluation at the beginning of each window to construct a tractable local envelope for the event rate. Combining this construction with quantitative mixing estimates and finite-time bounds on the expected numbers of bounces and flips yields query complexity guarantees from a Gaussian cold start.

For total-variation error ε, the expected query counts are O(κ^(1/2) · d · (d log κ + log(1/ε))) gradient queries for the bouncy particle sampler and O(κ · d^(1/4) · (d log κ + log(1/ε))) full-gradient equivalents for Zigzag, where d coordinate-partial queries count as one equivalent.