Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes a heuristic PDLP for large-scale LP by combining some existing techniques into PDHG. Emprical results are good, but no convergence guarantees are provided. 
main_review: This paper makes beneficial attempts for applying first-order methods into LP. But I found that all the tricks and heuristics in this paper are already known in existing papers --- the algorithm in this paper just simply combines these parts. As a result, this paper is more like instructions of a software package, not like an academic paper. For engineering implementation, this is a good guideline; but for academic research, this is not enough. 


Some other comments:

In my understanding, a linear convergence result is not enough to prevent the tailing-off effect, because the condition number can be arbitrarily large so contracting by 1/2 is still very expensive. I believe that the reason why we say IPMs can provide high-accurate solution is they have superlinear convergence at the end of the stage which is independent of the condition number and make us get an almost exact solution in finite steps. 

Algorithm 2 is the main part for the algorithm, but the name is "step size heuristic", which is not proper. 

In the line 133-134, the two uses of the notation $\rho_{\cdot}^{\cdot}$ is not consistent. The first subscript is a constant, while the second one is a variable. 

limitations_and_societal_impact: No Societal Impact
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper applies the primal-dual hybrid-gradient (PDHG) method (also sometimes referred to as Chambolle-Pock algorithm) to
solve very large linear programs. The motivation is to solve problems which are out of reach for commerical LP solvers
that are based on simplex or interior-point approaches. Moreover, the algorithm is admissible to highly parallel computation due to the simple update rules of PDHG. 

The main contribution is a careful combination of existing heuristic which are known to speed up PDHG in practice: restarts, "line search" and preconditioning.

In experiments, this combination of heuristics is shown to substantially improve a basic PDHG baseline. Contrary to existing wisdom,
it is shown that FOMs, when enhanced with good heuristics, can indeed find highly accurate solutions to large-scale problems. 

main_review: First of all, I found this paper to be very well written and enjoyable to read. The main strength of the paper is
the quality and clarity of the writing and the experimental setup. It is convincingly demonstrated
that the combination of proposed heuristics provide a strong improvement over the baseline method and existing solvers like SCS.

The introduction gives a beautiful overview and motivation of linear programming with first-order methods.
I fully agree with the points raised in the extensive and complete literature review. Also from my experience with these methods,
PDHG typically tends to perform much better than "matrix-free" implementations of ADMM or DRS.

A comprehensive comparison to other FOMs for LPs (eg. [21,28,41,63,64] mentioned in the introduction) would have been nice to see, but likely
out of scope for this work given the already very extensive experiments. Still, it would be nice to know whether PDLP is expected to perform
better than, e.g., the ECLIPSE method.

However, I see this more of a problem with the field of first-order methods of convex optimization, where countless algorithmic variants and tweaks
are proposed but not properly evaluated on challenging standard benchmarks. This paper performs a strong experimental evaluation, which can serve
as a baseline for further algorithmic developments. 

In the introduction, the paper mentions that FOMs for LPs might not have a "tailing" effect due to the linear convergence rate. I found this to be
a bit misleading. To best of my knowledge, such convergence rates are all based on Hoffmann's constant which is a very loose worst case bound which
does not coincide with the practical performance at all. Rather, the fast convergence could be due to a quick identification
of the active set of constraints at the solution. Once the active set is identified, typically much faster linear convergence rates
than Hoffmann's bound apply. 

After reading the paper, I was wondering why PDHG was considered, since there are many other matrix-free first order methods. Was it simply the one
that performed best in practice or is there something special about it? I feel that the fast gradient method (with restarting) on the homogeneous self-dual embedding as considered in the paper 
by Neocara, Nesterov, Glineur, "Linear convergence of first order methods for non-strongly convex optimization", 2019, Sec 6.4 with similar enhancements
could also be strong candidate for linear programming. 

For the experiments, the number of KKT passes is limited to 100.000 / the solve time to 1 hour. Was there a specific reason for this limitation?
Can more problems in the MIP library be solved by increasing this limit, by say, factor 10x, or are there some problems which are completely "out of reach" for first-order methods? 

One might argue that the weak point of the paper is perhaps its originality, since most considered heuristics are already known. 
But there are some novel ideas, for example the considered combination of Ruiz+Pock/Chambolle diagonal preconditioning, which 
has a surprisingly strong effect on the performance in my opinion. 

This is a matter of taste, but as mentioned, I would have liked to see a longer concluding discussion on what have we learned about
linear programming or PDHG/first-order methods from this study. Does the paper generate any new insights or shed new light on the nature of PDHG?
Does it the paper open up directions for theoreticians to work on?

For example, as shown in experiments, preconditioning of PDHG often drastically improves the
performance. But preconditioning for PDHG is far less understood than preconditioning for linear systems. For linear systems, a direct connection
of the condition number to the convergence speed can be made. But for nonlinear problems like linear-programming,
what is a good notion of "condition number"?  Can we develop a theory which guides
the design of better preconditioners, similar to the theory of preconditioning for linear systems? 

