Barriers to online algorithms for optimization from the overlap gap property. Three case studies

Zoom Link

 Many  optimization problems over random structures (such as random graphs and some statistical physics models) exhibit a gap between the existential and algorithmically achievable values, dubbed as statistics-to-computation gap. For some of these problems the best known algorithms exhibit a certain online features: the decisions are made sequentially based on partially revealing information about the problem input step by step. We will exhibit three examples where we prove the following:  subject to such online restrictions, these algorithms are best. The proof is based on establishing variants of the overlap gap property (ogp), inspired by the theory of spin glasses,  tailored for each individual problem. Previously ogp was used to prove barriers to stable algorithms. While algorithms under the consideration are not stable,  they are still obstructed by ogp, as we demonstrate. Three examples to be  considered are (a) finding largest clique in dense random graphs, (b) finding a dense submatrix of a Gaussian matrix, and (c) the symmetric binary perceptron problem.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.