Metraipolis › archive › dc_ef5cd4556c2d

Frank-Wolfe is Approximate Broximal Gradient Descent — arXiv:2611.02942

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.02942
License (as archived)
CC0-1.0
Archived
2026-11-03T18:45:42.415Z
SHA-256 of the archived text
aa1ac83663b51ddbbab28a532392abade4d5f5cd34bd3ca313de8c2875e279e0
Stable URL of this page
https://metraipolis.com/documento/dc_ef5cd4556c2d

How to cite

Frank-Wolfe is Approximate Broximal Gradient Descent — arXiv:2611.02942 — arXiv (en), https://arxiv.org/abs/2611.02942 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ef5cd4556c2d (Metraipolis archive dc_ef5cd4556c2d, sha256 aa1ac83663b51ddbbab28a532392abade4d5f5cd34bd3ca313de8c2875e279e0)
BibTeX
@misc{dcef5cd4556c2d,
  title = {Frank-Wolfe is Approximate Broximal Gradient Descent — arXiv:2611.02942},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.02942},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ef5cd4556c2d; sha256 aa1ac83663b51ddbbab28a532392abade4d5f5cd34bd3ca313de8c2875e279e0},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02942. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We show that the Frank-Wolfe method is an approximation of Broximal Gradient Descent (BroxGD), and hence of the ball-proximal method. For constrained minimization, the ball-proximal method minimizes the objective over the intersection of the feasible set with a ball around the current iterate. Linearizing the objective gives BroxGD, but the intersection can remain difficult to handle even when linear minimization over the feasible set alone is cheap. We therefore replace the intersection by a smaller copy of the feasible set, obtained by shrinking it toward the current iterate so that it lies inside the ball. Minimizing the linear model over this smaller set gives exactly Frank-Wolfe, with the shrinking factor as its step size. We examine what this approximation preserves and what it can lose. For smooth convex objectives on compact convex sets, Frank-Wolfe retains a linear-model decrease guarantee that gives it and BroxGD a common convergence proof, recovering the classical $O(1/k)$ bound. Among compact convex regions inside the ball chosen before the gradient is known, the smaller copy is the smallest that preserves the same linear-model decrease guarantee. Nevertheless, Frank-Wolfe can achieve much less linear-model decrease than BroxGD at the same radius. A simplex example illustrates the sparsity gained by restricting the region, while a family of triangles shows how Frank-Wolfe can lose the distance decrease guaranteed by BroxGD. We also give a computable test for recovering the distance guarantee and a refinement procedure that terminates after finitely many oracle calls on polytopes.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2611.02942 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T18:14:37.792Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).