Timezone: »
Poster
Lower Bounds on Rate of Convergence of Cutting Plane Methods
Xinhua Zhang · Ankan Saha · S.V.N. Vishwanathan
In a recent paper Joachims (2006) presented SVM-Perf, a cutting plane method (CPM) for training linear Support Vector Machines (SVMs) which converges to an $\epsilon$ accurate solution in $O(1/\epsilon^{2})$ iterations. By tightening the analysis, Teo et al. (2010) showed that $O(1/\epsilon)$ iterations suffice. Given the impressive convergence speed of CPM on a number of practical problems, it was conjectured that these rates could be further improved. In this paper we disprove this conjecture. We present counter examples which are not only applicable for training linear SVMs with hinge loss, but also hold for support vector methods which optimize a \emph{multivariate} performance score. However, surprisingly, these problems are not inherently hard. By exploiting the structure of the objective function we can devise an algorithm that converges in $O(1/\sqrt{\epsilon})$ iterations.
Author Information
Xinhua Zhang (University of Illinois at Chicago (UIC))
Ankan Saha (Linkedin Corporation)
S.V.N. Vishwanathan (UCSC)
More from the Same Authors
-
2022 : Poisoning Generative Models to Promote Catastrophic Forgetting »
Siteng Kang · Xinhua Zhang -
2022 : Continual Poisoning of Generative Models to Promote Catastrophic Forgetting »
Siteng Kang · Xinhua Zhang -
2022 Poster: Moment Distributionally Robust Tree Structured Prediction »
Yeshu Li · Danyal Saeed · Xinhua Zhang · Brian Ziebart · Kevin Gimpel -
2022 Poster: Certifying Robust Graph Classification under Orthogonal Gromov-Wasserstein Threats »
Hongwei Jin · Zishun Yu · Xinhua Zhang -
2021 Poster: Distributionally Robust Imitation Learning »
Mohammad Ali Bashiri · Brian Ziebart · Xinhua Zhang -
2021 Poster: Implicit Task-Driven Probability Discrepancy Measure for Unsupervised Domain Adaptation »
Mao Li · Kaiqi Jiang · Xinhua Zhang -
2020 Poster: Certified Robustness of Graph Convolution Networks for Graph Classification under Topological Attacks »
Hongwei Jin · Zhan Shi · Venkata Jaya Shankar Ashish Peruri · Xinhua Zhang -
2020 Spotlight: Certified Robustness of Graph Convolution Networks for Graph Classification under Topological Attacks »
Hongwei Jin · Zhan Shi · Venkata Jaya Shankar Ashish Peruri · Xinhua Zhang -
2020 Poster: Proximal Mapping for Deep Regularization »
Mao Li · Yingyi Ma · Xinhua Zhang -
2020 Spotlight: Proximal Mapping for Deep Regularization »
Mao Li · Yingyi Ma · Xinhua Zhang -
2018 Poster: Distributionally Robust Graphical Models »
Rizal Fathony · Ashkan Rezaei · Mohammad Ali Bashiri · Xinhua Zhang · Brian Ziebart -
2017 Poster: Decomposition-Invariant Conditional Gradient for General Polytopes with Line Search »
Mohammad Ali Bashiri · Xinhua Zhang -
2017 Poster: Bregman Divergence for Stochastic Variance Reduction: Saddle-Point and Adversarial Prediction »
Zhan Shi · Xinhua Zhang · Yaoliang Yu -
2017 Spotlight: Bregman Divergence for Stochastic Variance Reduction: Saddle-Point and Adversarial Prediction »
Zhan Shi · Xinhua Zhang · Yaoliang Yu -
2017 Poster: Large-Scale Quadratically Constrained Quadratic Program via Low-Discrepancy Sequences »
Kinjal Basu · Ankan Saha · Shaunak Chatterjee -
2016 Poster: Convex Two-Layer Modeling with Latent Structure »
Vignesh Ganapathiraman · Xinhua Zhang · Yaoliang Yu · Junfeng Wen -
2015 Poster: A Structural Smoothing Framework For Robust Graph Comparison »
Pinar Yanardag · S.V.N. Vishwanathan -
2014 Poster: Convex Deep Learning via Normalized Kernels »
Özlem Aslan · Xinhua Zhang · Dale Schuurmans -
2014 Poster: Robust Bayesian Max-Margin Clustering »
Changyou Chen · Jun Zhu · Xinhua Zhang -
2013 Poster: Learning with Invariance via Linear Functionals on Reproducing Kernel Hilbert Space »
Xinhua Zhang · Wee Sun Lee · Yee Whye Teh -
2013 Spotlight: Learning with Invariance via Linear Functionals on Reproducing Kernel Hilbert Space »
Xinhua Zhang · Wee Sun Lee · Yee Whye Teh -
2013 Poster: Convex Two-Layer Modeling »
Özlem Aslan · Hao Cheng · Xinhua Zhang · Dale Schuurmans -
2013 Spotlight: Convex Two-Layer Modeling »
Özlem Aslan · Hao Cheng · Xinhua Zhang · Dale Schuurmans -
2013 Poster: Polar Operators for Structured Sparse Estimation »
Xinhua Zhang · Yao-Liang Yu · Dale Schuurmans -
2012 Poster: Convex Multi-view Subspace Learning »
Martha White · Yao-Liang Yu · Xinhua Zhang · Dale Schuurmans -
2012 Poster: Accelerated Training for Matrix-norm Regularization: A Boosting Approach »
Xinhua Zhang · Yao-Liang Yu · Dale Schuurmans -
2011 Poster: t-divergence Based Approximate Inference »
Nan Ding · S.V.N. Vishwanathan · Yuan Qi -
2010 Poster: t-logistic regression »
Nan Ding · S.V.N. Vishwanathan -
2010 Spotlight: Multiple Kernel Learning and the SMO Algorithm »
S.V.N. Vishwanathan · Zhaonan sun · Nawanol T Ampornpunt · Manik Varma -
2010 Poster: Multiple Kernel Learning and the SMO Algorithm »
S.V.N. Vishwanathan · Zhaonan sun · Nawanol T Ampornpunt · Manik Varma -
2010 Poster: Multitask Learning without Label Correspondences »
Novi Quadrianto · Alexander Smola · Tiberio Caetano · S.V.N. Vishwanathan · James Petterson -
2008 Poster: Kernel Measures of Independence for non-iid Data »
Xinhua Zhang · Le Song · Arthur Gretton · Alexander Smola -
2008 Spotlight: Kernel Measures of Independence for non-iid Data »
Xinhua Zhang · Le Song · Arthur Gretton · Alexander Smola -
2006 Poster: Hyperparameter Learning for Graph Based Semi-supervised Learning Algorithms »
Xinhua Zhang · Wee Sun Lee