Consistency of the group Lasso and multiple kernel learning

Francis Bach

Source-linked AI summary

Consistency of the group Lasso and multiple kernel learning

Francis Bach

arXiv:0707.3390v2Jul 23, 2007cs.LG

TL;DR

The paper asks when grouped regularization consistently recovers the active model, including under practical misspecification and infinite-dimensional function spaces. It extends group Lasso theory using covariance operators, connects the nonparametric case to multiple kernel learning, and proposes adaptive estimation. The results establish consistency conditions for finite- and infinite-dimensional groups, while identifying limitations of the non-adaptive conditions and refined results.

Problem
The paper studies whether group Lasso can consistently recover active groups, including under model misspecification and in infinite-dimensional function spaces.
Method
The paper extends finite-dimensional group Lasso analysis to Hilbert spaces using covariance operators, links the functional problem to multiple kernel learning, and develops adaptive schemes.
Results
Necessary and sufficient conditions are provided for model consistency of group Lasso and multiple kernel learning under practical distributional assumptions.
Takeaways & Limitations
Group Lasso and its nonparametric multiple-kernel counterpart can consistently estimate the model under the paper’s stated conditions, with adaptive schemes addressing cases where the non-adaptive condition fails.
Takeaways & Limitations
For group Lasso, the strong condition is sufficient and the weak condition necessary, and the refined results for Section 2.4 are not extended to infinite-dimensional groups.

Abstract

from arXiv · show

We consider the least-square regression problem with regularization by a block 1-norm, i.e., 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 1-norm where all spaces have dimension one, where it is commonly referred to as the Lasso. In this paper, we study the asymptotic model consistency of the group Lasso. We derive necessary and sufficient conditions for the consistency of group Lasso under practical assumptions, such as model misspecification. 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 covariance 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.

1. Introduction

The introduction motivates group Lasso as a structured extension of Lasso and frames the paper around its consistency under grouped covariates, misspecification, and infinite-dimensional generalizations.

Motivation: Regularization supports learning from high-dimensional data and has well-developed theory for squared Euclidean and Hilbertian norms.These methods also lead to practical algorithms based on linear algebra.
Lasso: The Lasso uses the ℓ1-norm to enable variable selection through sparse loading vectors with many zeros.Its consistency asks whether the true sparsity pattern is recovered as the number of observations grows.
Lasso: Lasso consistency depends on covariance conditions: it holds in low-correlation settings but fails under strong correlations.Adaptive data-dependent weights can preserve consistency across these settings.
Group Lasso: The group Lasso replaces individual absolute-value penalties with Euclidean norms over covariate groups, encouraging entire groups to be selected or discarded together.The paper extends Lasso consistency results while allowing practical model misspecification.
Paper Scope: The paper develops consistency results for group Lasso and Hilbert-space extensions, adaptive schemes, and synthetic simulations.The sections cover finite-dimensional groups, infinite-dimensional spaces, adaptive methods, and experiments.
Multiple Kernel Learning: For groups represented by reproducing kernel Hilbert spaces, group Lasso becomes multiple kernel learning through convex combinations of basis kernels.The framework applies to kernel selection, heterogeneous data fusion, and nonlinear variable selection.

2. Consistency of the Group Lasso

The group Lasso is consistent under a strict covariance-and-weight condition, while a weaker condition is necessary; adaptive weighting can restore consistency when the non-adaptive condition fails.

Setup: The group Lasso estimates grouped covariates using a block ℓ1-norm and targets consistency of both loading vectors and group sparsity patterns.The analysis assumes a fixed finite number of groups and permits model misspecification under the stated covariance assumptions.
Consistency conditions: The strict condition is sufficient for path consistency, whereas the weak condition is necessary whenever a consistent solution exists.The sufficient result requires λn → 0 and λn n^1/2 → +∞; the necessary result applies even to possibly data-dependent regularization sequences.
Consistency conditions: When the weak correlation condition fails, the group Lasso cannot consistently recover the model along its solution path.For groups larger than one, the strict condition is not generally necessary, unlike the dimension-one Lasso case.
Adaptive scheme: Adaptive weighting can achieve consistency by increasing weights on inactive groups and decreasing them on active groups, provided the sparsity pattern is known or estimated.This weighting strategy is proposed to overcome failure of the non-adaptive necessary condition.
Refinements: Even when full loading-vector consistency fails, the sparsity pattern may remain consistently estimable under a positive limiting regularization parameter.The relevant criterion is whether the corresponding population optimization problem has the correct sparsity pattern.
Functional extension: The functional extension replaces finite-dimensional groups with Hilbert spaces, connecting non-parametric group selection to multiple kernel learning.The alternative squared block-norm formulation preserves the solution path and supports consistency analysis in the functional case.

