Source-linked AI summary
Structured sparsity-inducing norms through submodular functions
Francis Bach
TL;DR
Sparse supervised learning seeks accurate predictors with small supports, but cardinality penalties and fixed allowed-pattern norms do not capture broader structural knowledge. The paper uses Lovász extensions of nondecreasing submodular support functions to define polyhedral norms, with generic algorithms and theory. These norms recover known structured penalties, introduce non-factorial priors, and outperform related greedy approaches in simulations.
Problem
Sparse supervised learning needs convex penalties that incorporate structural knowledge beyond cardinality or predefined allowed support patterns.
Method
The paper constructs convex relaxations of w 7→F(Supp(w)) from Lovász extensions of nondecreasing submodular functions and develops subgradient, proximal, and theoretical tools.
Results
The resulting polyhedral norms recover or reinterpret rank-statistic and overlapping-group norms, define non-factorial supervised-learning priors, and outperform related greedy approaches in simulations.
Takeaways & Limitations
Submodular support penalties provide a unified family of structured sparsity-inducing norms with shared algorithms and analyses across several structured regularization settings.
Takeaways & Limitations
The paper does not extensively evaluate non-factorial convex priors and notes that its generic minimum-norm-point algorithm may be inefficient for simpler norm subclasses.
Abstract
from arXiv · showhide
Sparse methods for supervised learning aim at finding good linear predictors from as few variables as possible, i.e., with small cardinality of their supports. This combinatorial selection problem is often turned into a convex optimization problem by replacing the cardinality function by its convex envelope (tightest convex lower bound), in this case the L1-norm. In this paper, we investigate more general set-functions than the cardinality, that may incorporate prior knowledge or structural constraints which are common in many applications: namely, we show that for nondecreasing submodular set-functions, the corresponding convex envelope can be obtained from its \lova extension, a common tool in submodular analysis. This defines a family of polyhedral norms, for which we provide generic algorithmic tools (subgradients and proximal operators) and theoretical results (conditions for support recovery or high-dimensional inference). By selecting specific submodular functions, we can give a new interpretation to known norms, such as those based on rank-statistics or grouped norms with potentially overlapping groups; we also define new norms, in particular ones that can be used as non-factorial priors for supervised learning.
1 Introduction
The paper extends sparsity-inducing convex regularization beyond cardinality and predefined sparsity patterns by using nondecreasing submodular penalties on supports. It connects these penalties to the Lovász extension, algorithms, theory, and structured norms.
- Structured parsimony extends cardinality-based selection by incorporating prior knowledge and structural constraints in applications such as image processing, text processing, and bioinformatics.
- Unlike norms designed only to allow specific support families, the proposed penalties explicitly assign values to support sets through F(Supp(w)).
- For nondecreasing submodular functions, the convex envelope of w 7→F(Supp(w)) on the ℓ∞-ball is obtained from the Lovász extension.
- The resulting polyhedral norms admit generic subgradient and proximal-operator tools, along with support-recovery and high-dimensional-inference guarantees.
- Specific submodular functions recover or reinterpret rank-statistic and overlapping-group norms, define non-factorial supervised-learning priors, and outperform related greedy approaches in simulations.
2 Review of submodular function theory
The paper reviews nondecreasing submodular functions, their polyhedral representations, and the Lovász extension that connects set functions to convex norms. It also introduces stable and inseparable sets, greedy optimization, and the resulting geometric structure.
- The framework assumes F(∅)=0, F is nondecreasing and submodular, and F is strictly positive on singletons without loss of generality.
- Lovász extension: The Lovász extension orders vector components and combines them with successive set-function increments, producing a piecewise-linear function that is convex when F is submodular.
- Lovász extension: The extension agrees with F on indicator vectors, and minimizing it over {0,1}^p is equivalent to minimizing it over [0,1]^p.
- Submodular polyhedron and greedy algorithm: The submodular polyhedron consists of nonnegative vectors satisfying s(A) ≤ F(A), and its linear representation can be evaluated by a greedy ordering of vector components.
- Stable and separable sets: Stable sets cannot be enlarged without increasing F, while stable inseparable sets define relevant polyhedral faces and allowed sparsity patterns.
- Submodular function minimization: The minimum-norm-point algorithm solves submodular minimization through an equivalent base-polyhedron problem and is often faster in practice, though combinatorial methods have best known complexity O(p^6).
- For two variables, changing F changes the polyhedral unit ball and can remove extreme points; the cardinality and capped-cardinality examples yield ℓ1 and ℓ∞ norms.
3 Definition and properties of structured norms
The paper defines structured sparsity norms by applying the Lovász extension to absolute coefficient values. Under submodularity and related assumptions, this construction yields the convex envelope of a support penalty and a polyhedral norm with a characterized dual norm and unit-ball geometry.
- Definition: The structured norm is defined as Ω(w) = f(|w|), where f is the Lovász extension of a nondecreasing submodular set-function F.The construction applies the extension to componentwise absolute values.
- Convex envelope: Under the stated assumptions, Ω is the convex envelope of the support penalty F(Supp(w)) on the unit ℓ∞-ball.The assumptions require F to be submodular, nondecreasing, and strictly positive on singletons.
- Dual norm: The dual norm is characterized by a maximization over subsets of variables.This gives a set-based characterization of the dual norm associated with Ω.
- Unit-ball geometry: Because the Lovász extension is piecewise-linear, Ω is a polyhedral norm whose unit-ball extreme points are determined by stable inseparable sets and sign vectors.The extreme-point characterization supports the geometric analysis of the norm.
- Unit-ball geometry: The number and cardinality of stable inseparable sets determine whether the unit ball has 2^p or up to 3^p − 1 extreme points.The lower count occurs with only singleton sets, while the upper count corresponds to all possible sign vectors.
- Examples: The paper illustrates structured norms through group designs for contiguous patterns and regularization paths contrasting ℓ1, rectangular, and mixed penalties.The examples show how different group constructions encode distinct support behaviors.
4 Examples of nondecreasing submodular functions
The paper instantiates nondecreasing submodular functions into grouped, grid-based, rank-statistic, and spectral norms, recovering known constructions while defining new structured penalties and non-factorial priors.
- Grouped norms: Potentially overlapping grouped ℓ1/ℓ∞ norms correspond to submodular functions that count weighted groups intersecting the support.This reinterpretation extends support-pattern analysis beyond merely restricting supports to stable sets.
- Grouped norms: Hierarchical norms encode the cardinality of the union of ancestors of selected variables in directed acyclic graphs.They have applications in bioinformatics, computer vision, and topic models.
- Grid norms: Adding a multiple of the cardinality function to grid-based penalties reduces the large empty-to-nonempty gap, encouraging contiguous patterns without forcing all variables to enter together.The resulting regularization corresponds to adding a multiple of the ℓ1-norm.
- Grid norms: A new grid norm penalizes support size plus the number of intervals, favoring contiguity without restricting selection to a single interval.Unlike total variation, it relaxes structure in the support rather than the number of jumps in the coefficient vector.
- Spectral functions: Spectral functions F(A)=tr h(Q_AA) yield nondecreasing submodular functions for logarithmic and fractional-power choices of h.Fractional powers h(λ)=λ^q for q∈(0,1] provide novel examples according to the paper.
- Spectral functions: With Q=X^⊤X, linear h produces weighted cardinality and weighted ℓ1 penalties, whereas sub-linear spectral penalties provide non-factorial prior constructions.The paper illustrates these priors in simulations but does not extensively evaluate them.
- Rank-statistic norms: For F(A)=h(|A|) with concave nondecreasing h, the induced norm is a weighted sum of ordered absolute coefficients and includes the sum of the q largest elements.The paper notes that the associated algorithms and analysis apply, although it does not pursue new unstructured-selection norms here.
5 Convex analysis and optimization
The paper develops generic optimization tools for polyhedral submodular norms, including subgradients and proximal methods. Proximal evaluation is reduced to submodular minimization, while the generic algorithm may be inefficient for simpler norm subclasses.
- Optimization tools: Because the norms may have exponentially many unit-ball vertices or faces, standard linear-programming toolboxes are not directly suitable.The paper therefore develops dedicated algorithmic tools for optimization with these norms.
- Optimization tools: A subgradient can be computed in polynomial time as a maximizing element of the submodular polyhedron, enabling subgradient descent.The paper reports slower convergence than proximal methods in Figure 4.
- Proximal methods: The proximal operator is equivalent to minimizing the submodular function A↦λF(A)−|z|(A) with the minimum-norm-point algorithm.This links proximal optimization for the norm to submodular function minimization.
- Proximal methods: Submodular minimization algorithms can recover the unique proximal solution's support directly, and repeated minimizations can recover the full solution.The paper distinguishes this result from earlier links focused on symmetric submodular functions.
- Algorithmic scope: The minimum-norm-point approach is generic for submodular functions but may be inefficient for ℓ1/ℓ∞, tree-structured, or general overlapping-group norms.Simpler subclasses may therefore benefit from specialized algorithms.
6 Sparsity-inducing properties
The paper analyzes sparsity-inducing norms through decomposability, stable support patterns, and conditions for support recovery and consistent estimation.
- 6 Sparsity-inducing properties: The regularized least-squares estimator is studied through the norm’s decomposability and its implications for allowed sparsity patterns and estimation.The analysis covers both unrestricted model specification and well-specified high-dimensional linear models.
- 6.1 Decomposability: Under a magnitude-separation condition, the norm decomposes into contributions from a subset and its complement.Specifically, if the smallest absolute coefficient on J is at least the largest absolute coefficient on Jc, then Ω(w) = ΩJ(wJ) + ΩJ(wJc).
- 6.1 Decomposability: The complement pseudonorm is a norm if and only if J is a stable set.This condition determines when the decomposition has a genuine norm structure on the complement.
- 6.2 Stable sparsity patterns: With probability one, the unique minimizer has a stable support under an absolutely continuous response and invertible X⊤X.The result applies without assuming that the linear model is correctly specified.
- 6.3 High-dimensional inference: For well-specified Gaussian linear models, the paper extends support-recovery and consistency analyses using stable-set enlargement, decomposability, and restricted-eigenvalue-type conditions.The framework also provides concentration inequalities for the dual norm.
7 Experiments
Synthetic experiments compare optimization procedures, combinatorial relaxations, and predictive performance for submodular sparsity-inducing norms.
- 7 Experiments: FISTA is faster than ISTA and much faster than subgradient descent for F(A) = |A|^1/2 in a p = n = 1000 experiment.The comparison uses k = 100 and λ = 0.1.
- 7 Experiments: Convex optimization performs better on hard combinatorial cases, while matching greedy approaches in easier cases with more observations.The strategies compared are the proposed norm-based approach, forward selection, and thresholding the ordinary least-squares estimate.
- 7 Experiments: The norm based on non-factorial priors is more robust than the ℓ1-norm when observations are fewer and support cardinality is larger.The predictive comparison includes greedy approaches and ℓ1- or ℓ2-regularization.
- 7 Experiments: The combinatorial-relaxation experiments report normalized prediction errors across high-dimensional and lower-dimensional settings.The settings include p = 120, n = 20, k = 40 and p = 120, n = 120, k = 40.
8 Conclusions
The paper presents submodularity-based sparsity-inducing norms for incorporating prior knowledge or structural constraints into linear predictors, alongside algorithms, theory, and synthetic illustrations.
- 8 Conclusions: The proposed family targets prior knowledge or structural constraints on the supports of linear predictors.The paper identifies extensions to concave penalties, matrix norms, submodular relaxations, and total variation as future directions.
A.1 Proof of Proposition 1
The proof establishes norm properties from the Lovász-extension representation and characterizes subgradients and decompositions used by the sparsity analysis.
- A.1 Proof of Proposition 1: The Lovász-extension representation makes Ω positively homogeneous and convex, while a lower bound ensures it is a norm.Convexity follows from representing Ω as a maximum of s⊤|w| over a submodular polyhedron.
- A.1 Proof of Proposition 1: The proof uses submodularity to express conjugate and bidual operations as optimization over [0,1]^p with componentwise constraints.The resulting minimization evaluates the function at |w| under the stated monotonicity condition.
- A.1 Proof of Proposition 1: Stable inseparable sets identify faces of the submodular polyhedron and can restrict the maximization defining the norm.This links the polyhedral geometry to the norm’s decomposition structure.
- A.1 Proof of Proposition 1: When nonzero magnitudes are strictly ordered, the subdifferential on the active coordinates is determined by successive differences of F.For a general support, the subdifferential decomposes across the support, its stable closure, and the remaining coordinates.
B.1 Proof of Proposition 3
The proof reduces the proximal computation to a minimum-norm problem over a submodular polyhedron, then recovers the primal solution from its optimizer. It also identifies an alternative route using the minimum-norm solution of a modified submodular function.
- Proof conditions: The proof invokes Slater’s condition to justify the convex-duality step underlying the reduction.The assumption that z has nonnegative components is used in establishing equivalent minimization domains.
- Proximal computation: The proximal problem is reduced to minimizing the Euclidean distance from s to z/λ over the submodular polyhedron.Nonnegative z allows equivalent restrictions to nonnegative, absolute-valued, or unrestricted polyhedron variables.
- Proximal computation: The optimal primal vector is recovered from the polyhedron solution by w = z − λs.This relation is stated after applying convex duality.
- Minimum-norm formulation: The reduced problem is, up to a total-set constraint, the minimum-norm point problem for G(A) = F(A) − λ−1z(A).The proof uses the submodular function G to connect the proximal computation with standard submodular optimization.
- Algorithmic routes: The simulations apply the minimum-norm point algorithm directly, while an alternative obtains s from the negative part of the minimum-norm solution t.The alternative then recovers w using the same relation w = z − λs.
C.2 Proof of Proposition 5
The proof characterizes solutions with a fixed support through polyhedral optimality conditions and affine representations. It also uses the norm’s decomposition properties and dual-norm bounds in the support-recovery argument.
- Affine solution structure: For a fixed support J, the fitted coefficients are represented as an affine function of r, and the relevant affine parameters belong to a finite set independent of r.This supports the piecewise-affine characterization of the solution path.
- Support restrictions: If J is not stable, the proof shows that support J can occur only when a nonzero linear function of y is constant, an event of probability zero.The argument uses invertibility of Q and the Schur complement lemma.
- Affine solution structure: The polyhedral norm representation expresses Ω_J as the maximum of finitely many linear forms indexed by extreme points of its submodular polyhedron.This finite representation is used to derive the affine form when the support is fixed.
- Optimality conditions: The optimality conditions introduce nonnegative coefficients η_z supported on maximizers of z^⊤w_J, with their sum equal to one.Carathéodory’s theorem allows the number of nonzero coefficients to be at most |J| + 1.
- Support-recovery analysis: The recovery analysis uses the decomposition property of Ω together with dual-norm control and a restricted eigenvalue condition.These ingredients appear in the bounds for the noise and constrained minimizer.
- Support-recovery analysis: The dual norm is evaluated by maximizing w^⊤z over the unit ball, with the maximum attained among its extreme points.This finite extreme-point representation supplies the bound used in the proof.