An Empirical Analysis of Optimization for Max-Margin NLP


Despite the convexity of structured max-margin objectives (Taskar et al., 2004; Tsochantaridis et al., 2004), the many ways to optimize them are not equally effective in practice. We compare a range of online optimization methods over a variety of structured NLP tasks (coreference, summarization, parsing, etc) and find several broad trends. First, margin methods do tend to outperform both likelihood and the perceptron. Second, for max-margin objectives, primal optimization methods are often more robust and progress faster than dual methods. This advantage is most pronounced for tasks with dense or continuous-valued features. Overall, we argue for a particularly simple online primal subgradient descent method that, despite being rarely mentioned in the literature, is surprisingly effective in relation to its alternatives.

Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing
Jonathan K. Kummerfeld
Jonathan K. Kummerfeld
Postdoctoral Research Fellow

Postdoc working on Natural Language Processing.