Timezone: »
The recent introduction of indefinite SVM by Luss and dAspremont [15] has effectively demonstrated SVM classification with a non-positive semi-definite kernel (indefinite kernel). This paper studies the properties of the objective function introduced there. In particular, we show that the objective function is continuously differentiable and its gradient can be explicitly computed. Indeed, we further show that its gradient is Lipschitz continuous. The main idea behind our analysis is that the objective function is smoothed by the penalty term, in its saddle (min-max) representation, measuring the distance between the indefinite kernel matrix and the proxy positive semi-definite one. Our elementary result greatly facilitates the application of gradient-based algorithms. Based on our analysis, we further develop Nesterovs smooth optimization approach [16,17] for indefinite SVM which has an optimal convergence rate for smooth problems. Experiments on various benchmark datasets validate our analysis and demonstrate the efficiency of our proposed algorithms.
Author Information
Yiming Ying (State University of New York at Albany)
Colin I Campbell (Bristol University)
Mark A Girolami (University of Glasgow)
Related Events (a corresponding poster, oral, or spotlight)
-
2009 Spotlight: Analysis of SVM with Indefinite Kernels »
Tue. Dec 8th 11:26 -- 11:27 PM Room None
More from the Same Authors
-
2021 Poster: Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learning »
ZHENHUAN YANG · Yunwen Lei · Puyu Wang · Tianbao Yang · Yiming Ying -
2021 Poster: Generalization Guarantee of SGD for Pairwise Learning »
Yunwen Lei · Mingrui Liu · Yiming Ying -
2010 Workshop: Monte Carlo Methods for Bayesian Inference in Modern Day Applications »
Ryan Adams · Mark A Girolami · Iain Murray -
2009 Poster: Sparse Metric Learning via Smooth Optimization »
Yiming Ying · Kaizhu Huang · Colin I Campbell -
2008 Poster: Accelerating Bayesian Inference over Nonlinear Differential Equations with Gaussian Processes »
Ben Calderhead · Mark A Girolami · Neil D Lawrence -
2007 Spotlight: A Spectral Regularization Framework for Multi-Task Structure Learning »
Andreas Argyriou · Charles A. Micchelli · Massimiliano Pontil · Yiming Ying -
2007 Poster: A Spectral Regularization Framework for Multi-Task Structure Learning »
Andreas Argyriou · Charles A. Micchelli · Massimiliano Pontil · Yiming Ying -
2006 Poster: Data Integration for Classification Problems Employing Gaussian Process Priors »
Mark A Girolami · Mingjun Zhong -
2006 Poster: Sparse Multinomial Logistic Regression via Bayesian L1 Regularisation »
Gavin Cawley · Nicola Talbot · Mark A Girolami -
2006 Poster: Kernel Maximum Entropy Data Transformation and an Enhanced Spectral Clustering Algorithm »
Robert Jenssen · Torbjorn Eltoft · Mark A Girolami · Deniz Erdogmus