## Archive for Montréal

## Montréal street art [jatp]

Posted in Statistics with tags jatp, Mont Royal, Montréal, murals, Québec, street art on July 4, 2017 by xi'an## MCM 2017

Posted in Statistics with tags ABC, ABC algorithm, ABC consistency, Bayesian model choice, curse of dimensionality, Hilbert curve, MCM 2017, Montréal, population genetics, Québec, random forests, summary statistics, Wasserstein distance on July 3, 2017 by xi'an## Hamiltonian MC on discrete spaces

Posted in Statistics, Travel, University life with tags École Polytechnique, BNP11, capture-recapture, ergodicity, Hamiltonian Monte Carlo, Jolly-Seber model, Laplace distribution, Montréal, open population on July 3, 2017 by xi'an**F**ollowing a lively discussion with Akihiko Nishimura during a BNP11 poster session last Tuesday, I took the opportunity of the flight to Montréal to read through the arXived paper (written jointly with David Dunson and Jianfeng Liu). The issue is thus one of handling discrete valued parameters in Hamiltonian Monte Carlo. The basic “trick” in handling this complexity goes by turning the discrete support via the inclusion of an auxiliary continuous variable whose discretisation is the discrete parameter, hence resembling to some extent the slice sampler. This removes the discreteness blockage but creates another difficulty, namely handling a discontinuous target density. (I idly wonder why the trick cannot be iterated to second or higher order so that to achieve the right amount of smoothness. Of course, the maths behind would be less cool!) The extension of the Hamiltonian to this setting by a convolution is a trick I had not seen since the derivation of the Central Limit Theorem during Neveu’s course at Polytechnique. What I find most exciting in the resolution is the move from a Gaussian momentum to a Laplace momentum, for the reason that I always wondered at alternatives [without trying anything myself!]. The Laplace version is indeed most appropriate here in that it avoids a computation of all discontinuity points and associated values along a trajectory. Since the moves are done component-wise, the method has a Metropolis-within-Gibbs flavour, which actually happens to be a special case. What is also striking is that the approach is both rejection-free and exact, provided ergodicity occurs, which is the case when the stepsize is random.

In addition to this resolution of the discrete parameter problem, the paper presents the further appeal of (re-)running an analysis of the Jolly-Seber capture-recapture model. Where the discrete parameter is the latent number of live animals [or whatever] in the system at any observed time. (Which we cover in Bayesian essentials with R as a neat entry to both dynamic and latent variable models.) I would have liked to see a comparison with the completion approach of Jérôme Dupuis (1995, Biometrika), since I figure the Metropolis version implemented here differs from Jérôme’s. The second example is built on Bissiri et al. (2016) surrogate likelihood (discussed earlier here) and Chopin and Ridgway (2017) catalogue of solutions for not analysing the Pima Indian dataset. (Replaced by another dataset here.)

## complexity of the von Neumann algorithm

Posted in Statistics with tags accept-reject algorithm, John von Neumann, Luc Devroye, McGill University, Montréal, pseudo-random generator, qadtree, random bit, random number generation, Riemann integration on April 3, 2017 by xi'an

“Without the possibility of computing infimum and supremum of the density f over compact subintervals of the domain of f, sampling absolutely continuous distribution using the rejection method seems to be impossible in total generality.”

**T**he von Neumann algorithm is another name for the rejection method introduced by von Neumann *circa* 1951. It was thus most exciting to spot a paper by Luc Devroye and Claude Gravel appearing in the latest Statistics and Computing. Assessing the method in terms of random bits and precision. Specifically, assuming that the only available random generator is one of random bits, which necessarily leads to an approximation when the target is a continuous density. The authors first propose a bisection algorithm for distributions defined on a compact interval, which compares random bits with recursive bisections of the unit interval and stops when the interval is small enough.

In higher dimension, for densities f over the unit hypercube, they recall that the original algorithm consisted in simulating uniforms x and u over the hypercube and [0,1], using the uniform as the proposal distribution and comparing the density at x, f(x), with the rescaled uniform. When using only random bits, the proposed method is based on a quadtree that subdivides the unit hypercube into smaller and smaller hypercubes until the selected hypercube is entirely above or below the density. And is small enough for the desired precision. This obviously requires for the computation of the upper and lower bound of the density over the hypercubes to be feasible, with Devroye and Gravel considering that this is a necessary property as shown by the above quote. Densities with non-compact support can be re-expressed as densities on the unit hypercube thanks to the cdf transform. (Actually, this is equivalent to the general accept-reject algorithm, based on the associated proposal.)

“With the oracles introduced in our modification of von Neumann’s method, we believe that it is impossible to design a rejection algorithm for densities that are not Riemann-integrable, so the question of the design of a universally valid rejection algorithm under the random bit model remains open.”

