PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparse group lasso and high dimensional multinomial classification

Martin Vincent, Niels Richard Hansen

arXiv:1205.1245v2stat.MLcs.LGstat.CO

TL;DR

The paper addresses the challenge of efficiently optimizing the non-differentiable sparse group lasso penalty. It develops a coordinate gradient descent algorithm for convex losses and establishes convergence; across three real data examples, group lasso achieved optimal estimated classification performance, while sparse group lasso sometimes matched it with fewer features.

  • Problem

    The sparse group lasso penalty is non-differentiable, making an efficient and robust optimization algorithm nontrivial to formulate.

    Source: §1 · p. 2

  • Method

    The paper combines coordinate gradient descent with block and modified coordinate descent to solve sparse group lasso problems for convex losses, and establishes convergence.

    Source: §1 · p. 2, §6 · pp. 25–26

  • Results

    Across three real data examples, multinomial group lasso achieved optimal estimated expected misclassification performance; sparse group lasso solutions matched performance using fewer features in one example.

    Source: §6 · p. 26

  • Takeaways & Limitations

    The implementation is available as an R package for multinomial and logistic regression, and sparse group lasso solutions can be useful for model selection.

    Source: §6 · p. 26

    The simulation study is restricted to multiclass data with Gaussian feature distributions conditional on class.

    Source: §4 · p. 11

Abstract

from arXiv · show

The sparse group lasso optimization problem is solved using a coordinate gradient descent algorithm. The algorithm is applicable to a broad class of convex loss functions. Convergence of the algorithm is established, and the algorithm is used to investigate the performance of the multinomial sparse group lasso classifier. On three different real data examples the multinomial group lasso clearly outperforms multinomial lasso in terms of achieved classification error rate and in terms of including fewer features for the classification. The run-time of our sparse group lasso implementation is of the same order of magnitude as the multinomial lasso algorithm implemented in the R package glmnet. Our implementation scales well with the problem size. One of the high dimensional examples considered is a 50 class classification problem with 10k features, which amounts to estimating 500k parameters. The implementation is available as the R package msgl.

1. Introduction

The paper introduces a sparse group lasso algorithm for convex losses and applies it to multinomial classification, where group and sparse group lasso outperform multinomial lasso. It also defines the penalty through parameter blocks and weights.

1.1. Sparse group lasso

  • The sparse group lasso combines lasso and group lasso penalties; its parameter blocks can reflect feature groups, and α=1 and α=0 recover lasso and group lasso, respectively.Source: §1 · p. 1, §1.1 · pp. 3–4

1. Introduction

  • The proposed sparse group lasso algorithm applies to a broad class of convex losses and combines coordinate gradient descent, block coordinate descent, and modified coordinate descent.Source: §1 · p. 2
  • A Hessian upper bound lets the algorithm skip complete Hessian calculations for many blocks, reducing runtime on large data sets by more than a factor of 2.Source: §1 · p. 2
  • Across three multiclass problems, multinomial group and sparse group lasso achieved substantially lower error rates than the best multinomial lasso results, using fewer features with non-zero coefficients.Source: §1 · p. 2
  • In the 50-class Amazon review task with 10k features, error fell from approximately 40% for lasso to less than 20% for group lasso.Source: §1 · p. 2
  • The C++ template implementation is available for multinomial and logistic regression as an R package, with runtime comparable in order of magnitude to glmnet multinomial lasso and scaling well with problem size.Source: §1 · pp. 2–3

The multinomial sparse group lasso classifier

The study examines multinomial sparse group lasso classification across three real data sets, spanning 10, 18, and 50 classes. It also examines the method on simulated data.

2. Setup

The setup specifies multinomial classification from feature vectors and categorical responses, then estimates model parameters by minimizing a sparse group lasso penalized negative log-likelihood. Features define the parameter groups.

  • The classification setup has K classes, N samples, and p features, with each feature vector in R^p and each response in {1, …, K}.Source: §2 · p. 4
  • The multinomial model uses K intercept parameters and K parameters per feature, with feature-associated parameters grouped by feature.Source: §2 · p. 5
  • The estimator minimizes the sparse group lasso penalized negative log-likelihood.Source: §2 · p. 5

3. Data examples

Across three real-data classification problems, group and sparse group lasso models generally achieve lower error than lasso with fewer selected features. The comparisons use cross-validation and evaluate models at matched counts of parameter blocks or parameters.

3. Data examples

  • Models are compared at matched counts of non-zero parameter blocks or parameters, using cross-validation estimates of expected generalization error.Normalization is used for the two biological datasets; standardization is applied last for all three datasets.Source: §3 · pp. 6–7

3.1. Cancer sites

  • Group and sparse group lasso achieve lower expected error than lasso with fewer genes; α = 0.25 offers a low-error, lower-parameter compromise against group lasso.The comparison uses 10-fold cross-validation across five α values.Source: Figure 1 · p. 8, §3.1 · p. 8

