NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID:8763
Title:Faster width-dependent algorithm for mixed packing and covering LPs

Reviewer 1

1. Page 4, the ell_{infty} barrier. The limitations of performing first-order methods over the ell_{infty} ball go beyond the fact that strongly convex functions grow too fast (Lemma 3.1): there are provable oracle complexity lower bounds for this problem (see Guzman & Nemirovski, "On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization" 2015). I believe Lemma 3.1 is great to make a point, but it is also interesting to point out the provable lower bounds that area convexity circumvents. 1. Page 6, line 215. "is precisely the primal-dual gap". I don't think this is the case, since the primal-dual gap should be the supremum over \bar{w} variable, not just for any primal-dual pair. Could the authors clarify this? 2. Page 6, definition 4.1. In the same spirit as the previous comment: What is the relation between an eps-optimal solution and the duality gap? 3. Page 7, eqn (3). Shouldn't the supremum be over \bar{w}, instead of \bar{x}? 4. Page 7, line 253. I believe \bar{\eta} is exactly the function defined in (3). If this is the case, it would be better to define it in the same equation 5. Page 7, algorithm 1. It is mentioned that the algorithm is related to dual extrapolation, but it also looks similar to the extragradient method (a.k.a. Mirror-Prox). Are there connections in this direction? 6. Page 11, line 381. This is a very minor detail, but after assuming there exists a feasible \tilde{x}, shouldn't the second case start with: Suppose no \tilde{x} is feasible? (as opposed to just x). Starting from x is formally correct, but it is a bit confusing, given the assumption of the previous paragraph. 7. Page 11, proof of Lemma 4.5. This proof needs some polishing. I believe one can directly appeal to Schur complements, and the first two lines are just confusing. Besides, there is a typo on the inverse of A: a_{22}=a, and not d.

Reviewer 2

The paper presents an original application of the novel framework of area-convexity to the design of accelerated algorithms for mixed packing and covering LPs that break the \ell_\infty regularization barrier. It is very significant in that it extends the area-convexity idea beyond the original applications in Sherman's 2017 paper. I believe it will lead to more scholars getting to know this line of work and deploying it for their problems. The paper is well-written.

Reviewer 3

Originality: Maybe the idea is applying [She17] to MLP itself is not very hard to come up with, doing it right seems to be non-trivial. Quality: I didn't find any flaw in the proof as far as I checked. Clarity: The paper is well written and easy to follow. Significance: As I mentioned, it seems the obtained result is significant as the dependency on eps is often problematic.