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: This paper studies the classical algorithm of IRLS for solving $\ell_p$ regression for $p \in (0,1]$. The algorithm updates between solving a weighted least squares problem and updating the weights, where the authors also use a dynamically updated smoothing (regularization). Under a stable range space property, which is satisfied by Gaussian matrices, the authors prove that IRLS with $p=1$ converges linearly. Furthermore, for $p<1$, the authors show that the algorithm converges at a superlinear rate provided that the algorithm has good local initialization.
strengths_and_weaknesses: Strengths:
- The paper is very clear and well-written.
- The authors give an improved result for the convergence of IRLS with $p=1$ over [15]. In particular, the result of the authors works under a generic condition and uses a better smoothing update rule.
- The result for superlinear convergence with $p<1$ is interesting, and the result extends to the case of $p=0$, which is the first time I have seen this in the literature.
- The choice of $p<1$ for phase retrieval achieves the theoretical minimum number of samples.

Weaknesses:
- There is not a novel algorithmic twist developed here, and the work is gauged to purely developing theory. How realistic is the assumption in the linear regression without correspondences that only $k$ of the rows are permuted?
- It is unclear how stringent the initialization condition in Theorem 2 is.
- There is not a driving application for this method, and it rather serves as a general-purpose methodology.
- There is no discussion of the choice of $p$ in practice. It seems like $p<1$ is beneficial. However, in the case of phase retrieval, it seems to do poorly in the balanced regime of $|I^+| = |I^-|$.


questions: - What is the point of the $(p,k,\eta)$ RSP when even for the case of $p<1$ you use the $(1,k,\eta)$ RSP?
- Is there a connection between the IRLS algorithm with $p=0$ and a Newton method, which is typical of exhibiting such quadratic rates?
- Does Proposition 3 hold for sub-Gaussian rather than just Gaussian?
- Since the regularization update as well as the reweighting scheme have been considered before, what are the “novel variants of IRLS” considered here? What other notions of IRLS with $p<1$ exist in the literature? Some examples are  
    - Mohan, K., & Fazel, M. (2012). Iterative reweighted algorithms for matrix rank minimization. The Journal of Machine Learning Research, 13(1), 3441-3473.
    - "​Lerman, G., & Maunu, T. (2018). Fast, robust and non-convex subspace recovery. Information and Inference: A Journal of the IMA, 7(2), 277-336
- What is the connection, if any, between RSP conditions and the notion of restricted isometry properties?


limitations: Limitations of the algorithm for $p<1$ are discussed in the example of phase retrieval. Also, the suboptimality with respect to $m$ is discussed in 177-179.
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: In this paper, the authors propose a new variant of iteratively reweighted least square (IRLS) algorithm and studied its theoretical property as well as the practical performance. The authors stated the stable range space property, which plays the fundamental role in the theoretical analysis of the new IRLS method. The authors showed that for the case of $p = 1$, the IRLS can achieve a global linear convergence rate. The authors also presented that for the case of $p \in (0, 1)$, the IRLS reach a superlinear convergence rate of the order of $2 - p$. Both local and global convergence rates can match the state-of-art results. The authors also conduct numerical experiments on different applications. And the empirical results showed that the performance of the IRLS algorithm is competitive against other methods.
strengths_and_weaknesses: This paper has the following strengths in terms of the originality, significance, quality and clarity:

Originality and significance: as far as we know, this paper provides the one of the first novel IRLS algorithm that could reach linear rate for the global convergence and superlinear rate for the local convergence. This is the main and independent theoretical contribution of this paper.

Quality and clarity: the authors provides detailed proof in the theoretical section and the consistent empirical results in the numerical experiments section. These empirical results show that the performance of the proposed IRLS method is competitive against other state-of-art algorithms in the application areas of real phase retrieval, regression without correspondences and robust face restoration. The new IRLS algorithm is specially good at handling the outliers, which is the key property in the problem of robust $l_p$ quasinorm regression. The paper is also organized with clear and clean structure and the language is well-organized so that the readers can easily understand the content of this submission.

