Antonio Coppola edited Introduction.tex  over 9 years ago

Commit id: 0f4aaab2cef006fcb8bf51174dbfedd53fbbddfe

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.