Sudakov-Fernique post-AMP, and a new proof of the local convexity of the TAP free energy
This work addresses theoretical challenges in optimization for statisticians and machine learning researchers, offering incremental advancements in analyzing algorithm convergence and landscape properties.
The paper tackles the problem of establishing local convexity in non-convex optimization landscapes, particularly in statistical and machine learning contexts, by deriving an asymptotic comparison inequality called Sudakov-Fernique post-AMP, and applies it to provide a simpler proof of existing results and confirm a conjecture related to efficient sampling in the Sherrington-Kirkpatrick model.
In many problems in modern statistics and machine learning, it is often of interest to establish that a first order method on a non-convex risk function eventually enters a region of parameter space in which the risk is locally convex. We derive an asymptotic comparison inequality, which we call the Sudakov-Fernique post-AMP inequality, which, in a certain class of problems involving a GOE matrix, is able to probe properties of an optimization landscape locally around the iterates of an approximate message passing (AMP) algorithm. As an example of its use, we provide a new, and arguably simpler, proof of some of the results of Celentano et al. (2021), which establishes that the so-called TAP free energy in the $\mathbb{Z}_2$-synchronization problem is locally convex in the region to which AMP converges. We further prove a conjecture of El Alaoui et al. (2022) involving the local convexity of a related but distinct TAP free energy, which, as a consequence, confirms that their algorithm efficiently samples from the Sherrington-Kirkpatrick Gibbs measure throughout the "easy" regime.