Examples for Sparse Optimization

Examples of sparse non-smooth convex optimization problems

The sparse non-smooth convex optimization usually have the following representations:
$$\min_{x} \hspace{0.5cm} f(Ax)+g(x)$$
where $f$ is smooth convex function and $g$ is potentially non-smooth convex function and $A$ is a linear operator.

Some examples of this model are listed here:

1. Lasso problem: see wiki and its generalizations:
   • Elastic net
   • Group Lasso
   • Fused lasso
   • Quasi-norms and bridge regression
   • Adaptive lasso
   • Prior lasso
2. Blasso problem (infinite dim ver of Lasso): see [2]
3. Entropy regularized Optimal transport problem: see [5] equation (5)
   $$\min_{P \in \Pi(\mu, \nu)} \sum_i\sum_j C_{ij} P_{ij} - \varepsilon H(P)$$
   Note that this problem is convex.
4. Basic Pursuit problem $$\min_{x: Ax=b} ||x||_1$$
5. Some $f$ functions:
   • proposed in [1], epage 10:
     • Quadratic distance (a.k.a. least squares or linear regression)
     • $\beta$-divergence
     • Kullback-Leibler divergence
     • Logistic regression
   • proposed in [3], epage :
     • (Non-smooth) Hinge Loss function (in Support Vector Machine problems): see [3], epage 11
     • Smooth Hinge Loss function: see [3], epage 38
     • $\ell_1/\ell_2$ Multi-task Regression and $\ell_1/\ell_2$ Multinomial Logistic Regression: see [3] epage 37
6. Some $g$ functions:
   • proposed in [4], table 1, epage 6: $\ell_1$-norm (Lasso), $\ell_\infty$-norm (anti-sparse coding problem), $\ell_p$-norm, atomic-norm, elastic-net-regularization, ridge regression, …
   • Sparse group Lasso: see [3] epage 39

References

[1]: Dantas, Cassio F., Emmanuel Soubies, and Cédric Févotte. “Expanding boundaries of Gap Safe screening.” The Journal of Machine Learning Research 22.1 (2021): 10665-10721.
[2]: Bredies, Kristian, and Hanna Katriina Pikkarainen. “Inverse problems in spaces of measures.” ESAIM: Control, Optimisation and Calculus of Variations_ 19.1 (2013): 190-218.
[3]: Ndiaye, Eugene. Safe optimization algorithms for variable selection and hyperparameter tuning. Diss. Université Paris-Saclay (ComUE), 2018.
[4]: Jaggi, Martin. “Revisiting Frank-Wolfe: Projection-free sparse convex optimization.” International conference on machine learning. PMLR, 2013.
[5]: Rawson, Michael, and Jakob Hultgren. [“Optimal Transport for Super Resolution Applied to Astronomy Imaging.”[ref5] 2022 30th European Signal Processing Conference (EUSIPCO). IEEE, 2022.