3.2. Amazon reviews

  • For this data set, lasso performs badly; group lasso performs best, achieving around 0.82 accuracy with a feature set of approximately 1k, and outperforming the neural network in.Source: §3.2 · p. 9

3.3. Muscle diseases

  • Group lasso performs well but is not significantly better than the closest sparse group lasso models at α = 0.25; sparse group lasso also outperforms lasso.The comparison is based on 10-fold cross-validation.Source: Figure 3 · p. 10, §3.3 · p. 10

4. A simulation study

The simulation examines how sparse group lasso performance changes with α across thin, sparse, and dense configurations. The results show that the best-performing penalty depends on the configuration, while variable selection also involves sensitivity–precision trade-offs.

4. A simulation study

  • The simulated Gaussian feature distributions vary in sparsity, and the study expects lasso to favor very sparse differences, interior α values less-sparse differences, and group lasso dense differences.The simulation study is reported to confirm these expected trends.Source: §4 · p. 11
  • The study samples μ configurations, fits models on training data, and estimates generalization error, true-positive rate, and positive predictive value on test data.It averages these estimates over M = 100 configurations, with N = 15 samples per class and K = 25 classes.Source: §4 · pp. 12–13
  • For thin configurations, lasso and sparse group lasso at α = 0.8 have the lowest estimated error; for dense configurations, group lasso is among the lowest-error methods.For sparse configurations, the optimal α appears to lie inside (0, 1), although all α choices yield comparable error.Source: §4 · p. 13
  • Outside thin configurations, lasso is markedly less sensitive than sparse group and group lasso, while those methods generally have lower precision than lasso except in dense configurations.Group lasso has the worst precision except for dense configurations.Source: §4 · p. 13

The sparse group lasso algorithm

This section presents a nested coordinate-descent algorithm for sparse group lasso, establishes convergence for its outer and inner loops, and describes a Hessian upper-bound optimization to reduce computation. For multinomial sparse group lasso, the run-time reductions grow with the number of blocks, with the same trend across α values.

The sparse group lasso algorithm

  • The algorithm applies to convex, twice continuously differentiable losses and uses four nested loops: λ continuation, outer coordinate gradient descent, middle block coordinate descent, and inner modified coordinate descent.The assumptions also require the loss and its quadratic approximations on the specified sublevel set to be bounded below.Source: The sparse group lasso algorithm · pp. 13, 15

4.1. The sparse group lasso penalty

  • The sparse group lasso penalty is separable across groups, a property required for convergence of coordinate-descent methods.Source: §4.1 · p. 15

4.2. The λ-sequence

  • For sufficiently large λ, the solution is zero; λmax is the infimum of those values, and the algorithm decreases λ from λmax to a user-specified λmin.The relevant function for computing λmax is piecewise quadratic and monotone.Source: §4.2 · p. 17

4.3. Outer loop

  • Every cluster point of the outer coordinate-gradient-descent sequence solves the sparse group lasso problem.The method uses a quadratic approximation of the loss and a line search along the resulting descent direction.Source: §4.3 · p. 18

4.4. Middle loop

  • Because the penalty is block separable, block coordinate descent converges to a minimizer of the convex quadratic subproblem.The middle loop solves the subproblem by minimizing one block at a time.Source: §4.4 · p. 19

4.5. Inner loop

  • Ordinary block coordinate descent is not guaranteed to converge because the penalty is nondifferentiable at zero, but the modified inner loop has minimizing cluster points for any ϵ > 0.The inner loop addresses the nondifferentiability and its convergence guarantee applies to the minimization problem for each block.Source: §4.5 · p. 21

4.6. Hessian upper bound optimization

  • An upper bound on each block gradient can identify zero blocks, reducing gradient computations when the bound can be computed efficiently.The paper notes that Cauchy-Schwarz can provide sufficiently good bounds for a broad class of loss functions.Source: §4.6 · pp. 23–24
  • The Hessian bound scheme decreases multinomial-loss run-time, and the runtime ratio grows with the number of blocks m across three data sets, with the same trend for other α values.The comparison used α = 0.5 and measured run-time without bound optimization relative to run-time with it.Source: §4.6 · p. 24

5. Software

The software comprises the msgl R package for multinomial and logistic sparse-group-lasso routines and the generic sgl C++ template library. Table 3 reports run-times for msgl solutions on three real datasets; glmnet timings are provided for comparison.

5. Software

  • The msgl R package provides multinomial and logistic sparse-group-lasso routines, while the sgl C++ template library provides generic sparse-group-lasso routines and underlies the R package.The C++ library uses Armadillo and Boost libraries and supports OpenMP for cross-validation and subsampling.Source: §5 · p. 25
  • The msgl R package is available from CRAN, while the sgl library is available upon request.Source: §5 · p. 25

5.1. Run-time performance

  • Table 3 lists run-times for three real-data examples; glmnet took 5.2s, 8.3s, and 137.0s, respectively, to fit the lasso path.Source: §5.1 · p. 25

