Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: The paper studies the problem of solving LP and more generally convex programming via sketching based approaches. In particular, the running time of proposed algorithm in this paper matches the running time of the best known algorithms [Cohen et al(19b) and Lee et al(19)]. However, this paper provides some further useful properties: 1) oblivious sketching, 2) sparse sketching which can be of interest in many applications. The paper has provided theoretical guarantees of their proposed algorithm. The problem that is studied in this paper is very important and the sketching based approach is also very practical. The paper would benefit from an empirical comparison of the proposed algorithm with the existing methods for solving LPs.  

Also, one way of motivating the new approach is the use of sparse sketching methods. Recently for several tasks in numerical linear algebra it has been shown that NN can learn efficient sparse sketching matrices which outperform the standard "randomized" sketching constructions such as CountSketch.  

However, my only concern is whether ICLR is the right venue for this purely theoretical paper. While I am supportive of the paper I can understand the potential objections regarding lack of empirical evaluations.  

Minor Comments:
- fix quotation marks (e.g., the "iterate and sketch" in the abstract.)
- page 2: We only updating -> We only update
- page 2: our method decrease -> our method decreases
- page 2: sketching methodology proposed by Clarkson and Woodruff'13. I would instead say Sarlos'06 and Clarkson and Woodruff'13
- page 3:  generalizes to subspace -> subspace embedding
- page 4: Literature Vaidya (1989) shows -> The work of ... shows that
- page 4: ... potential function characterize -> charcterizing
- page 5: rephrase the sentence before Def 2.2
- page 6: matricesand -> matrices and
- page 7: state-of-art -> state of the art (fix all instances)
- page 7: The new update ->The new update rule
- page 7: solve the linear system inexactly -> solve the linear system approximately?
- page 7: the feasibility of our approach prevents us from the complicated analysis -> maybe need to rephrase it? 
- page 7: implementing of Eq. (4) reduces back -> implementing Eq. (4) reduces
- page 8: we only need to do matrix-vector multiplications. How many such multiplications are needed? O(1)? specify it.
- page 8: fasten -> speed up?

=====POST-REBUTTAL COMMENTS========
As I mentioned earlier in my review, I like the result and I feel it could be interest of the TCS community. However, as correctly raised by other reviewers, ICLR may not be the right venue for this paper and also it would be beneficial if authors improve the presentation of their result and the motivation of their work further. 
review_title: Nice result with theoretical guarantees

final_score: rating: 4: Ok but not good enough - rejection
review_content: SUMMARY: The paper is based on the works of Lee et al and Cohen et al. Building upon these works, the paper comes up with an interior point method that matches the state-of-the-art in LPs. The paper's contribution is in a new type of sketching used inside the interior point method, that demonstrates some advantages over those of Lee et al and Cohen et al. Notable among these advantages are (1) the ability to preserve sparsity of an LP, and (2) exact solutions to the system of linear equations obtained from optimality conditions. 

REVIEW: I don't think the paper is ready for publication yet, since it needs significant polish and strengthening. My reasons are stated below. 

1. My biggest issue with the paper is that the motivation doesn't seem strong enough to me. If, despite being able to use exact solvers in each step of the IPM, the paper is able to merely match the run time of Lee et al and Cohen et al, then what is the advantage of doing the exact solves? I think the paper could be greatly strengthened if they are able to apply this technique to *improving* run times of some problem classes, as opposed to just matching state-of-the-art on one problem class.  

2. While one could argue that using exact solvers and having feasibility in each step is theoretically interesting, I personally don't think it's interesting enough to merit publication at ICLR; of course, this is a subjective matter of taste, so one could argue otherwise as well. However, I think if this were to be of interest to the broader theoretical CS audience (beyond the handful of researchers that have worked on this problem in the recent past), then the paper's scope would need to be wider. Can the authors try to make more changes to these methods and *still* match the state-of-the-art? With the current modifications, to me, the paper doesn't seem sufficiently different from previous works to merit publication. 

3. The sketching techniques shown are not different enough. I have the same comment about it as 1. and 2.

