Frank-Wolfe-based Algorithms for Approximating Tyler's M-estimator
Authors: Lior Danon
Dan Garber
Venue: NeurIPS 2022 Accept (2022)
Keywords: Frank-Wolfe
conditional gradient
projection-free
Tyler's M-estimator
robust covariance estimation
heavy tailed distributions
elliptical distributions
convex optimization
nonconvex optimization

Abstract: Tyler's M-estimator is a well known procedure for robust and heavy-tailed covariance estimation. Tyler himself suggested an iterative fixed-point algorithm  for computing his estimator however, it requires super-linear (in the size of the data) runtime per iteration, which maybe prohibitive in large scale. In this work we propose, to the best of our knowledge, the first Frank-Wolfe-based algorithms for computing Tyler's estimator. One variant uses standard Frank-Wolfe steps, the second also considers \textit{away-steps} (AFW), and the third is a \textit{geodesic} version of AFW (GAFW). AFW provably requires, up to a log factor, only linear time per iteration, while GAFW runs in linear time (up to a log factor) in a large $n$ (number of data-points) regime.  All three variants are shown to provably converge to the optimal solution with sublinear rate, under standard assumptions, despite the fact that the underlying optimization problem is not convex nor smooth. Under an additional fairly mild assumption, that holds with probability 1 when the (normalized) data-points are i.i.d. samples from a continuous distribution supported on the entire unit sphere, AFW and GAFW are proved to converge with linear rates. Importantly, all three variants are  parameter-free and use adaptive step-sizes.

