PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimization with Sparsity-Inducing Penalties

Francis Bach, Rodolphe Jenatton, Julien Mairal, Guillaume Obozinski

arXiv:1108.0775v2cs.LGmath.OCstat.ML

TL;DR

Sparse estimation replaces difficult cardinality-based selection with convex penalties and structured norms. The paper surveys and compares optimization methods for these formulations, finding method-specific strengths across losses and problem settings.

  • Problem

    Cardinality-based sparse estimation is combinatorial, motivating convex norm penalties that retain sparse or structured solutions.

  • Method

    The paper presents a general framework covering proximal, block-coordinate, reweighted-ℓ2, homotopy, working-set, and nonconvex approaches for sparsity-inducing penalties.

  • Results

    Proximal methods are broadly applicable and often competitive; homotopy is fastest for square-loss small or medium problems and highly correlated designs, while block-coordinate descent is fastest for smooth losses but limited to separable regularizers.

  • Takeaways & Limitations

    Algorithm choice should reflect the loss, regularizer, scale, correlation structure, and whether implementation simplicity or full regularization paths is prioritized.

  • Takeaways & Limitations

    The experiments focus on sparse machine-learning regimes with p larger than n; settings with n much larger than p and denser solutions were out of scope.

Abstract

from arXiv · show

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 non-smooth norms. The goal of this paper 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 $\ell_2$-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.

Introduction

The paper frames sparse estimation as convex optimization with sparsity-inducing norms, extending variable selection to structured sparsity and related settings. It develops and compares optimization methods for these problems.

  • Sparsity supports interpretable or computationally cheaper models and can encode prior knowledge that the underlying model should be sparse.
  • Replacing cardinality by the ℓ1-norm converts hard combinatorial variable-selection problems into convex programs.
  • Convex formulations provide efficient estimation algorithms and support theoretical analysis of consistency and prediction or model efficiency.
  • Structured sparsity extends cardinality-based parsimony by using norms that encode variable relationships such as groups, hierarchies, and other structures.
  • The monograph covers proximal, block-coordinate, reweighted-ℓ2, working-set, homotopy, greedy, nonconvex, Bayesian, and multiple-kernel methods.
  • Experiments compare algorithmic convergence speed for ℓ1, grouped ℓ1/ℓp, and more general structured cases.

1.1 Notation

This section defines vector and matrix notation, norms, the ℓ0-penalty, and subvector or submatrix indexing used throughout the manuscript.

  • The ℓq-norm is defined for q ≥ 1, with the ℓ∞-norm given by the maximum absolute coordinate.
  • The ℓ0-penalty counts the nonzero elements of a vector.
  • The Frobenius norm is defined for matrices using the square root of the sum of squared entries.
  • Subvector and submatrix notation selects entries or columns indexed by a subset J.

1.2 Loss Functions

The learning framework minimizes a smooth convex loss plus a sparsity-inducing norm penalty. Penalized and constrained formulations trace equivalent solution paths, but the penalized form is easier to tune empirically.

  • The central optimization problem combines a convex differentiable function f with a typically nonsmooth, non-Euclidean sparsity-inducing norm Ω.
  • In supervised learning, f generally represents empirical risk from losses such as square or logistic loss for linear models.
  • The monograph restricts its main treatment to smooth f, excluding losses such as hinge and absolute deviation without modifications.
  • Under weak assumptions, penalized and constrained formulations have equivalent solution paths as λ and μ vary, although corresponding parameter values do not map directly.
  • The penalized formulation is empirically easier to tune because performance is usually robust to small changes in λ.

1.3 Sparsity-Inducing Norms

Sparsity-inducing norms select individual variables, groups, or structured patterns by shaping which coefficients become zero. The section covers grouped, overlapping, hierarchical, matrix, and other extensions whose proximal operators enable efficient algorithms.

  • The ℓ1-norm induces coefficient sparsity by setting a number of coefficients exactly to zero.
  • The mixed ℓ1/ℓ2 norm promotes group sparsity by encouraging entire groups to vanish while avoiding sparsity within groups.
  • Overlapping groups encode structured supports such as contiguous sequence patterns, rectangles on grids, and hierarchical tree patterns.
  • Hierarchical penalties enforce that selected nodes include their ancestors, producing rooted connected subtrees.
  • Latent group formulations produce supports that are generally unions of selected groups and can relax related nonconvex penalties.
  • Efficient proximal-operator computation supports extensions to other sparsity-inducing norms.