In conclusion, I enjoyed very much reading this paper, especially the reflection it proposes on the connection between Riemann integrability and rejection algorithms. (Actually, I cannot think straight away of a simulation algorithm that would handle non-Riemann-integrable densities, apart from nested sampling. Or of significant non-Riemann-integrable densities.)

## MCM 2017

Posted in pictures, Statistics, Travel, University life with tags Approximate Bayesian computation, Canada, MCMC, Monte Carlo integration, Monte Carlo Statistical Methods, Montréal, probabilistic numerics, Québec, Robert Charlebois, scalability, stochastic gradient on February 10, 2017 by xi'an**J**e reviendrai à Montréal, as the song by Robert Charlebois goes, for the MCM 2017 meeting there, on July 3-7. I was invited to give a plenary talk by the organisers of the conference . Along with

Steffen Dereich, WWU Münster, Germany

Paul Dupuis, Brown University, Providence, USA

Mark Girolami, Imperial College London, UK

Emmanuel Gobet, École Polytechnique, Palaiseau, France

Aicke Hinrichs, Johannes Kepler University, Linz, Austria

Alexander Keller, NVIDIA Research, Germany

Gunther Leobacher, Johannes Kepler University, Linz, Austria

Art B. Owen, Stanford University, USA

Note that, while special sessions are already selected, including oneon Stochastic Gradient methods for Monte Carlo and Variational Inference, organised by Victor Elvira and Ingmar Schuster (my only contribution to this session being the suggestion they organise it!), proposals for contributed talks will be selected based on one-page abstracts, to be submitted by March 1.

## je reviendrai à Montréal [MCM 2017]

Posted in pictures, R, Running, Statistics, Travel with tags Annecy, Canada, conference, Luc Devroye, MCM, MCM 2017, MCQMC, Monte Carlo methods, Monte Carlo Statistical Methods, Montréal, Pierre Lecuyer, Québec, stochastic simulation on November 3, 2016 by xi'an**N**ext summer of 2017, the biennial International Conference on Monte Carlo Methods and Applications (MCM) will take place in Montréal, Québec, Canada, on July 3-7. This is a mathematically-oriented meeting that works in alternance with MCqMC and that is “devoted to the study of stochastic simulation and Monte Carlo methods in general, from the theoretical viewpoint and in terms of their effective applications in different areas such as finance, statistics, machine learning, computer graphics, computational physics, biology, chemistry, and scientific computing in general. It is one of the most prominent conference series devoted to research on the mathematical aspects of stochastic simulation and Monte Carlo methods.” I attended one edition in Annecy three years ago and enjoyed very much the range of topics and backgrounds. The program is under construction and everyone is warmly invited to contribute talks or special sessions, with a deadline on January 20, 2017. In addition, Montréal is a Monte Carlo Mecca of sorts with leading researchers in the field like Luc Devroye and Pierre Lécuyer working there. (And a great place to visit in the summer!)

## je suis revenu de Montréal [NIPS 2015]

Posted in Mountains, pictures, Running, Statistics, Travel, University life with tags Frank-Wolfe Bayesian quadrature, Montréal, probabilistic integration, probabilistic numerics on December 17, 2015 by xi'an**A**fter the day trip to Montréal, a quick stop in Paris, and another one in London, I thought back on the probabilistic integration workshop of last week. First, I had a very good time discussing with people there, with no (apparent) adverse reaction to my talk on “estimating constants”. Second, I finally realised what Mark Berliner meant by saying that he was a Bayesian if not a statistician, in a discussion we had in the early 1990’s, in Cornell. Third, I became [moderately] more open to the highly structured spaces used in the approaches discussed by François-Xavier Briol, Arthur Gretton, Roman Garnett, and Francis Bach. The (RKHS) functional assumptions made in those approaches are allowing for higher and more precise convergence rates, with the question being what happens when the assumptions do not hold. A comment similar to the impact of a Gaussian process as the prior on the integrand in Bayesian quadrature.

François-Xavier presented the recently arXived probabilistic integration that Andrew discussed a week ago. (While I obviously have no relevant remark to make about the maths in this paper, I wonder at the difficulty and cost in sequentially selecting the states behind the quadrature. Which presumably is covered in the earlier Frank-Wolfe paper by the same team.) Another discussion with Arthur clarified a wee bit how RKHS can be perceived in practice, with a lingering question on the size of RKHS within the entire space of functions and more importantly the significant impact of the kernel representation on the resulting approximations. Anyway, those are exciting times, when considering that different branches of numerics and probability and statistics come together to improve upon existing techniques and I am once again glad I could took part in this workshop (although sorry I had to miss the ABC workshop that took place in parallel!)