# Proximal Quasi-Newton for Computationally Intensive L1-regularized M-estimators

arXiv: https://arxiv.org/abs/1406.7321 · HTML: https://mlsanity.com/paper/1406.7321/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jun 2014.

## Built on by (most cited first, 2 of 2)

- [On the Sparse DAG Structure Learning Based on Adaptive Lasso](https://mlsanity.com/paper/2209.02946/) (2022)
- [Deep Nonparametric Convexified Filtering for Computational Photography, Image Synthesis and Adversarial Defense](https://mlsanity.com/paper/2309.06724/) (2023)

## Abstract (arXiv)

We consider the class of optimization problems arising from computationally intensive L1-regularized M-estimators, where the function or gradient values are very expensive to compute. A particular instance of interest is the L1-regularized MLE for learning Conditional Random Fields (CRFs), which are a popular class of statistical models for varied structured prediction problems such as sequence labeling, alignment, and classification with label taxonomy. L1-regularized MLEs for CRFs are particularly expensive to optimize since computing the gradient values requires an expensive inference step. In this work, we propose the use of a carefully constructed proximal quasi-Newton algorithm for such computationally intensive M-estimation problems, where we employ an aggressive active set selection technique. In a key contribution of the paper, we show that the proximal quasi-Newton method is provably super-linearly convergent, even in the absence of strong convexity, by leveraging a restricted variant of strong convexity. In our experiments, the proposed algorithm converges considerably faster than current state-of-the-art on the problems of sequence labeling and hierarchical classification.