Rank-Adaptive and Linearly Convergent Frank--Wolfe Method over Spectrahedron via Nonconvex Oracle

Abstract

For Frank--Wolfe (FW) methods for convex optimization over the spectrahedron, it remains open whether a block-update variant can be linearly convergent when the update rank never exceeds the (unknown) optimal rank $r^{\ast }$ at each iteration. Existing block and spectral FW methods require an update rank at least $r^{\ast }$---and typically prior knowledge of $r^{\ast }$---to obtain a linear rate. This paper develops a rank-adaptive FW method whose update ranks satisfy ${\hat{r}}_t\le r_t\le r^{\ast }$ at every iteration and which converges linearly after a finite burn-in under quadratic growth and strict complementarity, the two conditions commonly used in spectral FW analyses. The method is built on two designs. The first is a nonconvex spectral oracle, motivated by the geometric connection between the simplex and the spectrahedron; it yields a thresholding rank $r_t$ of the current iterate and a closed-form low-rank solution. Computing $r_t$ exactly, however, requires a full eigendecomposition. The second introduces the efficient rank ${\hat{r}}_t$ of the current iterate, a cheap surrogate that inherits the optimality properties of the spectral oracle. The algorithm switches between the thresholding rank and the efficient rank so that the actual FW update uses ${\hat{r}}_t$, keeps the per-iteration cost comparable to standard FW, and eventually identifies $r^{\ast }$. These results close the gap between low-rank efficiency and fast convergence for Frank--Wolfe methods over the spectrahedron. Numerical experiments demonstrate the advantage of the proposed method.