# Screen & Relax for Sparse Support Identification

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

► To cite this version:

Théo Guyard, Cédric Herzet, Clément Elvira. Screen & Relax for Sparse Support Identification. PGMO DAYS 2023 - Conférence annuelle du Programme Gaspard Monge pour l'Optimisation, Nov 2023, Paris Saclay, France. pp.1-1. hal-04313014

HAL Id: hal-04313014

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

Submitted on 28 Nov 2023

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_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Screen & Relax for Sparse Support Identification

Théo Guyard<fnref n="1" />,<fnref n="2" /> Cédric Herzet<fnref n="1" /> Clément Elvira<fnref n="3" /> Ayşe-Nur Arslan<fnref n="4" />

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

Sparse representations arise in many application fields such as machine learning and signal processing. They usually result from the resolution of some convex optimization problem of the form $x^* \in \arg\min_x f(x) + \lambda g(x)$, where $f(\cdot)$ is a loss function, $g(\cdot)$ is a sparsity-inducing regularization [1] and $\lambda > 0$ is a tradeoff parameter. 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). 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 [2]. We propose a complementary strategy, dubbed relaxing, to detect the position of non-zeros in $x^*$. We then leverage this knowledge to perform second-order iterations on the latter subset of entries, thus expecting improvements in the convergence rate.

The adjacent figure shows the improvements allowed by screening and relaxing on two large-scale datasets, namely bctgca and cancer, drawn from the HDRM database. We set $f(\cdot)$ as a Least-squares and Logistic loss, respectively, and $g(\cdot)$ as an Elastic-net regularization. For each dataset, we solve the corresponding problem for

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

20 logarithmically spaced values of $\lambda$ to span different working regimes and we report the overall solution time. We observe an acceleration factor up to three orders of magnitude when implementing both screening and relaxing tests compared to a vanilla implementation of PG, CD and ADMM, which assesses the interest for the presented “Screen & Relax” strategy.

## References

[1] Shen, L. et al. (2019). Structured sparsity promoting functions. *Journal of Optimization Theory and Applications*, 183, 386-421.

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

<footnote n="1">¹Inria, Centre de l'Université de Rennes, France</footnote>

<footnote n="2">²Insa Rennes, IRMAR UMR CNRS 6625, France</footnote>

<footnote n="3">³CentraleSupélec Rennes, IETR UMR CNRS 6164, France</footnote>

<footnote n="4">⁴Inria, Centre de l'Université de Bordeaux, France</footnote>