3. Covariance Operators and Multiple Kernel Learning

The paper extends group-Lasso consistency analysis to infinite-dimensional function spaces using covariance operators and connects the resulting estimator to multiple kernel learning. Under stated operator and moment conditions, empirical covariance estimates converge and sparsity-pattern consistency follows under necessary and sufficient conditions.

Multiple Kernel Learning: Nonparametric group Lasso estimates sparse combinations of functions and can be interpreted as multiple kernel learning.Each group is a potentially infinite-dimensional function space; in MKL, the framework corresponds to learning a convex combination of kernels.
Covariance Operators: Covariance operators generalize covariance matrices to RKHSs and organize cross-covariances across multiple input spaces.The construction uses block covariance operators on the product space F = F1 × · · · × Fm.
Covariance Operators: Under finite fourth-order kernel moments, empirical covariance operators converge in Hilbert-Schmidt and operator norms at rate Op(n^-1/2).The same rate is stated for the natural empirical estimators of the cross-covariance and joint covariance operators.
Assumptions: The analysis assumes an invertible joint correlation operator, ensuring uniqueness of the component functions and excluding nontrivial constant linear combinations.In generalized additive models, this is the empty concurvity space assumption.
Consistency: If condition (18) holds and μn → 0 while μn n^1/2 → +∞, the estimator and its sparsity pattern converge in probability to the target.A converse theorem states that consistency of the estimate and selected set implies condition (19).
Estimation: The nonparametric group Lasso estimate has a unique solution with probability tending to one and reduces to a finite-dimensional optimization problem.The representer result implies each fitted component is supported by kernel evaluations at the observed data.

4. Adaptive Group Lasso and Multiple Kernel Learning

The paper develops adaptive two-step procedures for group Lasso and multiple kernel learning that achieve consistency without the usual correlation conditions. The finite-dimensional procedure also recovers the correct sparsity pattern at the standard parametric rate, while the nonparametric result establishes consistency without a parametric-rate guarantee.

Adaptive procedures: Adaptive two-step procedures achieve consistency without conditions such as Eq. (4) or Eq. (18).They are adapted from the adaptive Lasso and address both group Lasso and multiple kernel learning.
Adaptive Group Lasso: For finite-dimensional groups, the adaptive group Lasso achieves both Op(n^-1/2) consistency and correct pattern estimation.The result covers asymptotic properties of both estimation error and selected models.
Adaptive Group Lasso: If n^-1/2 ≫ µn ≫ n^-1/2−γ/2, the adaptive estimate converges to w, selects J consistently, and has asymptotically normal active-group errors.The limiting normal distribution has mean zero and covariance involving Σ^-1.
Adaptive Multiple Kernel Learning: The nonparametric procedure has no established Op(n^-1/2) consistency result, and precise convergence rates remain open.This distinguishes the infinite-dimensional result from the finite-dimensional adaptive group Lasso theorem.
Adaptive Multiple Kernel Learning: In the nonparametric setting, the adaptive estimate converges to f and its sparsity pattern converges to J in probability.The procedure is constructed from a consistent least-square estimate and adaptive weights.
Adaptive Multiple Kernel Learning: Data-dependent weights are theoretically motivated for multiple kernel learning, while trace-normalized kernel weights may produce suboptimal solutions.The proposed weighting scheme is intended to address consistency problems in the usual MKL framework.

5. Simulations

Synthetic experiments examine finite- and infinite-dimensional group Lasso behavior under satisfied and violated consistency conditions, comparing non-adaptive and adaptive weighting schemes. The results show that adaptive weighting can recover both model and estimation consistency in settings where non-adaptive regularization is limited.

