NeurIPS 2020

Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method

Meta Review

All reviewers agreed that this paper made a nice contribution to NeurIPS and recommend acceptance. It considers a novel perspective on constrained non-smooth optimization (by proposing algorithms that reduce the number of projection / linear-minimization oracle calls), improving the previous state-of-the-art rates (removing d^1/4 for the projection oracles and sqrt(d) for LMO over previous best rates, obtaining an optimal rate for LMO and answering an open problem dating from 1993 [83]!). While R1 initially expressed concerns about the writing and the technical correctness of Lemma 1, the reviewers agreed in discussion that this was properly addressed in the rebuttal. The authors should implement these changes in the camera ready version of the paper, as discussed in their rebuttal (clarity, etc.; also include the LMO new empirical results).