However, despite the above advantages, the paper has the following weaknesses.

 The theoretical results only hold under the assumptions that $m$ must be much larger than the $n$ and $k$. However, in the numerical experiments, the IRLS algorithm also performs well under the condition that $m$ is comparable larger than $k$ and $n$. Hence, there is some gap between the theoretical analysis and the numerical experiments. Also the authors should mention in the paper any theoretical results for the case of $m$ is not large enough, i.e.,  assumption (10) doesn't hold. Is there any significant results for this special case?

Another minor issue is that the authors should add an independent conclusion section after the numerical experiments/applications section for the summary, discussion and future research directions of the paper.
questions: One question for the structure of the paper.

Could the authors put the discussion and future work on page 9 of the paper into one independent conclusions section? This can make the paper more clean and clear.
limitations: The authors have presented the limitations of this paper in the final page of the submission.
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 work analyzes the famous IRLS algorithm with any choice of $p\in [0,1]$ and the adaptively updated smoothing parameter $\epsilon_t$. It is able to establish global linear convergence theory for $p=1$ with arbitrary initialization. Unlike previous works, it also establishes local superlinear convergence theory with sufficiently good initialization, for any $p\in [0,1]$. Experiments confirm the advantages of IRLS with $p<1$.
strengths_and_weaknesses: Strengths:

1. This work improved the analysis and the result of the previous global convergence theory for IRLS with $p=1$.

2. The authors are able to show local superlinear convergence for any $p\in [0,1]$, which is not done in previous works.

3. The paper is very well-written. The previous works are reviewed in detail. The contributions are highlighted. The content is well-structured.

Weaknesses:

1. Although the stable RSP condition is satisfied for Wigner matrices, it does not seem to be easy to verify in general (one has to check all subsets of coordinates of size k). I understand that it was also adopted in some previous works, but it would be nice to have a condition that can be more easily verified in a general setting.

2. The radius of the convergence zone (RHS of eq. 13) for the nonconvex IRLS depends on the min over the nonzero residuals. Thus, the radius could be small when k (the number of nonzero elements), n, m are all large (consider an extreme case where $k,n,m\to \infty$), unless one can show that the smallest nonzero element is sufficiently far away from zero.


This work has made a nice contribution to the theory of the iteratively reweighted least squares, although there is still room for improvement on the theory side.



questions: 1. Would it be possible to analyze the radius of the convergence zone (RHS of eq. 13) under some probabilistic assumptions. For example, one may consider the entries of $A$, $x^*$ are i.i.d standard normal, $y = Ax^* +r^*$, where $r^*$ is k-sparse. The coordinates of nonzero elements of $r^*$ are randomly sampled, and its nonzero elements follow any smooth distribution with zero mean and finite second order moments. Would the RHS of (13) converge to 0 as $k=\lambda m$, $n,m\to \infty$ where $\lambda$ is a small constant? I suspect that it is true (since you take a min of a set of random variables that has a growing cardinality), but I would like the authors to confirm or disprove my conjecture.

2. Following my point 1, if my conjecture is true, would it contradict your claim in line 66 that your radius of local convergence does not diminish as $m\to \infty$? It probably won't diminish if $k$ is fixed even when $m\to \infty$ (not $k=\lambda m$), but the author should add some discussions about which assumption is more reasonable, and which one is more common in real practice. In some sense, $k$ should grow with $m$, but I welcome the author(s) to provide me with some counterexamples in real applications.

3. As for the experiments, the performance of IRLS-0.1 is very impressive. Is $p=0.1$ typically (approximately) the best choice in all experiments? What if you choose $p=0.05$? Also, how the IRLS-1 and IRLS-0.1 are sensitive to the choice of update rules of smoothing parameters (as you introduced in section 2.2)? Is the current update rule of $\epsilon$ critical to the success of the presented IRLS-0.1? It might be good to add some simple experiments in the supplementary material.



limitations: Yes.
review_title: null

Meta-review: metareview: Thank you for your submission to NeurIPS. The reviewers unanimously found the contributions to be solid, and the paper to be clear and well-written. All three reviewers unanimously recommend accepting the paper. One reviewer remarks that "it is actually interesting to see that the smoothing parameter plays a critical rule in the convergence of IRLS, and I believe that it has been ignored by many practitioners in this area." Please incorporate reviewer feedback in preparing the camera ready version.
confidence: Certain
Decision: Accept