PaperlayerView exact revision on arXiv

Source-linked AI summary

Oracle Inequalities and Optimal Inference under Group Sparsity

Karim Lounici, Massimiliano Pontil, Alexandre B. Tsybakov, Sara van de Geer

arXiv:1007.1771v3math.ST

TL;DR

The paper asks how to estimate sparse regression vectors when known groups create a stronger sparsity structure, for prediction and model selection. It analyzes Group Lasso through oracle inequalities and mixed-norm bounds, then establishes minimax optimality up to logarithmic factors and shows cases of improvement over Lasso. These results extend to multi-task learning and, with a new maximal moment inequality, to noise distributions having bounded fourth moment.

  • Problem

    The paper studies sparse regression estimation when variables belong to known groups and only a few groups are relevant, for prediction and model selection.

  • Method

    The paper analyzes Group Lasso oracle inequalities and mixed (2,p)-norm bounds, applies the method to multi-task regression through a block-diagonal formulation, and extends the analysis beyond Gaussian noise.

  • Results

    Group Lasso prediction and (2,p)-norm rates are minimax optimal up to a logarithmic factor, and Group Lasso can improve prediction and estimation over Lasso in some cases.

  • Takeaways & Limitations

    The group sparsity assumption can provide quantitative advantages over usual sparsity, particularly in multi-task learning.

  • Takeaways & Limitations

    Sparsity-pattern selection requires active group coefficients to be sufficiently separated from zero, with norms at least somewhat larger than the noise level.

Abstract

from arXiv · show

We consider the problem of estimating a sparse linear regression vector $β^*$ under a gaussian noise model, for the purpose of both prediction and model selection. We assume that prior knowledge is available on the sparsity pattern, namely the set of variables is partitioned into prescribed groups, only few of which are relevant in the estimation process. This group sparsity assumption suggests us to consider the Group Lasso method as a means to estimate $β^*$. We establish oracle inequalities for the prediction and $\ell_2$ estimation errors of this estimator. These bounds hold under a restricted eigenvalue condition on the design matrix. Under a stronger coherence condition, we derive bounds for the estimation error for mixed $(2,p)$-norms with $1\le p\leq \infty$. When $p=\infty$, this result implies that a threshold version of the Group Lasso estimator selects the sparsity pattern of $β^*$ with high probability. Next, we prove that the rate of convergence of our upper bounds is optimal in a minimax sense, up to a logarithmic factor, for all estimators over a class of group sparse vectors. Furthermore, we establish lower bounds for the prediction and $\ell_2$ estimation errors of the usual Lasso estimator. Using this result, we demonstrate that the Group Lasso can achieve an improvement in the prediction and estimation properties as compared to the Lasso.

1 Introduction

The paper studies Group Lasso estimation when known variable groups induce structured sparsity, targeting prediction, estimation, and sparsity-pattern selection. It establishes oracle bounds, minimax optimality up to logarithmic factors, and cases where Group Lasso improves on Lasso, including multi-task learning.

  • 1 Introduction: Group sparsity assumes that variables are partitioned into known groups, with only a few groups relevant to estimating the regression vector.The Group Lasso uses mixed (2,1)-norm regularization across groups.
  • 1.1 Outline of the main results: The paper establishes prediction and ℓ2 estimation bounds for the general Group Lasso, including a slow-rate bound requiring no assumption on the design matrix.In multi-task learning, the bound’s dependence on M disappears as T increases when M grows slower than exp(T).
  • 1.1 Outline of the main results: The analysis extends sparsity-pattern selection to Group Lasso and derives convergence rates for mixed (2,p)-norm estimation errors with 1 ≤ p ≤ ∞.The multi-task formulation represents each variable’s coefficients across tasks as one group.
  • 1.1 Outline of the main results: The prediction and (2,p)-norm upper-bound rates are minimax optimal up to a logarithmic factor over a class of group-sparse vectors.This establishes optimality across all estimators in the stated class.
  • 1.1 Outline of the main results: Group Lasso can outperform usual Lasso in prediction and estimation, with the comparison clarified especially for multi-task learning.The paper establishes lower bounds for Lasso and compares them with Group Lasso upper bounds under the same model assumptions.
  • 1.1 Outline of the main results: The multi-task analysis extends to noise distributions with bounded fourth moment through a new maximal moment inequality.The inequality may also be of independent interest.

2 Method

