Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work proposes to apply a Jacobi-based approximate eigenvalue decomposition method in proximal slitting algorithms for minimization of convex spectral function with matrix variable. The adopted Jacobi-based method is used to compute proximal operators in each iteration, and by taking the previous iterate as the initial point, the Jacobi-based method appears to reach required accuracy within fewer sweeps. The method can be parallelized, and its GPU implementation shows improvement in efficiency compared with standard eigenvalue decomposition functions in LAPACK and CUSOLVER in numerical experiments.
main_review: The Jacobi-based approximate eigenvalue decomposition method is not novel, and its cyclic and parallelized implementation is also not new. These are introduced in section 3.1. There is certain novelty in applying the method to compute proximal operators in proximal algorithms, which is introduced in section 3.2. In order to better clarify the contribution, it is suggested that section 3.1 and 3.2 should be separated into two different sections, since the former is a review of existing work, and the latter is the main contribution.

The significance and novelty can be improved by bringing more theoretical insights. For example, is the number of sweeps bounded by the increment between the previous and current iterates? How many sweeps would be required for a certain class of proximal algorithms such as ADMM?

Randomized approximate eigenvalue decomposition (or singular value decomposition) has been an active research topic. How is the adopted Jacobi-based method compared with these randomized methods? It is suggested that such discussion should be added in the related work, and in the experiments the proposed approach should be compared with these methods. 

From the experimental results in Table 1, one sweep of the Jacobi method is about 10 times faster when n is moderate (256 or 512), but the improvement is only about 3 times when n is large (2048). Does it indicate that the advantage would become less and less when n scales up?

In the experiments, there are some parameters in the accuracy $\epsilon_k$, namely, the scale taking values 0.1 and 1 and the power taking value 2.5. Are these parameters carefully tuned? Are their choices crucial to the performance?
limitations_and_societal_impact: It would be better to provide certain bound on the complexity of the method and to compare it with existing randomized approximate eigenvalue decomposition methods, in order to better demonstrate its advantage and limitation.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes using a classical but often unused method for computing the eigenvalue decomposition of a symmetric matrix: the Jacobi method. The method simply iterates by zeroing out off-diagonal entries using Givens rotations one at a time, until the matrix converges to a diagonal matrix. It is further noted that it is possible to parallelize the removal of ~n/2 entries at a time if disjoint indices are picked (for a matrix of size n-by-n).

Proximal methods are a popular choice for solving convex optimization problems over matrices. A commonly required oracle for such problems is the computation of the (full) eigenvalue decomposition of the current iterate, e.g., to compute the projection of the iterate onto the positive semidefinite cone. It is observed that as the iterations progress, the distance between iterates decreases and so the eigenvalue decomposition of consecutive iterates is not perturbed too much. Therefore, it is expected that few sweeps of the Jacobi method are required to compute the (approximate) eigenvalue decomposition of the next iterate.

The paper further provides bounds on the error of the prox operator as a function of the Frobenius norm of the matrix of off-diagonal entries of the iterate of the Jacobi method. This allows one to establish termination criteria in order to run the Jacobi method to obtain an approximate eigenvalue decomposition, while guaranteeing convergence of the (approximate) proximal algorithm.

The authors provide some numerical experiments on several matrix optimization problems such as solving sparse inverse covariance selection, SDPs, nuclear norm minimization, for small to moderately sized problems. Their experiments show that using the Jacobi algorithm for a small number of sweeps obtains sufficient accuracy to proceed to the next iteration of the proximal algorithm, and therefore reduces the overall wall-clock time to convergence, compared to using an eigenvalue/singular value decomposition implemented on CPUs or GPUs.
main_review: Originality:
I've not seen the Jacobi algorithm applied in this way, so as far as I can tell, the result is original. Though most results in this paper are not particularly new, there is merit in combining the ideas of using a few Jacobi sweeps (with guaranteed and easy to compute convergence criteria).

Quality:
Overall, the results of the paper appear sound, though I have some comments about certain results and experiments.
  - Beginning of section 5: I do not see the significance of comparing a single sweep of the Jacobi algorithm against the computation of the full eigenvalue/singular value decomposition. A single sweep will not compute anything meaningful and obviously does less work than any full decomposition, so Table 1 is not helpful and in general misleading
  - Numerical experiments in general: these problems are quite small by today's standards, and the iteration time per problem is quite fast (on the order of ms) for all methods involved. Especially given the message of the paper, which focuses on exploiting parallelism for large scale problems, it is necessary to increase the size of the problems in the experiments section.
  - Remark 1: what floating point precision was used in your experiments? It is clear that continuously applying givens rotations would result in loss of orthogonality over time, but this can be addressed by re-orthogonalizing U periodically (which s equivalent to 1 sweep of Jacobi; in fact, it should be faster since it can be implemented using BLAS 3 operations on the GPU).

Some other comments:
  - It would be helpful to include convergence results for the cyclic Jacobi methods. The authors provide convergence results for the classical method that picks the largest off-diagonal entry, but this algorithm isn't used in this paper.
  - Out of curiosity, are there convergence results for a randomized Jacobi algorithm.
  - For each experiment, what was the fraction of time spent running the Jacobi sweep vs. computing the Frobenius norm of the error? In fact, how often was the Frobenius error computed to determine whether sufficient accuracy was reached?

Clarity:
The paper is overall well-written, and I think communicates its ideas well.

Significance:
If this paper can be shown to work well on truly large scale problems, then it's significance would be improved. However, with the current experiments, it's difficult to say that it's a truly significant result.
limitations_and_societal_impact: As discussed in the previous section, my main concern is over the numerical experiments, and seeing this applied on truly large scale problems, rather than those that can be solved with conventional approaches quickly already.

