A local relaxation rate is introduced through the spectral measure of the region's centered indicator rather than a Dirichlet-form Rayleigh quotient, which exceeds the global one, shrinking the burn-in, and with a maximum-principle ceiling it caps the trajectory probability uniformly in time.
Abstract
Training a model with noisy gradient descent can be idealized as overdamped Langevin dynamics, and a natural safety question is to bound the probability $\nu_t(\mathcal{A}_H) = \mathbb{P}(Q_t \in \mathcal{A}_H)$ that the trajectory lies in a designated failure region $\mathcal{A}_H$. We study this for a smooth, strongly convex loss in $d$ dimensions, with $\mathcal{A}_H$ separated from the minimizer by an energy gap. At the end of training, the equilibrium mass $\pi(\mathcal{A}_H)$ is exponentially small in $d$, with a complementary energy-barrier rate when the noise is small. Along the trajectory, a shape-free bound $\nu_t(\mathcal{A}_H) \le \pi(\mathcal{A}_H)(1 + \sqrt{\chi_0^2/\pi(\mathcal{A}_H)}\,e^{-mt})$ shows the in-set probability relaxes to (twice) the static value after a burn-in of order $d$, using only the global spectral gap $m$. A worked Ornstein-Uhlenbeck example shows this burn-in is necessary: an angular slice of the equilibrium shell can transiently swell by a factor exponential in $d$, though its equilibrium mass is tiny. To rule this out we introduce a local relaxation rate, defined through the spectral measure of the region's centered indicator rather than a Dirichlet-form Rayleigh quotient. For geometrically isolated regions this rate exceeds the global one, shrinking the burn-in, and with a maximum-principle ceiling it caps the trajectory probability uniformly in time. Strong convexity sets how fast training relaxes, but the shape of the unsafe set decides whether the trajectory bulges through it on the way to equilibrium.
For $(Q_t,P_t)$ governed by suitably damped underdamped Langevin dynamics, we quantify the convergence in KL divergence of the positional marginal to a $\sigma$-strongly log-concave target $\pi(dq) = \frac{1}{Z}e^{-V(q)}dq$ as \begin{align*} \operatorname{KL}(\operatorname{Law}(Q_t) \| \pi) \leq e^{-\sqrt{\sigma} t}\operatorname{KL}(\operatorname{Law}(Q_{0}, P_{0})\, \|\, \Pi_0), \end{align*} where $\Pi_0$ denotes an appropriately selected reference measure. When $\pi$ is merely log-concave, the estimate \begin{align*} \operatorname{KL}(\operatorname{Law}(Q_t) \| \pi) \leq \frac{\tau^2}{t^2}\operatorname{KL}(\operatorname{Law}(Q_{\tau}, P_{\tau})\, \|\, \Pi_{\tau}) \end{align*} is derived, where $\Pi_\tau$ denotes another correspondingly chosen reference measure at time $\tau>0$. Both rates match precisely the canonical rates of the corresponding accelerated gradient flows in $\mathbb{R}^d$. They are achieved by the novel interpretation of the underdamped Langevin dynamics as a combination of strategies in an online sampling game and by estimating the KL divergence using a cost function informed by fictitious competitors.
Let $\pi(\mathrm{d} x)\propto e^{-U(x)}\,\mathrm{d} x$ on $\mathbb R^d$, where $0<m\leq L<\infty$, $mI_d\preceq\nabla^2U(x)\preceq LI_d$, and $\kappa=L/m$. It is known that, under warm-start assumptions, fixed-step Metropolis-adjusted Langevin algorithm (MALA) with properly tuned step size has mixing time of order $\kappa \sqrt{d}$ up to logarithmic factors. By contrast, when the condition number is bounded away from one, no single fixed step size yields a matching spectral-gap lower bound of order $(\kappa \sqrt{d})^{-1}$ uniformly over this target class. We show that MALA with a uniformly randomized step size admits a spectral-gap lower bound of this size. At each iteration, the randomized-step MALA considered here draws $h$ uniformly from $(0,H)$ and performs one ordinary MALA transition with step size $h$. We show that, when $H$ is of order $(L\sqrt{d})^{-1}$, the right spectral gap of randomized-step MALA admits a lower bound of order \[ \frac{1}{\kappa\sqrt{d}\,[1+\log(d+1)+\log\kappa]}. \] The main new ingredient in the proof is a Cheeger-type inequality for aggregating estimates of the one-step flow of MALA out of measurable sets at various step-size scales. It allows the scale used to control the flow to depend on the set and avoids the additional loss that would result from first summing the flows and then applying the standard Cheeger inequality. This work was developed with substantial assistance from ChatGPT, which suggested the uniformly randomized-step approach, developed the principal proof arguments, and generated the simulation and Lean 4 code. The human author checked and verified the mathematical content and take full responsibility for the results.
We study the underdamped (kinetic) Langevin dynamics confined to a bounded convex domain $\Omega\subset\mathbb{R}^d$ by specular reflection of the velocity at the boundary. This process is the natural momentum-based analogue of the normally reflected overdamped Langevin diffusion, and it is used in practice for constrained sampling; however, no explicit quantitative convergence rate is available in the literature. We provide the first such rate. Assuming only that the position marginal $\mu_x\propto e^{-U}$ satisfies a Poincar\'e inequality on $\Omega$ with constant $m>0$ and that $\nabla^2U\succeq-K\,\mathrm{Id}$, we prove that the law converges to the Gibbs measure exponentially fast in $L^2$, with an explicit rate that scales like $\sqrt m$, which is optimal when $U$ is convex. Since the normally reflected overdamped dynamics converges exactly at rate $m$, this establishes a square-root acceleration for constrained sampling in the small-gap regime when $m$ is small, matching the acceleration known in the unconstrained case. The proof adapts the modified $L^2$ hypocoercivity method of Dolbeault--Mouhot--Schmeiser with the gap-shifted corrector of Fan--Li--Lu. The specular symmetry makes the transport operator antisymmetric, and that the corrector automatically selects the Neumann realization of the overdamped generator, which is precisely the boundary condition that keeps every auxiliary function inside the specular class. The Bochner identity used in the whole-space argument is replaced by a weighted Reilly formula, whose boundary contribution involves the second fundamental form of $\partial\Omega$ and is nonnegative for convex $\Omega$.
This work improves the upper bound to match the best known lower bound, thus establishing the optimal error guarantee for learning under Tsybakov noise.
Steve Hanneke, Hongao Wang, Mingyue Xu· 0 citations
We study the computational effort required for global optimization of a smooth, possibly nonconvex objective $\Gamma:\mathbb{R}^d\to\mathbb{R}$. An algorithm satisfies the $(\varepsilon,\delta)$-PAC performance requirement if its output $\widehat X$ obeys $\mathbb{P}\{\Gamma(\widehat X)-\Gamma^\star>\varepsilon\}\leq\delta$. Algorithm design and analysis are in continuous time. We compare classical simulated annealing and fixed-temperature Langevin diffusion with two approaches introduced and analyzed here: parallel-restart Langevin and a Langevin--gradient scheme using stochastic dynamics for global exploration and gradient flow for local exploitation. Let $L=\log(1/\delta)$ and let $E_*$ denote the dominant energy barrier. At logarithmic precision in the low-temperature regime, the first two approaches require simulation time exponential in $L/\varepsilon$. For parallel fixed-temperature Langevin, an appropriate number of independent trials gives $ C_3=L^{1+o(1)}/\varepsilon$ as $\delta\downarrow0$, for each fixed $\varepsilon>0$. The most substantial improvement comes from separating exploration from exploitation. If $\eta$ is the attraction margin of a target region containing the global minimizers, a sufficient low-temperature estimate for total simulation time in the best-state Langevin--gradient variant is $ C_4^{(c)}\approx N\exp\{EL/(N\eta)\} +O(\log(1/\varepsilon))$, with $E>E_*$. Thus global exploration is decoupled from the requested accuracy. Analysis beyond logarithmic precision reveals dimension-dependent prefactors, while experiments on the six-hump camel and Rastrigin objectives illustrate the benefits of warmer exploration and the usefulness of spectral information for understanding exploration time.
We prove a strict space separation between static and ordinary dynamic approximate membership at every fixed error rate. For each fixed $\varepsilon\in(0,1)$, a capacity-$n$ ordinary dynamic filter over a universe of size $u$, with zero false negatives, pointwise false-positive probability at most $\varepsilon$, arbitrary history dependence, a free public random tape, and at most $H$ bits of persistent state, satisfies \[ H\ge \bigl(\log_2(1/\varepsilon)+a_\varepsilon^{\rm c}\bigr)n-o(n), \] under only $u/n\to\infty$. The constant $a_\varepsilon^{\rm c}$ is an explicit variational threshold obtained by preserving the dependence between the parent accepted mass and the successor reservoir. The structural step is a common-continuation transport lemma. A joint posterior KL bound gives a branch-specific survivor support; the same legal delete--insert word transports that support to one successor state, forcing an accepted reservoir. We then keep the parent outside mass $1-X$ in the conditional-entropy argument instead of replacing it by $1-\varepsilon$. This yields a two-variable analytic envelope, with no selected thresholds, dyadic witnesses, or numerical assumptions.
Qizhi Chen, Zhebei Shen, Zhehan Yu· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
