Complexity of randomized algorithms for underdamped Langevin dynamics

dc.contributor.author

Cao, Y

dc.contributor.author

Lu, J

dc.contributor.author

Wang, L

dc.date.accessioned

2020-07-30T01:20:23Z

dc.date.available

2020-07-30T01:20:23Z

dc.date.updated

2020-07-30T01:20:23Z

dc.description.abstract

We establish an information complexity lower bound of randomized algorithms for simulating underdamped Langevin dynamics. More specifically, we prove that the worst $L^2$ strong error is of order $\Omega(\sqrt{d}, N^{-3/2})$, for solving a family of $d$-dimensional underdamped Langevin dynamics, by any randomized algorithm with only $N$ queries to $\nabla U$, the driving Brownian motion and its weighted integration, respectively. The lower bound we establish matches the upper bound for the randomized midpoint method recently proposed by Shen and Lee [NIPS 2019], in terms of both parameters $N$ and $d$.

dc.identifier.uri

https://hdl.handle.net/10161/21208

dc.publisher

International Press of Boston

dc.subject

math.NA

dc.subject

math.NA

dc.subject

cs.NA

dc.subject

math.PR

dc.title

Complexity of randomized algorithms for underdamped Langevin dynamics

dc.type

Journal article

duke.contributor.orcid

Lu, J|0000-0001-6255-5165

duke.contributor.orcid

Wang, L|0000-0002-9130-0505

pubs.organisational-group

Trinity College of Arts & Sciences

pubs.organisational-group

Chemistry

pubs.organisational-group

Mathematics

pubs.organisational-group

Physics

pubs.organisational-group

Duke

pubs.organisational-group

Student

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
2003.09906v2.pdf
Size:
344.74 KB
Format:
Adobe Portable Document Format