1.4 Optimization Tools

This section develops convex-analysis tools for nonsmooth sparsity-inducing regularization, including subgradients, dual norms, Fenchel duality, and variational formulations. These tools yield optimality conditions, thresholding operators, duality-gap certificates, and algorithmic decompositions for sparse optimization.

  • Convex analysis: Subgradients provide a geometric representation of nonsmooth convex functions as lower-bounding affine tangents.At any point, subgradients correspond one-to-one with tangent affine functions.
  • Convex analysis: For convex optimization, a point is globally optimal exactly when zero belongs to the function’s subdifferential.This generalizes the differentiable first-order condition ∇g(w) = 0.
  • Proximal operators: The ℓ1-regularized scalar problem has a closed-form soft-thresholding solution, a core component of sparse-estimation algorithms.The operator sets values within the threshold to zero and shrinks larger magnitudes toward zero.
  • Duality: Dual norms characterize optimality conditions for sparsity-regularized problems and support estimation bounds and working-set strategies.For ℓq norms, the dual is the ℓq′ norm; ℓ1 and ℓ∞ are dual, while ℓ2 is self-dual.
  • Duality: A duality gap measures the difference between primal and dual objective values and equals zero at paired primal-dual optima.The paper uses duality gaps to provide rigorous approximate optimality conditions rather than relying on weak stopping criteria.
  • Variational formulations: An upper-bound variational formulation partially decouples loss optimization from norm optimization and yields a general algorithmic scheme for sparsity-inducing penalties.The framework includes subquadratic norms, which are equivalent to H-norms, and extends quadratic variational forms to all norms with non-diagonal bilinear forms.
  • Variational formulations: The unit ball of the constructed norm is the convex hull of the mirror image of H, and identical convex hulls define identical norms.This establishes a geometric characterization of the associated variational norm.

1.5 Multiple Kernel Learning

Multiple kernel learning is linked to sparsity-inducing regularization through convex duality and variational norm formulations. This connection extends from ℓ1/ℓ2 regularization to structured norms and corresponding kernel combinations.

  • Connection between sparsity and MKL: Multiple kernel learning is connected to sparsity-inducing norms through duality, with corresponding kernel-learning schemes for a large class of norms.The relationship also extends in the reverse direction: each multiple kernel learning scheme defines a related norm.
  • Kernel optimization: The dual problem depends on the design only through the kernel matrix K = XX⊤, and its objective is convex in K.This convexity motivates optimizing over kernel matrices or learning combinations of predefined kernels.
  • Kernel representations: The kernel trick replaces high-dimensional primal optimization with dual optimization using a kernel matrix whose entries are inner products in the feature space.This is advantageous when n^2 ≤ d, where the feature representation dimension is high relative to the number of observations.
  • From group sparsity to MKL: Learning convex combinations of kernels over the simplex is equivalent to penalizing predictor norms with an ℓ1/ℓ2 regularizer.For partitioned groups, the ℓ1 norm is applied to the ℓ2 norms of the group predictors.
  • Special cases: MKL with rank-one kernel matrices is equivalent to ℓ1-regularization when groups are single variables.In this case, the kernel matrices have feature spaces of dimension one, allowing simpler algorithms to be used.
  • Structured MKL: Structured norms with variational representations correspond to structured MKL formulations with kernel weights constrained by the associated convex set.The same correspondence can replace individual variables with whole Hilbert spaces, including tree-structured RKHS variables.

Generic Methods

