<figure><img src="image_1.png" /></figure>

HAL
open science

# Screen-and-Relax for Sparse Support Identification

Théo Guyard, Cédric Herzet, Clément Elvira

<figure><img src="image_2.png" /></figure>

## To cite this version:

Théo Guyard, Cédric Herzet, Clément Elvira. Screen-and-Relax for Sparse Support Identification. Journées SMAI MODE 2024, Mar 2024, Lyon, France. pp.1-1. hal-04423101

HAL Id: hal-04423101

https://hal.science/hal-04423101v1

Submitted on 29 Jan 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Screen-and-Relax for Sparse Support Identification

• Théo Guyard (Inria and Insa, CNRS, IRMAR - UMR CNRS 6625, Rennes, France)

• Cédric Herzet (Ensai, CNRS, CREST - UMR 9194, Rennes, France)

• Clément Elvira (CentraleSupelec, CNRS, IETR - UMR 6164, Rennes, France)

**Keywords:** Sparse problems, screening tests, relaxing tests.

**Abstract:** Sparse modeling arises in various application fields such as machine learning, signal processing and inverse problems, among others [1]. In this context, it is of tantamount interest to solve convex optimization problems of the form

$$x^* \in \arg \min_{x} f(x) + \lambda g(x)$$

where $f(\cdot)$ is a loss function and $g(\cdot)$ is a sparsity-inducing regularization whose strength is driven by the parameter $\lambda > 0$. The latter problem can be addressed with first-order optimization methods such as Proximal Gradient (PG), Coordinate Descent (CD) or Alternating Direction Method of Multipliers (ADMM) [2]. A popular strategy to exploit the problem structure is to enhance these algorithms with screening tests to detect the position of zeros in $x^*$. This allows shrinking the problem dimensionality and saving computational resources during the resolution process [3]. We propose a complementary strategy, dubbed relaxing, to detect the position of non-zeros in $x^*$. Leveraging this knowledge, we partially smooth the objective function of the problem which allows performing second-order iterations instead of first-order ones. In particular, this allows reaching super-linear convergence rates in finite time although only sub-linear or linear convergence rates are typically accessible for such optimization problems. By implementing screening and relaxing tests together in any solution method, we thus expect a double acceleration resulting from the dimensionality reduction and the convergence rate improvement. The proposed method is assessed on both synthetic and real-world datasets of varying characteristics and we observe an acceleration factor of up to three orders of magnitude compared to a vanilla implementation of the PG, CD and ADMM algorithms.

References

[1] Tropp, J. et al., Computational methods for sparse solution of linear inverse problems, *Proceedings of the IEEE*, 98(6), 948-958, 2010.

[2] Bach, F. et al., Convex optimization with sparsity-inducing norms *Optimization for machine learning*, 5, 19-53, 2011.

[3] Xiang, Z. et al., Screening tests for lasso problems. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, 39(5), 1008-1027, 2016.