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. This article is part of the theme issue 'Bayesian inference: challenges, perspectives, and prospects'.

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

Let 𝒢 be a compact group and let fij∈C(𝒢). We define the Non-Unique Games (NUG) problem as finding g1,…,gn∈𝒢 to minimize ∑i,j=1nfijgigj-1. We introduce a convex relaxation of the NUG problem to a semidefinite program (SDP) by taking the Fourier transform of fij over 𝒢. The NUG framework can be seen as a generalization of the little Grothendieck problem over the orthogonal group and the Unique Games problem and includes many practically relevant problems, such as the maximum likelihood estimator to registering bandlimited functions over the unit sphere in d-dimensions and orientation estimation of noisy cryo-Electron Microscopy (cryo-EM) projection images. We implement a SDP solver for the NUG cryo-EM problem using the alternating direction method of multipliers (ADMM). Numerical study with synthetic datasets indicate that while our ADMM solver is slower than existing methods, it can estimate the rotations more accurately, especially at low signal-to-noise ratio (SNR).

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

The little Grothendieck problem consists of maximizing Σ ij Cijxixj for a positive semidef-inite matrix C, over binary variables xi ∈ {±1}. In this paper we focus on a natural generalization of this problem, the little Grothendieck problem over the orthogonal group. Given C ∈ ℝ dn × dn a positive semidefinite matrix, the objective is to maximize [Formula: see text] restricting Oi to take values in the group of orthogonal matrices [Formula: see text], where Cij denotes the (ij)-th d × d block of C. We propose an approximation algorithm, which we refer to as Orthogonal-Cut, to solve the little Grothendieck problem over the group of orthogonal matrices [Formula: see text] and show a constant approximation ratio. Our method is based on semidefinite programming. For a given d ≥ 1, we show a constant approximation ratio of αℝ(d)2, where αℝ(d) is the expected average singular value of a d × d matrix with random Gaussian [Formula: see text] i.i.d. entries. For d = 1 we recover the known αℝ(1)2 = 2/π approximation guarantee for the classical little Grothendieck problem. Our algorithm and analysis naturally extends to the complex valued case also providing a constant approximation ratio for the analogous little Grothendieck problem over the Unitary Group [Formula: see text]. Orthogonal-Cut also serves as an approximation algorithm for several applications, including the Procrustes problem where it improves over the best previously known approximation ratio of [Formula: see text]. The little Grothendieck problem falls under the larger class of problems approximated by a recent algorithm proposed in the context of the non-commutative Grothendieck inequality. Nonetheless, our approach is simpler and provides better approximation with matching integrality gaps. Finally, we also provide an improved approximation algorithm for the more general little Grothendieck problem over the orthogonal (or unitary) group with rank constraints, recovering, when d = 1, the sharp, known ratios.