Probability and Mathematical Physics Seminar

Optimization via Langevin dynamics in complex landscapes

Location: Warren Weaver Hall 512

Date: Friday, September 21, 2018, 11 a.m.

Synopsis:

Consider the problem of recovering \(v \in \mathbb S^{N-1}\) from an i.i.d. Gaussian \(k\)-tensor spiked by the rank-one tensor \(v^{\otimes k}\). The likelihood function for this is an example of a complex high-dimensional landscape. It is information-theoretically possible to detect the spike at order 1 signal-to-noise ratios, but if \(k>2\) it is expected that the signal-to-noise ratio needs to diverge in \(N\) to efficiently recover \(v\). We seek to understand the mechanisms for, and obstructions to, such planted signal recovery in high dimensions, via locally optimizing algorithms. We study recovery thresholds for a family of "vanilla" algorithms known as Langevin dynamics, on general landscapes consisting of a planted non-linear signal function perturbed by isotropic Gaussian noise. We propose a mechanism for success/failure of recovery via such algorithms in terms of the curvature of the planted signal.

Joint work with G. Ben Arous and A. Jagannath.