Optimizing Costly Functions with Simple Constraints: A Limited-Memory Projected Quasi-Newton Algorithm
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.
Cite
Text
Schmidt et al. "Optimizing Costly Functions with Simple Constraints: A Limited-Memory Projected Quasi-Newton Algorithm." Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, 2009.Markdown
[Schmidt et al. "Optimizing Costly Functions with Simple Constraints: A Limited-Memory Projected Quasi-Newton Algorithm." Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, 2009.](https://mlanthology.org/aistats/2009/schmidt2009aistats-optimizing/)BibTeX
@inproceedings{schmidt2009aistats-optimizing,
title = {{Optimizing Costly Functions with Simple Constraints: A Limited-Memory Projected Quasi-Newton Algorithm}},
author = {Schmidt, Mark and Berg, Ewout and Friedlander, Michael and Murphy, Kevin},
booktitle = {Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics},
year = {2009},
pages = {456-463},
volume = {5},
url = {https://mlanthology.org/aistats/2009/schmidt2009aistats-optimizing/}
}