Consistency of the group Lasso and multiple kernel learning

By Francis R. Bach. Journal of machine learning research, 2007

823 citations recorded by the source corpus.

We consider the least-square regression problem with regularization by a block l1-norm, that is, a sum of Euclidean norms over spaces of dimensions larger than one. This problem, referred to as the group Lasso, extends the usual regularization by the l1-norm where all spaces have dimension one, where it is commonly referred to as the Lasso. In this paper, we study the asymptotic group selection consistency of the group Lasso. We derive necessary and sufficient conditions for the consistency of group Lasso under practical assumptions, such as model mis specification. When the linear predictors and Euclidean norms are replaced by functions and reproducing kernel Hilbert norms, the problem is usually referred to as multiple kernel learning and is commonly used for learning from heterogeneous data sources and for non linear variable selection. Using tools from functional analysis, and in particular covar iance operators, we extend the consistency results to this infinite dimensional case and also propose an adaptive scheme to obtain a consistent model estimate, even when the necessary condition required for the non adaptive scheme is not satisfied.

View Paper: https://www.semanticscholar.org/paper/5214b65ed56efffd97493a59114a772dfb54caf1

How researchers see this paper

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

Citations in the corpus

Rademacher Chaos Complexities for Learning the Kernel Problem (2010, background): “The latter is often referred to as multiple kernel learning (MKL) in machine learning and nonparametric Group Lasso (Bach, 2008) in statistics. Lanckriet, Cristianini, Bartlett, Ghaoui, and Jordan (2004) pioneered work onMKL and proposed to automatically learn a linear combination of candidate kerne”
On the Linear Convergence of a Proximal Gradient Method for a Class of Nonsmooth Convex Minimization Problems (2013, methodology): “We refer readers to [1, 9] for recent applications of the group Lasso technique.”
Robust Inference on Average Treatment Effects with Possibly More Covariates than Observations (2013, unknown): “In contrast, we obtain sharp results for logistic regression under the same simple and intuitive conditions used for linear modeling by exploiting mathematical techniques of self-concordant functions put forth by Bach (2010). We also provide extensions to prior work on linear models needed to apply ”
Simple and Efficient Multiple Kernel Learning by Group Lasso (2010, methodology): “It is important to note that although the equivalence be- tween MKL and group lasso is not our invention (Bach, 2008), the variational formulation derived in this work is more effective in motivating an efficient optimization algorithm for MKL.”
Breaking the Curse of Dimensionality with Convex Neural Networks (2014, background): “The conditional gradient algorithm may deal with approxima te oracles; however, what we need in this paper is not the additive errors situations considered by Jaggi(2013), but multiplicative ones on the computation of the dual norm ( si ilar to ones derived by Bach(2013) for the regularized problem)”
Multiple Kernel Learning from Noisy Labels by Stochastic Programming (2012, methodology): “We first review a formulation of MKL based on the equivalence between MKL and group Lasso (Xu et al., 2010; Bach, 2008).”
High-dimensional regression with unknown variance (2011, methodology): “We refer to the introduction of [8] for practical examples of this so-called group-sparsity assumption.”
Structured sparsity through convex optimization (2011, background): “…scheme arise also in the context of multi-task learning (Obozinski, Taskar and Jordan, 2010; Quat-toni et al., 2009; Liu, Palatucci and Zhang, 2009) to account for features shared across tasks, and multiple kernel learning (Bach, 2008) for the selection of diﬀer-ent kernels (see also Section 5).”
Minimax Optimal Rates of Estimation in High Dimensional Additive Models: Universal Phase Transition (2015, background): “An application of Talagrand’s concentration inequality yields, with probability at least 1− e−t Rjn(u) ≤ 2 ( ERjn(u) + u √ t n + t n ) .”
Bolasso: model consistent Lasso estimation through the bootstrap (2008, methodology): “…which explain various portions of the regularization path (we assume (A1-3)); many of these results appear elsewhere (Yuan & Lin, 2007; Zhao & Yu, 2006; Fu & Knight, 2000; Zou, 2006; Bach, 2008; Lounici, 2008) but some of the .ner results presented below are new (see Section 2.4).”
Oracle Inequalities and Optimal Inference under Group Sparsity (2010, methodology): “Bach [3] assumes that the predictors (rows of matrixX) are random with a positive definite covariance matrix and proves result s on consistent selection of sparsity patternJ(β∗) when the dimension of the model ( K in our case) is fixed andN → ∞.”
A Selective Review of Group Selection in High-Dimensional Models. (2012, methodology): “Several authors have studied the selection, estimation and prediction properties of the group LASSO in this model; see, for example, Bach (2008), Lounici et al. (2009), Lounici et al. (2011) and Obozinski, Wainwright and Jordan (2011) under various conditions on the design matrices and other regular”
Group sparse optimization by alternating direction method (2013, background): “Thus, we consider the weighted `2-norm in place of the `2-norm in the definition of `w,2,1-norm (2).”
Exploring Large Feature Spaces with Hierarchical Multiple Kernel Learning (2008, methodology): “Note that the last two propositions are not consequences of the similar results for flat MKL [4], because the groups that we consider are overlapping.”
On the asymptotic properties of the group lasso estimator for linear models (2008, methodology): “Besides ANOVA models, the group-lasso penalty has been applied to generalized linear models in Dahinden et al. (2006), Meier et al. (2006) and Nardi and Rinaldo (2007) and to non-parametric problems in Bach (2007) and Ravikumar et al. (2007).”