Groups of Finite Sizes: The simulations compare unit-trace and adaptive weighting schemes under correlation conditions that are either satisfied or violated.Finite-dimensional experiments use four groups of size two, while the nonparametric experiments use four function-valued groups.
Groups of Finite Sizes: When the strict consistency condition is satisfied, non-adaptive and adaptive schemes obtain model-consistent estimates with good loading-vector estimation.This behavior is illustrated for both finite-dimensional and nonparametric group Lasso experiments.
Groups of Finite Sizes: When the consistency condition is violated, non-adaptive regularization can yield no model-consistent estimates or model consistency without regular consistency, whereas adaptive weighting achieves both consistencies.The finite-dimensional experiments distinguish regimes with and without model-consistent estimates; the adaptive scheme allows both consistencies.
Groups of Finite Sizes: Across sampled covariance matrices, good model-consistent estimates become less frequent as the consistency-condition quantity exceeds one.Below one, model-consistent estimates with errors below 10^-1 occur with overwhelming probability; above one, model-inconsistent estimates become more common.
Nonparametric Case: In the nonparametric experiments, adaptive weighting achieves both consistencies, while non-adaptive weighting fails to obtain good model estimates when the condition is not satisfied.The experiments use Gaussian kernels and compare regularization paths for 1000 independent samples.

6. Conclusion

The paper extends Lasso consistency theory to finite- and infinite-dimensional group Lasso problems. It provides necessary and sufficient conditions for model consistency and identifies several directions for extending the analysis.

6. Conclusion: The paper provides necessary and sufficient conditions for model consistency of finite-dimensional group Lasso and its nonparametric multiple-kernel version.These results hold under practical assumptions on the data-generating distributions.
6. Conclusion: The analysis could be extended to limiting distributions and convergence rates for group Lasso and adaptive group Lasso estimators.The authors also identify generalized linear models, growing numbers of groups or kernels, and other sparsity-inducing norms as extensions.
Proof and optimization machinery: The appendices derive optimality conditions and dual formulations using second-order-cone constraints and KKT conditions.The functional formulation is reduced through representer-theorem expansions to finite-dimensional kernel-matrix problems.

A.5 Proof of Proposition 14

The proof establishes uniqueness of the solution in the infinite-dimensional setting by showing that non-uniqueness would contradict invertibility of the covariance operator.

A.5 Proof of Proposition 14: A non-unique solution would produce distinct coefficient vectors whose centered kernel-function value vectors are linearly dependent.The corresponding empirical covariance matrix would be singular while marginal empirical variances remain normalized.
A.5 Proof of Proposition 14: Consistency of the empirical covariance operator and invertibility of CXX rule out the singular covariance structure implied by non-uniqueness.This contradiction proves uniqueness of the solution.

B.1 Proof of Theorem 2

The proof of Theorem 2 first establishes consistency on the active groups and then verifies that the zero-extended estimator satisfies the full problem's optimality conditions with probability tending to one.

B.1 Proof of Theorem 2: When λ_n tends to zero, the active-group objective converges to a population quadratic objective uniquely minimized at the true loading vector.Standard M-estimation results then yield convergence of the active-group estimator.
B.1 Proof of Theorem 2: The active-group estimator is extended by zeros on inactive groups before checking the remaining optimality condition.Uniqueness of the full solution holds with probability tending to one under invertibility of ΣXX.
B.1 Proof of Theorem 2: The probability that the constructed estimator is optimal converges to one.The argument uses convergence of empirical covariances and the assumed fourth-order moment condition.

B.2 Proof of Theorem 3

The proof derives the asymptotic behavior of the relevant stochastic terms and uses the optimality conditions to establish the theorem by contradiction.

The proof assumes an inactive group violates the required condition and derives a contradiction from the resulting optimality failure.
With probability tending to one, the estimated active set equals J, allowing the optimality condition to be applied on the selected support.
The assumed inequality ∥v∥ > d_i yields a nonvanishing probability of violating optimality, completing the contradiction.
The statistic C_n is asymptotically normal because it is a U-statistic with a square-integrable kernel.Its mean is zero under E(Xε)=0.
The conditional covariance of X_i given X_J is positive definite when Σ_XX is invertible.

B.3 Proof of Theorem 4

The proof analyzes the reduced group-Lasso problem and verifies optimality for inactive groups under the condition in Eq. (6).

