# Sparsity-Constraint Optimization via Splicing Iteration

arXiv: https://arxiv.org/abs/2406.12017 · HTML: https://mlsanity.com/paper/2406.12017/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 43 references that are in the map.
- First posted on arXiv 17 Jun 2024.

## Builds on (most cited first, 11 of 11)

- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [On Iterative Hard Thresholding Methods for High-dimensional M-Estimation](https://mlsanity.com/paper/1410.5137/) (2014)
- [Fast Best Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms](https://mlsanity.com/paper/1803.01454/) (2018)
- [Optimal structure and parameter learning of Ising models](https://mlsanity.com/paper/1612.05024/) (2016)
- [A unified approach to mixed-integer optimization problems with logical constraints](https://mlsanity.com/paper/1907.02109/) (2019)
- [A Tight Bound of Hard Thresholding](https://mlsanity.com/paper/1605.01656/) (2016)
- [Global and Quadratic Convergence of Newton Hard-Thresholding Pursuit](https://mlsanity.com/paper/1901.02763/) (2019)
- [Iterative Hard Thresholding with Adaptive Regularization: Sparser Solutions Without Sacrificing Runtime](https://mlsanity.com/paper/2204.08274/) (2022)
- [Global Optimization of Mixed-Integer Nonlinear Programs with SCIP 8](https://mlsanity.com/paper/2301.00587/) (2023)
- [Forward-Backward Greedy Algorithms for General Convex Smooth Functions over A Cardinality Constraint](https://mlsanity.com/paper/1401.0086/) (2013)
- [A Lagrange-Newton Algorithm for Sparse Nonlinear Programming](https://mlsanity.com/paper/2004.13257/) (2020)

## Abstract (arXiv)

Sparsity-constrained optimization underlies many problems in signal processing, statistics, and machine learning. State-of-the-art hard-thresholding (HT) algorithms rely on an appropriately selected continuous step-size parameter to ensure convergence. In this paper, we propose a naturally convergent iterative algorithm, SCOPE (Sparsity-Constrained Optimization via sPlicing itEration). The algorithm is capable of optimizing nonlinear differentiable objective functions that are strongly convex and smooth on low-dimensional subspaces. SCOPE replaces the gradient step with a splicing operation guided directly by the objective value, thereby eliminating the need to tune any continuous hyperparameter. Theoretically, it achieves a linear convergence rate and recovers the true support set when the sparsity level is correctly specified. We also establish parallel theoretical results without relying on restricted-isometry-property-type conditions. We apply SCOPE's versatility and power to solve sparse quadratic optimization, learn sparse classifiers, and recover sparse Markov networks for binary variables. With our C++ implementation of SCOPE, numerical experiments on these tasks show that it achieves superior support recovery performance, confirming both its algorithmic efficiency and theoretical guarantees.