Generic optimization methods apply broadly to convex sparse-estimation problems but largely ignore problem structure. Subgradient descent is simple and widely applicable, whereas generic mathematical-programming solvers can be precise but inefficient for machine-learning workloads.

  • Problem setting: The central optimization problem is convex when both the loss f and regularizer Ω are convex.The generic methods considered here are designed for settings where sparsity-inducing norms make the regularizer convex but non-smooth.
  • Subgradient descent: Subgradient descent applies whenever subgradients of the loss and regularizer can be computed efficiently.It has low per-iteration complexity and broad applicability, but does not exploit problem structure.
  • Subgradient descent: O(log t) convergence is obtained for Lipschitz-continuous functions with β = 1/2, but convergence is typically slow in practice.Many iterations may be needed, and the resulting solutions are usually not sparse.
  • Structure-aware methods: Proximal methods are more adapted to sparse problems, with convergence rates of O(1/t) and O(1/t^2).The paper contrasts these rates with subgradient descent's slower practical behavior and typically non-sparse solutions.
  • Generic mathematical programming: Sparsity-inducing regularized least-squares problems can be reformulated as LP, QP, SOCP, or SDP problems.For example, ℓ1-regularized least squares yields a quadratic program, while grouped ℓ2 norms lead to a second-order cone program.
  • Practical limitations: Generic solvers may be too slow or memory-intensive because they ignore problem structure, while machine-learning applications generally do not require machine-precision duality gaps.These limitations motivate methods specifically adapted to sparsity-inducing regularization.

Proximal Methods

Proximal methods optimize smooth-plus-nonsmooth objectives by linearizing the smooth term and handling the regularizer through a proximal operator. Their basic and accelerated variants provide global convergence guarantees, with stronger rates under strong convexity, and extend to structured norms and multiple kernel learning.

  • Core framework: Proximal methods target objectives combining a smooth differentiable function with Lipschitz-continuous gradient and a nondifferentiable regularizer.At each iteration, the smooth term is linearized and stabilized by a quadratic proximal term.
  • Core framework: The proximal operator is central because the main update computes the regularized problem through this operator.It generalizes gradient and projected-gradient updates, and can be computed using Euclidean projections onto convex sets.
  • Convergence: Basic proximal methods converge globally at O(1/t), while accelerated variants such as FISTA achieve O(1/t^2), optimal for first-order techniques.The accelerated rate concerns the objective function.
  • Convergence: When the smooth term is strongly convex, both basic and accelerated proximal methods can converge linearly.Accelerated schemes nevertheless need not produce convergent iterates or decrease the objective at every iteration.
  • Structured extensions: For structured norms, correctly ordered groupwise proximal operators can be composed, with complexity O(p) for q = 2 and O(pd) for q = ∞.The composition result depends on the required group ordering and does not hold for q outside {1, 2, ∞}.
  • Structured extensions: The framework extends to structured multiple kernel learning by obtaining structured RKHS proximal operators from corresponding subquadratic-norm proximal operators.This includes the general structured MKL setting described in the paper.

(Block) Coordinate Descent Algorithms

Coordinate and block-coordinate descent exploit separability in sparsity-inducing regularizers to optimize one variable or group at a time. Under suitable conditions they converge, with linear rates for strongly convex objectives, and extend to grouped norms and multiple kernel learning.

  • Coordinate descent: Coordinate descent updates one variable while holding the others fixed, and applies to ℓ1-regularized problems because the nonsmooth regularizer is separable.Without this separability, coordinate descent is not generally guaranteed to converge for nonsmooth objectives.
  • Coordinate descent: For square loss, each ℓ1-regularized coordinate update is obtained by solving the unregularized one-dimensional problem and soft-thresholding the result.This closed-form update underlies the shooting algorithm, which cycles through variables.
  • Coordinate descent: For general smooth losses, coordinate subproblems may require numerical optimization, including modified Newton steps or quadratic approximations with inexact line search.The Tseng–Yun method uses a quadratic approximation and line search at each iteration.
  • Convergence: Under suitable conditions, coordinate descent is convergent and asymptotically linear; for strongly convex objectives its convergence is linear, but strong input correlations can slow it when strong convexity is absent.The stated rates depend on the objective’s curvature and conditioning.
  • Block-coordinate descent: Block-coordinate descent generalizes coordinate updates to groups for ℓ1/ℓq norms, optimizing quadratic surrogates rather than necessarily solving each reduced problem exactly.With Ht = LtI|g| and q ∈ {2, ∞}, the block subproblem can be solved in closed form; q = 2 yields group soft-thresholding.
  • Multiple kernel learning: Block-coordinate methods also apply to multiple kernel learning by treating each RKHS as a block and successively performing group soft-thresholding.The resulting updates produce a non-increasing primal objective sequence and can use a compact parameterization.

