# Frank-Wolfe-based Algorithms for Approximating Tyler's M-estimator

arXiv: https://arxiv.org/abs/2206.09370 · HTML: https://mlsanity.com/paper/2206.09370/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 34 references that are in the map.
- First posted on arXiv 19 Jun 2022.

## Builds on (most cited first, 13 of 13)

- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [Convergence Rate of Frank-Wolfe for Non-Convex Objectives](https://mlsanity.com/paper/1607.00345/) (2016)
- [Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets](https://mlsanity.com/paper/1406.1305/) (2014)
- [Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method](https://mlsanity.com/paper/2010.01848/) (2020)
- [Fast and Simple PCA via Convex Optimization](https://mlsanity.com/paper/1509.05647/) (2015)
- [Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Balls](https://mlsanity.com/paper/1708.02105/) (2017)
- [Rigorous Guarantees for Tyler's M-estimator via quantum expansion](https://mlsanity.com/paper/2002.00071/) (2020)
- [Robust Estimation of Structured Covariance Matrix for Heavy-Tailed Elliptical Distributions](https://mlsanity.com/paper/1506.05215/) (2015)
- [Faster Projection-free Convex Optimization over the Spectrahedron](https://mlsanity.com/paper/1605.06203/) (2016)
- [Self-Concordant Analysis of Frank-Wolfe Algorithms](https://mlsanity.com/paper/2002.04320/) (2020)
- [Tyler's Covariance Matrix Estimator in Elliptical Models with Convex Structure](https://mlsanity.com/paper/1404.1935/) (2014)

## Built on by (most cited first, 3 of 3)

- [Cubic-Regularized Newton for Spectral Constrained Matrix Optimization and its Application to Fairness](https://mlsanity.com/paper/2209.01229/) (2022)
- [A Randomized Linearly Convergent Frank-Wolfe-type Method for Smooth Convex Minimization over the Spectrahedron](https://mlsanity.com/paper/2503.01441/) (2025)
- [T-Rex: Fitting a Robust Factor Model via Expectation-Maximization](https://mlsanity.com/paper/2505.12117/) (2025)

## Abstract (arXiv)

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 textitaway-steps (AFW), and the third is a textitgeodesic 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.