Optimization Algorithms for Multi-Species Spherical Spin Glasses

Understand

This paper develops approximate message passing algorithms to optimize multi-species spherical spin glasses.

• We first show how to efficiently achieve the algorithmic threshold energy identified in our companion work, thus confirming that the Lipschitz hardness result proved therein is tight.
• Next we give two generalized algorithms which produce multiple outputs and show all of them are approximate critical points.
• Namely, in an $r$-species model we construct $2^r$ approximate critical points when the external field is stronger than a "topological trivialization" phase boundary, and exponentially many such points in the complementary regime.