Orateur
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{equation}
\label{prob}
\tag{$\mathcal{P}$}
\textstyle\min_{\mathbf{x} \in \mathbf{R}^{n}} \ f(\mathbf{x}) + \lambda |\mathbf{x}|_0
\end{equation}
where $f(\cdot)$ is some model-dependent loss function, $\|\cdot\|_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 \eqref{prob} 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 \eqref{prob} 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 \eqref{prob} 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.
| Thématiques | Optimization, High-dimensional statistics, Machine learning |
|---|
