Convex envelopes of complexity controlling penalties: the case against premature envelopment


Vladimir Jojic, Suchi Saria, Daphne Koller ;
Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, PMLR 15:399-406, 2011.


Convex envelopes of the cardinality and rank function, l_1 and nuclear norm, have gained immense popularity due to their sparsity inducing properties. This gave rise to a natural approach to building objectives with sparse optima whereby such convex penalties are added to another objective. Such a heuristic approach to objective building does not always work. For example, addition of an L_1 penalty to the KL-divergence fails to induce any sparsity, as the L_1 norm of any vector in a simplex is a constant. However, a convex envelope of KL and a cardinality penalty can be obtained that indeed trades off sparsity and KL-divergence. We consider cases of two composite penalties, elastic net and fused lasso, which combine multiple desiderata. In both of these cases, we show that a hard objective relaxed to obtain penalties can be more tightly approximated. Further, by construction, it is impossible to get a better convex approximation than the ones we derive. Thus, constructing a joint envelope across different parts of the objective provides means to trade off tightness and computational cost. [pdf]

Related Material