The paper formulates grouped sparse linear regression and applies the Group Lasso to simultaneous estimation of multiple regression equations, including multi-task learning and related settings.

  • Model: The regression model uses a deterministic design matrix X, response vector y, coefficient vector β*, and random noise W.The framework also extends to random designs satisfying the stated assumptions with high probability.
  • Group sparsity: Variables are partitioned into prescribed disjoint groups, and group sparsity means only a small number of groups contain nonzero coefficients.The mixed (2,p)-norm aggregates Euclidean norms within groups, while J(β) and M(β) record relevant groups and their number.
  • Estimator: The Group Lasso estimator minimizes penalized least squares with group-specific positive tuning parameters λ1,...,λM.Its optimality conditions are characterized through the subdifferential of the convex objective.
  • Multi-task learning: In the multi-task formulation, stacking T regressions creates a block-diagonal single regression with groups collecting each variable across all tasks.The common group structure encodes variables that are relevant in at least one task, with group sparsity bounded by s.
  • Applications: The framework covers multi-task learning, conjoint analysis, seemingly unrelated regressions, and longitudinal or panel data.Multi-task learning is motivated by exploiting relationships across tasks when the number of tasks and variables can be large relative to the sample size.

3 Sparsity oracle inequalities

The paper establishes high-probability Group Lasso oracle inequalities for prediction and estimation, first under restricted eigenvalue conditions and with extensions for approximate sparsity and overlapping groups.

  • Design conditions: The restricted eigenvalue assumption extends the usual Lasso condition by replacing ℓ1 norms with weighted mixed (2,1)-norms.It can be satisfied under conditions including a positive minimum eigenvalue, restricted isometry, or coherence of the normalized Gram matrix.
  • Main oracle inequalities: Theorem 3.1 gives high-probability prediction and ℓ2 estimation bounds for Group Lasso solutions under Gaussian noise.The result includes a slow-rate bound requiring no design-matrix assumption and faster bounds under restricted eigenvalue conditions.
  • Approximate sparsity: Theorem 3.2 generalizes the oracle inequality to include a bias term, making it applicable when β* is only approximately group sparse.The bound compares the estimator with an arbitrary vector and accounts for coefficients outside a small reference set.
  • Overlapping groups: Several prediction and estimation inequalities remain valid when the prescribed groups overlap.The extension follows because the relevant parts of the proofs do not require disjoint groups.

4 Sparsity oracle inequalities for multi-task learning

In multi-task learning, the general Group Lasso results yield non-asymptotic oracle bounds whose dependence on the variable dimension becomes negligible when the number of tasks is sufficiently large.

  • Multi-task specialization: The multi-task design has K = MT and N = nT, with each group containing one variable’s coefficients across the T tasks.The block-diagonal structure gives Ψj = (1/T)I_T for every group.
  • Dimension dependence: As T increases, the oracle bounds’ dependence on M disappears provided M grows more slowly than exp(T).This improves the multi-task results while retaining non-asymptotic guarantees.
  • Regime of validity: The bounds are meaningful when the group sparsity index s is small relative to the sample size n and the logarithm of the dimension.They remain valid for fixed n, M, and T, with asymptotic regimes treated as special cases.
  • High-dimensional regime: M = exp(nγ) is allowed for arbitrarily large γ > 0 when T > nγ.Thus, no relation between n and M is required in the regime where T exceeds log M.
  • Prediction and tuning: The multi-task results include a slow-rate prediction guarantee without restrictions on X^T X when the mixed (2,1)-norm of β* is bounded.The authors choose a smaller tuning parameter than in earlier work because it leads to minimax rate optimality.

5 Coordinate-wise estimation and selection of sparsity pattern

Under a stronger coherence condition, the paper obtains coordinate-wise mixed-norm bounds and uses them to estimate the group sparsity pattern, including in the multi-task setting.

  • Mixed-norm bounds: Bounds are derived for mixed (2,p)-norms for every 1 ≤ p ≤ ∞ under Assumption 5.1, a stronger coherence-type condition.The condition extends the usual coherence assumption and implies the restricted eigenvalue condition used earlier.
  • Coordinate-wise estimation: Theorem 5.1 strengthens compound risk bounds by controlling estimation error for each group separately.This coordinate-wise control enables subsequent sparsity-pattern selection.
  • Pattern selection: For p = ∞, thresholding the Group Lasso group norms yields an estimator of the correct sparsity pattern with high probability.The thresholded set is intended to recover J(β*) under the theorem’s assumptions.
  • Selection condition: Exact sparsity-pattern selection requires active groups to be separated from zero by more than a noise-level threshold.This beta-min condition is described as inevitable because arbitrarily small active groups cannot be reliably distinguished from noise.
  • Inference: The mixed-norm inequalities with data-driven right-hand sides can serve as confidence bands for the unknown coefficient vector β*.Their high-probability validity makes them usable for uncertainty assessment across mixed norms.

6 Minimax lower bounds for arbitrary estimators