6. Conclusion

The multinomial group lasso achieved optimal estimated expected misclassification performance across three real-data examples, while some sparse-group-lasso solutions matched that performance using fewer features. The paper also establishes convergence of an algorithm for sparse group lasso with general convex loss.

6. Conclusion

  • The algorithm solves sparse group lasso with a general convex loss, and its convergence is established in a framework that includes multinomial penalized negative log-likelihood.Source: §6 · pp. 25–26
  • Table 3 reports run-times for multinomial sparse-group-lasso solutions on three real datasets, using a 100-value lambda sequence and one thread.The table specifies a 2.20 GHz Intel Core i7 processor and sample counts of 162, 107, and 1500 for Cancer, Muscle, and Amazon, respectively.Source: Table 3 · p. 26
  • The multinomial group lasso achieved optimal estimated expected misclassification performance in all three real-data examples; some sparse-group-lasso solutions achieved comparable performance with fewer features in one example.Sparse-group-lasso solutions were generally sparser than group-lasso solutions, which may aid model selection and interpretation.Source: §6 · p. 26

Appendix A. Block coordinate descent methods

The appendix reviews coordinate gradient descent, block coordinate descent, and modified block coordinate descent in a block-structured convex optimization setting. It outlines the coordinate-gradient procedure and gives a convergence result under twice-continuous differentiability.

Appendix A. Block coordinate descent methods

  • The reviewed methods are coordinate gradient descent, block coordinate descent, and modified block coordinate descent for unconstrained optimization with naturally divided coordinate blocks.The objective is bounded below and combines a convex function with convex block-specific terms.Source: Appendix A · pp. 26–27

Appendix A.1. Coordinate gradient descent

  • The coordinate-gradient scheme forms a quadratic approximation, computes a search direction, and uses an Armijo rule to choose the step size.Source: Appendix A.1 · p. 27
  • The scheme assumes the smooth part is twice continuously differentiable everywhere; every cluster point generated by the algorithm is then a minimizer of the objective.Source: Appendix A.1 · p. 27

Appendix A.2. Block coordinate descent

Block coordinate descent repeatedly minimizes over selected blocks and guarantees coordinatewise-minimizing cluster points. Differentiability strengthens the convergence result to a minimizer guarantee.

Appendix A.2. Block coordinate descent

  • Each iteration selects a block cyclically, minimizes over that block, and repeats until a stopping condition is met.The section also outlines a modified coordinate descent loop that uses a descent direction and line search to reduce F.Source: Appendix A.2 · pp. 28–29
  • When f is differentiable, the section states that block coordinate descent converges to a minimizer, with coordinatewise minimizers being stationary points.The stationary-point result is stated for a coordinatewise minimizer where f is differentiable.Source: Appendix A.2 · p. 28
  • Every cluster point of the block coordinate descent sequence is a coordinatewise minimizer of F.A point is coordinatewise minimizing when changing any single block cannot decrease F.Source: Appendix A.2 · p. 28

Appendix B. Modified block coordinate descent

At a non-optimal point where f may fail to be differentiable, ordinary block coordinate descent may get stuck. A modified loop uses descent steps to ensure cluster points are minimizers under the stated assumption.

Appendix B. Modified block coordinate descent

  • Ordinary block coordinate descent may get stuck at p and is not guaranteed to converge globally when f is nonsmooth there.A descent direction and line search can move to a point with lower F, but the text says this remedy discards a carefully chosen starting point.Source: Appendix B · p. 29
  • Under the assumption that f is differentiable except at a non-optimal point p, the modified loop has minimizers of F as its cluster points.The result is stated for any ϵ > 0 and a sequence generated by Algorithm 8.Source: Appendix B · p. 29
  • The proof uses decreasing objective values and a step below F(p) to rule out p as a cluster point.If an iterate is sufficiently close to p while its objective is at least F(p), Algorithm 8 takes a subsequent step with objective below F(p).Source: Appendix B · p. 29

Appendix C. Proof of Proposition 1

The proof characterizes the minimizer over X using the norm of κ(v, z) relative to a. When that norm exceeds a, it constructs a unique minimizer by subtracting the radius in the κ(v, z) direction.

Appendix C. Proof of Proposition 1

  • The proof characterizes 0 ∈ X by the condition ∥κ(v, z)∥2 ≤ a.It also establishes the reverse implication by selecting a point in Y whose negative lies in aBn.Source: Appendix C · p. 30
  • When ∥κ(v, z)∥2 > a, x* = (1 − a/∥κ(v, z)∥2)κ(v, z) lies in X and has norm ∥κ(v, z)∥2 − a.The proof establishes its minimizing property by comparing it with other points in X.Source: Appendix C · p. 30
  • The minimizer is unique because X is convex and the norm is strictly convex.Source: Appendix C · p. 30

Related papers

Loading 1205.1245v2…