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^*$ at each iteration. Existing block and spectral FW methods require an update rank at least $r^*$---and typically prior knowledge of $r^*$---to obtain a linear rate. This paper develops a rank-adaptive FW method whose update ranks satisfy $\widehat{r}_t\le r_t\le r^*$ 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 $\widehat{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 $\widehat{r}_t$, keeps the per-iteration cost comparable to standard FW, and eventually identifies $r^*$. 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.