{
  "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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.08522",
  "author_total": 3,
  "authors": [
    {
      "name": "Houduo Qi"
    },
    {
      "name": "Haoning Wang"
    },
    {
      "name": "Liping Zhang"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/e36g9qm0yfxaz.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.08522",
  "fulltext_url": null,
  "id": "e36g9qm0yfxaz",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.08522",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "math.OC"
    ],
    [
      "openalex",
      "2612|Advanced Optimization Algorithms Research"
    ]
  ],
  "openalex": "W7211988328",
  "pdf_url": "https://arxiv.org/pdf/2609.08522",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-08",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/e36g9qm0yfxaz.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:19:58Z",
      "native_id": "2609.08522",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.08522"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.OC",
      "subfield": "optimisation-control"
    }
  ],
  "title": "Rank-Adaptive and Linearly Convergent Frank--Wolfe Method over Spectrahedron via Nonconvex Oracle",
  "title_text": "Rank-Adaptive and Linearly Convergent Frank--Wolfe Method over Spectrahedron via Nonconvex Oracle",
  "type": "preprint",
  "updated_at": "2026-10-30T12:19:58Z",
  "url": "https://research.draconitic.com/paper/e36g9qm0yfxaz",
  "venue": "arXiv",
  "versions": []
}