28. listopadu 2022
Řečník · 0 sledujících
Řečník · 0 sledujících
Řečník · 0 sledujících
The most widely used technique for solving large-scale semidefinite programs (SDPs) in practice is the non-convex Burer-Monteiro method, which explicitly maintains a low-rank SDP solution for memory efficiency. There has been much recent interest in obtaining a better theoretical understanding of the Burer-Monteiro method. When the rank r of the SDP solution is above the Barvinok-Pataki bound (where a globally optimal solution of rank at most r is guaranteed to exist), a recent line of work established convergence to a global optimum for generic or smoothed instances of the problem. However, it was open whether there even exists an instance in this regime where the Burer-Monteiro method fails. We prove that the Burer-Monteiro method can fail for the Max-Cut SDP on n vertices when the rank is above the Barvinok-Pataki bound (r ≳√(2n)). We provide a family of instances that have spurious local minima even when the rank r = n/2. Combined with existing guarantees, this settles the question of the existence of spurious local minima for the Max-Cut formulation in all ranges of the rank, and justifies the use of beyond-worst-case paradigms like smoothed analysis to obtain guarantees for the Burer-Monteiro method.The most widely used technique for solving large-scale semidefinite programs (SDPs) in practice is the non-convex Burer-Monteiro method, which explicitly maintains a low-rank SDP solution for memory efficiency. There has been much recent interest in obtaining a better theoretical understanding of the Burer-Monteiro method. When the rank r of the SDP solution is above the Barvinok-Pataki bound (where a globally optimal solution of rank at most r is guaranteed to exist), a recent line of work esta…
Účet · 961 sledujících
Profesionální natáčení a streamování po celém světě.
Prezentace na podobné téma, kategorii nebo přednášejícího
Yuanwei Liu, …
Pro uložení prezentace do věčného trezoru hlasovalo 0 diváků, což je 0.0 %
Zhiyuan You, …
Pro uložení prezentace do věčného trezoru hlasovalo 0 diváků, což je 0.0 %
Pro uložení prezentace do věčného trezoru hlasovalo 0 diváků, což je 0.0 %
Yuanyu Wan, …
Pro uložení prezentace do věčného trezoru hlasovalo 0 diváků, což je 0.0 %
Pro uložení prezentace do věčného trezoru hlasovalo 0 diváků, což je 0.0 %
Pro uložení prezentace do věčného trezoru hlasovalo 0 diváků, což je 0.0 %