Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees
William de Vazelhes, Xiao-Tong Yuan, Bin Gu · 2025
Read Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees by William de Vazelhes, Xiao-Tong Yuan, Bin Gu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-08558.txt.
Description
William de Vazelhes, Xiao-Tong Yuan, and Bin Gu improve optimization when the answer must be sparse and must obey extra rules, in a 2025 paper. Keeping only a few active variables gives clean, cheap models, but real problems add constraints that the sparse set must respect. Older algorithms demanded a projection formula that may not exist, or promised only local success. Their variant of iterative hard thresholding projects in two steps, tuned to support-preserving constraints.
A fresh trade-off between relaxing sparsity and accepting sub-optimality yields global guarantees on the result. The proof rests on extending a classic three-point lemma to their two-step projector. The guarantees cover plain, random, and derivative-free versions of the problem. Even without extra constraints, the zero-order result beats the prior best, which one author set in earlier work.
Catalog record
| CREATOR | William de Vazelhes, Xiao-Tong Yuan, Bin Gu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 214 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-08558