4. I feel the writing also needs to be significantly improved. Leaving aside error of language and grammar, what I think needs a vast improvement is the story-telling aspect of the paper. There needs to be greater effort put into telling *why* characteristic X of algorithm A is "bad" or "good", *why* some question is interesting, etc. I think, at its current state, the paper can be read and comprehended by a very small handful of people (the ones whose works are cited), and that, to me, is really not enough. 

5. Finally, I was disappointed that a paper marketed as so heavily theoretical, there is not even a proof sketch shown of the high level technique or any of the technical contributions. I shouldn't have to go to the appendix to see these, and the authors should put some effort into putting some math into the main body. I believe that highlighting novel proof techniques in the main body would also go a long way into convincing the reader(s) (such as myself) of novelty of the paper's contributions. 
review_title: Oblivious sketching based interior point method matching state-of-the-art LPs

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary:  The authors propose a randomized linear program solver that applies sketching to the central path calculations. The resulting algorithm maintains feasibility and employs oblivious sketching matrices as opposed to other randomized solvers. The algorithm is relatively simpler to describe. However, the requirement of feasibility and oblivious sketching is not well motivated.


Major comments/questions
1. The difference between oblivious and non-oblivious sketches.
The advantage of the oblivious sketching is not well explained and motivated. Is there an algorithmic advantage of the oblivious sketching methodology? Oblivious sketching has clear advantages in streaming data settings, however it's not clear what would be the benefit in an iterative algorithm with an obvious sketch. Given that the computational complexity is the same as leverage score sampling based non-oblivious sketching based methods, the authors need to provide a stronger motivation.

2. Maintaining feasibility.
It's not clear why exact feasibility is important in this class of randomized algorithms. Maintaining approximate feasibility should be possible to obtain relatively easily in the state of the methods. Please correct me if I'm wrong.

3. Sparsity.
The authors mention destroying the sparsity pattern as a shortcoming. Does the proposed method leverage input sparsity and sparsity pattern? Is it possible to quantify this, e.g., in terms of the number of nonzero entries?


Minor comments/questions

1. Left and right sketch.
Can you clarify what is the algorithmic consequence of the left/right sketching property in Table 2.

2. Coordinate-wise embedding
It looks like coordinate wise embedding property is a standard property that is satisfied for almost all known randomized JL embeddings, as opposed to a new construction. Is there a known JL construction that doesn't satisfy the coordinate-wise embedding property?

3. In corollary 2.8, what are the dimensions of A_i ?
 
Minor comment
1. Some small typos
page 1 footnote 1. Missing word or typo in 'We use O* hides;
page 2 'linear programmings'. I believe 'linear programs' is more idiomatic.
review_title: This paper analyzes a randomized linear program solver that employs oblivious sketching and maintains feasibility. However, the requirement of feasibility and oblivious sketching is not well motivated.

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper improves robust central path based methods for linear programming. It's able to keep intermediate matrices oblivious, and solutions feasible. It builds upon a line of recent work that solves linear programs in time proportional to the cost of inverting a single matrix.

In my opinion, these improved methods are of mostly theoretical interest: if one assume n^{3} time matrix multiplication, the rank-1 update schemes from the original Karmarkar paper already obtain an n^{3} runtime. Such gains also hold for more intermediate values of matrix multiplication (e.g. Strassen fast matrix multiplication has bene implemented, so 2.8 is a reasonable assumption from practical perspectives), but I think the 2-batch update scheme of Vaidya is already sufficient as well.

Therefore, I'm concerned whether this paper is suitable for this venue. There are no experimental evaluations of the algorithm, and the theoretical gains are too reliant on the matrix multiplication exponent being < 2.5.
review_title: theoretical result, unclear implications

Meta-review: The reviewers found it hard to understand the motivation of using both oblivious sketching and maintaining feasibility throughout the course of the algorithm, given that the ultimate running times matched those of existing work. Because there wasn't a concrete improvement over prior work, the worry is what the impact of the paper would ultimately be. There was also a concern with novelty, similarity to the work of Cohen, Lee, and Song, and a reliance on fast matrix multiplication exponents. The paper could also benefit from an improved presentation. 
Decision: Reject