Antonio Coppola edited Introduction.tex  over 9 years ago

Commit id: b9d20773a7440c2edc7ebdfac1d9e5bb7fcc1233

deletions | additions      

       

\section{Introduction}  In this vignette we demonstrate how to use the \textbf{lbfgs} R package. \footnote{We are extremely thankful to Dustin Tingley for his advice and support.} The original motivation for writing the package was the lack of a general R implementation of the Orthant-Wise Quasi-Newton Limited-Memory (OWL-QN) optimization algorithm \cite{Andrew_Gao_2007}, except in limited-scope contexts. The package uses the \href{http://www.chokkan.org/software/liblbfgs/}{libLBFGS} C++ library written by Naoaki Okazaki, which itself is a port of the Fortran method by Jorge Nocedal \cite{Nocedal_1980}. The linkage between R and C++ is achieved using Rcpp \cite{Eddelbuettel_2013}. The package is suitable for large-scale applications with significant numbers of parameters.  \subsection{Notation} 

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 interested reader to the original article \cite{Andrew_Gao_2007}.  \subsection{Features of the Package}  The lbfgs package is intended as a general-purpose library for numerical optimization with L-BFGS and OWL-QN. As such, its syntax and usage closely mirror those of other popular packages for numerical optimization in R. The following list provides brief comparisons between lbfsg and several other packages:  \begin{itemize}  \item optim(x): The lbfgs package can be used as a drop-in replacement for the L-BFGS-B method of the optim and optimx, with performance improvements on particular classes of problems (see Section ...), especially if lbfgs is used in conjuction with C++ implementations of the objective and gradient functions. In addition, the possibility of introducing $L_1$ penalization of the objective function allows for solution vectors with much higher sparsity, as most of the otherwise quasi-zero parameters are driven to zero.  \item penalized: The penalized package fits regression models with both $L_1$ (lasso and fused lasso) and $L_2$ (ridge) penalizations. TODO.  \item glmnet: The glmnet package fits lasso and elastic-net generalized linear models. TODO.  \end{itemize}