# Alternating Iteratively Reweighted ℓ1 and Subspace Newton Algorithms for Nonconvex Sparse Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 45 references that are in the map.
- First posted on arXiv 24 Jul 2024.

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

- [Calculus of the exponent of Kurdyka-Lojasiewicz inequality and its applications to linear convergence of first-order methods](https://mlsanity.com/paper/1602.02915/) (2016)
- [A proximal difference-of-convex algorithm with extrapolation](https://mlsanity.com/paper/1612.06265/) (2016)
- [Nonconvex and Nonsmooth Sparse Optimization via Adaptively Iterative Reweighted Methods](https://mlsanity.com/paper/1810.10167/) (2018)
- [Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimization](https://mlsanity.com/paper/1912.04365/) (2019)
- [A Reduced-Space Algorithm for Minimizing ℓ1-Regularized Convex Functions](https://mlsanity.com/paper/1602.07018/) (2016)
- [A Family of Inexact SQA Methods for Non-Smooth Convex Minimization with Provable Convergence Guarantees Based on the Luo-Tseng Error Bound Property](https://mlsanity.com/paper/1605.07522/) (2016)
- [Newton acceleration on manifolds identified by proximal-gradient methods](https://mlsanity.com/paper/2012.12936/) (2020)
- [An Extrapolated Iteratively Reweighted l1 Method with Complexity Analysis](https://mlsanity.com/paper/2101.03763/) (2021)
- [Sparse Regularization: Convergence Of Iterative Jumping Thresholding Algorithm](https://mlsanity.com/paper/1402.5744/) (2014)
- [A Globally Convergent Proximal Newton-Type Method in Nonsmooth Convex Optimization](https://mlsanity.com/paper/2011.08166/) (2020)
- [Convergence Rate Analysis of Proximal Iteratively Reweighted ℓ1 Methods for ℓp Regularization Problems](https://mlsanity.com/paper/2007.05747/) (2020)
- [A unified analysis of convex and non-convex lp-ball projection problems](https://mlsanity.com/paper/2203.00564/) (2022)
- [A Second-Order Method for Convex ℓ1-Regularized Optimization with Active Set Prediction](https://mlsanity.com/paper/1505.04315/) (2015)
- [A regularized Newton method for ℓq-norm composite optimization problems](https://mlsanity.com/paper/2203.02957/) (2022)

## Abstract (arXiv)

This paper presents a novel hybrid algorithm for minimizing the sum of a continuously differentiable loss function and a nonsmooth, possibly nonconvex, sparse regularization function. The proposed method alternates between solving a reweighted ℓ1-regularized subproblem and performing an inexact subspace Newton step. The reweighted ℓ1-subproblem allows for efficient closed-form solutions via the soft-thresholding operator, avoiding the computational overhead of proximity operator calculations. As the algorithm approaches an optimal solution, it maintains a stable support set, ensuring that nonzero components stay uniformly bounded away from zero. It then switches to a perturbed regularized Newton method, further accelerating the convergence. We prove global convergence to a critical point and, under suitable conditions, demonstrate that the algorithm exhibits local linear and quadratic convergence rates. Numerical experiments show that our algorithm outperforms existing methods in both efficiency and solution quality across various model prediction problems.