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 ef-fective in practice. We compare a range of online optimization methods over a vari-ety of structured NLP tasks (coreference, summarization, parsing, etc) and find sev-eral 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 pri-mal subgradient descent method that, de-spite being rarely mentioned in the litera-ture, is surprisingly effective in relation to its alternatives.