New for: D1, D2, D3, INET, D4, D5
A promising approach to solve such problems with provable guarantees is the sum-of-squares (SOS) meta-algorithm, which has been discovered multiple times across different disciplines including control theory, proof complexity, and quantum information.
My collaborators and I show in a sequence of recent works that for a wide range of optimization and estimation problems, this meta-algorithm achieves the best known provable guarantees, often improving significantly over all previous methods.
For example, for mixtures of spherical Gaussians, we obtain guarantees that improve exponentially over the previous best ones and approach, for the first time, the information-theoretic limits.
Remarkably, the SOS meta-algorithm achieves these guarantees without being tailored to this specific problem.
Moreover, we prove that for a rich class of problems, the guarantees that SOS achieves are best possible with respect to a restricted but very powerful model of computation.
This result leads to the strongest known concrete lower bounds for NP-complete problems.
Taken together these results point toward a unified theory for efficient optimization and estimation centered around SOS that could change how we think about efficient computation in general.