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: The paper studies the important non-negative least squares problem. The authors obtain stronger guarantees than for traditional least squares by assuming that the data matrix A is also non-negative. They showed that the problem can be solved up to multiplicative error and with complexity that is independent of any matrix constants.
strengths_and_weaknesses: The paper is clear and develops a quite fast algorithm for the NNLS+ problem. It shows convergence by using a nice combination of a relaxed gap function combined with a random coordinate update. 

The problem for me is how relevant the problem NNLS+ is. I think that the argumentation should be stronger because it is not clear, in principle, how and when this particular instance of NNLS would be interesting. Very precise references linking it to the applications should be presented. For example, Proposition 2.1 is very strong and it is not so clear what would happen without it (e.g. the choice of the box-constrained property of the optimum).
The numerical section needs to be reformulated, in my opinion, and more extensive (and simpler) numerical results should be presented, as I discussed in the "questions" section. Sparse vs dense ground truths usually present different behavior for the NNLS problem. What happens with SI-NNLS+in this case?

Even though something was mentioned on line 180, it would be important to stress, at least in the appendix, why this new algorithm is not a simple application/modification of the VRPDA algorithm in order to make the importance of novelty even more concrete.
questions: Line 29: "without the need to tune a regularization parameter or perform cross-validation [33, 6, 13]". I would add the references https://ieeexplore.ieee.org/document/8022909, https://ieeexplore.ieee.org/document/5608519 and https://arxiv.org/abs/1901.05727 given the theoretical importance that they have for the problem.

Line 32: "This is true, for example, in problems arising in image processing, computational genomics, functional MRI". It would be very interesting to have at least one example where this is clearly the case and/or references for each of these applications where it is crucial to have positive data since this is crucial for the paper.

Lina 40: Even though it seems to be correct, it is not well written. I would suggest rewriting this part.

Line 48: what is nnz(A)? Is it the number of nonzero elements of A? It should be clearly defined already at line 48.

Line 57: "What is significant about Theorem 1.1 is the invariance of the computational complexity to the scale of A—it does not depend on any matrix constants". Could you please explain the nature of this invariance? It is something that I didn't understand from the manuscript. Why does the positivity data give this invariance "for free" to the least squares problem? Would it be the case for other constraints as well?

Line 87: "for problems with strong convexity, a property not satisfied by underdetermined systems". If the matrix satisfies RIP, this is a form of strong convexity, at least when applied to sparse vectors. This sentence needs to be changed and more should be commented on that issue. I think that TNT-NN still works well for problems without strong convexity, even though there are no theoretical results to support it.

