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

By Ian En-Hsu Yen, Xiangru Huang, Kai Zhong, Ruohan Zhang, Pradeep Ravikumar, Inderjit S. Dhillon. 2016

9 citations recorded by the source corpus.

Many applications of machine learning involve structured outputs with large domains, where learning 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 oracle with 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 is orders-of-magnitude faster than current state-of-the-art algorithms for training Structural SVMs.

Subfields: Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

Frank-Wolfe Splitting via Augmented Lagrangian Method (2018, methodology): “Furthermore, some challenging optimization problems such as multiple sequence alignment are naturally expressed over an intersection of sets (Yen et al., 2016a) or more generally as a linear relationship between these sets (Huang et al., 2017).”
Greedy Direction Method of Multiplier for MAP Inference of Large Output Domain (2017, background): “Note a similar strategy could be also exploited at the training phase for some specific loss function such as structured support vector machine [17, 18].”