Sparse learning with duality gap guarantee

We propose a general regularized empirical risk minimization framework for sparse learning which accommodates popular regularizers such as lasso, group lasso, and the trace norm. Within this framework, we develop two optimization algorithms. The first method is based on squared penalties added to the empirical risk and is solved using a subgradient-based L-BFGS quasi-Newton method. The second method is based on constraints imposed on sparsity-inducing norms and is solved using a gradient projection method. A notable advantage of our approaches is that a simple way to access the dual objective value is available, which is use-ful in tracking the progress of optimization and deciding when to terminate the optimization procedure.