Line 100: "[16] and [24] mentioned in the preceding paragraph provide only asymptotic convergence guarantees". As far as I know, reference [24] (or its auxiliary paper https://ieeexplore.ieee.org/abstract/document/8425520) does not establish convergence of TNT for NNLS. It is a good algorithm in practice but without any theoretical guarantees.

Line 104-114: It would be simpler to visualize these algorithms on a table with the different results and assumptions that each one of them needs.

Line 142: I understand the change of variables. But matrix A will change as well. This should be stated in the paper. And what are the implications of this fact?

I dont understand the Lagrangian defined after line 158 and its construction is a crucial part for the analysis, if I understood correctly. I understand that you recover your primal problem from it but I don't understand why it is natural or what is the connection with the "standard" Lagrangian. Am I missing something obvious? 

Line 182: Implementation version of Lazy SI-NNLS+. Is "Lazy" part of the name of the algorithm? If I understand correctly, in line 701, you described that the update of \tilde(x)_k and \tilde(y)_k would not be efficient if the matrix is sparse and, therefore, you have a lazy version of the algorithm. It would be interesting to briefly comment on this difference in the main text. I understand that on line 744 you mention the equivalence between Algorithms 1 and 2 but this should be in the main text somehow.

Line 227: You employ a randomized coordinate update in order to reduce the per-iteration complexity. But can you get a deterministic result as well without the randomized coordinate update?

Line 277: "Numerical experiments and discussion". I understand that there is a lack of space but for this kind of contribution I think it is crucial to have detailed numerical experiments. Or have more extensive experiments in the appendix. In the case of NNLS, a comparison with the Lawson-Hanson algorithm is very important given how much it is used in the literature. Maybe a comparison with TNT-NNLS as well since it was mentioned and it works really well in practice. I would also add a comparison with PGD and accelerated PGD with restart. I think that a comparison of all algorithms in situations where the matrix does not have RIP as well as matrices that are very ill-conditioned should be performed. And tests with synthetic and simple data to understand better what is going on. Also, differences between problems with sparse ground-truth versus dense ground truth. This is really important to convince a general audience of the usefulness of the algorithm in different situations.

Since the matrix A has all the entries positive, the matrix obviously satisfies the M_{+} condition (see, e.g., https://ieeexplore.ieee.org/document/5608519). What happens to your algorithm when the matrix A does not satisfy the M_{+} condition but does not have all the entries positive? What is the behaviour of the algorithm for the case that the ground truth is sparse?

limitations: As mentioned before, it is not clear how important the NNLS+ problem is and how the technique developed in this paper would be useful for NNLS problems under more general assumptions.

Also, it is not clear if the results are a simple application/modification of the VRPDA algorithm or not.

Moreover, the numerical section is quite limited and more extensive experiments must be performed.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work studies Nonnegative (linear) least squares problems (NNLS) where the data itself is nonnegative. This work shows an interesting result that the nonnegativity of data makes the problem easier. In particular, they are able to present a nice and clean result of error bound (or complexity bound given an $\epsilon$ error) that is independent of any matrix constants (for example operator norm of the matrix), in this nonnegative coefficient/data case. With a new adaptive restart strategy, a linear convergence theory is also established. As the authors already mentioned, this is the first theoretical guarantee for NNLS+ (with nonnegative coefficient matrix $A$) that simultaneously satisfies the properties of being scale-invariant, accelerated, and linearly-convergent. Numerical experiments demonstrate the superior performance of the proposed method on large-scale data. 
strengths_and_weaknesses: Strengths:

1. This work has a very interesting and novel idea that uses the assumption of nonegativity of data to accelerate the algorithm and establish the improved theory.

2. The theory looks very nice and clean. Most importantly, the theoretical results look strong. In particular, the time complexity bounds for the proposed algorithm(s) are scale invariant. Indeed, they primarily rely on nnz($A$), and do not rely on its matrix norm. This nnz($A$) dependence also suggests that the theory and the proposed methods handle sparse matrices well (even though their dimension could be large).

3. The results from the numerical experiments look impressive.

4. This work is clearly motivated, well-organized, and very well-written. The proofs also look correct. I really enjoyed reading this paper.

Weaknesses:

Given the current state of the paper, the only "weakness" I can think of is its nonegative assumption of data, which may limit its applications. However, I would NOT say that it is really a weakness, since it is this nonegative assumption that brings advantages to the proposed methods (it also motivates the entire paper). 

In summary, this work has made a strong contribution to the field of NNLS. It is well-written, and its idea is novel. Thus, I highly recommend accepting this manuscript.


questions: 1. The authors did a great job on improving the time complexity dependence from $O(1/\sqrt{\epsilon})$ to $O(\log(1/\epsilon))$ by introducing adaptive restart. I wonder if $O(\log(1/\epsilon))$ (linear convergence) the best one can do in theory, or, is superlinear convergence even possible in the NNLS/NNLS+ setting?

2. The running time of the proposed method seems to be quite sensitive to the batch size $bs$. Ideally, different $bs$ should be used for handling different sparsity levels of matrices. Is there a way to (roughly) choose this parameter before running the algorithm? It seems to be a complicated problem, as it also depends on how the hardware works.

limitations: Yes.
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 paper considers NNLS (nonnegative least squares) problems with an element-wise nonnegative data matrix and argues that in this scenario it is possible to obtain stronger guarantees than for traditional least squares. To support this claim, a scale-invariant iterative algorithm is provided that constructs an epsilon-multiplicative approximate solution. To obtain their approximation guarantees, the authors use the iterates of the algorithm to construct a sequence of upper estimates of the duality gap. The gap estimate itself is computed as a difference between an upper and lower bound on the Lagrangian. The gap estimate then enables them to obtain a bound on the primal error. The authors then describe how their proposed method can be combined with adaptive restart to obtain a linear convergence rate. The paper concludes with numerical experiments where the proposed method is compared to several competing optimization algorithms. The competing algorithms are outperformed in terms of runtime on one of three datasets while being competitive on the other two.

strengths_and_weaknesses: - Originality:
The paper provides a novel algorithm and proves its convergence. Moreover, the authors show how it can be adapted by combining it with a restart mechanism to achieve linear convergence. In the experiments it is shown to achieve competitive results.

- Quality:
The theoretical analysis seems to be sound but I was not able to check it in detail. The experimental evaluation is a bit weak and could be extended to more datasets.

- Clarity:
The structure of the paper could be improved, as the algorithm Lazy SI-NNLS+ is only defined in the appendix but already used in Theorem 4.1. It should at least be stated in the main paper that Lazy SI-NNLS+ is in fact equivalent to Algorithm 1, as proven in the Appendix. 

- Significance:
The paper's contribution is mostly technical and allows the authors to obtain stronger theoretical guarantees compared to earlier work. The techniques used to obtain those improved theoretical guarantees (including the use of the adaptive restart technique) may be of value for the optimization and machine learning community. On the other hand, the experimental evaluation shows that the proposed algorithm is competitive but not consistently better than competing algorithms.


----
EDIT: Taking into account the feedback of the authors during the discussion phase, I have increased my score.
questions: It is a bit confusing that in the plots in Figure 1, there is no consistent choice of batch sizes even for the same dataset, e.g. for the new20 dataset, the batch size 50 is used in the plot for the number of data passes (e) but batch size 10 is used for the time plot (f). How were the batch sizes chosen for each plot? The effect of the choice of batch size could be further investigated in an experiment.
 

limitations: The paper does not contain any discussion of the societal impact of the paper.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper considers the classical non-negative least squares problem, and makes an observation that when the 
data itself is also non-negative, this considerably simplifies the problem.  It proposes an algorithm inspired
by primal-dual variance reduction, and establishes scale-invariant (not dependent on matrix norms) multiplicative
convergence guarantees, and linear convergence using an adaptive restart technique.
strengths_and_weaknesses: Key strengths of the paper:
* pointing out that NNLS is significantly easier with non-negative data (called NNLS+ in the paper). 
* Developing a new optimization algorithms for NNLS+, and its detailed convergence analysis. 
* Numerical experiments show cases with significant improvement upon existing  methods (some comments below).
* The paper is clearly written.

Weaknesses:

1) I'm not fully convinced of the prevalence of NNLS+ (as opposed to plain NNLS) in applications. Taking NNLS+ and 
simply subtracting the mean, de-trending, or removing first principal component (or any kind of residual) will in general induce 
negative values in the data. Most practical applications of NNLS I've seen included some negative data. Even in the 
experiments both examples included negative data (1st example is indeed trivially addressed, while 2nd is not NNLS+). 
Also, since you applied the approach to plain NNLS in experiments -- can you comment on whether you expect the approach 
to be competitive for NNLS at large?

2) As you mentioned,  an important application of NNLS+ is to NMF.  Is the proposed approach competitive w.r.t. state-of-the-art 
NMF solvers? (Are these based on alternating NNLS -- or are there other approaches as well?)

