Introduction
In modern machine learning and signal processing, the pursuit of sparse solutions—models that utilize only a minimal subset of features—is a fundamental objective. While the $\ell_0$ pseudo-norm is the standard tool for inducing sparsity, real-world applications frequently impose additional convex constraints. These may include non-negativity constraints in image reconstruction, budget limits in portfolio optimization, or box constraints in robust statistics.
The primary mathematical hurdle in these scenarios is the projection onto the intersection of a non-convex sparsity constraint and a convex set. This operation is generally computationally intractable. Existing approaches often rely on complex closed-form projections that are rarely available or settle for local optimality guarantees, leaving the algorithm susceptible to sub-optimal local minima. This paper introduces the Two-Step Projection (2SP) framework, providing a computationally efficient method with the first global optimality guarantees for this class of problems.
The Two-Step Projection (2SP) Framework
The authors propose a modification to the standard Iterative Hard Thresholding (IHT) algorithm. Instead of attempting a direct projection onto the intersection of constraints, the IHT-2SP algorithm decomposes the operation into two sequential, manageable steps:
- Hard Thresholding ($H_k$): The vector is first truncated to its $k$ largest components, enforcing the sparsity constraint.
- Convex Projection ($\Pi_\Gamma$): The resulting sparse vector is then projected onto the additional convex constraint set $\Gamma$.
The success of this decomposition hinges on the concept of support-preserving sets. These are convex sets (such as $\ell_p$ norm balls or box constraints) where the projection of a sparse vector does not alter its support—meaning the indices of the non-zero components remain unchanged.
Theoretical Contributions: The Three-Point Lemma
To establish global convergence, the authors developed a novel Constrained $\ell_0$-Three-Point Lemma. In classical convex optimization, the three-point lemma is a cornerstone for proving convergence. Extending this to the non-convex $\ell_0$ setting is a significant theoretical contribution. It allows for bounding the distance between the algorithm's iterates and the global optimum, even in the presence of non-convex sparsity constraints.
This theoretical framework enables the derivation of global optimality bounds across various settings:
- Deterministic (IHT-2SP): Standard gradient-based optimization.
- Stochastic (HSG-HT-2SP): Utilizing stochastic gradients for large-scale data.
- Zeroth-Order (HZO-HT-2SP): Gradient-free optimization where only function values are accessible.
Key Results and Comparison
The proposed 2SP methods achieve global optimality guarantees of the form $R(w_T) \le (1 + 2\rho)R(\bar{w}) + \epsilon$, where $\bar{w}$ is the true sparse optimum and $\rho$ is a user-defined relaxation parameter. This parameter allows for a trade-off: a tighter objective bound can be achieved by allowing a slightly higher sparsity level $k$.
Notably, in the zeroth-order setting, the 2SP framework eliminates the "system error" prevalent in previous state-of-the-art methods. By refining the proof techniques, the authors demonstrate that the error term can be effectively managed, leading to cleaner and more reliable convergence.
Experimental Evaluation
The effectiveness of the 2SP framework was validated through several benchmarks:
- Synthetic Linear Regression: Confirmed the theoretical trade-off between the relaxation parameter $\rho$ and the required sparsity $k$.
- Portfolio Index Tracking: Using data from the S&P500, HSI, and CSI300, IHT-2SP outperformed "naive" baselines. It successfully tracked market indices while strictly adhering to sector-specific budget and sparsity constraints.
- Multiclass Logistic Regression: On the high-dimensional DNA dataset, the algorithm demonstrated superior performance in classification tasks involving group-wise norm constraints.
Conclusion and Future Work
The Two-Step Projection framework provides a robust and theoretically grounded solution for sparse optimization under additional convex constraints. By simplifying the projection process and introducing the support-preserving property, the authors bridge the gap between practical efficiency and global theoretical guarantees.
Future research directions include extending the 2SP logic to more complex non-convex structures, such as low-rank matrix constraints or graph-based sparsity. Additionally, refining the relationship between the required sparsity $k$ and the problem's condition number remains an important open challenge for tightening theoretical bounds.
Summary updated