The Library
Noisy gradient flow from a random walk in Hilbert space
Tools
Pillai, Natesh S., Stuart, A. M. and Thiéry, Alexandre H. (2014) Noisy gradient flow from a random walk in Hilbert space. Stochastic Partial Differential Equations: Analysis and Computations, 2 (2). pp. 196232. doi:10.1007/s4007201400293
PDF
stuart111.pdf  Published Version Embargoed item. Restricted access to Repository staff only  Requires a PDF viewer. Download (540Kb) 
Official URL: http://dx.doi.org/10.1007/s4007201400293
Abstract
Consider a probability measure on a Hilbert space defined via its density with respect to a Gaussian. The purpose of this paper is to demonstrate that an appropriately defined Markov chain, which is reversible with respect to the measure in question, exhibits a diffusion limit to a noisy gradient flow, also reversible with respect to the same measure. The Markov chain is defined by applying a Metropolis–Hastings accept–reject mechanism (Tierney, Ann Appl Probab 8:1–9, 1998) to an Ornstein–Uhlenbeck (OU) proposal which is itself reversible with respect to the underlying Gaussian measure. The resulting noisy gradient flow is a stochastic partial differential equation driven by a Wiener process with spatial correlation given by the underlying Gaussian structure. There are two primary motivations for this work. The first concerns insight into Monte Carlo Markov Chain (MCMC) methods for sampling of measures on a Hilbert space defined via a density with respect to a Gaussian measure. These measures must be approximated on finite dimensional spaces of dimension NN in order to be sampled. A conclusion of the work herein is that MCMC methods based on priorreversible OU proposals will explore the target measure in O(1)O(1) steps with respect to dimension NN . This is to be contrasted with standard MCMC methods based on the random walk or Langevin proposals which require O(N)O(N) and O(N1/3)O(N1/3) steps respectively (Mattingly et al., Ann Appl Prob 2011; Pillai et al., Ann Appl Prob 22:2320–2356 2012). The second motivation relates to optimization. There are many applications where it is of interest to find global or local minima of a functional defined on an infinite dimensional Hilbert space. Gradient flow or steepest descent is a natural approach to this problem, but in its basic form requires computation of a gradient which, in some applications, may be an expensive or complex task. This paper shows that a stochastic gradient descent described by a stochastic partial differential equation can emerge from certain carefully specified Markov chains. This idea is wellknown in the finite state (Kirkpatricket al., Science 220:671–680, 1983; Cerny, J Optim Theory Appl 45:41–51, 1985) or finite dimensional context (German, IEEE Trans Geosci Remote Sens 1:269–276, 1985; German, SIAM J Control Optim 24:1031, 1986; Chiang, SIAM J Control Optim 25:737–753, 1987; J Funct Anal 83:333–347, 1989). The novelty of the work in this paper is that the emergence of the noisy gradient flow is developed on an infinite dimensional Hilbert space. In the context of global optimization, when the noise level is also adjusted as part of the algorithm, methods of the type studied here go by the name of simulated–annealing; see the review (Bertsimas and Tsitsiklis, Stat Sci 8:10–15, 1993) for further references. Although we do not consider adjusting the noiselevel as part of the algorithm, the noise strength is a tuneable parameter in our construction and the methods developed here could potentially be used to study simulated annealing in a Hilbert space setting. The transferable idea behind this work is that conceiving of algorithms directly in the infinite dimensional setting leads to methods which are robust to finite dimensional approximation. We emphasize that discretizing, and then applying standard finite dimensional techniques in RNRN , to either sample or optimize, can lead to algorithms which degenerate as the dimension NN increases.
Item Type:  Journal Article  

Divisions:  Faculty of Science > Mathematics Faculty of Science > Statistics 

Journal or Publication Title:  Stochastic Partial Differential Equations: Analysis and Computations  
Publisher:  Springer  
ISSN:  21940401  
Official Date:  29 April 2014  
Dates: 


Volume:  2  
Number:  2  
Page Range:  pp. 196232  
DOI:  10.1007/s4007201400293  
Status:  Peer Reviewed  
Publication Status:  Published  
Access rights to Published version:  Restricted or Subscription Access 
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 