Archive for October, 2010
You can say the words “The UC Santa Barbara campus is right on the ocean” but it doesn’t really hit home until you see it for yourself. I had a great (but far too short!) time visiting the campus, the talk itself can now be downloaded here.
My first visit to UCSB! I will be speaking Wednesday in the Statistics and Applied Probability Seminar:
Title: Randomized adaptive cooling schedules for Monte Carlo Integration
Abstract: Cooling schedules have long been a staple of Markov chain methods: they form the basis of simulated annealing and tempering. These schedules are not only useful for generating random variates, they also yield a powerful technique for using the samples to estimate the integrals of interest. The advantage of these estimation methods is that the standard deviation of the estimate can be bounded a priori. A drawback to these methods is the need to come up with the cooling schedule in the first place. In this talk I will discuss a new method for creating cooling schedules on the fly. The resulting randomized adaptive cooling schedules (RACS) have provably nice properties and can lead to estimation of high dimensional integrals that are both provably good and much faster than existing methods. I will illustrate these methods with several applications.
The AMS meeting was an exciting two days. My talk (which can be downloaded here) went over well, and there was a lot of exciting stuff going on. This includes several sessions organized by folks from Microsoft Research. Allan Sly has brought the upper bound on the computational threshold for the hard core gas model down to meet the lower bound (see here.) My third published paper was on generating random variates from this model, so I was excited to see this result.
Tomorrow I’ll be giving a talk at the Fall Western AMS meeting, at UCLA, in Boelter Hall 2444. The talk is titled “Near-linear time perfect simulation of corrugated surfaces”.
Given a bipartite graph with n nodes, a corrugated surface can be viewed as a vector in [0,1]n such that all nodes in one partition are local maxima, and all the nodes in the other partition are local minima. In order to draw samples from this random landscape, Caracciolo, Rinaldi, and Sportiello (2008) constructed a Markov chain whose stationary distributionwas uniform over the set of corrugated surfaces. They conjectured from experiments that the mixing time of the chain was O(n ln n) for the special case of a square lattice. Here a new Markov chain is presented that provably mixes in O(n ln n) time for all bipartite graphs. Like the Caraccilo, et al. chain, this new chain can also be used with coupling from thepast to obtain samples drawn exactly from the desired distribution. Furthermore, this approach can then be combinedwith randomized cooling schedule methods in order to obtain a 1 + ε approximation (with probability at least 1 – δ) of the corrugated surface volume in time O(n2(ln n)ε-2 ln (1/δ)).
So I’m sitting here about to give a talk tomorrow, and I’m thinking two things:
1) I should really promote my talks/papers/research more.
2) That stuff really shouldn’t go on my regular blog.
Hence yet another blog was born! This blog is going to be all about what’s going on with my research. I’ll use this space to relay things that I think are important or interesting in Monte Carlo methods. This includes the usual: talks, papers, upcoming conferences I’m attending, interesting things that happened in class, or anything else that comes in under the research rubric. Unlike my personal blog, I plan to post here at least once a week, every Friday. So let’s get started!