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 r̂t≤ rt≤ 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 rt of the current iterate and a closed-form low-rank solution. Computing rt exactly, however, requires a full eigendecomposition. The second introduces the efficient rank 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 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.
Related
- An Adaptive Augmented Lagrangian Method for Deterministic and Stochastic Nonconvex Optimization
- Fully Convergent Projection-based Methods with Momentum under Nonconvex Geometric Constraints
- A Parallel Adaptive Proximal ADMM for Linearly Constrained Separable Composite Optimization Problems
- A method for global minimization of nonconvex quadratic functions
- Douglas-Rachford splitting method for nonconvex stochastic optimal control
BibTeX
@misc{qi2026rankadaptive,
title = {{Rank-Adaptive and Linearly Convergent Frank--Wolfe Method over Spectrahedron via Nonconvex Oracle}},
author = {Houduo Qi and Haoning Wang and Liping Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08522},
eprint = {2609.08522},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08522},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Rank-Adaptive and Linearly Convergent Frank--Wolfe Method over Spectrahedron via Nonconvex Oracle
AU - Houduo Qi
AU - Haoning Wang
AU - Liping Zhang
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.08522
UR - https://arxiv.org/abs/2609.08522
AB - 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 r̂_t≤ r_t≤ 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 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 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.
ER -