Working-Set and Homotopy Methods

Working-set methods solve progressively larger restricted problems and use optimality checks to activate variables, while homotopy methods exploit piecewise-affine regularization paths to track solutions across regularization parameters.

  • Working-set methods: Working-set algorithms solve an increasing sequence of smaller subproblems restricted to a subset of variables, exploiting sparse solutions computationally.Any solver from the monograph can serve as the inner-loop method, making working-set procedures meta-algorithms.
  • Working-set methods: After each restricted solve, global optimality is checked; if it fails, inactive variables violating the dual-norm condition are added to the working set.For the ℓ1-norm, the dual norm is the ℓ∞-norm, making the check straightforward.
  • Working-set methods: Forward working-set algorithms grow the set monotonically and therefore terminate after finitely many iterations under that assumption.The described forward procedures do not allow variables to leave the working set.
  • Homotopy methods: Homotopy methods exploit the Lasso solution’s piecewise-affine dependence on λ by following affine segments and updating the active set at kinks.The path can be initialized at a value of λ with a trivial solution and then followed as λ decreases.
  • Homotopy methods: With fixed active variables and signs, the Lasso solution is affine in λ, enabling path-following updates when optimality conditions change.The procedure assumes invertibility of the active design submatrix and single-variable active-set changes.
  • Homotopy methods: The complexity of homotopy procedures depends on the number of path kinks, although variables leaving the active set are often rare in practice.Large numbers of kinks can occur in constructed examples, while implementation choices also affect complexity.

Sparsity and Nonconvex Optimization

The paper contrasts greedy and non-convex approaches for sparse modelling, including matching pursuit and iterative convex surrogates for concave penalties. These methods seek stronger sparsity or approximate hard cardinality constraints while retaining computational tractability.

  • Greedy Algorithms: The underlying ℓ0-sparse approximation problem is NP-hard, although greedy procedures can provide approximate solutions and, under assumptions on X, optimality guarantees.Efficient updates can exploit matrix factorizations rather than explicitly solving every least-squares problem.
  • Greedy Algorithms: Greedy methods begin with a null vector and iteratively add variables until a target sparsity level is reached.Matching pursuit selects the variable most correlated with the current residual and updates its coefficient.
  • Greedy Algorithms: Matching pursuit decreases the objective at every iteration, but may select the same variable repeatedly and lacks finite-step convergence.Orthogonal matching pursuit instead maintains residual orthogonality to previously selected columns.
  • Nonconvex Penalties: Non-convex separable penalties use concave, non-decreasing functions such as ℓq variants, logarithmic penalties, or SCAD.These penalties are motivated by inducing more sparsity than the ℓ1-norm while remaining amenable to continuous optimization.
  • Nonconvex Penalties: Reweighted-ℓ1 schemes minimize a tangent convex upper bound of the non-convex objective at each iteration, thereby producing a sequence of convex subproblems.The surrogate is justified by concavity, and a few iterations can push the smallest nonzero coefficients to zero.
  • Sparse Matrix Factorization and Dictionary Learning: Dictionary learning applies sparse modelling to natural image patches, with structured penalties producing dictionaries distinct from those learned using the ℓ1-norm.The paper describes overcomplete dictionaries whose elements span low-dimensional subspaces of image-patch data.

Quantitative Evaluation

