Convex Relaxation for Combinatorial Penalties
This work provides a theoretical foundation for improving optimization in machine learning models with structured sparsity, though it is incremental as it unifies and extends existing methods.
The paper tackles the problem of structured sparsity in parameter estimation by proposing a convex relaxation framework for combinatorial penalties, showing that these relaxations can be characterized by a new concept called the lower combinatorial envelope.
In this paper, we propose an unifying view of several recently proposed structured sparsity-inducing norms. We consider the situation of a model simultaneously (a) penalized by a set- function de ned on the support of the unknown parameter vector which represents prior knowledge on supports, and (b) regularized in Lp-norm. We show that the natural combinatorial optimization problems obtained may be relaxed into convex optimization problems and introduce a notion, the lower combinatorial envelope of a set-function, that characterizes the tightness of our relaxations. We moreover establish links with norms based on latent representations including the latent group Lasso and block-coding, and with norms obtained from submodular functions.