Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The submission considers a Frank-Wolfe based algorithm for approximating Tyler's M-Estimator. Overall, main benefits of Frank-Wolfe based algorithms for this problem is the lower computational complexity per iteration. Compared to the standard fixed-point iteration, the computation complexity is improved from $O(np^2)$ to $O(np)$. Three variants of Frank-Wolfe algorithms are proposed, and sublinear convergence guarantees are provided for them. With a slightly milder assumption, the paper shows linear convergence. 
strengths_and_weaknesses: Overall, presentation of the paper is not very good. I do not see major benefits of presenting three variants in parallel. The authors could first have elaborated on the basic FW algorithm and develop the most basic ideas first, e.g., how to establish sublinear convergence and what are the main technical challenges. Then, the authors could have proposed two more variants (AFW, GAFW) that enjoys slightly better convergence, and faster convergence with slightly milder conditions. In its current form, it is very hard to understand what are the major technical challenges. Maybe more importantly, I wonder why the Frank-Wolfe approach is interesting especially when the scope of the paper is very specific to one objective function. There could be other approaches that lead to similar computational benefits other than FW. 
questions: - It is hard to understand why Assumption 2 brings a major improvement (from sublinear to linear), because it sounds very natural for all i.i.d. data. It would be better to come up with more directly related assumption for the improvement. 

- The linear convergence results could have been more stressed, instead of filling one full page (page 7) with a bunch of non-informative algebras. Please discuss the relation to the PL condition in a more detail, starting from the definition of it, in more detail. It could have made the paper more interesting. 
limitations: I do not see any negative societal impact.
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 proposes a Frank-Wolfe algorithm for
approximating a well-known covariance matrix estimator.
The estimator is known to minimize a particular non-convex,
locally gradient dominated function (as shown in Theorem 5)
over the set of positive definite matrices with a fixed trace,
i.e., a convex set which is a neither open nor closed.
These are atypical settings for a Frank-Wolfe algorithm,
nevertheless the paper establishes strong convergence results
for the original Frank-Wolfe algorithm and two variants with away
steps, e.g., linear convergence in function value
for the away-step variants
for a non-convex function over a non-polyhedral domain.
The convergence is for a quantity similar to the dual gap
for the original algorithm.

The computational results are poor: only one setting, wrong data displayed (accuracy in a help function of a method instead of accuracy for the original problem independent of method of solution, measuring cost via theoretical bounds instead of actual performance), making a claim even contradicting the graph.
strengths_and_weaknesses: The theoretical results are excellent for the theory of Frank-Wolfe
algorithms with correct proofs, even providing detailed discussion of theoretical upper bounds for costs of each operation.  A slight weakness is the presentation of results in Table 1: the last two columns display different measures of rates without this being clearly indicated.

Since the problem is specific to appplication of covariance estimators,
it would have been good to address performance for the original
covariance estimating problem, which it is meant to solve.
For this an accuracy measure for covariance matrix estimators should
be studied independent of the method of solution.

In the computational experiments,
such a measure ought to be displayed on the vertical axis,
instead of the function value of questionable practical relevance.

On the horizontal axis, the authors stated aim was a measure
independent of implementation issues, a worthy goal, but unfortunately
the chosen "estimated runtime" is the best worst-case known bound
on operation cost, which is heavily biased against
algorithms with high worst-case computational cost.
For example, such a measure would show the ellipsoid methpd
as far faster for linear programming than the simplex method,
despite the latter being faster in practice.
Due this error it is not possible to deduce acutal performance from the graphs,
e.g., the baseline FPI might have outperformed all the other algorithms.

The claim in Line 300 that GAFW is significantly faster than FPI
is contradicting to the graphs, even if we ignore the errors
discussed above.  FPI has the same performance on the right and nnly
slightly worse on the left, so the difference is insignificant.

Overall the computational results are worthless, and likely to cause only misinterpretations.
questions: None.
limitations: Not applicable.
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 paper discusses a new way of computing the Tyler covariance estimator, which is the solution $Q$ to the fixed point relation 
$\frac{p}{n} \sum_{i=1}^n \frac{x_ix_i^T}{x_i^TQ^{\*-1}x_i} = Q^{*}$.
Here, $p$ is the feature dimension and $n$ is the number of samples.
The usual method is to evaluate this iteratively, with $Q_k^{-1}$ on the left hand side and $Q_{k+1}$ on the right hand side. There are two main computational issues here: inverting $Q$, which is $O(p^3)$ and evaluating the matrix/vector multiplications $O(np^2)$ at each iteration.