Frank-Wolfe-based Algorithms for Approximating Tyler's M-estimator
Lior Danon
Dan Garber
Technion Israel Institute of Technology Haifa, Israel 3200003
Technion Israel Institute of Technology Haifa, Israel 3200003
Liordanon@campus technion. ac a1l
dangar@technion. ac ill
Abstract
Tyler's M-estimator is a well known procedure for robust and heavy-tailed covari- ance estimation. Tyler himself suggested an iterative fixed-point algorithm for computing his estimator however, it requires super-linear (in the size of the data) runtime per iteration, which maybe prohibitive in large scale. In this work we propose, to the best of our knowledge, the first Frank-Wolfe-basee computing Tyler's 's estimator. One variant uses standard Frank- steps, the second also considers away-sleps (AFW), and the third is geodesic version of AFW (GAFW). AFW provably requires, up to a log factor, only linear time per iteration, while GAFW runs in linear time (up log factor) in large (number data-points) regime. All three variants are shown to provably converge to the optimal solution with sublinear rate, under standard assumptions, despite the fact that the underlying optimization problem is not convex nor smooth. Under an addi- tional fairly mild assumption, that holds with probability when the (normalized) data-points are i.i.d. samples from a continuous distribution supported on the entire unit sphere, AFW and GAFW proved converge with linear rates. Importantly, all three variants are parameter-free and use adaptive step-sizes.
algorithms for
Introduction
Given data-points in RP, XI....,X, E R' different from zero, Tyler's M-estimator (TME), originally proposed by Tyler his seminal work 227, a x p positive definite matrix Q" which satisfies:
P
x;X Q' X,
(1)
1=1
While the TME is not guaranteed exist for any points the following assumption proposed in (27), it does.
Xn, it is well known that under
Assumption 1. The data {xi,..., x C TRP satisfies that x; o 0 for all i 1 n, and that for any proper subspace L TRP,, denoting by N(L) the number of data-points lying in it holds that N(C)
n
d. P.
The TME is a well known distribution-free robust covariance estimator. is also a maximum likelihood estimator for the shape matrix of angular and compound Gaussian distributions, and often used for estimation of heavy-tailed distributions (28). Tyler's M-estimator has received notable interest within the statistics and signal processing communities,
for instance the excellent survey 28 (including the many important references therein), well as the recent works 610 29 25
16 20 24
which provide additional analysis results, related estimators, as well as structured
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

versions of Tyler's estimator (e.g., convex constraints, low-rank structure, sparse structure, and more), to name only a few.
is also well known that when the TME exists, it is given by the optimal solution to the following optimization problem:
n P 72
min {f(Q) QEB
:-
=
log(x; Q-xx,--xxxx1 + log QQ) s.t. Q > 0, Tr Q = p.
where S denotes the set of real-valued symmetric p x p matrices, and Q > 0 (Q = 0) denotes that Q is positive definite (positive semidefinite..
Indeed the connection between and becomes more apparent when examining the gradient given by
n V P
x Q-1 n X Q- +Q
(3)
Thus, matrix Q > 0 satisfying @ also satisfies QV 0. meaning V [[(Q) 0, and the
other way around. In particular, it can be shown that matrices Q > for which V Vf(Q) (Q) 0, are the
only stationary points of Problem ② (i.e., do not have descent directions).
Theorem 1 (see for instance (28)). Under Assumption 7 Problem 2 admits a unique optimal
solution Q > 0. This solution is also the unique solution to Eq. ① with trace equals p.
Throughout this paper we assume that Assumption | indeed holds true. Note also that 1 is invariant to scaling of each data-point x,, L, ......... and the matrix Q' Hence, throughout this paper, as often customary, we assume that XI...., Xn. are normalized to have unit-length, i.e., ||x:||2 1, = : p. and Q" normalized to have trace equals p, i.e., Tr(Q*) p.
The subject of this paper are efficient algorithms for approximating the TME large-scale, i.e., when both n, p large. In 2 Tyler proposed simple algorithm for computing the TME which performs fixed-point iterations, as we define next.
Definition (Fixed-point iterations for computing the TME). The FPI method computes the following iterations:
x
Q++1
P
Σ x,
T1
Q x;
and the returned solution is given by Q P Tr(Qm) where Qr is the last iterate computed.
Note that each iteration requires O(p² + nup²) runtime: O(p²) time in order to compute the inverse matrix Q from the previous iterate Qt, and additional O(np²) time to compute the sum of rank-one matrices. In particular, the runtime super-linear in the size of the input which nip and thus can be prohibitive when n. p are both very large (note that under Assumption I we always have
n > p).
In [27 Tyler also proved the convergence of the iteration 4 (under Assumption D but without rate. Recently, it was proved in [6] that when the data x Xn are i.i.d. samples from an elliptical distribution, the FPI method produces a matrix Q > with Tr(QQ) = p. such that with high probability, ||I - 1-10t-11QQ- - S after O[log det Σ) + (1e) iterations, for any error tolerance e, where Q* is the solution to ① with trace equals p. Σ is the shape matrix of the underlying elliptical distribution, and I|- denotes the Frobenius (Euclidean) norm. The proof of this result is highly involved and relies on deep mathematical concepts such as strong geodesic convexity and quantum expanders. Note that taking into account the runtime of single iteration and the bound on number of iterations, the total runtime to reach e error (according to the measure of convergence in ( is (pp + npp))
4
The goal of this paper is present new simple and efficient first-order methods for solving Problem which avoid the super-linear runtime barrier of np². and even the matrix inversion barrier (O(p3)
'There is variant in which the normalization of the trace is performed after each iteration and was observed have similar empirical performance (28

---

in practical implementations), required by each iteration of 4.. Our algorithms are based on the well known Frank- Wollee method (aka conditional gradient method) for constrained smooth minimization To the best of our knowledge this is the first time that the Frank-Wolfe method has been considered for computing the TME. We provide three such variants with the following properties:
S 15
All three variants provably converge the optimal solution (the one satisfying Eq. ① under Assumption with a sublinear rate- - ((1/2) iterations for approximation error c.
Two variants, AFW and GAFW, are also proved to converge with a linear rate (i.e,. log(1/4 /e) dependence on the error tolerance e), under an additional fairly mild assumption that holds with probability when the (normalized) data-points are i.id. samples from a continuous distribution supported on the entire unit sphere (note that the (log(L//e) rate proved in K also holds under an assumption that the data is sampled i..dd from an elliptical distribution).
All three variants are parameter-free and do not require any tuning of parameters, and apply adaptive step-sizes (i.e., not fixed beforehand).
The AFW variant requires only (mp) runtime per iteration which is linear in the size of the data, up to single logarithmic factor, while another variant GAFW runs in the same time when n 2 p². This in contrast to FPI which requires Ompp + p²) time per iteration. In fact, even if processing the data could be ideally distributed / done in parallel, FPI still requires an expensive matrix inversion on each iteration (which practically runs in (p²)) time), while our AFW variant only requires additional O(p²) runtime per iteration.
A quick summary of our results is brought in Table !
Importantly and quite pleasingly, our derivations and proofs rely mostly on standard arguments for continuous optimization in Euclidean spaces, and we believe that as such, are quite accessible.
Beyond our contribution to efficient algorithms for computing the TME, our work also contributes more broadly the theory of Soonk-Wolfe-tppe methods, which have received significant interest in recent years in the context of obtaining faster rates for convex and smooth problems (e.g.. [I0 19 g
I dealing with nonsmooth objectives (e.g.. 26 ) and dealing with non-convex objectives
(e.g., (8). While Problem ( is nonsmooth and nonconvex, our Frank- Wolfe variants, with our sifored-designel adaptive step-sizes, are guaranteed converge to the global minimum, and this is the first result of its kind for Frank-Wolde Wolfe- methods that we are aware of. Moreover, while to the best of our knowledge, so called away--teps in Frank-Woll Wolff algorithms were only shown to facilitate linear convergence rates when optimizing over polytopes
[19, here we establish that also such stay-steps can lead to linear convergence rates (under proper assumptions), as we prove for our AFW and GAFW variants. An additional contribution is our connection between Frank- Wolfe methods and optimization over manifolds as captured by our GAFW variant which applies Frank- steps and away-steps w.r.t. to the geodesic grudient of Problem ( thus our hope that our work will lead to additional efficient Frank- Wolfe-based algorithms for other important and well-structured non-convex and potentially nonsmooth problems.
for the feasible set of positive semidefinite matrices in Problem
We introduce the following notation. We let S and Sh denote the sets of positive semidetinite and positive definite matrices in SP, respectively. We denote S, = {Q E S [T((Q) - p}. Spt = (Q E & Tr(Q)= = p}. For a matrix M E S", we let (M denote the ith largest signed eigenvalue of M. We also denote times by Amax (M) and Amin (M) the largest and smallest (signed) eigenvalues, respectively. For real matrices we let ||.1|2, II- ||-1/1 denote the spectral norm (largest singular value), Frobenius (Euclidean) norm, and trace norm (sum of singular values), respectively. We also denote by (s--) the standard inner- product in SP.
It is known that for every Q E Spt, f(Q) is finite, while for every sequence (Qa)22 C Sp+ with 0, it holds that f(Qx)
Amin ( (uk)
0G, see 28 This implies the following lemma that will
i 00
be used throughout the paper.
Lemma 1. Fix Qo Spz. There exists a constant À > such that for every Q Spt satisfying f(Q) < f(Q)), it holds that Amiu Q)= 2 X.
3

---

Table 1: Summary of main results. The bounds given in simplified form excluding constants
and logarithmic factors. We denote by Ko, Ao, Ko the maximal values of Amax (Q)
Awenn (Q) Amax (Q),
A (Q)
Amtn Q
over the level set (Q E Sp f(Q) S f(Qo)): where Qo is the initialization point, respectively. The
ff notation denotes the gradient at the current point. p is the constant of linear convergence (see
Theorem 4.. The linear rates are w.r.t. the approximation error in function value. The sublinear
rates of AFW and GAFW are w.r.t. the distance in spectral norm from satisfying Eq. while the
sublinear rate for FW is for a related, yet slightly different measure, see Theorem single iteration runtime
FW variant
sublinear rate
linear rate
(Theorem
(Theorem 3)
(Theorem
FW
(p" + np) VI Amfn
Ra/e"
AFW
P mp
Ra/e*
KōP log(
GAFW
np
Ap/e"
log(L//))
2 Frank-Wolfe-based Algorithms for Approximating Tyler's M-estimator
We consider three Frank-Wolfe variants for Problem 2 all described below in Algorithm I All three variants require solve (approximately) certain eigenvalue problem, different one for each variant, see more details below. All three variants have the following two properties: 1. they all the same adaptive scheme compute the step-size 14,, which in particular does not require any knowledge of the parameters of the problem (this choice will become clearer in the convergence analysis), and 2. since the gradient of the objective f(-) requires the inverse matrix Q where Q₁ is the current iterate of the algorithm, they all explicitly and efficiently maintain the inverse Q using the well-known Sherman-Morrison formula and capitalizing on the fact that the algorithm performs rank-one update. Hence, the inverse could be updated in only Opp²) time per iteration (as opposed to the standard (p²)) matrix inversion time). Below we expand each of the eigenvalue problems in Algorithm| T and how they correspond to familiar and new Frank- Wolfe-type methods.
We note that Algorithm is completely independent of any parameter of Problem ( The only parameter the algorithm accepts the approximation parameter [0, 1). however this choice not very important will be evident from our convergence theorems, and only brought for convinience. In particular one can always simply choose some universal constant, for instance 8 = 1/2. The algorithm also requires feasible initialization point Qo E Sp+ and its inverse, and convenient choice is to simply take Qo = I Q
Algorithm Frank- Wolfe variants for approximating Tyler's M-estimator
Input: Qo Q7 such that Qo > 0, 3 E 1) for to o.... do
Solve an approximate eigenvalue problem: let V, E TRP be such that ||ve|| = vp and satisfies one of the following:
1. V. V.(Q.vv; 2 -p(1 3) (V)(Q.))
(FW step)
(5)
2. V. V v/l 2 -
(AFW step)
(6)
v VVV.)
3.
2 211-3) -1)1
(GAFW step)
(7)
v. Q,Q,1 V.
VV.
14 [v] Q vv. V/Q.A.
H1 -v. -v. V...v
71 4- 1- [v. vx))²
Q411 + Q + +H((vv
Qi)
Q. vv.vv. Q.
Q +- I-ke
(Q, - 7h I- Q
end for
Standard Frank-Wolfe update: For the feasible set Sp,, is well known that the solution the FW linear optimization problem minves, (V, V.V.((Q)) at the current point Q₂ is given w.l.o.g. as
V+ = T, where you and is unit-length cigenvector of Vf(Q:) corresponding to the

---

smallest eigenvalue, i.e., u n Amin (f see for instance 1415. This is exactly the step in Eq. ① in Algorithm only that Eq. S we do not require exact computation of the eigenvector, but allow for a (1 3) multiplicative approximation w.r.t. the smallest eigenvalue.
Frank-Wolf with Away-Steps (AFW) update: The AFW update (see [K] applies one of two types of updates, One is the standard FW step discussed above. The other, called away-step, takes the form Q++1 t- Q: + uQ VV-.. μ 0, where V- E Sp is ideally chosen so that V- maximizes the inner product (V-.. V)(( over Sp. subject to the constraint that there indeed exists a corresponding μ 0, so that Qu+1 is feasible [13 [9.. For Q 0, all points in Sp give rise to such positive μa, and so, V_ is simply the solution to maxves, (V, V ((Q)) which w.l.o.g. is of the form V_ vv where v /pu and u is a unit-length eigenvector of f(Q,) corresponding to the largest (signed) eigenvalue.
If (Q. V+, V(QQ:)) 2 (V- - Q. Vf(Q.). AFW performs standard FW update with V+, and otherwise, it performs an away-step with V_. In case of Problem Q a straight- forward calculation shows that (Q., v)()))) = O. Thus, in our case, a FW step is taken if -(V+, (Q())) 2. (V-,V V.Q)).) i.e., -pAmin (V/(Q))) 2 pdmax (Vfix and other- wise an away-step is taken. Thus, taking both cases into account, AFW performs a step of the form Q++1 + Q2 + p(vv" - -Q,) (here μ can also negative), where |v Vf(Quvv] N p max{ -nmin (vf(Q))). Amax (v)():)) p(V)(QQ which is exactly what we have in Eq. O in Algorithm II only that in 6 we again do not require precise computation, but allow for a (1 3) multiplicative approximation.
Geodesic Frank- Wolfe with Away-Steps (GAFW) update: GAFW performs the same updates as AFW, but not w.r.t. to the (standard) gradient V V Q+), but with respect to the so-called geodesic
gradient given by Q 1/2 /VV(((Q
(see for instance
Note that IQQ, V (Q
1/2 l|2
m| j Q 1/2 // ( /2 u22.. Consider the paramctrization u Q, 1/2
(note it is
11Q, 172 vlI2
v'v. which is exactly maxy Q, the update step in Eq. (7) in Algorithm || only that in Eq. 7 it suffices to find (1 - multippliccattie
invariant to the norm of v). This gives
approximation. As will be evident from our analysis, and in particular the error reduction argument in Lemma S this step maximizes the decrease in function value on each iteration.
The following lemma establishes that the step-sizes of Algorithm | indeed always produce feasible iterates in Sp+. The proof is given in the appendix.
Lemma 2 (Feasibility of Algorithm D. Suppose that Tr( Tr(Qo) p and Qu > 0. Then, for every iteration t 2 of Algorithm L it holds that Tr ((:))) and Q: > 0.
2.1 Efficient implementation of the eigenvalue oracles in Algorithm
We now discuss how the various eigenvalue problems in Algorithm I could be solved (to sufficient approximation) efficiently via simple and well-known iterative algorithms for leading eigenvector computation, such the power method or the Lanczos algorithm 12 23 These implementations rely on three simple ideas:
1. Use of the Sherman-Morrisot formula for rank-one updates to update the inverse matrix Q from the previous one Q given the vector v., in Opp²) time.
2. Explicitly maintaining and updating the vectors Q₂ x,, I,..., n, which can be done in overall (mpp) time per iteration. This allows to compute matrix-vector product of the form V vv for some v E R. in only (rrp) time (see expression for V in Eq. (
3. Apply the power method the Lanczos algorithm (or any other method for leading eigen- vector computation) to solve the leading eigenvalue problems 5. 6 7 relying on the fact that due to the pervious two items, each iteration of the power method requires only Opp + ne)) time.
The complete proof of the following theorem is given in the appendix.
Theorem 2. Let 3 [0, 1) be some universal constant (e.g.. 3 1/2). Algorithm admits implementations based on fast algorithms for leading eigenvector computation (e.g., the power
5

---

method/ / Lanczos 112 231), such that each iteration of Algorithm 7 could be implemented in: Ómpp + p²) time when using AFW steps (Eq. (6)), O(p") + (np + p²) time when using GAFW
steps (Eq. 7)) and Ô (V & (QQlla (np + +²) when using FW steps (Eq. ( where in all cases (((())))))
the Ô notation hides logarithmic factor in the dimension p and the probability failure 6.
Remark 1. Note that the worst-case time solve the standard FW eigenvalue problem, in terms of the dependence on the size of the data rop, is much worse than that of AFW and GAFW. This is because, while the eigenvalue problems in AFW, GAFW require approximate the largest eigenvalue in magnitude, FW requires to approximate the smallest signed eigenvalue.
Remark 2. Since leading eigenvector algorithms such as the power method are usually initialized with a random vector, their guarantees only hold with high probability, as captured in Theorem 2 However, since the dependence on the probability of failure is only logarithmic, for the clarity of presentation, henceforth neglect such considerations and treat these computations as they always succeed.
3 Sublinear Convergence of Algorithm 1
While the measure of convergence in our sublinear rates for AFW and GAFW will be simply the distance in spectral norm from satisfying the TME equation ①I our measure of convergence for the standard FW variant is slightly less obvious and is motivated by the following observation, the proof of which is given the appendix.
Observation For any
Q
E
Sp+,
Amiu (Q- -Q--2 -
0, and
Aminn
Q
P D
X:X.
if and only i = Q²
Theorem (0(1/e) convergence of Algorithm
Consider the iterates of Algorithm and define the function T(ë) = (QQ)) ".. Fix > O and define
min (Q) max Q) (1 B)c, EAEW = (a5S min
Amin (2)
Amin Q))
Epw =
(1 -1-18 8)e,
(QES)
max Q)
&GAPW ==
max
Amax ()) (1-
(Q
Then, when using FW steps (Eq. 5 it holds that for all 2 T(ěrw).
max
Amin
Q,
P
x;
2 -.
(8)
T=
ni
X
Q
X,
When using AFW steps (Eq. t 2 T(EGArW), respectively, that
or GAFW sleps (Eq.
7., it holds for all 1 2 T((AFW) or
Q
P n
n
X x Q Q
SC.
Remark 3. Note that one motivation for considering the use of the GAFW variant in light of Theorem 3 that it enjoys better conditioning than AFW in terms of the maximal condition number Amax Amin (Q) over the initial level set {Q E S, f(Q)= < f(Qo)}
The complete proof of Theorem
given in the appendix. Below we state and prove the key technical step bound on the improvement in function value that Algorithm makes on single iteration. In particular, the lemma is independent of the way the vector v, is generated and hence applies to all three variants described in Algorithm!]
Lemma 3. Fix some iteration of Algorithm and define L, v. V.V.(Q It holds that v. Q, v
f(Q(+1) f(Q.) min(1, L.}.
(10)

---

Remark 4. An immediate important consequence of Lemma 3 is that Algorithum 1 is decent method, i.e. the function value never increases from one iteration to the next. Lemma 3 also reveals one motivation for the GAFW step in Eq. 7 (up to a (1 3) factor) it maximizes the reduction in function value.
Proof of Lemma
Using the definition of Q++1 we have that,
[(Q(+1)
P n1
Σ
log(x; ((1 ((I-,+)Q + pevev])- + log(det((1 Nc) :eviv.))
(11)
Using the Therman-Morrison formula we have that,
(1-14)Q4 + ((vovl) 1 μi (Qr - 1 NvV Q₂ Vi
Q, 'vvv Q,
(12)
where we recall that 7/-
Pr.
I-p-
Using the well-known matrix determinant lemma for rank-one updates we have,
det((1 - Q. + (.v.v))) = (1--)) (1- (1) + nv, Q, v.) det(Q.).
(13)
Plugging
12 and
into
we obtain
p n
x; (Qr" - 76 Q v.v, vvv Q, Q,"
f(Qu+1)
log
vv Q₂ -i've'
i=1
+ log
((1
M1) (1) + vi Q, vı) det (Qi))
Q - m Q v.v, Q
v.v,
log
x;
+ +og ((1 + + Q vct)(QQQ))))))
+ v Qi 'v'v
i=1
T Q xx 71 (x] Qi v2)
log
-xix;
+ log(1 + yev Q, 'v)) + log det (Q:)
vi Qi 'v.
1
(x] Qi vo)² 'v)²
log(x; 0x'x;)) + log
71 7h
7ov Q 'v, x; Qi x,
+ +log(1 + yov Q, (v) + log det
= f(Q)) P
log
1
(x] Q 'vc)3
+ +log(1 + v.v Q.'v,,
+ JAV, Q -,
x Q,'xx;
1=1
(x Qi v.))²
< ((Q)) 1 n,, Q, Q,'v; (a)
Ft.
P
+ +log(1 + 7 Qi
x Q,
= =(Q)) + 1 Q, Vi
7t
(v. Vf(Q.vv -v, v.Q + log(1 + v tviv:),
where (a) follows from the inequality (1 + x) S x.
We now consider two cases. If y 2 O, using the inequality log(1 ( +x) S
2 2+
I+z x 21+e]
for all
> 0, we have that
72 Q 'v,
log(1 + n Q vv,) S I Q 'v,
2(1 + n.v Q 'v:)
If 7/e O, using the inequality log(1 + x) I
2x
2t for all 0
1, have that
24
Vi Q 1v)2
log(1 + v Q (v,) E 7. Q 'v,
2 2+ Q -v.
7

---

-v, V. (v) Q v.)a it holds that
is easily verified that for our choice "
Tí ++ 1v,, Q Ve VV( v. Q Qv)v + +wv Q, 0.
Thus, considering both options for 7t (2 or < 0), we have that
((Q+1)) /(Q:) < 2/ (v, Qi v2)
L 2(1 + h Q vil) 2(1 + [xel
The Lemma follows from considering the two cases
L.l 2 1 and [Lel < 1, and simplifying
Corollary 1. Fix e > O. For any 1. 1 [4(S(Q)) f(Q))) (1 + 3) iterations of Algorithm holds that, min,= ||_| S.
Proof. Fix some iteration of Algorithm
!
Using Lemma we have that
1
- < f(:)) f(Qo) = E (((0--))-(0A
min { (1n L
==0
Thus, for t 2 [4(](Qo) - ((Q))) (1 +c] iterations there must exist some 7 E (0...., -1) such that |,|| S E.
Linear Convergence of AFW and GAFW
In this section we prove that under an additional (to Assumption GAFW variants converge linearly in function value.
D mild assumption, the AFW and
Assumption 2. The data-points X1...., .n. satisfy that > 2p. and for any subset S S
{xi,..., }x,} such that |S| 2 n/2,, it holds that span(S) = IRP.
Remark 5. Note that for any fixed if the (normalized have unit norms) data-points are i.i.d. samples from a continuous distribution which is supported on the entire unit sphere, Assumption 2 holds with probability 1.
Theorem 4 (Linear convergence of AFW and GAFW). Denote h4 = f(Q:) f(Q") for all t 2 0.
Suppose Assumption holds. Then, Algorithm when run with AFW steps, satisfies
(1
3)²
Vt > 0: he S ho exp
4 Ku (t -
where p > O is the constant implied by Theorem and Ku = maxqES,
Ammaz Q
Xuain Q)
When using GAFW steps, Algorithm D satisfies
(- ---30² p(t p
Vt 120: 0: hr S hg exp
Remark 6. As with Theorem 3 we see that GAFW enjoys better conditioning than AFW w.r.l. the maximal condition number Xmax (Q)/Amin (Q) over the initial level set.
The complete proof of Theorem 4 is given in the appendix. The key part in the proof is to establish
that, under Assumption Problem 2 satisfies -ojssk--.ojasiewiiz (PL. condition w.r.t. both
the standard gradient V f() and the geodesic gradient ((Q)Q which is property well-known to facilitate linear convergence rates for first-order methods, see for instance 22 [7 M.
A (standard, i.c., non geodesic) PL condition at some query point Q takes the form Q
C(f(Q) f("))) )), for some constant C > O independent of Q.
The proof of our PL condition is highly non-trivial and is very much inspired by the analysis in G.. However, while the proof 6 relies heavily on geodesic strong convexity and quantum expansion arguments, we give different proof (in particular, our Assumption is different from their explicit assumption that the data is sampled from an elliptical distribution) that does not use such considerations and, we believe, is more straightforward and accessible.

---

Theorem 5
condition). Suppose Assumption 2 holds, and let Qo Sp+. Then, there exists constant p such that for any Q Spt satisfying [{Q) - f fQn), holds that,
|1 IQ"
-
Remark 7. While Theorem establishes that the PL parameter is strictly positive, its precise value (i.e., its dependence on the data) is quite intricate and does not admit simple formula (see proof in appendix for more details).
5 Numerical Simulations
In order to give some demonstration for the empirical performance of our Frank- Wolfe-based algorithms, we conducted two types of experiments that closely follow those in [28] (Chapter 3) with some minor changes, which consider a Gaussian distribution with outlier contamination, and a heavy-tailed multivariate t-distribution. We consider large sample regime in which p². We recall that in this regime each iteration of the Fixed-point Iterations method (FPI) takes ((pp)) time, while AFW, GAFW variants require only (mpp) time, up single log term, per-iteration.
Following the experiments conducted [28] with some minor changes, we consider i. Gaussian distribution with outliers contamination in which, each Gaussian-ditrriutee vector is replaced with probability 0.9/p with the eigenvector associated with the smallest eigenvalue of the covariance, and ii heavy-tailed multivariate t-distribution with degrees of freedom. In both experiments we set 50, n = 2500, and we take the true unknown covariance to be a Toeplitz matrix with the elements Qu, = 0.851K-j
Data generation:
To present results that implementation and scale independent possible, for each of the considered methods we estimate the required running time per number of itera- tions, normalized by the data-size np. Since consider the regime n p², each iteration of FPI takes (mpp² time. For all Frank-Wolfe variants (FW, AFW, and GAFW) we use Python's WWW.YSPPRRE.LLNLG....
Methodology:
procedure, which is based on the Lanczos algorithm, corresponding eigenevalue problem to low-accuracy (which corresponds to the approximation pa- rameter 3 in Algorithm D. We verified that in all of our experiments and for all FW variants, this procedure makes at most 2 iterations, and thus, per the discussion in Section 2. the runtime per iteration of each of these variants is estimated by (np). Thus, normalizing the estimated runtime by the data-size np, in the figures below each iteration of FPI is estimated to take p times more than that of any of the FW variants. All methods are initialized from the sample covariance (normalized to have trace equals p) and each figure is the average of 20 i.i.d. experiments.
solve the
Results: For all experiments we compute Tyler's estimator to high accuracy by running 250 iterations of the Fixed-point method and we denote the resulting matrix by Q'. In Figure 1 we report the distance spectral norm (in log scale) of the iterates of the different methods form Q and in Figure 2 we report the approximation error f(Q:) f(Q") of the iterates (also in log scale). It can seen that in both setups and with respect to both measures, GAFW converges faster than FPI, and that in the contaminated Gaussian distribution setup it is significantly faster. Moreover, looking at the approximation error in log-scale, it indeed seems to exhibit a lincar convergence rate. We also observe that the FW and AFW variants converge significantly slower than GAFW, which demonstrates how the better conditioning of GAFW (as captured also in our convergence theorems, Theorems
3 and 4 may be significant. Additionally. and perhaps surprisingly, AFW converges slower than FW, which suggests a situation in which AFW takes many away-steps, since they are better descent directions than the standard FW step, but in turn results in much smaller step-sizes, and thus overall, the convergence is slower.
6 Conclusions
We have presented the first Frank- Wolfe-based variants for approximating Tyler's M-estimator for robust and heavy-tailed covariance estimation. In particular these include parameter-free and globally- convergent variants with nearly linear runtime per-iteration and, under mild assumption, with linear convergence rates, despite the fact that the underlying optimization problem is not convex

---

-25
log distance
diizannc
-30
-480
GAFW
APW
FW
-153
203
29
estimated runtimm [datasize]
estimated runtime [datasize]
Figure 1: log ||Q Q2 for Gaussian distribution with outlier contamination (left panel) and for heavy-tailed t-distribution (right panel).
lag apprrox extor
log approx enror
10
-23
FP1
-20
FPI
GAFW
-25
GAPW
FW
FW
Figure 2: Log approximation error - for Gaussian distribution with outlier contamina- tion (left panel) and for heavy-tailed t-distribution (right panel).
nor smooth. We hope these results will pave the way to nearly linear-time algorithms for additional highly-structuredd nonconvex and nonsmooth problems.
Acknowledgements
This research was supported by the ISRAEL SCIENCE FOUNDATION (grant No. 2267/22).
References
[1] Zeyuan Allen-Zhi Elad Hazan, Wei Hu, and Yuanzhi Li. Linear convergence of frank-wolfe type algorithm over trace-norm balls, Advances Neural Information Processing Systems, 30, 2017.
[2] Florent Bouchard, Amaud Breloy, Guillaume Ginolhac, Alexandre Renaux, and Frederic Pascal. riemannian framework for low-rand structured elliptical models. IEEE Transactions on Signal Processing, 69:1185-111 199, 2021.
[3] Alejandro Carderera, Mathieu Besançon, and Sebastian Pokutta. Simple steps are all you need: Frank-wolfe and generalized self-concordant functions. Advances in Neural Information Processing Systems, 34, 2021.
[4] Pavel Dvurechensky, Petr Ostroukhov, Kamil Safin, Shimrit Shtern, and Mathias Staudigl. Self-concordant analysis of frank-wolfe algorithms. In International Conference Machine Learning, pages 2814-2824. PMLR, 2020.
[5] M. Frank and P. Wolfe. An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3: 3:14 1956.
[6] William Cole Franks and Ankur Moitra. Rigorous guarantees for tyler?s m-estimator via quantum expansion. In Conference on Learning Theory, pages 1601-1632, PMLR, 2020.
[7] Dan Garber. Faster projection-free convex optimization over the spectrahedron. Advances in Neural Information Processing Systems, 29, 2016.
10

---

[8] Dan Garber and Elad Hazan. Fast and simple pea via convex optimization. arXiv preprint 1rX.v:1509.05647, 2015.
[9] Dan Garber and Elad Hazan. Faster rates for the frank-wolfe method over strongly-conves sets. In International Conference on Machine Learning, pages 541-549. PMLR, 2015.
[10] Dan Garber and Elad Hazan. A linearly convergent variant of the conditional gradient algorithm under strong convexity, with applications to online and stochastic optimization. SIAM Journal on Optimization, 26(3): 1493-12899 2016.
[11] John Goes, Gilad Lerman, and Boaz Nadler. Robust sparse covariance estimation by threshold- ing tyler's m-estimator. The Annals of Statistics, 48(1):86-110, 2020.
[12] Gene H Golub and Charles F Van Loan. Matrix computations. JHU press, 2013.
[13] Jacques GuéLat Lat and Patrice Marcotte. Some comments on Wolfe's "away step'. Mathematical Programming. 35(1), 1986.
[14] Elad Hazan. Sparse approximate solutions semidefinite programs. In Latin American symposium on theoretical informatics, pages 306-316. Springer, 2008.
[15] Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In Interna- lional Conference on Machine Learning, pages 427-435. PMLR, 2013.
[16] Abla Kammoun, Romain Couillet, Frederic Pascal, and Mohamed-Sline Alouini. Convergence and fluctuations of regularized tyler estimators. IEEE Transactions on Signal Processing, 64(4):1048-4) 1060, 2016.
[17] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-tojasiewice condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 795 111.811..0 Springer, 2016.
[18] Simon Lacoste-Julien. Convergence rate of frank-wolfe for non-convex objectives. arXiv preprint arXiv 2016.
[19] Simon Lacoste-Julien and Martin Jaggi. On the global linear convergence of frank-wolfe optimization variants. Advances in neural information processing systems, 28, 2015.
[20] Bruno Mériaux, Chengfang Ren, Arnaud Breloy, Mohammed Nabil El Korso, and Philippe Forster. Matched and mismatched estimation of kronecker product of linearly structured scatter matrices under elliptical distributions. IEEE Transactions on Signal Processing, 69:603-616 -16,,1 2020.
[21] Cameron Musco and Christopher Musco. Randomized block krylov methods for stronger and faster approximate singular value decomposition. Advances in neural information processing systems, 28, 2015.
[22] Ion Necoara, Yu Nesterov, and Francois Glineur. Linear convergence of first order methods for non-strongly convex optimization. Mathematical Programming, 175(1):69-007, 2019. 2019.
[23] Yousef Saad. Numerical methods for large eigenvalue problems: revised edition. SIAM, 2011.
[24] Ilya Soloveychik and Ami Wiesel. Tyler's 's covariance matrix estimator in elliptical models with convex structure. IEEE Transactions on Signal Processing, 62(20):525155555 2014.
[25] Ying Sun, Prabhu Babu, and Daniel P Palomar. Robust estimation of structured covariance matrix for heavy-tailed elliptical distributions. IEEE Transactions on Signal Processing, 64(14):3576-3500 2016.
[26] Kiran K Thekumparampii, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Projection efficient subgradient method and optimal nonsmooth frank-wolfe method. Advances in Neural Information Processing Systems, 13:12211-12221 2020.
[27] David E Tyler. distribution-free m-estimator of multivariate seatter. The annals of Statistics, pages 234-251 1987.

---

[28] Ami Wiesel, Teng Zhang, et al. Structured robust covariance estimation, Foundations and Trends in Signal Processing, 8(3):127-216, 2015.
[29] Teng Zhang, Xiuyuan Cheng, and Amit Singer. Marvcenko-pastur law for tyler?s m-estimator. Journal of Multivariate Analysis, 149:114-123, 2016.
[30] Teng Zhang and Gilad Lerman. A novel m-estimator for robust pea. The Journal of Machine Learning Research, 15(1):749-88) 808, 2014.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as URL)? [Yes] The details in the experimental section allow to reproduce the results exactly
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "wU-jttT-F00", "reviewer": "Reviewer_Q7uf", "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. ", "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.\n2. 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.\n3. The release of the codes can help make the paper more convincing.\n4. Can FW methods really exhibit linear convergence in real experiments? It is not obvious in the current experiment.\n5. 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.\n6. There is inequality between the nuclear norm and the Frobenius norm. I feel changing the norm in Theorem 3 might make it clearer.\n\nSmaller issues:\nLine 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}?\nLine 52: FPI is not defined\nLine 69: Omega is not defined\nLine 327: Typo in reference", "limitations": "I think the authors do well in this aspect. ", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\nI 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. \n\nWeakness:\n1. 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. \n2. 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.\n3. 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. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "g-x495XQdV7", "reviewer": "Reviewer_6Bnc", "summary": "This paper discusses a new way of computing the Tyler covariance estimator, which is the solution $Q$ to the fixed point relation \n$\\frac{p}{n} \\sum_{i=1}^n \\frac{x_ix_i^T}{x_i^TQ^{\\*-1}x_i} = Q^{*}$.\nHere, $p$ is the feature dimension and $n$ is the number of samples.\nThe 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.\n\nThis 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.", "questions": "See previous box", "limitations": "Not applicable", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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)$). \n\n - 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).\n\n - 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?\n\n - 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?\n\n - 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.\n\n - 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.)\n\n - 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.\n\nIf all of these points are addressed clearly by the authors, I may raise my score. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OhEEOjgn0nA", "reviewer": "Reviewer_6ubv", "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. ", "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. \n\n- 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. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Jhlspx2RWll", "reviewer": "Reviewer_6Ljb", "summary": "The paper proposes a Frank-Wolfe algorithm for\napproximating a well-known covariance matrix estimator.\nThe estimator is known to minimize a particular non-convex,\nlocally gradient dominated function (as shown in Theorem 5)\nover the set of positive definite matrices with a fixed trace,\ni.e., a convex set which is a neither open nor closed.\nThese are atypical settings for a Frank-Wolfe algorithm,\nnevertheless the paper establishes strong convergence results\nfor the original Frank-Wolfe algorithm and two variants with away\nsteps, e.g., linear convergence in function value\nfor the away-step variants\nfor a non-convex function over a non-polyhedral domain.\nThe convergence is for a quantity similar to the dual gap\nfor the original algorithm.\n\nThe 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.", "questions": "None.", "limitations": "Not applicable.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The theoretical results are excellent for the theory of Frank-Wolfe\nalgorithms 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.\n\nSince the problem is specific to appplication of covariance estimators,\nit would have been good to address performance for the original\ncovariance estimating problem, which it is meant to solve.\nFor this an accuracy measure for covariance matrix estimators should\nbe studied independent of the method of solution.\n\nIn the computational experiments,\nsuch a measure ought to be displayed on the vertical axis,\ninstead of the function value of questionable practical relevance.\n\nOn the horizontal axis, the authors stated aim was a measure\nindependent of implementation issues, a worthy goal, but unfortunately\nthe chosen \"estimated runtime\" is the best worst-case known bound\non operation cost, which is heavily biased against\nalgorithms with high worst-case computational cost.\nFor example, such a measure would show the ellipsoid methpd\nas far faster for linear programming than the simplex method,\ndespite the latter being faster in practice.\nDue this error it is not possible to deduce acutal performance from the graphs,\ne.g., the baseline FPI might have outperformed all the other algorithms.\n\nThe claim in Line 300 that GAFW is significantly faster than FPI\nis contradicting to the graphs, even if we ignore the errors\ndiscussed above.  FPI has the same performance on the right and nnly\nslightly worse on the left, so the difference is insignificant.\n\nOverall the computational results are worthless, and likely to cause only misinterpretations.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept