Limited-memory quasi-newton optimization algorithm for l1-regularized objectives

Abstract

An algorithm that employs modified methods developed for optimizing differential functions but which can also handle the special non-differentiabilities that occur with the L-regularization. The algorithm is a modification of the L-BFGS (limited-memory Broyden-Fletcher-Goldfarb-Shanno) quasi-Newton algorithm, but which can now handle the discontinuity of the gradient using a procedure that chooses a search direction at each iteration and modifies the line search procedure. The algorithm includes an iterative optimization procedure where each iteration approximately minimizes the objective over a constrained region of the space on which the objective is differentiable (in the case of L-regularization, a given orthant), models the second-order behavior of the objective by considering the loss component alone, using a 'line-search' at each iteration that projects search points back onto the chosen orthant, and determines when to stop the line search.