This paper tries instead to find this fixed point using a Frank-Wolfe method, where at each iteration, they first compute a $1-\beta$-approximate LMO (a low rank matrix), and then merge it to $Q$ using a carefully designed merge parameter $\mu_k$. The idea is that FW is solving the (nonconvex) problem of minimizing $f(Q) = \frac{p}{n}\sum_{i=1}^n \log(x_i^TQ^{-1}x_i) + \log\det(Q)$ over the constraint $Q\succ 0, tr(Q) = p$. By using lanczos methods, the approximate LMOs can be found of order $O(p^2+np)$ per iteration, over $O(1/k^2)$ iterations to get to $\epsilon$ error.
strengths_and_weaknesses:  - The approach is very clever, and though is heavily FW based, is not a trivial extension at all. Especially, the choice of $\mu_k$ seems to have this method deviate from the usual rates ($O(1/k)$ not $O(1/k^2)$). 

 - After taking a "careful skim" of the paper, I do not see any red flags in terms of proofs or weirdly magical steps. However, there are some things I think should be clarified (see below).

 - First, it is confusing to me that the per iteration rate for FW and AFW are so different. I believe AFW has actually two steps, one for the min LMO and the other for the max LMO. So it puzzles me that it doesn't have about the same per-iteration rate (if not worse) than FW. Besides, AFW also has the memory overhead of holding onto all past atoms--how is this avoided in this implementation?

 - The idea of keeping both $Q$ and $Q^{-1}$ through the Sherman Morrison Woodbury formula is very interesting, but I wonder if numerical error will accumulate because of this. Can the authors comment?

 - In general, if there is to be proofs in the main paper (and not the appendix) I think it is better if each step is discussed more intuitively, with the expectation that the reader will basically follow all the main points without a ton of effort. Maybe the proof to Lemma 3 can be amended to be more clear.

 - I would also like to see more discussion on the construction of the $\mu_k$ sequence, since that seems to be a significant novelty (usually, we pick $\mu_k = 2/(2+k)$ and obtain an $O(1/k)$ iterations rate to $\epsilon$ error, and we use a very different proof technique.)

 - the numerical results are not strong. Though the FPI has a large per-iteration rate, I'm not sure Fig. 1 supports this new approach well. While I do think there is enough theoretical novelty in this paper that we don't need SOTA numerical results, I do think a better motivating example would make the paper much stronger.

If all of these points are addressed clearly by the authors, I may raise my score. 
questions: See previous box
limitations: Not applicable
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper is aimed at approximating Tyler's M-estimator by proposing a series of new methods, which, compared with the previous fixed-point approach, are cheaper in the complexity per iteration. They propose three kinds of Frank-Wolfe methods, following the framework of standard FW, away-step FW, and geodesic FW, and prove their sublinear convergence rates. Furthermore, when a mild additional assumption also holds, they can prove their linear convergence. In my view, the most significant improvement over the previous fix-point method is that they avoid the expensive matrix inverse and propose new methods which can be applied to large-scale problems. Finally, the improvements are demonstrated by some small experiments. 
strengths_and_weaknesses: Strength:
I am not an expert in Tyler's M-estimator, so more literature review about the other algorithms in dealing with the problem can help me a lot. But in general, I think this paper has a significant contribution in decreasing the per iteration complexity, compared with the fixed-point method, and the idea of proving the convergence of FW for this nonsmooth nonconvex problem is also interesting and novel. 

Weakness:
1. In general, the structure and logic of this paper are clear but there are still some issues of writing, which make it hard for a person without relevant knowledge to understand. 
2. The dependence of the PL parameter on the data is not studied enough. I doubt whether it can be extremely bad in the worst case. If so, the comparison in Table 1 can be very misleading and the improvement over the fixed-point method will be not enough for publication.
3. The experiment results don't show the priority of the three FW methods enough. I think a figure of showing the convergence results (linear convergence and sublinear convergence of FW methods) should also be necessary. And I am also interested in the complexity of getting the eigenvector of the smallest eigenvalue for standard FW methods. 


questions: 1. What is the relationship of the PL parameter and the data? It shows in Table 1 without a thorough explanation. Will it be super small in the worst case? I suggest the author show that it is not bad in a certain proper way.
2. I am familiar with the Frank-Wolfe method but I still suggest authors add more literature review about the Frank-Wolfe method, and explain the idea and general framework of the Frank-Wolfe method separately (not in Algorithm 1). I believe the current layout, especially the way this paper introduces Eq. (5-7), might be very confusing for readers.
3. The release of the codes can help make the paper more convincing.
4. Can FW methods really exhibit linear convergence in real experiments? It is not obvious in the current experiment.
5. Does FW methods still have advantages over the fixed-point methods in real-world datasets instead of artificial data? I observe in Table 1 that the complexity is highly related to the condition number of Q, so the dataset might play an important role too.
6. There is inequality between the nuclear norm and the Frobenius norm. I feel changing the norm in Theorem 3 might make it clearer.

Smaller issues:
Line 24: the definition of N(L) is not clear. I think the number of points in a subspace should be infinite? Does that mean the number of points in {x_i}?
Line 52: FPI is not defined
Line 69: Omega is not defined
Line 327: Typo in reference
limitations: I think the authors do well in this aspect.
review_title: null

Meta-review: metareview: The scores on this paper were quite spread (and the reviews at times a little imprecise), however looking more closely at the discussion as well as reading the paper myself, I believe this paper should be accepted.
confidence: Certain
Decision: Accept