Convergence of Langevin-simulated annealing algorithms with multiplicative noise

2024/03/15 by Pierre Bras, Gilles Pagès
Mathematics · Computer Science · #Markov Chains and Monte Carlo Methods #Bayesian Methods and Mixture Models #Statistical Methods and Inference

paper · doi:10.1090/mcom/3899

Abstract

We study the convergence of Langevin-Simulated Annealing type algorithms with multiplicative noise, i.e. for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper V colon double-struck upper R Superscript d Baseline right-arrow double-struck upper R"> <mml:semantics> <mml:mrow> <mml:mi>V</mml:mi> <mml:mo>:</mml:mo> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">R</mml:mi> </mml:mrow> <mml:mi>d</mml:mi> </mml:msup> <mml:mo stretchy="false"> → </mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">R</mml:mi> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">V : \mathbb R^d → \mathbb R</mml:annotation> </mml:semantics> </mml:math> </inline-formula> a potential function to minimize, we consider the stochastic differential equation <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d upper Y Subscript t Baseline equals minus sigma sigma Superscript down-tack Baseline nabla upper V left-parenthesis upper Y Subscript t Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>d</mml:mi> <mml:msub> <mml:mi>Y</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:mo>=</mml:mo> <mml:mo> − </mml:mo> <mml:mi> σ </mml:mi> <mml:msup> <mml:mi> σ </mml:mi> <mml:mi mathvariant="normal"> ⊤ </mml:mi> </mml:msup> <mml:mi mathvariant="normal"> ∇ </mml:mi> <mml:mi>V</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msub> <mml:mi>Y</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">dY_t = - σ σ ^\top ∇ V(Y_t)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d t plus a left-parenthesis t right-parenthesis sigma left-parenthesis upper Y Subscript t Baseline right-parenthesis d upper W Subscript t plus a left-parenthesis t right-parenthesis squared normal upper Upsilon left-parenthesis upper Y Subscript t Baseline right-parenthesis d t"> <mml:semantics> <mml:mrow> <mml:mi>d</mml:mi> <mml:mi>t</mml:mi> <mml:mo>+</mml:mo> <mml:mi>a</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>t</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mi> σ </mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msub> <mml:mi>Y</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:mo stretchy="false">)</mml:mo> <mml:mi>d</mml:mi> <mml:msub> <mml:mi>W</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:mo>+</mml:mo> <mml:mi>a</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>t</mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mn>2</mml:mn> </mml:msup> <mml:mi mathvariant="normal"> Υ </mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msub> <mml:mi>Y</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:mo stretchy="false">)</mml:mo> <mml:mi>d</mml:mi> <mml:mi>t</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">dt + a(t)σ (Y_t)dW_t + a(t)²Υ (Y_t)dt</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis upper W Subscript t Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:msub> <mml:mi>W</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(W_t)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a Brownian motion, where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="sigma colon double-struck upper R Superscript d Baseline right-arrow script upper M Subscript d Baseline left-parenthesis double-struck upper R right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi> σ </mml:mi> <mml:mo>:</mml:mo> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">R</mml:mi> </mml:mrow> <mml:mi>d</mml:mi> </mml:msup> <mml:mo stretchy="false"> → </mml:mo> <mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">M</mml:mi> </mml:mrow> <mml:mi>d</mml:mi> </mml:msub> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">R</mml:mi> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">σ : \mathbb R^d → \mathcal M_d(\mathbb R)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is an adaptive (multiplicative) noise, where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="a colon double-struck upper R Superscript plus Baseline right-arrow double-struck upper R Superscript plus"> <mml:semantics> <mml:mrow> <mml:mi>a</mml:mi> <mml:mo>:</mml:mo> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD">

Citations

• Gradient-based learning applied to document recognition

Related

• Greedy wavelet projections are bounded on BV
• Convergence of Langevin-Simulated Annealing algorithms with multiplicative noise II: Total Variation
• Convergence of Langevin-Simulated Annealing algorithms with multiplicative noise
• On the convergence of an improved and adaptive kinetic simulated annealing
• Fast simulated annealing in \R^d and an application to maximum likelihood estimation