One implicit DDIM inversion step is the cheapest probe of whether a pretrained diffusion model encodes local manifold geometry at the Bayes limit, strongly convex at the Bayes limit.
Abstract
One implicit DDIM inversion step is the cheapest probe of whether a pretrained diffusion model encodes local manifold geometry. It is the stationarity condition of an explicit potential, $x-G(x)=\nabla\Psi_t(x)$, strongly convex at the Bayes limit with modulus exactly $e^{-h_t}$ for the step's log-SNR gap $h_t$ $-$ for every data law, schedule and point, with no manifold, reach or unimodality hypothesis. Three consequences must be kept apart. (i) The solution is unique at the Bayes limit; a second one requires the trained score to violate the posterior-covariance bound by $1/(1-e^{-h_t})$, a hypothesis-free certificate of model error; the same bound makes contraction a schedule constant, $\rho_g^{\star}=1-e^{-h_t}<0.326$ throughout the standard DDPM schedule. (ii) The solver can still fail: Picard iteration is unit-step gradient descent on $\Psi_t$, unstable wherever $\lambda_{\max}(\nabla^2\Psi_t)>2$, so oscillation certifies nothing; damping below $2/\lambda_{\max}$ cures it. (iii) The geometry lives in the convergence domain: on the scale-free depth $w=r\kappa_{\max}$ the oscillation shell sits at $w=\tfrac12$, schedule-free, and the divergence shell at $w=1/(1+\rho_g^{\star})$, with a measured finite-noise correction in $\|\mathrm{II}\|^2$. Exact scores reproduce both to within $0.54\%$ on three classes; no trained score we probe shows a shell $-$ a derived limitation, not a null result: the Fermi window conflicts with the model's own training support by $3.6$-$5.6\times$, and the trained Hessian-Lipschitz constant is $2$-$12\%$ of the curvature the law reads, $0$ on a ReLU net. Finally the unconditional ceiling $\sigma_t\lambda_{\max}(\mathrm{sym}\,J)\le1$, from $\mathrm{Cov}(x_0\mid x_t)\succeq0$ alone, holds for the exact score to $3\times10^{-7}$ but is violated in all DDPM CIFAR-10/CelebA-HQ-256 settings, by $1.26$-$4.66\times$.
Exhaustive moment fitting in this constant-dimensional space produces a proper mixture and, together with the dimension-free moment characterization of Gaussian mixtures, achieves the optimal Hellinger rate in polynomial arithmetic time for every fixed $k$.
Given a strongly convex function $u$, equip $R^d$ with a Riemannian metric given by the Hessian $\nabla^2 u$. This is a so-called Hessian manifold. Given a probability density $\mu$ one may run a Langevin diffusion intrinsic to the manifold with stationary distribution $\mu$. Such (Hessian) manifold-valued Langevin diffusions are called Mirror Langevin diffusions (MLD) which have recently become popular. One of the questions we explore is whether, given $\mu$, one can choose $u$ to get an exponential convergence to equilibrium for the MLD, especially if $\mu$ is not strongly log-concave. Our results are based on Lyapunov function methods and give sufficient conditions for a Poincar\'e or a log-Sobolev inequality to hold for the MLD. These, in turn, imply exponential convergence. We also introduce a Markov chain approximation to the MLD given by a two step Gibbs sampler with stationary distribution $\mu$. This Markov chain is a variant of the Sinkhorn Markov chain introduced in arXiv:2307.16421 that is conjectured to converge to a time-inhomogeneous generalization of the MLD. Under suitable assumptions, we prove that the Markov chain has a guaranteed convergence rate in $\chi^2$ that is consistent with the diffusion time scale. Our proofs are based on ideas from entropic optimal transport and strong data processing inequalities.
Benjamin Capdeville, Young-Heon Kim, Soumik Pal· 0 citations
\noindent We study residual-polynomial acceleration of the proximal point method (PPM) for maximal monotone inclusions, with Anderson acceleration (AA) as the prototypical adaptive scheme. We answer three questions exactly. (i)~The minimax complexity over all adaptive methods is precisely $d_0/(K+1)$ per $K$ resolvent evaluations. The upper bound is attained by the averaged-reflection estimator; the matching lower bound uses an explicit skew-adjoint instance with resolvent eigenvalues at the roots of $u^{K+1}=-1$ and $\csc^2$-distributed masses, on which every degree-$K$ polynomial method satisfies $\|r(y_K)\|\ge 1/(K+1)$. The optimal polynomial is uniquely the Fej\'er kernel, and the same instance certifies a per-step floor. (ii)~A sharp phase transition separates regimes: Jackson-kernel polynomials achieve $O(d_0/(K^2 s))$ when the spectral floor $s$ satisfies $sK\to\infty$, while at the critical scale $s\asymp 1/K$ the barrier is exactly $1/(K+1)$. The picture extends to normal operators and the nonlinear family $M=S+N_C$. (iii)~On linear problems AA-PPM needs no safeguarding; on nonlinear problems certification of the $O(1/k)$ envelope requires exactly two oracle evaluations per iteration, and this factor is optimal. We also correct and complete the theory for structured problems---affine, strongly monotone, piecewise-affine, and H\"olderian growth---and confirm all predictions numerically.
We study the local density-dependent diffusion $dY_t=-\Xi(p_t(Y_t))\nabla\Phi(Y_t)\,dt+\sqrt2\,dW_t$ and a clipped, randomly shifted histogram particle approximation on $\mathbb{R}^d$. The central difficulty is that the empirical density is evaluated at the particles'locations and re-enters their drift, while the confining force $\nabla\Phi$ may be unbounded. We provide a path-space entropy proof under two verifiable analytic conditions: a uniform pointwise Gaussian envelope for the true density $p_t$, and a Gaussian--polynomial bound for its spatial gradient $\nabla p_t$. The potential is allowed to have a gradient of at most linear growth. The probabilistic input is a weighted exponential occupancy estimate under the independent product law. It is proved by Poissonizing the system at total intensity $N-1$, performing a one-cell leave-one-out estimate bounded via Poisson information, using Gaussian cell summability, and de-Poissonizing. For every fixed time horizon $T$, we obtain $\operatorname{Ent}(P_t^{N,k}|p_t^{\otimes k})\leq C_T k(h^2(1+|\log h|)+(h^{-d}+\log N)/N)$. Consequently, selecting the optimally balanced bandwidth $h\asymp (N\log N)^{-1/(d+2)}$ yields a total variation error of $\Vert P_t^{N,k}-p_t^{\otimes k}\Vert_{\operatorname{TV}}\leq C_T\sqrt{k}\,N^{-1/(d+2)}(\log N)^{d/[2(d+2)]}$ for fixed $k$. This includes the usual Ornstein--Uhlenbeck density and the density-dependent OU model whenever the PDE estimates hold on the considered interval. Furthermore, the histogram estimator offers a scalable approach for particle approximations. Using occupied-cell hashing, one algorithm step evaluates in expected $O(dLN)$ operations under standard constant-time hashing assumptions. For a fixed dimension and number of shifts, this requires expected $O(N)$ time, avoiding the $O(N^2)$ evaluation cost typical of standard kernel density estimators.
We consider the Langevin diffusion $dX_t = - \beta \nabla V(X_t) dt + \sqrt{2} dB_t$ for a general nonnegative real-analytic potential $V$ and a large parameter $\beta$. In the large-$\beta$ limit the process is confined to the zero set of $V$, assuming that it starts there. We derive a candidate limiting evolution on the zero set. To do so, the zero set is partitioned into strata according to a measure of local codimension known as the local learning coefficient and its multiplicity. It is then shown that the Dirichlet form associated with $X$ converges in a certain sense to a hierarchy of Dirichlet forms corresponding to a stochastic evolution on the strata. This evolution is strongly biased toward higher-dimensional, or"more singular", strata. This result is motivated by a question from Watanabe's singular learning theory regarding the learning dynamics of overparameterized statistical models and the generalization puzzle in deep learning. The result suggests a mechanism for the observation that stochastic gradient methods tend to be biased toward singular solutions that generalize well.
The lifted-selector reduction has an inverse-polynomial radial gap, proved through a quantitative theorem for rational cyclic zonogons, and the results apply to Euclidean zonotope radius and positive-semidefinite binary quadratic maximization parameterized by rank.
Pahan Dewasurendra, Subhashini Jayawardhana· 1 citation