  We present safe active incremental feature selection~(SAIF) to scale up the
computation of LASSO solutions. SAIF does not require a solution from a heavier
penalty parameter as in sequential screening or updating the full model for
each iteration as in dynamic screening. Different from these existing screening
methods, SAIF starts from a small number of features and incrementally recruits
active features and updates the significantly reduced model. Hence, it is much
more computationally efficient and scalable with the number of features. More
critically, SAIF has the safe guarantee as it has the convergence guarantee to
the optimal solution to the original full LASSO problem. Such an incremental
procedure and theoretical convergence guarantee can be extended to fused LASSO
problems. Compared with state-of-the-art screening methods as well as working
set and homotopy methods, which may not always guarantee the optimal solution,
SAIF can achieve superior or comparable efficiency and high scalability with
the safe guarantee when facing extremely high dimensional data sets.
Experiments with both synthetic and real-world data sets show that SAIF can be
up to 50 times faster than dynamic screening, and hundreds of times faster than
computing LASSO or fused LASSO solutions without screening.
