NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID: 7769 Complexity of Highly Parallel Non-Smooth Convex Optimization

### Reviewer 1

Quality: The submission is purely theoretical supported by solid analysis. I do not check the proofs in the appendix, but the claims sound correct to me. However, the constants in the almost all theorems seem to be too complicated to be the inherent constants for the problem. Originality: The lower bound for parallel non-smooth optimization has not been very well-studied and the submission presents a fairly thorough answer to that for both upper and lower bound. Clarity: Although the problem setting is clear, it is hard to understand the proof techniques in the lower bound part. More explanations perhaps with a figure for the wall function will be helpful. Significance: Obtaining the lower bound and constructing the random wall function are non-trivial in theory. Although the proposed algorithm seems to be impractical, the results provide a guideline on the lower bound for other algorithms fallen in the regime. Updates after rebuttal: In Theorem 7, usually \eps<1, then it requires \delta<10^{-20}, which suggests the algorithm needs an exact gradient oracle.

### Reviewer 2

The work is very original and provides novel approaches for both the lower bound problem, where the new idea of a wall function is introduced, and for the upper bound side, where the authors deploy a new framework for the design of accelerated algorithms. Related work is adequately cited and the key ideas in previous works are properly summarized and explained, which makes it easier to follow the novel technical arguments. The results are significant. The authors also provide a number of open problems and conjectures to build on.