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.

在本研究中，我们提出了一种精心构造的近端拟牛顿算法，用于解决计算密集的 M - 估计问题，特别是针对条件随机场的 L1 正则化 MLE 问题，该问题由于涉及到要求代价昂贵的推理步骤来计算梯度值，因此具有特别昂贵的优化成本。我们的算法在序列标记和分类等问题上比当前最先进的算法收敛速度更快。