NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID:8572
Title:Computational Separations between Sampling and Optimization

The paper demonstrates computational separation between sampling and optimization, specifically problems where sampling is easy but computing a global optima is hard, and vice versa. One nice aspect here is that the paper brings complexity-theoretic tools to the optimization community, which has been thinking about lower bounds mostly via information theoretic tools (Nesterov's black box model). One confusion that was clarified in the discussion is that the reductions used need to preserve continuity/Lipschitzness, which I recommend the authors emphasize in the paper. I also recommend that the results be translated to Wasserstein distance (as opposed to TV) as discussed in the reviews and the author response.