On free energy barriers in Gaussian priors and failure of cold start MCMC for high-dimensional unimodal distributions.

We exhibit examples of high-dimensional unimodal posterior distributions arising in nonlinear regression models with Gaussian process priors for which Markov chain Monte Carlo (MCMC) methods can take an exponential run-time to enter the regions where the bulk of the posterior measure concentrates. Our results apply to worst-case initialized ('cold start') algorithms that are local in the sense that their step sizes cannot be too large on average. The counter-examples hold for general MCMC schemes based on gradient or random walk steps, and the theory is illustrated for Metropolis-Hastings adjusted methods such as preconditioned Crank-Nicolson and Metropolis-adjusted Langevin algorithm.

NON-UNIQUE GAMES OVER COMPACT GROUPS AND ORIENTATION ESTIMATION IN CRYO-EM.

Let be a compact group and let . We define the (NUG) problem as finding to minimize . We introduce a convex relaxation of the NUG problem to a (SDP) by taking the Fourier transform of over .

Approximating the Little Grothendieck Problem over the Orthogonal and Unitary Groups.

The little Grothendieck problem consists of maximizing Σ for a positive semidef-inite matrix , over binary variables ∈ {±1}. In this paper we focus on a natural generalization of this problem, the little Grothendieck problem over the orthogonal group. Given ∈ ℝ × a positive semidefinite matrix, the objective is to maximize [Formula: see text] restricting to take values in the group of orthogonal matrices [Formula: see text], where denotes the ()-th × block of We propose an approximation algorithm, which we refer to as , to solve the little Grothendieck problem over the group of orthogonal matrices [Formula: see text] and show a constant approximation ratio.