Dual Decomposed Learning with Factorwise Oracle for Structural SVM of Large Output Domain

Many applications of machine learning involve structured outputs with large domains, wherelearning of a structured predictor is prohibitive due to repetitive calls to an expensive inference oracle. In this work, we show that by decomposing training of a Structural Support Vector Machine (SVM) into a series of multiclass SVM problems connected through messages, one can replace an expensive structured oraclewith Factorwise Maximization Oracles (FMOs) that allow efficient implementation of complexity sublinear to the factor domain. A Greedy Direction Method of Multiplier (GDMM) algorithm is then proposed to exploit the sparsity of messages while guarantees convergence to ɛ sub-optimality after O(log(1/ɛ)) passes of FMOs over every factor. We conduct experiments on chain-structured and fully-connected problems of large output domains, where the proposed approach isorders-of-magnitude faster than current state-of-the-art algorithms for training Structural SVMs.