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

CREATORWilliam de Vazelhes, Xiao-Tong Yuan, Bin Gu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE214 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-08558

Browse the full library · About the Tower of Babel