The experiments compare sparse-optimization algorithms across scales, correlations, regularization strengths, losses, and structured-sparsity settings. Performance varies substantially by scenario, with dedicated methods generally outperforming generic optimization techniques.

  • Benchmark Design: 8 conditions combine 2 problem scales, 2 correlation levels, and 2 regularization strengths, with results averaged over 5 runs.The benchmarks monitor computation time and objective values while varying scale, feature correlation, regularization, and required precision.
  • Lasso Speed Benchmarks: LARS outperforms other methods in almost every small-scale Lasso scenario and remains competitive at larger scale for very sparse or highly correlated problems.Its performance depends primarily on solution sparsity rather than design-matrix correlation, and homotopy computes the exact regularization path.
  • Lasso Speed Benchmarks: FISTA outperforms ISTA in all but one scenario, with the largest advantage under high correlation or low regularization.Both proximal methods are generally slower than LARS in small-scale settings and are affected by correlated features.
  • Lasso Speed Benchmarks: Reweighted-ℓ2 was outperformed in all reported Lasso experiments, while generic methods such as subgradient descent, QP, and CP were consistently inferior to dedicated methods.The comparison included LARS, coordinate descent, reweighted-ℓ2, ISTA, FISTA, subgradient descent, and generic conic or quadratic programming.
  • Group Sparsity: BCD appears to be the best option across sparsity and scale conditions in the group-sparsity experiments.The results are reported in Figures 8.3 and 8.4.
  • Denoising of Natural Image Patches: Across sparsity levels, the accelerated proximal scheme performs better than or similarly to the alternatives, while reweighted-ℓ2 matches FISTA only in the least sparse setting.Reweighted-ℓ2 does not produce truly sparse solutions and would require subsequent thresholding.
  • General Structured Cases: Proximal methods, ADMM, and Lin-ADMM compare favorably with other methods on three problem sizes, with ProxFlow consistently better than Lin-ADMM.ADMM approaches generic subgradient performance in the largest-scale setting after 10^4 seconds.

Extensions

The paper identifies extensions beyond its main treatment, including broader proximal splitting frameworks, dedicated formulations, geometry-adapted proximal metrics, second-order acceleration, and stochastic optimization.

  • Scope Boundary: The literature review is not exhaustive, and earlier comparisons focused mainly on ℓ1-regularization without proximal methods.The authors also question whether prior comparison metrics are the most relevant for machine learning.
  • Proximal Extensions: The forward-backward proximal framework extends beyond a smooth loss plus norm to two proper, convex, lower-semicontinuous functions with one Lipschitz-gradient term.This broader formulation enlarges the class of convex objectives addressed by proximal methods.
  • Proximal Extensions: Douglas-Rachford splitting remains applicable when the objective is proper, convex, and lower-semicontinuous without smoothness assumptions.The paper notes that proximal methods have also been extended to other settings.
  • Dedicated Methods: Some loss–regularization combinations admit dedicated algorithms, including linear programming for LAD loss with an ℓ1 regularizer.Specialized methods also exist for certain multiple-kernel-learning regularizers.
  • Acceleration and Geometry: Proximal operators can use rescaled metrics to better fit data geometry and can be combined with Newton or quasi-Newton methods for acceleration.These modifications target improved algorithmic adaptation and speed.
  • Stochastic Extensions: The deterministic optimization problem may also be addressed with stochastic optimization approaches, which the paper identifies as broader related work.The stochastic direction is presented as an outlook rather than part of the main treatment.

Conclusions

The paper unifies sparsity and structured sparsity through convex analysis and compares four major algorithmic families, while also covering non-convex extensions and kernel learning. Its conclusions emphasize method-specific trade-offs involving scalability, regularizer structure, problem size, implementation, and numerical stability.

  • The paper presents a unified convex-optimization view of sparsity and structured sparsity, while acknowledging that other paradigms provide complementary perspectives.
  • Four representative algorithm families are compared: proximal methods, block-coordinate descent, reweighted-ℓ2 schemes, and LARS/homotopy.
  • Proximal methods are efficient, scalable, broadly applicable across loss functions and norms, simple to implement, and often competitive with alternatives.
  • For square loss, homotopy is fastest on small or medium problems and highly correlated designs, but implementation is difficult and numerical instability is a drawback.
  • For smooth losses, block-coordinate descent is among the fastest algorithms but is limited to separable regularizers.
  • Reweighted-ℓ2 schemes are generic and competitive for square loss, whereas general losses require iterative solutions of ℓ2-regularized problems.
  • For difficult non-convex, non-differentiable problems, the paper advocates iteratively solving convex problems because more stable algorithms are available and progress can be monitored.
  • Duality connects multiple kernel learning with sparsity and supports structured MKL and kernelized algorithms for reproducing kernel Hilbert spaces.
Loading 1108.0775v2…