Vi studerar problemet med provtagning från en distribution där den negativa logaritmen av måltätheten är L-smooth överallt och m-starkt konvex utanför en boll med radien R, men potentiellt icke-konvex inuti denna boll. Vi studerar både överdämda och underdämda Langevin MCMC och bevisa övre gränser på den tid som krävs för att få ett prov från en distribution som ligger inom ε av målfördelningen i 1-Wasserstein avstånd. För första ordningens metod (over damed Langevin MCMC) är tids komplexiteten Õ e cLR 2 d ε 2, där d är dimensionen av det underliggande utrymmet. För den andra ordningens metod (undertryckt Langevin MCMC) är tidskomplexiteten Õ e cLR 2 ε d ε för någon explicit positiv konstant c. Överraskande är konvergenskvoten endast polynom i dimensionen d och målnoggrannheten ε. Det är dock exponentiellt i problemparametern LR 2, som är ett mått på icke-logconcavity av målfördelningen. I ett mer algoritmiskt arbete begränsade Dalalyan (2017) diskretiseringsfelet hos överdämt Langevin MCMC, och tillhandahöll den första icke-asymptotiska konvergensen av överdämt Langevin MCMC under log-koncavity antaganden. Detta följdes av en sekvens av papper i starkt log-concave inställning (se t.ex., Durmus och Moulines, 2016, Dalalyan och Karagulyan, 2017, Dwivedi et al., 2018. Mest relevant för vårt arbete är tidningen av Eberle (2016), som fastställde konvergensen av överdämd Langevin diffusion enligt antaganden (A1) -(A3). Den kontinuerliga tidsspridning som studeras i detta papper är inte genomförbar algoritmiskt. Vi noterar att våra bevis i detta dokument är starkt beroende av Eberles argument för reflektionskoppling (2016). Två resultat är särskilt relevanta för detta dokument. Enligt det starka antagandet om logkonkavitet etablerade Durmus och Moulines (2016) aÕ d/ε 2 iteration komplexitet för överdämda Langevin MCMC, och Cheng et al. (2017) fastställde att Langevin MCMC var komplext i iterationsprocessen för undertryckt Langevin. Denna quadratic speedup i d och ε visas också i våra resultat som sammanfattas i Theorem 1.1. Även mycket relevant för detta arbete är tidningen av Eberle et al. (2017) som visade en sammandragning av den kontinuerliga tidsförloppet (2). Detta resultat handlar dock om en mycket större klass av potentiella funktioner, och på grund av detta avståndet till den invarianta fördelningen skalar exponentiellt med dimension d. På en hög nivå, vår analys i Avsnitt 3 ger ett mer gynnsamt resultat genom att kombinera idéer från både Eberle et al. (2017) och Cheng et al. (2017) enligt nya antaganden. Också anmärkningsvärt är att problemet med provtagning från icke-logconcave distributioner har studerats av Raginsky et al. (2017), men under svagare antaganden, med en värsta fall konvergensgrad som är exponentiellt i d. Å andra sidan, Ge et al. (2017) fastställde en poly(d, 1/ε) konvergenshastighet för provtagning från en distribution nära en blandning av Gaussians, där blandningen komponenter har samma varians (som subsumeras av våra antaganden). Slutligen finns det en stor klass av samplingsalgoritmer som kallas Hamiltonian Monte Carlo (HMC), som involverar Hamiltons dynamik i någon form. Vi hänvisar till Ma et al. (2015) för en undersökning av resultaten på detta område. Bland dessa har den variant som studeras i detta papper (Algoritm 2), baserad på diskretisering av (2), en naturlig fysisk tolkning som utvecklingen av en partikel dynamik under ett viskös kraftfält. Denna modell studerades först av (Kramers, 1940) i samband med kemiska reaktioner. Kontinuerlig tidsprocessen har studerats ingående (Hérau, ) studera konvergensen av HMC under log-koncavity antaganden. Efter det oberoende slutförandet av detta dokument, Bou-Rabee et al. (2018) publicerade en pre-print på arXiv analysera Hamiltonian Monte Carlo under liknande antaganden som våra. I detta avsnitt presenterar vi grundläggande definitioner, notationskonventioner och antaganden som används i hela dokumentet. För q  på N vi låter v q betecknar q-norm av en vektor v  på R d. I hela papperet använder vi Bt för att beteckna standard Brownian rörelse (Mörters och Peres, 2010).
Konvergensen för dessa två algoritmer har ytterligare fastställts för provtagning från icke-log-concave densiteter REF.
Sharp Convergence Rates for Langevin Dynamics in the Nonconvex Setting
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}