Timezone: »

 
Poster
Proximal Quasi-Newton for Computationally Intensive L1-regularized M-estimators
Kai Zhong · Ian En-Hsu Yen · Inderjit Dhillon · Pradeep Ravikumar

Tue Dec 09 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D
in Poster Session »

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 our proximal quasi-Newton algorithm 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.

[ PDF] 

Author Information

Kai Zhong (Amazon)
Ian En-Hsu Yen (University of Texas at Austin)
Inderjit Dhillon (Google & UT Austin)
Pradeep Ravikumar (Carnegie Mellon University)

More from the Same Authors