CS Paper Radar

On the Optimisation Landscape of Overparameterised Weighted MMD

Tharrshann Jayan Logarajah, Jeremias Knoblauch, Louis Sharrock

cs.LG stat.MLmath.OC ·submitted 2026-10-14 09:24 UTC · v1

Abstract

We study the optimisation landscape of the maximum mean discrepancy (MMD) over weighted atomic measures. For the one-dimensional Gaussian kernel, we show that, for any compactly supported target distribution, sufficiently many particles ensure that every local minimum has arbitrarily small MMD. Moreover, any stationary point whose MMD remains bounded away from zero is unstable under an unweighted gradient flow over the particle locations. These results hold both when the weights are constrained to the simplex, and when they are unconstrained but optimised at each step. When the target is itself finitely supported, we further strengthen this result: beyond an explicit particle threshold, there are no spurious local minima, and every spurious stationary point is unstable. To our knowledge, these are the first finite-particle overparameterisation guarantees of their kind for weighted MMD optimisation.

Closest papers

Nearest neighbours by meaning across the whole index.

Muon meets Tamed Langevin: Momentum Preconditioning beyond Convex and gradient-Lipschitz Potentials

cs.LG math.OCmath.PRstat.ML ·2026-10-01 ·Nikolaos Makras, Sotirios Sabanis
theory similarity 0.64
Abstract · 26pages

We consider the problem of sampling from Gibbs distributions on matrix spaces whose potential energies are neither convex nor globally gradient-Lipschitz. We introduce a family of non-quadratic kinetic energies that lead to a new underdamped Langevin system with momentum preconditioning, in which the gradient of the kinetic energy acts as a smooth spectral taming of the momentum. We prove that, under these relaxed assumptions on the potential, the resulting dynamics leaves the target Gibbs measure invariant, and we establish exponential convergence to equilibrium in a weighted total variation distance. Finally, we show that the corresponding Euler-Maruyama discretization admits moment bounds that are uniform in time, without any modification of the potential gradient, which ensures the stability of the resulting sampling algorithm.

0.43

Diffusion Removes Langevin's Conditioning Dependence: A Sharp Gaussian Analysis

cs.LG stat.ML ·2026-10-08 ·Adam Perbost, Francis Bach, Pierre Marion
hot direction similarity 0.60
Abstract · 49 pages (10 main + appendix), 3 figures

Despite their empirical success, why diffusion models overcome the bottlenecks of classical score-based samplers remains unclear. In this work, we leverage Gaussian distributions to isolate this phenomenon. We establish 2-Wasserstein convergence bounds for optimized hyperparameters, showing that diffusion processes achieve a sampling error of $O(\sqrt{dλ_{\max}}\log N/N)$, where $d$ is the dimension, $N$ the number of sampling steps, and $λ_{\max}$ the largest eigenvalue of the target covariance matrix. Unadjusted and underdamped Langevin dynamics suffer from an additional $\sqrtκ$ factor, where $κ$ is the condition number. These rates follow from spectral bounds which are sharp: we confirm them via matching first-order asymptotics as $N\rightarrow\infty$. Our analysis provides a rigorous characterization, in the Gaussian setting, of how time-dependent score trajectories remove condition-number dependence during sampling. By contrast, in the learning phase, we show that estimating the unnoised score by gradient descent leads to essentially the same estimator as estimating a noisy score, which suggests that the benefits of noising do not come from the learning phase.

0.35

A Jump-Modified Wasserstein Gradient Flow for Maximum Mean Discrepancy with Energy Kernels

cs.LG math.APmath.PRstat.ML ·2026-10-21 ·Ansh Desai, Jason Liu, Srujan Roplekar, Matthew Rosenzweig
theory similarity 0.60
Abstract · 63 pages

We study a jump-modified Wasserstein gradient flow of the squared maximum mean discrepancy generated by the energy kernels $K(z)=-|z|^q$, $0<q<2$, in every dimension $d\ge2$ as well as the one-dimensional range $1\le q<2$. Under subcritical density and finite-moment assumptions, we prove global well-posedness. The added jumps transfer mass toward smaller values of the first variation and dissipate the same MMD energy as the transport term. Under our hypotheses on the target and jump rates, every Borel probability measure with finite MMD energy and zero jump dissipation is equal to the target. Combining this rigidity with compactness and a second-moment identity yields convergence to the target from finite-second-moment data, without additional uniform-in-time density or moment assumptions. We also construct a global collision-free particle process whose energy is nonincreasing along each path. A quantitative mean-field estimate applies to general initial empirical approximations, including deterministic configurations; propagation of chaos for exchangeable data and long-time target approximation follow as consequences.

