abstract
sparsity-based methods are widely used in machine learning, statistics, and signal processing. there
is now a rich class of structured sparsity approaches that expand the modeling power of the sparsity
paradigm and incorporate constraints such as group sparsity, graph sparsity, or hierarchical sparsity. while
these sparsity models offer improved sample complexity and better interpretability, the improvements
come at a computational cost: it is often challenging to optimize over the (non-convex) constraint sets
that capture various sparsity structures. in this paper, we make progress in this direction in the context of
separated sparsity – a fundamental sparsity notion that captures exclusion constraints in linearly ordered
data such as time series. while prior algorithms for computing a projection onto this constraint set
required quadratic time, we provide a perturbed lagrangian relaxation approach that computes provably
exact projection in only nearly-linear time. although the sparsity constraint is non-convex, our perturbed
lagrangian approach is still guaranteed to find a globally optimal solution. in experiments, our new
algorithms offer a 10× speed-up already on moderately-size inputs.