document: Training structural svms with kernels using sampled cuts Discriminative training for structured outputs has found increasing applications in areas such as natural language processing , bioinformatics , information retrieval , and computer vision . Focusing on large-margin methods , the most general ( in terms of loss function and model structure ) training algorithms known to date are based on cutting-plane approaches . While these algorithms are very efficient for linear models , their training complexity becomes quadratic in the number of examples when kernels are used . To overcome this bottleneck , we propose new training algorithms that use approximate cutting planes and random sampling to enable efficient training with kernels . We prove that these algorithms have improved time complexity while providing approximation guarantees . In empirical evaluations , our algorithms produced solutions with training and test error rates close to those of exact solvers . Even on binary classification problems where highly optimized conventional training methods exist ( e.g. SVM-light ) , our methods are about an order of magnitude faster than conventional training methods on large datasets , while remaining competitive in speed on datasets of medium size .
doc_bio_tags: O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O