  Proximal gradient methods have been found to be highly effective for solving
minimization problems with non-negative constraints or L1-regularization. Under
suitable nondegeneracy conditions, it is known that these algorithms identify
the optimal sparsity pattern for these types of problems in a finite number of
iterations. However, it is not known how many iterations this may take. We
introduce the notion of the "active-set complexity", which in these cases is
the number of iterations before an algorithm is guaranteed to have identified
the final sparsity pattern. We further give a bound on the active-set
complexity of proximal gradient methods in the common case of minimizing the
sum of a strongly-convex smooth function and a separable convex non-smooth
function.
