Journée Doctorant·e·s Rennais·e·s en Statistique - 2024

Discrete Optimization Methods for l0-norm Problems

18 mars 2024, 15:45

20m

Amphi Lebesgue (IRMAR)

Statistique théorique

Orateur

Theo Guyard (INSA Rennes / INRIA Rennes)

Description

Sparse linear models are ubiquitous in various applied mathematical fields such as high-dimensional statistics, machine learning and signal processing, among many others. Constructing such models can be done via the resolution of optimization problems of the form
$$\begin{array}{}\text{(}\mathcal{P}\text{)}& \underset{\mathbf{x}\in {\mathbf{R}}^n}{min}f(\mathbf{x})+\lambda |\mathbf{x}{|}_0\end{array}$$
where $f(\cdot )$ is some model-dependent loss function, $\Vert \cdot {\Vert }_0$ is the so-called ``${\ell }_0$-norm'' which promotes sparsity by counting the number of non-zero entries in its argument and $\lambda >0$ is a tuning hyperparameter. Although the solutions of $\text{(}\mathcal{P}\text{)}$ generally benefit from desirable statistical properties, this problem is NP-hard to solve in the general case and has long been considered intractable. Nonetheless, recent contributions have revived the interest in solving $\text{(}\mathcal{P}\text{)}$ and several lines of research have outlined that this problem can sometimes be solved efficiently via discrete optimization methods. We propose to discuss the statistical relevance of $\text{(}\mathcal{P}\text{)}$ regarding other strategies allowing to construct sparse linear models and review the recent advances made to solve this problem exactly. In particular, we will introduce some tools derived from the discrete optimization community that appear to be well-tailored to address this problem.