NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID:7941
Title:Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression

Reviewer 1

The paper proposes a simple algorithm for L_p regression problems and justifies its efficiency both theoretically and empirically. Major concerns: 1) Related work: The comparison with related works is not sufficient. [AKPS19] has a (log(1/\epsilon))^2 dependence in the number of iterations, but it is not mentioned in Section 1.1. In Section, it only compares with the polynomial dependence. 2) As mentioned in the related work, the dependence on m of the proposed method is marginally worse than Bubeck et al. [BCLL19] and Adil et al. [AKPS19] but the overall comparisons are not clear. What are the advantages of the proposed one? Furthermore, the lack of sufficient baselines (at least Bubeck et al. [BCLL19] or Adil et al. [AKPS19]) in the numerical experiments weakens the superior of the proposed algorithm. 3) This paper needs significant rewriting. One example is the logic in the first paragraph of page 2 (line [34] to [40]). It first says that the convergence in solution is more important than function values, and then argued that this paper will measure the convergence in the function value. Figure 4 needs more spaces between subfigures to avoid confusion. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The authors answered several questions regarding the comparison with existing methods. They are mainly on the theoretical side. The numerical part is difficult because there is no available codes. Theoretical results are mostly based on the worst case, so the referee is not fully convinced by the response on the numerical part. Still this is a good submission, and the overall score will not be changed.

Reviewer 2

The paper proposes a novel IRLS method to solve l_p linear regression for p>=2. The method is the first IRLS algorithm with provable linear convergence to the optimum. The paper is clearly written and well structured and easy to read. The obtained results (Thm. 3.1) are currently state-of-the-art for the given problem class. Furthermore, the experiments are reasonable. Although I did not go through the proofs, the obtained results are believable. Overall, I do not have any objection against the paper, and I think it is in good shape to be accepted. However, I must say I am not an expert on the IRLS algorithms. Minor comments: 1) l. 99: p-IRLS is said to be far simpler to implement to methods mentioned in the previous paragraph. This is not completely true; as the method from Maddison et al is in fact way simpler to implement to p-IRLS. Furthermore, the method from Maddison et al also allows for the linesearch. I suggest the authors make the mentioned paragraph more clear. 2) The author names in the references are inconsistent, some have fist name shortened while others do not

Reviewer 3

This paper is clearly written, well-motivated, and, to the best of this reviewer's knowledge, the proposed algorithm and corresponding analysis are novel. Of course, one may claim that the level of originality is limited, given that the proposed algorithm is nothing more than the combination of a couple of improvements to IRLS that had been independently proposed before, but the way in which they are combined and the corresponding analysis is novel. Moreover, the resulting algorithm is extremely fast in practice, as shown in the experimental section of the paper. -------------------- After reading the other reviews and the authors' response, I see no reason to change my score (8).