Structured sparsity-inducing norms through submodular functions

Abstract

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.

References in corpus (7)

• Supervised Dictionary Learning
• Near-optimal Nonmyopic Value of Information in Graphical Models
• Structured Sparse Principal Component Analysis
• Exploring Large Feature Spaces with Hierarchical Multiple Kernel Learning
• Group Lasso with Overlaps: the Latent Group Lasso approach
• Network Flow Algorithms for Structured Sparsity
• Convex Analysis and Optimization with Submodular Functions: a Tutorial

Cited by in corpus (25)

• Proximal Methods for Hierarchical Sparse Coding
• Network Flow Algorithms for Structured Sparsity
• The LASSO with Non-linear Measurements is Equivalent to One With Linear Measurements
• Efficient Minimization of Decomposable Submodular Functions
• Convex and Network Flow Optimization for Structured Sparsity
• A Convex Formulation for Learning Scale-Free Networks via Submodular Relaxation
• Style Imitation and Chord Invention in Polyphonic Music with Exponential Families
• Partition-wise Linear Models
• Scalable Variational Inference in Log-supermodular Models
• The Lovasz-Bregman Divergence and connections to rank aggregation, clustering, and web ranking
• On the Effectiveness of Richardson Extrapolation in Machine Learning
• Optimal approximation for unconstrained non-submodular minimization
• The Lovasz-Bregman Divergence and connections to rank aggregation, clustering, and web ranking
• Submodular Norms with Applications To Online Facility Location and Stochastic Probing
• Differentially Private Empirical Risk Minimization with Sparsity-Inducing Norms
• Learning Max-Margin Tree Predictors
• Black Box Submodular Maximization: Discrete and Continuous Settings
• Learning Hierarchical Interactions at Scale: A Convex Optimization Approach
• Multi-label Learning via Structured Decomposition and Group Sparsity
• On a reduction for a class of resource allocation problems
• FPT Approximation Schemes for Maximizing Submodular Functions
• Network Inference by Learned Node-Specific Degree Prior
• Scalable Projection-Free Optimization
• Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets
• Randomized Algorithms for Monotone Submodular Function Maximization on the Integer Lattice