0.19

Algorithmic threshold for high-dimensional projection pursuit I: general theory

cs.CC math.PRcond-mat.dis-nnmath-ph ·2026-08-29 ·Brice Huang, Mark Sellke, Nike Sun
highly cited similarity 0.59
Abstract · 295 pages. All ideas in this paper are human-generated, and all the writing was done by the human authors. AI was used in the writing of thi…

We study a null model of high-dimensional projection pursuit: we are given $M$ points sampled i.i.d. from a standard gaussian in $N$ dimensions, where $M,N\to\infty$ with $M/N\toα\in(0,\infty)$. Our goal is to characterize the possible empirical distributions of these points' projections along a data-dependent direction $x$, which ranges over either the sphere $S_N=\sqrt{N}\mathbb{S}^{N-1}$ or cube $Σ_N=\{-1,+1\}^N$. We consider this problem in an algorithmic setting, where $x$ must be the output of an algorithm with dimension-free Lipschitz dependence on the input; this class of algorithms includes general gradient-based methods such as Langevin dynamics and approximate message passing (AMP). Our main result exactly characterizes the set of empirical distributions attainable by this class in terms of a one-dimensional stochastic control problem. As a consequence of our main result, we obtain exact algorithmic thresholds for optimizing the Hamiltonian of a spherical or Ising perceptron model with general bounded continuous activation. For the spherical problem, independent work of Montanari and Zhou (2024) characterized the empirical distributions attainable by a related two-stage AMP algorithm, also in terms of stochastic control. Our proof of hardness builds on the branching overlap gap property introduced in earlier work by the first two authors. Our main innovation is to develop stochastic control theory within the branching OGP framework, significantly expanding the settings in which it locates an exact algorithmic threshold. Notably, our methods apply even though the non-algorithmic problem of characterizing all feasible projections remains a major outstanding challenge. For the matching algorithmic result, we construct a new incremental AMP algorithm that acts on a Brownian-bridge revelation of the gaussian disorder and simulates the same family of controlled SDEs.

0.59

Fine-Tuning Generative Models for Extreme Events via CVaR-Penalized Wasserstein Gradient Flows

cs.LG stat.ML ·2026-08-12 ·Thejani Gamage, Hyemin Gu, Zhizhen Zhang, Ziyu Chen, Markos A. Katsoulakis +1 more
similarity 0.58
Abstract

In many high-stakes domains, extreme events carry substantial consequences, yet learning the heavy-tailed distributions that govern them from finite samples remains challenging: the quantities of interest are driven by a few extreme observations, so the tail is under-sampled relative to its importance. Even generative models tailored for heavy tails capture the tail region inadequately in practice. We propose the Conditional Value-at-Risk (CVaR)-penalized Generative Particle Algorithm (CVaR-GPA), a tail-agnostic algorithm for fine-tuning generative models toward heavy-tailed targets, built as a time discretization of the Wasserstein gradient flow of the Lipschitz-regularized KL divergence penalized by a CVaR discrepancy term. Such a flow can be initialized from the output samples of the pre-trained model, which are then transported along the gradient descent of the loss functional, without requiring access to the pre-trained model's internal architecture. The Lipschitz-regularized KL divergence requires minimal assumptions on the target, while the CVaR penalty focuses the flow on the tail. The CVaR penalty depends on the target only through a scalar tail statistic, inducing a velocity field that remains active in the under-sampled tail region at a dimension-free estimation cost. The resulting velocity field, and hence the depth of the transport map, implicitly adapts to the target, without target-specific modifications. Across four targets, including two real-world, high-dimensional datasets (daily streamflow in the Ohio River basin ($d=64$) and the Fama-French portfolios ($d=25$) with tail indices ranging from $1.05$ to $3.34$), fine-tuning with CVaR-GPA reduces global and tail errors by geometric-mean factors of $14.0 \times$ and $9.8 \times$, respectively, across seven pre-trained models spanning GANs, diffusion models, and other generative flows, with a single set of hyperparameters.

0.34

Underdamped Anchored Langevin Dynamics

