Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: There are many highly structured large-scale problems that can be reformulated as generalized linear programs (GLP). Hence, this work focuses on the GLP in a large-scale setting. Inspired by previous work, they proposed an up-gradation version after reformulating (GLP) as an equivalent convex-concave min-max problem, claiming lower complexity and stronger guarantee. Meanwhile, the author shows that modeling framework distributionally robust optimization with ambiguity sets defined by f-divergence and Wasserstein metric can be reformulated to GLP.
strengths_and_weaknesses: Strengths：
This is a good extension of the previous work (VRPDA). 
As the author claimed, better per-iteration complexity and bounding.
The solid improvement on complexity with respect to nnz(A). It’s potentially a huge improvement for certain applications.

Weaknesses：
In one of the experiments that CLVR got defeated by the Gurobi, the author claimed that they believe is due to the preconditioners. It could be better if they could provide further experiments and analyses to make the claim stronger.

questions: I put my question in previous section.
limitations: No potential negative societal impact.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This work studies the generalized linear programming, which has an additional convex regularizer in the objective, in the primal-dual setting. The algorithm named CLVR was proposed to solve the problem, and its complexity depends on the number of nonzero elements in the linear constraint matrix, which makes the algorithm scalable for large-scale problems. The convergence of the algorithm was proved in the paper as well. In the special case where the problem reduces to the standard LP, a restart scheme that accelerates the algorithm was also proposed. The simulation result shows that the algorithm shows comparable and often better performance than the previous works.
strengths_and_weaknesses: Strengths: The proposed algorithm is the first one that solves PD-GLP with complexity that only depends on the number of nonzero elements in the constraint and not on any other dimensions of the problem. Theoretical convergence result is also provided.

Weakness: The work is mainly motivated by VRPDA of [53]. It seems like the proposed algorithm is the special case of VRPDA to the case where the Lagrangian is linear with respect to the dual variable, y. Thus the algorithm itself lacks originality. However, I could not check whether the analysis is also a simplification of [53] to the special case.
questions: * As I pointed out in the weakness, the authors should advertise the originality of CLVR compared to VRPDA in a more careful manner because the problem studied in this paper is less general than [53]. To be specific, I think that the authors should answer the following question: If we change the setting of VRPDA to PD-GLP and apply the lazy update, can we get an algorithm with complexity depending only on nnz(A)?
* Please add some explanation of the variables z, q in Algorithm 1 in Section 3.1. 
* What was the main difficulty or key idea in the proof of Theorem 1? How is it different from the proof of Theorem 1 or Theorem2 of [53]?
limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors of this paper proposed a scalable first-order algorithm, which is named as Coordinate Linear Variance Reduction (CLVR) for  generalized linear program (GLP). And they improved complexity results for GLP that depend on the max row norm of the linear constraint matrix in GLP rather than the spectral norm. 

strengths_and_weaknesses: Strengths: This paper is well-written. It illustrates the basic idea of the CLVR method for solving GLP in a clear way. The proposed CLVR algorithm is novel. The authors establish a better complexity bound for GLP. The authors provide nice explanations and discussions for their algorithm design and theoretical analysis.

Weakness: For GLP, these papers proposed primal-dual type methods. Some comparisons are necessary. 

[1] http://www.optimization-online.org/DB_FILE/2015/05/4901.pdf
[2] https://epubs.siam.org/doi/abs/10.1137/18M1229869
[3] https://arxiv.org/abs/2008.12946
[4] https://link.springer.com/article/10.1007/s40305-021-00344-x

questions: See the weakness.
limitations: See the weakness.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper develops a new primal-dual method for solving generalized linear programs (linear programs with regularizers) where each iteration requires cheap block coordinate updates. They claim an improved complexity results for linear programming and provide experiments on DRO problems.
strengths_and_weaknesses: I think this paper needs lots of work but has potential. In particular, if the authors can clearly demonstrate a useful generic LP solver that uses coordinate-based iterations then that would be of high value to the community. However, there are currently too many issues for me to recommend acceptance.

1. The authors present a new adaptive restart scheme. They do not give a convergence proof for this adaptive restart scheme. Also, they do not compare it empirically with existing restart schemes [9]. To be honest, I think the authors should either reuse existing adaptive restart schemes or demonstrate that their scheme is empirically better than existing schemes. I'd also remark that the results in [9] prove not only that restarts have linear convergence but the associated slope is better than what one gets is better than the linear converge rate one gets from the current iterate, and also stronger results for bilinear systems. I'd suggest the authors carefully read this paper [9] to see what I mean. I'm not sure if your restart metric would achieve these results.

2. For the numerical results please specify if PDHG uses a restart scheme and what restarts scheme it uses. You should also specify how the primal and dual step size is chosen for PDHG as this has a big impact on results e.g., see Adaptive Primal-Dual Hybrid Gradient Methods for Saddle-Point Problems by Tom Goldstein, Min Li, Xiaoming Yuan, Ernie Esser, and Richard Baraniuk.

3. I would like to have seen a much bigger variety of test problems. Currently, the method is only tested on DRO even though it is claimed to be a method for general linear programming. Ideally, you would test your method on the many standard benchmarks and report aggregate results. At a minimum you need a much larger variety of problems. Indeed, if all your method was useful for was DRO why not compare against specialized methods for DRO? E.g., Large-Scale Methods for Distributionally Robust Optimization. Daniel Levy, Yair Carmon, John Duchi & Aaron Sidford.

4. You need to cite Carmon, Yair, et al. "Coordinate methods for matrix games." 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2020, and include it in Table 1. Indeed in the general convex case I believe their complexity is better.

**Minor comments**

On line 314 you write "we believe much of the performance gap in this case is due to the poor conditioning of this instance and the use of pre-conditioners in the barrier method". I don't think this correct, to my knowledge, Gurobi does not use a preconditioner in its barrier method.

On Line 257-259 you claim [38] has an adaptive scheme. It only contains a fixed frequency restart scheme.

**Update after reading reviewer response**

Thanks for the response. I think my initial score was a little harsh and appreciated your clarification. I have updated my score accordingly. I look forward to the new experiments. Please note I have updated my score irrespective of the results of the experiments (e.g., if CVR is better or not for the new instances). My only condition is the promised experiments are included in the final paper (or appendix).
questions: Why do you state cost per iteration of O(nnz(A) + n + d) instead of O(nnz(A)) (at many points in the paper, e.g., Line 45, Table 1)? Unless A has empty rows or columns (which can be removed from the problem) then these are equivalent. With this in mind I find the statement "CLVR is the first algorithm that has no explicit dependence on the ambient dimensions d and n, instead depending on the number of nonzero elements nnz(A)" (Line 127-128) dubious.

**Update after reading reviewer response**

Thanks for the clarification. I have a further question and comment.

How did you pick the examples? This is a very small number of examples. With such a small number and no explanation how they are picked I worry that they are cherry picked.

I think it would have been better if you'd picked a larger standard set of regression problems and presented aggregated results.
limitations: N/A
review_title: null

Meta-review: metareview: Overall all reviewers were positive about this paper and I tend to agree, but no reviewer felt particularly excited about the results.
confidence: Less certain
Decision: Accept