I do not see any issues regarding this work and potential negative impacts on society.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a new method to accelerate proximal-mapping based algorithms  where the proximal mapping usually needs computing the eigen/singular value decomposition.   The authors discusses how to use the Jacobi method to get the eigen/singular value decomposition approximately and parallelly,  and the convergence can be guaranteed by easily controlling the norm of the off diagonal elements.  
Numerical experiments show the significant improvement over the state-of-art algorithms.
main_review: This paper is well-organized and well-written in general.  I have the following main comments:
1. The property of the spectral function in Theorem 1 will play a key role in proving Theorem 2. I suggest clarifying it in section  2.

2. The assumptions on $F(X)$ should be put in  the assumption environment so that the statement of Theorem 2 becomes more clear. 

3. It says 'One consequence of this is that the Jacobi method can have faster convergence if off(A) is small, whereas
  this is not the case of other algorithms that start by a reduction into tridiagonal form.' I'm not sure about this. Could you give more details in why the warm-start does not work in other eigenvalue algorithms? For example, can this be verified by experiments? The current implementation in NumPy solves the eigen decomposition exactly.

Minor comment:
The stopping criterion of in Section 5.1 and 5.3 should be given. 


 
limitations_and_societal_impact: Not apply.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers proximal algorithms for convex optimization problems over matrices. When the function to be optimized involves a function of the eigenvalues or singular values of a matrix, then prox methods need to evaluate the proximal operator in each iteration which usually boils down to a full eigenvalue decomposition or SVD. This can be very costly. The paper proposes to use the Jacobi eigenvalue algorithm for computing such decompositions. The Jacobi eigenvalue decomposition can be warm started with the decomposition from the last iteration. On average, a good enough approximation to the eigenvalue decomposition can thus be computed by less than one sweep ($n/2$ parallel Givens rotation) over the matrix. Hence, the evaluation of the proximal operator in ADMM or prox algorithms can be speeded up significantly (by a factor of 5 to 20).

Convergence results are provided and experiments validate the approach and its efficacy. 
main_review: The paper is very well written and a pleasure to read. It provides a very nice introduction to the Jacobi eigenvalue algorithm and uses it within the framework of (approximate) proximal methods. I did not check the proofs but the theorems seem correct. The core contribution of the paper is to bring Jacobi's eigenvalue algorithm 

Some concerns though: 
1. The paper uses the resulting algorithm for solving three problems in the experiments: (i) sparse inverse covariance selection, (ii) semidefinite programming, and (iii) low-rank matrix recovery. All experiments are run on synthetic data. There are better algorithms to solve these problems. For (i), use [1] or [2]. For (ii), make use of interior point methods for problems of this scale since they considerably need fewer iterations. For (iii), use a Frank-Wolfe type algorithm. These are the standard methods to solve each of these problems and they are considerably faster than the ADMM approach presented here. While the presented approach is nice and general, one would not use it in order to solve these problems on real-world machine learning instances. Hence,  I do not know, whether NeurIPS is the right venue for such a paper. Maybe some optimization journal/conference would be better suited.

2. The improvement in speed-up for each eigenvalue / SVD decomposition is provided. It would be nice to also report the total solving time, since this speedup does not translate to an overall speedup, e.g., in the case of the SDP experiment, it seems a factor of two improvement in the end.

3. Comparison to state-of-the-art approaches on real-world problems/data would be nice for an ML conference.

4. It is stated in the introduction that there are first-order methods that do not require solving a full eigenvalue decomposition / SVD but instead only need one eigenvector (Frank-Wolfe type algos for instance). It would be nice to also compare to such algorithms in the experimental section, since they are usually much more efficient and to provide a better global picture. 

5. What about interior point algorithms? They need much fewer iterations and since a full eigenvalue decomposition is computed in each iteration, the per-iteration complexity is comparable. Especially the size of the problems (up to 1000 x 1000)in the evaluation suggests using IP methods instead.

So all in all, the paper is really nice, but I am not sure if it is a suitable contribution for the ML community. 

References:
[1] Cho-Jui Hsieh, Matyas A. Sustik, Inderjit S. Dhillon, Pradeep Ravikumar. Sparse Inverse Covariance Matrix Estimation Using Quadratic Approximation. In NIPS 2011.
[2] Cho-Jui Hsieh, Matyas A. Sustik, Inderjit S. Dhillon, Pradeep K. Ravikumar, Russell Poldrack. BIG & QUIC: Sparse Inverse Covariance Estimation for a Million Variables. In NIPS 2013.

limitations_and_societal_impact: N/A.
review_title: null

Meta-review: The submission studies the application of the Jacobi method to compute approximate eigendecompositions or SVD in the context of solving composite optimization problems over matrices, where the objective functions are spectral. The main theoretical contribution of the paper shows how the error in the approximate decomposition (in terms of the $\ell_2$-norm of the off-diagonal entries) propagates into the analysis of proximal gradient descent and proximal accelerated gradient descent. The AC agrees with the reviewers that this is an interesting result, albeit fairly simple given previous work of inexact oracles for proximal methods. Moreover, the reviewers and the AC all find that the paper is well-written, making the technical contribution easy to grasp.

The main practical contribution is an experimental evaluation of the resulting Jacobi-based method against the  analogue QR-based methods, which generally shows the superiority of the Jacobi method. This is partly explained by the fact that the Jacobi method can effectively use previous decompositions as warm starts for the next. The AC agrees with reviewers BV6g and KM7u that the significance of such experiments would be increased by including larger matrices and real-world datasets. 

In conclusion, the AC believes that the interesting and well-explained theoretical contribution, together with the positive results on the experimental part, outweigh the lack of larger experiments and recommends that the paper be accepted.
Decision: Accept (Poster)