Recent analysis (Martins et al., 2012 ) has shown that: (i) AD 3 converges at a faster rate, 2 and (ii) the quadratic subproblems can be solved using the same combinatorial machinery that is used in the subgradient algorithm. This opens the door for larger subproblems (such as the combination of trees and head automata in instead of a many-components approach <cite>(Martins et al., 2011)</cite> , while still enjoying faster convergence.