Combinatorial Penalties: Which structures are preserved by convex relaxations?

This work addresses theoretical gaps in understanding convex relaxations for combinatorial penalties, which is important for researchers in optimization and machine learning, though it appears incremental as it builds on existing frameworks.

The paper analyzes convex relaxations of combinatorial penalty functions to determine which structures they preserve, identifying key differences in tightness through the concept of lower combinatorial envelopes and new necessary conditions for support identification. It also proposes a general adaptive estimator for convex monotone regularizers and derives new sufficient conditions for support recovery in asymptotic settings.