Antonio Coppola edited Introduction.tex  over 9 years ago

Commit id: 55db01558a203e12e28d7d5a8cb7a351f6e64de0

deletions | additions      

       

\subsection{The OWL-QN Algorithm}  The L-BFGS method cannot be applied to problems with an objective function of the form $r(x) = C \cdot \lvert \lvert x \lvert \lvert _1 = C \cdot \sum_i \lvert x_i \lvert$, such as LASSO regression or $L_1$-penalized log-linear models, given the non-differentiability of the objective function at any point where at least one of the parameters is zero. The OWL-QN algorithm exploits the fact that $L_1$-regularized objective functions will still be differential in any given orthant of the functional space. At each iteration, the algorithm chooses an orthant within which to evalute the function by estimating the sign of each of its parameters. The algorithm then constructs a quadratic approximation to the function in the given orthant using a regular L-BFGS procedure, and searches in the direction of the minimum of the approximation within the same orthant. For further details regarding OWL-QN, we refer the reader to the original article \cite{Andrew_Gao_2007}.