"We address the problem of upper bounding the mean square error of MCMC estimators. Our analysis is non-asymptotic. We first establish a general result valid for essentially all ergodic Markov chains encountered in Bayesian computation and a possibly unbounded target function $f.$ The bound is sharp in the sense that the leading term is exactly $\asvar/n$, where $\asvar$ is the CLT asymptotic variance. Next, we proceed to specific assumptions and give explicit computable bounds for geometrically and polynomially ergodic Markov chains. As a corollary we provide results on confidence estimation."

""We survey an area of recent development, relating dynamics to theoretical computer science. We discuss the theoretical limits of simulation and computation of interesting quantities in dynamical systems. We will focus on central objects of the theory of dynamics, as invariant measures and invariant sets, showing that even if they can be computed with arbitrary precision in many interesting cases, there exists some cases in which they can not. We also explain how it is possible to compute the speed of convergence of ergodic averages (when the system is known exactly) and how this entails the computation of arbitrarily good approximations of points of the space having typical statistical behaviour (a sort of constructive version of the pointwise ergodic theorem).""

"Set-functions appear in many areas of computer science and applied mathematics, such as machine learning, computer vision, operations research or electrical networks. Among these set-functions, submodular functions play an important role, similar to convex functions on vector spaces. In this tutorial, the theory of submodular functions is presented, in a self-contained way, with all results shown from first principles. A good knowledge of convex analysis is assumed."

Hot damn! "... in this paper we re-examine Freund's problem in case the experts have internal structure that enables them to learn. In this case the problem has two possible interpretations: should the experts learn from all data or only from the subsequence on which they are being tracked? The MPP algorithm solves the first case. Our contribution is to generalise MPP to address the second option. The results we obtain apply to any expert structure that can be formalised using (expert) hidden Markov models. Curiously enough, for our interpretation there are \emph{two} natural reference schemes: freezing and sleeping. For each scheme, we provide an efficient prediction strategy and prove the relevant loss bound."

"...we present a simple modification of the BP algorithm which gives a fully polynomial-time randomized approximation scheme (FPRAS)...This is the first instance where BP is proved to have fully-polynomial running time."

"...a website for research and coordination on Decentralized Techniques for Reasoning in Reduced Information Spaces (ONR 2009 Multi-disciplinary University Research Project)"

A course taught by Christos Papadimitriou

Issue on Interface of Probability and Algorithms

Nikolaos M. Freris, Hemant Kowshik, P. R. Kumar

lecture notes by Amir Dembo, Andrea Montanari

From the abstract: "We consider multi-armed bandit with distributed players, where each player independently samples one of N stochastic processes with unknown parameters and accrues reward in each slot without information exchange. Users choosing the same arm collide, and none or only one receives reward depending on the collision model. This problem can be formulated as a decentralized multi-armed bandit problem."

Francis Bach (INRIA Rocquencourt)

ICSI tech repots

Dominique Tschopp, Suhas Diggavi

David L. Donoho, Arian Maleki, Andrea Montanari

Kyomin Jung, Devavrat Shah, Jinwoo Shin

Remi Gribonval, Karin Schnass

Holger Höfling, Robert Tibshirani; JMLR 10(Apr):883--906, 2009 (via cshalizi)

M. Mézard, M.Tarzia, C. Toninelli

Laurent Jacob, Francis Bach (INRIA Rocquencourt), Jean-Philippe Vert

Workshop on the Frontiers in Distributed Communication, Sensing and Control, October 31 - November 2, 2008, Yale University

by A. Juditsky and A. Nemirovski

Olivier Cappe and Eric Moulines

by Christian Robert and George Casella

Haipeng Zheng, Sanjeev R. Kulkarni, H. Vincent Poor