3) It's worth mentioning other classical approaches to deal with non-negaitve targets, e.g. generalized linear models (e.g. Poisson 
regression). 

4) The paper claims that plain LS necessarily scales with matrix constants (e.g. spectral norms). In addition to iterative solution for
LS there are also exact direct solvers, which have finite termination.  Direct solvers can be very efficient for sparse matrices
with good structure (small fill-in).  Also preconditioners can dramatically increase convergence of iterative methods -- especially 
for near-chordal graphs.  So the statement seems somewhat too generic or misleading. 

5) There is some relevant work that would be helpful comment on / cite:  
There is a large body of work on multiplicative-update methods, e.g. see review by Satyan Kale, Elad Hazan and Sanjeev Arora, 
"The Multiplicative Weights Update Method: A Meta-Algorithm and Applications", which have a variety of applications (including NMF, 
online convex optimization, packing and covering).
For NMF specifically, there's work on separable (anchored) NMF, which has nice error guarantees, (Donoho et al, and Abhishek Kumar 
and Vikas Sindhwani, "Fast Conical Hull Algorithms for Near-separable Non-negative Matrix Factorization".

6) For numerical experiments -- you compared to plain FISTA, but it's well known that practical convergence can often be dramatically improved with adaptive restarts, e.g. "Adaptive Restart for Accelerated Gradient Schemes", Donoghue and Emmanuel Candes.  Since you employed adaptive restarts in your method -- it seems only fair to use them for FISTA as well.   Furthermore, it'd be helpful to improve the numerical experiments -- run on more examples, and comment why it performs well on certain problems and less well on others (e.g. in terms of runtime). Why are FISTA and OA+DS are so poor on E2006train -- is this due to ill-conditioning / poor scaling?   Also mentioning timing results w.r.t. competing code is not always informative -- as e.g. using advanced compiler techniques (SIMD/AVX512, e.t.c.) vs. say python for-loops can make orders of magnitude runtime difference in itself.  (So reporting that fast NNLS [5] took 6.63 days may mean that the algorithm is poor, or that the implementation is poor, or both). 
questions: 7) You report convergence in terms of natural residual.  Why is this a good measure (beyond being convenient for analysis).  It's worth 
commenting how well it translates to other standard convergence metric -- especially for the experimental section. Does your method work especially well under the lens of natural residual? 

8) Algorithm 2 is not defined -- is that the algorithm in Theorem 4.1?  

9) For restart versions we choose the best batch size in {10,50,300,500}.  For a solver to be used in practice -- how do you know (without 
running all versions) which batch size to use -- any heuristics? 
limitations: I would've liked to see more discussion of limitations and more thorough comparison with competing approaches.
review_title: null

Meta-review: metareview: The reviewers generally agreed that the paper has novel and solid contributions. Moreover, they were satisfied with the authors' responses. Please incorporate the reviewers' suggestions in your revision.
confidence: Certain
Decision: Accept