Limited-memory quasi-newton optimization algorithm for L1-regularized objectives
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 1 -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 1 -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.
1. A computer-implemented data processing system, comprising:
a parametric model having parameters that are determined by minimizing an objective function which includes a sum of a convex loss and an L 1 norm of the parameters; and
an optimization component for finding a parameter vector that globally minimizes the objective function for a plurality of iterations over an orthant on which the objective function is differentiable such that, at each iteration, a search direction is computed by approximately minimizing a quadratic function that models the objective function over the orthant containing a previous point and by using curvature information based on the convex loss alone; and
a processor that executes computer-executable instructions associated with at least one of the parametric model or the optimization component.
2. The system of claim 1 , wherein the optimization component trains the parameters of the parametric model, which is a machine learning model, to minimize the objective function.
3. The system of claim 1 , wherein the parametric model is associated with natural language processing.
4. The system of claim 1 , wherein the optimization component performs a line search at each of multiple iterations that projects search points onto a selected orthant.
5. The system of claim 1 , wherein the optimization component stops a line search based on a decrease in function value relative to a directional derivative in a direction of actual movement.
6. The system of claim 1 , wherein the optimization component optimizes the objective function approximately over a constrained region of space for each iteration.
7. The system of claim 1 , wherein the quadratic function comprises a limited-memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) quadratic function.
8. A computer-implemented method of processing a parametric model, comprising acts of:
selecting an orthant that includes a current point in which direction a parametric vector representing steepest descent is pointed;
computing a limited-memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) quadratic approximation that is valid for the orthant;
computing a minimum of the L-BFGS quadratic approximation;
restricting a search to the orthant; and
utilizing a processor that executes instructions stored in memory to perform at least one of the acts of selecting, computing, or restricting.
9. The method of claim 8 , further comprising iteratively selecting the orthant, computing the L-BFGS quadratic approximation, computing a minimum of the L-BFGS quadratic approximation and restricting the search until convergence.
10. The method of claim 8 , further comprising computing the L-BFGS quadratic approximation using an inverse Hessian matrix.
11. The method of claim 10 , further comprising estimating the Hessian matrix based on the loss component alone.
12. The method of claim 8 , further comprising searching in a direction in which the L-BFGS quadratic approximation is a minimum.
13. The method of claim 8 , further comprising projecting search points back onto the selected orthant.
14. The method of claim 8 , further comprising stopping the search, which is a line search, based on a decrease in function value relative to a direction of actual movement.
15. The method of claim 8 , further comprising minimizing the quadratic approximation over a constrained region of space that is differentiable.
16. A computer-implemented method of processing a parametric model, comprising acts of:
selecting an orthant having a set of points of a sign pattern;
minimizing a convex function over the orthant;
modeling second-order behavior of the convex function based on a loss component;
constraining a search direction to match the sign pattern of the set of points;
projecting each search point back to the orthant; and
utilizing a processor that executes instructions stored in memory to perform at least one of the acts of selecting, minimizing, modeling, constraining, or projecting.
17. The method of claim 16 , further comprising employing a pseudo gradient of the convex function.
18. The method of claim 16 , further comprising finding a vector of steepest descent.
19. The method of claim 18 , further comprising selecting the orthant based on the vector.