# Improved Complexities of Conditional Gradient-Type Methods with Applications to Robust Matrix Recovery Problems

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Feb 2018.

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

- [A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization](https://mlsanity.com/paper/2202.04296/) (2022)
- [Constrained Stochastic Nonconvex Optimization with State-dependent Markov Data](https://mlsanity.com/paper/2206.11346/) (2022)
- [Faster Projection-Free Augmented Lagrangian Methods via Weak Proximal Oracle](https://mlsanity.com/paper/2210.13968/) (2022)
- [First-Order Sparse Convex Optimization: Better Rates with Sparse Updates](https://mlsanity.com/paper/2506.19075/) (2025)
- [Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity](https://mlsanity.com/paper/2511.02821/) (2025)
- [Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization](https://mlsanity.com/paper/2609.24423/) (2026)

## Abstract (arXiv)

Motivated by robust matrix recovery problems such as Robust Principal Component Analysis, we consider a general optimization problem of minimizing a smooth and strongly convex loss function applied to the sum of two blocks of variables, where each block of variables is constrained or regularized individually. We study a Conditional Gradient-Type method which is able to leverage the special structure of the problem to obtain faster convergence rates than those attainable via standard methods, under a variety of assumptions. In particular, our method is appealing for matrix problems in which one of the blocks corresponds to a low-rank matrix since it avoids prohibitive full-rank singular value decompositions required by most standard methods. While our initial motivation comes from problems which originated in statistics, our analysis does not impose any statistical assumptions on the data.