limitations_and_societal_impact: The limitations of the approach are clearly mentioned throughout the paper; it is acknowledged that there are no convergence guarantees
and that the paper presents mainly a heuristic approach which works well in practice.

I don't believe that the paper needs to address possible negative societal impacts.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents PDLP, a practical first-order method for linear programming (LP) that can solve to the high levels of accuracy that are expected in traditional LP applications. The proposed algorithm is matrix-free and can scale to very large problems. The core idea is based on the saddle-point reformulation of LP and the celebrated primal-dual hybrid gradient (PDHG) method (cf. Chambolle and Pock, 2011). Combined with several new techniques, e.g., diagonal preconditioning, presolving, adaptive stepsizes and adaptive restarting, PDLP improves the state-of-the-art approaches, including SCS, by a significant margin. Experimental results on PageRank applications are encouraging. 

main_review: Pros: As far as I could see, the mathematics appears to be intuitive, theoretically sound, although I did not check the details thoroughly. Despite the lack of the convergence results for several heuristics, the extensive numerical experiments were presented and supported the practical benefits of this new approach. That's the thing that I liked most about this paper since it aims at some useful approaches in real scenario. The strategies for tuning stepsizes as well as the restart criteria and diagonal preconditioning make a lot of sense to me and I appreciate that the authors put effort to explain why these techniques are useful from a practical perspective. This is an important contribution of the paper.

Cons: One of the reasons that I did not give this paper a higher score is that some relevant literatures are missing. For example, due to a very specific structure of LP, some specialized second-order algorithms exhibit superior practical performance in real applications. (also with theoretical guarantee)

X. Li, D. Sun, K. C. Toh. "An asymptotically superlinearly convergent semismooth Newton augmented Lagrangian method for Linear Programming", SIOPT, 2020. 

A. Ali, E. Wong, J. Z. Kolter, "A semismooth Newton method for fast, generic convex programming", ICML 2017. 

The presolving and diagonal preconditioning techniques are also combined with some first-order interior-point methods for LP. The resulting approach outperforms SCS on NETLIB collections and some other ML datasets thanks to these heuristics. 

T. Lin, S. Ma, Y. Ye, S. Zhang, "An ADMM-based interior-point method for large-scale linear programming", Optimization Methods and Software, 2021. 

Moreover, on account of the unique role of NETLIB collections in LP history, it would be better to evaluate PDLP on some of these datasets and see if this approach is sufficient robust in practice. 
limitations_and_societal_impact: 1. I encourage the authors to do further literature review and include other recent methods for LP, especially FOMs. 

2. It would be better to evaluate PDLP on NETLIB collections and see if it still behaves well on hard LP instances. 

3. There are a couple of typos in the paper and the descriptions and language could be clearer in places.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors investigate several heuristics to accelerate the PDHG algorithm, when applied to solve large-scale linear programs.
main_review: 1) My main concern is that there is no formal proof of convergence, let alone linear convergence. linear convergence of the PDHG for linear programs (and a wide range of other problems with metric subregularity) has been shown in
Alacaoglu et al. "On the convergence of stochastic primal-dual hybrid gradient". So, you should explain for each heuristic whether it keeps or not the convergence guarantees. Preconditioning preserves convergence [53], but I don't know for the other heuristics.
2) Your proposed line search is said to be faster that the one in [37], but there is no formal statement that is is valid.
3) This is a paper on convex optimization, the relationship to machine learning is not clear enough to me to justify publication in NeurIPS. A journal on optimization would be more appropriate.
4) I am not sure, but I think that the stochastic PDHG in "Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications" could be applied to LPs, using at every iteration activation of a random row of A or G. I would be much more convinced by such a study than by the present one, in the context of NeurIPS. 

A remark: PDHG converges when tau.sigma||K||^2 <= 1, not <1, as proved in [18]. And fastest convergence is obtained in practice when tau.sigma||K||^2 = 1, so you should set eta=1/||K||.

=== update after author response period
I read all reviews and corresponding authors' responses, and I think that the authors did a very good job in responding, in a professional way, to all concerns raised.
You convinced me about the value of the paper for the practitioners willing to solve large LPs in practice. So, I revise my judgement about Neurips not being the most appropriate venue for the paper, and I recognize that the contributions are interesting for the Neurips community. Also, your reply to my point 4. is well argued. Therefore, I am increasing my score from 5 to 6. With some formal statements about convergence, I would have put an even higher score.
limitations_and_societal_impact: Not applicable
review_title: null

Meta-review: Thank you for your submission to NeurIPS. All four reviewers agree that the paper is valuable because it solves an important practical problem well. Initially, there were some concerns regarding the novelty of the methods, and the heuristic nature of the methods. Fortunately, most of these concerns were adequately addressed after discussion with the authors. Please ensure that the camera-ready version is adequately revised to capture the points raised during the discussion period, as these were important in helping the reviewers come to their final decisions. 
Decision: Accept (Poster)