Privacy-preserving data analysis has a large literature that spans several disciplines. Many early attempts have proved problematic either in practice or on paper. A new approach, "differential privacy" -- a notion tailored to situations in which data are plentiful -- has provided a theoretically sound and powerful framework, and given rise to an explosion of research (see the NIPS 2014 tutorial on December 8). We will review the definition of differential privacy, describe some recent algorithmic advances, and conclude with a surprising application.

It was recently proved using graph covers (Ruozzi, 2012) that the Bethe partition function is upper bounded by the true partition function for a binary pairwise model that is attractive. Here we provide a new, arguably simpler proof from first principles. We make use of the idea of clamping a variable to a particular value. For an attractive model, we show that summing over the Bethe partition functions for each sub-model obtained after clamping any variable can only raise (and hence improve) the approximation. In fact, we derive a stronger result that may have other useful implications. Repeatedly clamping until we obtain a model with no cycles, where the Bethe approximation is exact, yields the result. We also provide a related lower bound on a broad class of approximate partition functions of general pairwise multi-label models that depends only on the topology. We demonstrate that clamping a few wisely chosen variables can be of practical value by dramatically reducing approximation error.