cs.LG math.PR ·2026-10-27 ·Qi Feng, Hoang M. Nguyen, Lingjiong Zhu
similarity 0.58
Abstract · 66 pages

Classical Langevin Monte Carlo algorithms, such as the unadjusted Langevin algorithm (ULA), are based on discretization schemes of the overdamped Langevin dynamics and are widely used for sampling in machine learning because they scale to high dimensions and large datasets. However, they require differentiable log-densities, and are less efficient for sampling heavy-tailed distributions. Although various approaches have been proposed in the literature for sampling non-differentiable and heavy-tailed targets, all of them are developed in the overdamped setting only. We propose a novel momentum-based underdamped anchored Langevin dynamics (UALD), and underdamped anchored Langevin Monte Carlo (UALMC) algorithm based on a discretization scheme of UALD. Our paper is the first to provide a kinetic (momentum-based) Langevin algorithm for non-differentiable and heavy-tailed targets that is free of asymptotic bias. The method replaces the original potential with a smooth reference potential and modifies the underdamped Langevin dynamics via multiplicative scaling in the drift term. We establish non-asymptotic guarantees in the 2-Wasserstein distance to the target distribution and show that the resulting iteration complexity has better dependence on dimension and accuracy level compared to overdamped-based anchored Langevin algorithms. We provide numerical experiments to illustrate the theory and practical performance of our proposed approach.

0.08

Penalized Nonreversible Langevin for Constrained Sampling

cs.LG stat.MLmath.PR ·2026-09-21 ·Pervez Ali, Weihao Dong, Xiaoyu Wang
similarity 0.58
Abstract · 68 pages, 8 figures

We propose penalized nonreversible Langevin algorithms for sampling from $π(x)\propto e^{-f(x)}\mathbf 1_{\mathcal C}(x)$, where $\mathcal C\subset\mathbb R^d$ is a compact convex set. The algorithms combine a squared distance penalty with constant or compatible state dependent skew symmetric perturbations that preserve the penalized Gibbs distribution. For smooth, possibly nonconvex $f$, we derive nonasymptotic total variation bounds for the full gradient algorithm under a log Sobolev inequality. When unbiased stochastic gradients are available, we establish $2$-Wasserstein bounds under global contraction and Lipschitz conditions on the full drift in an adapted quadratic metric. For a fixed penalty parameter, the error relative to the penalized Gibbs distribution decays exponentially to an $\mathcal{O}(\sqrtη)$ neighborhood, where $η$ is the stepsize. We also bound the discrepancy between the penalized Gibbs distribution and the constrained target. In a two dimensional quadratic model, we establish nonreversible acceleration by tuning the skew perturbation to the curvature imbalance induced by penalization. With the target accuracy and smaller curvature fixed and initial Wasserstein distances uniformly bounded, tuning the skew perturbation improves the sufficient Euler iteration bound from linear to logarithmic in the curvature ratio. Numerical experiments evaluate the algorithms on constrained Bayesian regression, classification, neural networks, and truncated sampling, and examine the acceleration mechanism in a stochastic quadratic model.

0.17

Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization

cs.LG stat.ML ·2026-10-14 ·Haowei Wang, Yilin Zheng
theoryhot direction similarity 0.57
Abstract

Efficient global optimization aims to identify a global optimum of an expensive black-box function within a limited evaluation budget $N$. We investigate the convergence rates of Gaussian process Thompson sampling (GP-TS) under noiseless observations, assuming a fixed objective function in a reproducing kernel Hilbert space (RKHS). For Matérn kernels with smoothness parameter $ν$ in dimension $d$, we establish a worst-case expected simple-regret upper bound of $O(N^{-ν/d}\sqrt{\log N})$ for both discrete GP-TS on sufficiently fine grids and its continuous counterpart. For the continuous implementation, we develop a nested-grid argument to control posterior sample paths over the entire domain. We further establish matching lower bounds of $Ω(N^{-5/2}\sqrt{\log N})$ for both implementations under a fixed one-dimensional Matérn-$5/2$ kernel, demonstrating that the logarithmic penalty is intrinsic to standard GP-TS in this setting. Motivated by this limitation, we propose Gaussian Process Capped Thompson Sampling (GP-CTS), which caps posterior sample paths using a valid RKHS norm upper bound while preserving optimism. This modification successfully eliminates the logarithmic penalty and achieves the minimax-optimal rate $Θ(N^{-ν/d})$ for both discrete and continuous implementations.

0.28