Mark Sellke, Stanford University
I will survey recent progress on computing approximate ground states of mean-field spin glass Hamiltonians, which are certain random functions in high dimension. While the asymptotic ground state energy OPT is given by the famous Parisi formula, the landscape of H_N features many bad local optima impeding efficient optimization. In the positive direction, I will explain algorithms based on approximate message passing which achieve asymptotic value ALG given by an extended Parisi formula. The case ALG=OPT has a natural “no overlap gap” interpretation. In the negative direction, I will explain why no algorithm with suitably Lipschitz dependence on H_N can surpass ALG - this includes most standard optimization algorithms on dimension-free time scales. Based on joint works with Ahmed El Alaoui, Brice Huang, and Andrea Montanari.
You are invited to a scheduled Zoom meeting.
Topic: Yale S&DS Department Seminar
Time: 4:00pm - 5:00pm
Join from PC, Mac, Linux, iOS or Android: https://yale.zoom.us/j/99169700816?pwd=SWEvWHI5d3dPNVdHMkZMZURMWWJPUT09
Or Telephone：203-432-9666 (2-ZOOM if on-campus) or 646 568 7788
Meeting ID: 991 6970 0816
International numbers available: https://yale.zoom.us/u/acBOaD1ic6
For H.323 and SIP information for video conferencing units please click here: https://yale.service-now.com/it?id=support_article&sys_id=434b72d3db9e8fc83514b1c0ef961924