The paper proves minimax lower bounds for estimating group-sparse vectors, showing that the Group Lasso upper-bound rates are optimal up to a logarithmic factor. The result also generalizes known lower bounds for ordinary sparsity and clarifies the comparison with usual Lasso rates.

  • Minimax optimality: The convergence rates for prediction and mixed (2,p)-norm estimation are minimax-optimal up to a logarithmic factor over group-sparse vectors.The result applies to all estimators under the stated assumptions.
  • Proof strategy: The lower-bound proof relies on a restricted-eigenvalue-type Assumption 6.1 controlling vectors whose group support differs in at most 2s groups.The construction uses separated finite subsets of group-sparse vectors and Gaussian testing arguments.
  • Minimax optimality: When T > log(eM/s) and Ts < 8, the lower-bound rate is the standard parametric order 1/n.These bounds are obtained by reducing the problem to distinguishing between two group-sparse vectors.
  • Minimax optimality: The lower bounds cover squared and indicator losses, with rates matching corresponding Group Lasso upper bounds after replacing log M by log(eM/s).The paper conjectures that log(eM/s), rather than log M, is optimal, and notes this is known for T = 1 under prediction loss.
  • Relation to ordinary sparsity: For T = 1, the group-sparse class becomes the ℓ0-ball of radius s, so the theorem generalizes minimax lower bounds for ordinary sparsity.It additionally covers ℓp errors for 1 ≤ p ≤ ∞ and general loss functions.

7 Lower bounds for the Lasso

This section establishes lower bounds for the usual Lasso and compares them with Group Lasso upper bounds. The comparison shows that Group Lasso can have better prediction and ℓ2 estimation rates under group sparsity, especially in multi-task settings.

  • Comparison with Group Lasso: The usual Lasso does not exhibit the dimension independence available to Group Lasso in the multi-task setting.The comparison is made under the same model assumptions using Lasso lower bounds and Group Lasso upper bounds.
  • Multi-task example: In the orthogonal multi-task example, the Lasso lower bound remains dependent on the number of tasks, while Group Lasso bounds can become independent of M and T when T ≥ log M.The example assumes task design matrices are orthogonal and shared support across tasks.
  • Comparison with Group Lasso: When T ≥ log M, the Group Lasso upper bound is smaller than the Lasso lower bound by a logarithmic factor.For T < log M, the corresponding prediction-rate ratio is of order T in favor of Group Lasso.
  • Comparison with Group Lasso: For T < log M, the Lasso lower bound has order s(log M)/n, whereas the Group Lasso upper bound has order s(log M)/(nT).The same comparison extends to ℓ2 estimation errors.

8 Non-Gaussian noise

The paper extends its Group Lasso results beyond Gaussian noise to independent, zero-mean noise with finite fourth moment. Under additional design and coherence conditions, prediction, estimation, and sparsity-pattern guarantees remain available, with weaker concentration.

  • Assumptions: The non-Gaussian analysis assumes independent noise components with zero mean and finite fourth moment.The extension is developed for the multi-task setting.
  • Concentration: The concentration effect is weaker under non-Gaussian noise, although the resulting bounds remain similar to those established earlier.The technical analysis uses a mild bounded-design-type assumption and maximal moment inequalities.
  • Support recovery: With an additional condition, the estimated index set correctly recovers the sparsity pattern of β* with high probability.The result concerns any solution of the Group Lasso optimization problem under the theorem’s assumptions.

9 Maximal moment inequality

The paper proves a maximal moment inequality for coordinatewise maxima of sums of independent random vectors. The result provides an explicit constant and is used in the non-Gaussian Group Lasso analysis.

  • Inequality: Lemma 9.1 bounds the m-th moment of the maximum coordinate of sums of independent random vectors.The vectors lie in R^M, and the bound applies for any m ≥ 1 and M ≥ 1.
  • Constant: The inequality uses an explicit constant c(m) satisfying 2 ≤ c(m) ≤ e^(m−1) + 1.The constant is defined through the dimension M and moment order m.
  • Relation to prior inequalities: For m = 2, the lemma implies Nemirovski’s inequality up to constants but differs by interchanging the maximum and the sum.The paper’s result focuses on the ℓ∞ case rather than general ℓp norms.
  • Relation to prior inequalities: The explicit constant has optimal order in m, although it is larger than the constant available from Rio’s sharper moment inequality.The comparison concerns the order of the constant rather than the main inequality’s applicability.
  • Proof strategy: The proof combines Rademacher symmetrization, Hoeffding’s inequality, Jensen’s inequality, and de-symmetrization.These steps establish the maximal-moment bound for independent random variables.

A Auxiliary results

The appendix gathers auxiliary lemmas used to connect the paper’s structural assumptions and support the main analysis. It also records inequality-based arguments and a separation lemma used in the proofs.

  • Lemma A.1 supplies an auxiliary result for independent standard Gaussian variables and a nonzero vector, while an earlier result is cited as the source of a bound used in Lemma 3.1.
  • Lemma A.2 links Assumptions 5.1 and 3.1, providing a condition used extensively in the Section 5 analysis.
  • The proofs control separate terms using Assumption 5.1 together with Cauchy–Schwarz and Minkowski’s inequalities before combining the resulting bounds.
  • Lemma A.3 establishes a support-separation consequence under the condition ρ′(ω, ω′) ≥ Ts for Ts ≥ 8, using a contradiction argument based on |J(ω, ω′)|.
Loading 1007.1771v3…