Optimization with Sparsity-Inducing Penalties

By Francis R. Bach, Rodolphe Jenatton, Julien Mairal, Guillaume Obozinski. 2011

1,091 citations recorded by the source corpus.

Sparse estimation methods are aimed at using or obtaining parsimonious representations of data or models. They were first dedicated to linear variable selection but numerous extensions have now emerged such as structured sparsity or kernel selection. It turns out that many of the related estimation problems can be cast as convex optimization problems by regularizing the empirical risk with appropriate nonsmooth norms. The goal of this monograph is to present from a general perspective optimization tools and techniques dedicated to such sparsity-inducing penalties. We cover proximal methods, block-coordinate descent, reweighted l2-penalized techniques, working-set and homotopy methods, as well as non-convex formulations and extensions, and provide an extensive set of experiments to compare various algorithms from a computational point of view.

Subfields: Computational Mechanics, Numerical Analysis, Statistics and Probability, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Numerical Analysis

In Statistics and Probability

In Optimization & Training

Citations in the corpus

Learning to learn by gradient descent by gradient descent (2016, background): “ptimization 1 arXiv:1606.04474v1 [cs.NE] 14 Jun 2016 problem is known [Martens and Grosse, 2015]. In contrast, communities who focus on sparsity tend to favor very different approaches [Donoho, 2006, Bach et al., 2012]. This is even more the case for combinatorial optimization for which relaxations ”
FastText.zip: Compressing text classification models (2016, background): “While many approaches have been proposed to select groups of variables during training (Bach et al., 2012; Meier et al., 2008), we are interested in selecting a ﬁxed subset of K words and ngrams from a pre-trained model.”
Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, background): “These problems encompass both convex minimization and saddle point problems arising in robust supervised learning [8, 84] and learning with non-separable losses or regularizers [4, 34].”
Frank-Wolfe Algorithms for Saddle Point Problems (2016, background): “…sparsity inducing norm (Martins et al., 2011) for the parameter x , such as the overlapping group lasso for which the projection is expensive (Bach et al., 2012), while Y could be a combinatorial object such as a the ground state of a planar Ising model (without external ﬁeld) which admits…”
Optimization Methods for Large-Scale Machine Learning (2016, methodology): “thod. There exist other sparsity-inducing regularizers besides the ‘ 1-norm, including group-sparsityinducing regularizers that combine ‘ 1- and ‘ 2-norms taken with respect to groups of variables 74 [147,9], as well as the nuclear norm for optimization over spaces of matrices [32]. While we do not ”
A Universal Catalyst for First-Order Optimization (2015, background): “The functionψ in (1) acts as a regularizer; it is typically chosen to be the square d l2-norm, which is smooth, or to be a non-differentiable penalty such as the l1-norm or another sparsity-inducing norm [2].”
Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning (2014, methodology): “It is also used in sparse estimation for dealing with some nonconvex penalties [2].”
Stochastic Variance Reduction Methods for Saddle-Point Problems (2016, background): “Non-separableregularizers with available efficient proximal operators are numerous, s uch as grouped-norms with potentially overlapping groups, norms ba ed on submodular functions, or total variation (see [15] and references therein, and an example i n S ction 7).”
Auto-Sizing Neural Networks: With Applications to n-gram Language Models (2015, background): “In fact, the two problems can be solved by nearly identical algorithms, because they are convex conjugates of each other (Duchi and Singer, 2009; Bach et al., 2012).”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, methodology): “These representations may be used within alternative optimization frameworks (for more details, see [11] and references therein).”
SLiMFast: Guaranteed Results for Data Fusion and Source Reliability (2015, methodology): “L1-regularization is a well-known method to induce sparsity in the solution [4], i.”
On Regularizing Rademacher Observation Losses (2016, background): “Our second contribution came unexpectedly through this equivalence.”
Distributed Proximal Splitting Algorithms with Rates and Acceleration (2020, background): “But the ability to handle a nontrivial K is behind the success of the Chambolle–Pock [2] or Condat–Vũ algorithms [22,23]: they are well suited for regularized inverse problems in imaging [10], for instance with the total variation and its variants [24–26]; other examples are computer vision problems”
Playing with Duality: An overview of recent primal?dual approaches for solving large-scale optimization problems (2014, background): “Similarly, in fields like machine learning [3], [4], due to th e great ease with which data can now be collected and stored, quite often one has to cope with truly massive dat asets and to train very large models, which thus naturally lead to optimization problems of very high dimens io ality [5].”
On the Effectiveness of Richardson Extrapolation in Machine Learning (2020, neutral): “…can come from (a) non-smooth losses such as max-margin losses used in support vector machines and more generally structured output classiﬁ-cation (Taskar et al., 2005; Tsochantaridis et al., 2005), and (b) sparsity-inducing regularizers (see, e.g., Bach et al., 2012, and references therein).”
A Stochastic Semismooth Newton Method for Nonsmooth Nonconvex Optimization (2018, background): “, [37, 48, 8, 76, 15], and in many other applications.”
Seismic sparse-spike deconvolution via Toeplitz-sparse matrix factorization (2016, methodology): “The proximity operator in equation 18 depends on the regularization functionΨð·Þ, which may not have an explicit form but can be efficiently computed in general (Bach et al., 2012).”
Robust multi-task feature learning (2012, methodology): “Here we propose to employ the accelerated gradient descent [25, 26] to solve the optimization problem, which generates the solution at the k-th iteration (k ≥ 1) by computing the following proximal operator [20, 19, 21, 12, 37, 3]:”
Group sparse regularization for deep neural networks (2016, methodology): “Its use originated in the linear regression routine, where it is called the Lasso estimator, and it has been widely popularized recently thanks to the interest in compressive sensing [20], [21].”
Compressed Sensing using Generative Models (2017, background): “truct an image. These results have been extended by combining sparsity with additional structural assumptions [4, 22], and by generalizations such as translating sparse vectors into low-rank matrices [33, 3, 17]. These University of Texas at Austin, Department of Computer Science, email:ashish :bora”