Beyond a Single Sparse Solution: Certifying Feature Necessity under Inexact Multi-Label Supervision

Feature selection under inexact multi-label supervision is complicated by both ambiguous label assignments and redundant predictive supports. Existing methods typically identify the support of a single fitted solution, which may be predictive but does not establish whether its selected features are necessary. We study feature necessity over the family of near-optimal predictors. Our framework evaluates a feature set through counterfactual deletion: the set is removed, all remaining variables are re-optimized, and the resulting deletion cost determines whether any comparably good predictor can avoid it. This formulation characterizes both individual necessity, where a feature must appear in every near-optimal predictor, and collective non-removability, where individually replaceable features cannot be removed jointly. We instantiate the framework with a convex ambiguity-aware objective that preserves set-valued supervision and induces row-sparse feature selection. Strong convexity yields safe bounds on optimization error and deletion costs, enabling efficient screening and selective re-optimization, while monotonicity supports structured search for collective relevance. Extensive experiments on controlled and real-world datasets validate the predicted individual and collective structures and demonstrate the practical effectiveness of the resulting certificates and feature rankings.