Lemma 21 shows that the rescaled reduced-problem minimizer converges in probability to its unique limiting minimizer.
The proof checks inactive-group optimality separately for strict and boundary cases of the relevant inequality.
For boundary groups satisfying Eq. (6), the derived deterministic term is asymptotically strictly smaller than d_i.
This strict inequality establishes the required optimality condition and concludes the proof.

B.4 Proof of Proposition 6

The proof establishes the proposition by characterizing correct pattern selection through inactive-group optimality and deriving the required limiting Gaussian behavior.

On an event whose probability tends to one, correct sparsity-pattern selection is equivalent to satisfying the inactive-group optimality conditions.
The optimality condition reduces to the maximum normalized inactive-group statistic being at most λ_0.
The covariance of the limiting Gaussian vector is the conditional covariance Σ_XJcXJc|XJ.
The relevant empirical covariance operators converge at rate O_p(n^-1/2), supporting the asymptotic calculations.
The operator bounds used in the proof extend to suboperators such as Σ_XJXJ and Σ_XiXi.

C.2 Proof of Theorem 11

The proof extends the consistency argument to covariance operators and shows that the reduced multiple-kernel estimate converges under a slower regularization schedule.

If μ_n → 0 and μ_n n^1/2 → +∞, the reduced estimator converges in norm to the target function.
The proof controls the reduced objective using local differentiability, curvature bounds, and a shrinking neighborhood around the target.
Replacing D_n by its limit D incurs only an o_p(1) error in the optimality analysis.
The deterministic inactive-group term converges to a quantity strictly below one under Eq. (18).
Because the stochastic remainder is o_p(μ_n), the inactive-group optimality conditions hold with probability tending to one.

C.3 Proof of Theorem 12

The proof establishes that consistent recovery of the active group pattern requires μ_n n^1/2 to diverge, then uses contradiction and asymptotic optimality conditions to prove Theorem 12.

Necessary tuning condition: Consistency of both the estimator and its active groups implies μ_n n^1/2 →∞ in probability.This is stated directly as Proposition 26 under assumptions (A4-7) with a nonempty true active set.
Contradiction setup: The contradiction argument assumes a subsequence on which μ_n n^1/2 remains bounded and converges to a finite limit.This bounded subsequence is used to analyze the inactive-group optimality condition.
Asymptotic fluctuation: A constructed inactive-direction statistic has an asymptotically normal distribution with strictly positive variance.The construction uses covariance-operator range relations and a U-statistic representation of the stochastic term.
Optimality contradiction: The relevant optimality expression is asymptotically strictly positive, so the inactive-group optimality condition fails with nonvanishing probability.This contradicts model consistency and proves the required divergence of μ_n n^1/2.
Sufficiency argument: The theorem proof then combines consistency of the restricted estimator with bounds showing inactive-group conditions hold under the prescribed regularization scaling.For the least-squares estimator, the stochastic error is O_p(n^-1/2), while the penalty contribution is lower bounded by μ_n n^γ/2.

D.3 Proof of Theorem 18

The proof of Theorem 18 analyzes a function-space construction through covariance operators and establishes consistency using spectral and operator arguments, with Gaussian-kernel calculations providing a tractable setting.

Restricted estimator: The restricted minimizer ˜f converges in probability to f, and its zero pattern converges in probability as well.The proof sets f_Jc=0 and uses μ_n=μ_0 n^-1/3 together with Lemma 25.
Support recovery: When γ>1, the inactive-group optimality condition holds with probability tending to one.The proof compares upper bounds of O_p(n^-1/2+n^-1/6+η) with a penalty lower bound of n^-1/3 n^γ/6.
Operator framework: The operator framework uses convolution and pointwise-multiplication operators together with inner products in the RKHS and relevant L2 spaces.These definitions support the functional-analytic proof and its covariance-operator calculations.
Spectral construction: The covariance operator’s positive eigenvalues and eigenvectors define an orthonormal sequence in L2(pX) used in the function-space argument.The construction sets f_k=λ_k^-1/2 e_k and establishes orthonormality in L2(pX).
Gaussian-kernel setting: For Gaussian inputs and Gaussian kernels, orthonormal bases make covariance operators and consistency conditions computable without sampling.Required expectations can also be computed exactly using singular-value decomposition for positive matrices.