Abstract
An optimization algorithm for minimizing a smooth function over a convex set is described. Each iteration of the method computes a descent direction by minimizing, over the original constraints, a diagonal plus low-rank quadratic approximation to the function. The quadratic approximation is constructed using a limited-memory quasi-Newton update. The method is suitable for large-scale problems where evaluation of the function is substantially more expensive than projection onto the constraint set. Numerical experiments on one-norm regularized test problems indicate that the proposed method is competitive with state-of-the-art methods such as bound-constrained L-BFGS and orthant-wise descent. We further show that the method generalizes to a wide class of problems, and substantially improves on state-of-the-art methods for problems such as learning the structure of Gaussian graphical models and Markov random fields.
TL;DR
The Projected Quasi-Newton (PQN) algorithm bridges the gap between fast-but-limited L-BFGS solvers and slow-but-general gradient projection methods. By solving a constrained quadratic subproblem at every step using a spectral projected gradient method, PQN handles complex convex constraints while maintaining the efficiency of second-order optimization, making it ideal for machine learning problems where evaluating the objective function is the primary bottleneck.
What Problem Does This Paper Address?
In modern machine learning, we often want to minimize a smooth function (like a log-likelihood) subject to constraints (like sparsity-inducing norm balls). Researchers usually face a trade-off:
- First-order methods (e.g., Gradient Projection): These are easy to implement for many constraints but require a massive number of iterations to converge because they don't use information about the function's curvature.
- Second-order methods (e.g., Interior-Point): These converge in few iterations but require solving massive, complex linear systems at every step, which is computationally ruinous for large-scale problems.
- Specialized Quasi-Newton (e.g., L-BFGS-B): These are very fast but are typically restricted to simple "box" constraints (e.g., $x \ge 0$).
The authors address the "costly function" scenario—common in structure learning for Markov Random Fields (MRFs) or Conditional Random Fields (CRFs)—where a single function evaluation can take minutes or hours. In these cases, we need an algorithm that makes the most out of every evaluation by using second-order information, even when the constraints are more complex than simple bounds.
Methods
The authors propose the Projected Quasi-Newton (PQN) algorithm, which uses a two-level strategy:
- Outer Level: Like the standard L-BFGS algorithm, PQN builds a quadratic approximation of the objective function. It uses a "limited-memory" approach, representing the Hessian as a diagonal matrix plus a low-rank update, keeping the memory footprint small.
- Inner Level: Instead of a simple projection, PQN solves a subproblem: it minimizes the quadratic approximation subject to the original constraints. To do this efficiently, it uses the Spectral Projected Gradient (SPG) method.
The "secret sauce" is that because the L-BFGS Hessian approximation is low-rank, the inner SPG solver can perform matrix-vector products very quickly ($O(mn)$ time). This allows PQN to take "smarter" steps than a standard gradient method without the overhead of a full Newton method.
Key Results
The algorithm was evaluated on tasks ranging from CRF parameter estimation (using CoNLL-2000) to Gaussian Graphical Model (GGM) and MRF structure learning (using yeast and protein data).
- Competitive with Specialists: On CRF tasks with simple $\ell_1$ constraints, PQN performed as well as state-of-the-art specialized solvers like L-BFGS-B and Orthant-Wise Descent (OWD).
- Superior on Complex Tasks: For GGM and MRF structure learning—where constraints are more complex—PQN significantly outperformed standard Projected Gradient (PG) and Block Coordinate Descent (BCD) methods.
- Function Evaluation Efficiency: In the MRF experiments, PQN reached a high-quality solution in roughly 20-40 function evaluations, whereas the previous best method (SPG) required over 100 to reach the same level of accuracy.
Key Insights and Ideas
- The Projection Bottleneck: The authors realized that in many ML problems, the cost of projecting onto a constraint set is negligible compared to the cost of calculating the gradient of a complex model. PQN exploits this "cheap projection, expensive function" regime.
- Low-Rank Efficiency: By using the compact representation of L-BFGS, the inner optimization subproblem becomes computationally "cheap" enough to solve many times within a single outer iteration.
- Generality: Unlike previous L-BFGS variants that were hard-coded for specific constraints, PQN works for any convex set, provided you have a way to project onto it.
Limitations and Future Work
- Overhead: If the objective function is very "cheap" to evaluate, the overhead of the inner SPG solver might make PQN slower than simpler methods.
- Projection Dependency: The efficiency of the algorithm relies on having an efficient projection operator. While many common constraints have efficient projections, highly irregular constraint sets might slow the inner loop down.
- Future Directions: The authors suggest applying PQN to a wider variety of constraints, such as the probability simplex or positive semi-definite (PSD) cones.
Summary updated