Safe-screening rules for atomic-norm regularization

Safe-screening rules are algorithmic techniques meant to detect and safely discard unneeded variables during the solution process with the aim of accelerating computation. These techniques have been shown to be effective for one-norm regularized problems. This paper generalizes the safe-screening rule proposed by Ndiaye et al. [J. Mach. Learn. Res., 2017] to various optimization problem formulations with atomic-norm regularization. For nuclear-norm regularized problems in particular, it is shown that the proposed generalized safe-screening rule cannot safely reduce the problem size. In that case, approximation guarantees are developed that allows for reducing the problem size.