PQN: Optimizing Costly Functions with Simple Constraints

By Mark Schmidt, Ewout van den Berg, Michael Friedlander, Kevin Murphy (2009)
Last updated 3 July 2010.

Summary

PQN implements a limited-memory projected quasi-Newton algorithm for constrained optimization. It uses L-BFGS updates to build a diagonal plus low-rank quadratic approximation to the function, uses the spectral projected gradient (SPG) algorithm to minimize the quadratic approximation subject to the constraints present in the original problem, and uses a backtracking line search to generate new parameter vectors satisfying an Armijo-like sufficient decrease condition. The method is most effective when computing the projection onto the constraint set can be done much more efficiently than evaluating the function.

The PQN method is decribed in the following paper:

Clicking on the image below opens the slides of a talk giving an overview of the method and results:

PQN assumes that the function is differentiable, and that the user provides a function that computes the objective value (and optionally its gradient) for a given parameter vector. PQN also assumes that the set of values satisfying the constraints define a convex set, and that the user provides a function that computes the projection onto this set (ie. for a given parameter vector, this returns returns the closest parameter vector that satisfies the constraints).

Download and Examples

  • To use the code, download and unzip PQN.zip. Then, in Matlab, type: 
    >> cd PQN
>> addpath(genpath(pwd))
>> runSmall
    Typing the above commands will run a set of experiments that are similar to those in the paper, except they run very quickly because they are on small data sets (where the differences between methods are very small).

    We have included mex files for several operating systems. To compile the mex files for other operating systems, run the included mexAll function.

    The function PQN_examples runs a series of demos illustrating the types of problems that PQN can solve. The full list of demos is:

  • Linear Regression on the Simplex
  • Lasso regression
  • Lasso with Complex Variables
  • Group-Sparse Linear Regression with Categorical Features
  • Group-Sparse Simultaneous Regression
  • Group-Sparse Multinomial Logistic Regression
  • Group-Sparse Multi-Task Classification
  • Low-Rank Multi-Task Classification
  • L_1,inf Blockwise-Sparse Graphical Lasso
  • L_1,2 Blockwise-Sparse Graphical Lasso
  • Linear Regression with the Over-Lasso
  • Kernelized dual form of support vector machines
  • Smooth (Primal) Support Vector Machine with Multiple Kernel Learning
  • Conditional Random Field Feature Selection
  • Approximating node marginals in undirected graphical models with variational mean field
  • Multi-State Markov Random Field Structure Learning
  • Conditional Random Field Structure Learning with Pseudo-Likelihood

    The code, some documentation, and examples of the results of these demos can be found here.

    How to use the code

    This code addresses the problem of minimizing a differentiable function f(x) over (closed) convex set X: 
    min_x f(x), subject to x is in X
    The PQN method is implemented in the Matlab function minConf_PQN. It can be called using the interface: 
    >> x = minConf_PQN(funObj,x,funProj,options)
    The first input funObj is a function handle that returns the objective value and gradient for a given parameter vector. For example, if we want to minimize the linear least squares objective 
    f(x) = ||Ax - b||^2
    we could use: 
    >> funObj = @(x)SquaredError(x,A,b);
    The second input, x, is the initial guess at the optimal solution (this guess doesn't need to satisfy the constraints). For example, we might use: 
    >> p = size(A,2);
>> x = zeros(p,1);
    The third input, funProj, returns the projection onto the convex set for a given parameter vector (ie. the closest point in X to the input point x). That is, for a given x the function funProj returns the unique solution to: 
    P(x) = argmin_y ||y - x||, subject to y is in X
    For example, if the constraints enforce that the variables must be non-negative we could use: 
    >> funProj = @(x)boundProject(x,zeros(p,1),inf(p,1));
    The last (optional) argument, options, is a structure that specifies if we want to change any of the default options. For example, we can reduce the number of L-BFGS corrections to store and turn on using numerical differentiation (instead of requiring that funObj return the gradient vector) using: 
    >> options.corrections = 10;
>> options.numDiff = 1;
    The full list of options can be accessed by typing help minConf_PQN, and includes things like changing the verbosity level of the program, changing the optimality tolerances, changing the maximum number of function evaluations or projections, and changing the parameters of the line search or SPG sub-routine.

    Reproducing the Paper Results

    You can reproduce all of the figures in the paper using the plotAll function.

    To re-run the experiments in the paper, use the runAll function.

    This requires that you have the data sets available in the correct format. These data sets are not included in the zip file, they are available from the following sources: CoNLL 200 Chunking Task, Yeast Genomic Expression Data, Protein Signaling Data. The authors can be contacted about converting to our data format.

    The machine running these experiments had 4GB of RAM, you may need to decrease 'options.corrections' if your machine hass less.

    Related Codes:

    minConf - Other methods for multivariate differentiable optimization with different types of simple constraints
    Gsparse - Matlab functions implementing Spectral Projected Gradient methods for optimization with a Group L1-norm constraint.
    minFunc - Matlab function for unconstrained optimization of continuous real-valued multivariate functions (Examples).
    SPGL1 - A solver for large-scale sparse reconstruction problems (Lasso, Basis Pursuit, Basis Pursuit Denoising)
    crfChain - Matlab function implementing learning/inference/decoding/sampling in chain-structured conditional random fields with categorical features.
    UGMlearn - Matlab code for structure learning in discrete-state undirected graphical models (Markov Random Fields and Conditional Random Fields) using Group L1-regularization.

    Mark Schmidt > Software > PQN