Author name cluster

S.V.N. Vishwanathan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

TCS Journal 2014 Journal Article

Accelerated training of max-margin Markov networks with kernels

Xinhua Zhang
Ankan Saha
S.V.N. Vishwanathan

Structured output prediction is an important machine learning problem both in theory and practice, and the max-margin Markov network (M 3 N) is an effective approach. All state-of-the-art algorithms for optimizing M 3 N objectives take at least O ( 1 / ϵ ) number of iterations to find an ϵ accurate solution. Nesterov [1] broke this barrier by proposing an excessive gap reduction technique (EGR) which converges in O ( 1 / ϵ ) iterations. However, it is restricted to Euclidean projections which consequently requires an intractable amount of computation for each iteration when applied to solve M 3 N. In this paper, we show that by extending EGR to Bregman projection, this faster rate of convergence can be retained, and more importantly, the updates can be performed efficiently by exploiting graphical model factorization. Further, we design a kernelized procedure which allows all computations per iteration to be performed at the same cost as the state-of-the-art approaches.

Details DOI

JMLR Journal 2012 Journal Article

Smoothing Multivariate Performance Measures

Xinhua Zhang
Ankan Saha
S.V.N. Vishwanathan

Optimizing multivariate performance measure is an important task in Machine Learning. Joachims (2005) introduced a Support Vector Method whose underlying optimization problem is commonly solved by cutting plane methods (CPMs) such as SVM-Perf and BMRM. It can be shown that CPMs converge to an ε accurate solution in O(1/λ ε) iterations, where λ is the trade-off parameter between the regularizer and the loss function. Motivated by the impressive convergence rate of CPM on a number of practical problems, it was conjectured that these rates can be further improved. We disprove this conjecture in this paper by constructing counter examples. However, surprisingly, we further discover that these problems are not inherently hard, and we develop a novel smoothing strategy, which in conjunction with Nesterov's accelerated gradient method, can find an ε accurate solution in O * (min {1/ε, 1/√λε}) iterations. Computationally, our smoothing technique is also particularly advantageous for optimizing multivariate performance scores such as precision/recall break-even point and ROCArea; the cost per iteration remains the same as that of CPMs. Empirical evaluation on some of the largest publicly available data sets shows that our method converges significantly faster than CPMs without sacrificing generalization ability. [abs] [ pdf ][ bib ] &copy JMLR 2012. ( edit, beta )

PDF Details

JMLR Journal 2010 Journal Article

A Quasi-Newton Approach to Nonsmooth Convex Optimization Problems in Machine Learning

Jin Yu
S.V.N. Vishwanathan
Simon Günter
Nicol N. Schraudolph

We extend the well-known BFGS quasi-Newton method and its memory-limited variant LBFGS to the optimization of nonsmooth convex objectives. This is done in a rigorous fashion by generalizing three components of BFGS to subdifferentials: the local quadratic model, the identification of a descent direction, and the Wolfe line search conditions. We prove that under some technical conditions, the resulting subBFGS algorithm is globally convergent in objective function value. We apply its memory-limited variant (subLBFGS) to L 2 -regularized risk minimization with the binary hinge loss. To extend our algorithm to the multiclass and multilabel settings, we develop a new, efficient, exact line search algorithm. We prove its worst-case time complexity bounds, and show that our line search can also be used to extend a recently developed bundle method to the multiclass and multilabel settings. We also apply the direction-finding component of our algorithm to L 1 -regularized risk minimization with logistic loss. In all these contexts our methods perform comparable to or better than specialized state-of-the-art solvers on a number of publicly available data sets. An open source implementation of our algorithms is freely available. [abs] [ pdf ][ bib ] &copy JMLR 2010. ( edit, beta )

PDF Details

JMLR Journal 2010 Journal Article

Graph Kernels

S.V.N. Vishwanathan
Nicol N. Schraudolph
Risi Kondor
Karsten M. Borgwardt

We present a unified framework to study graph kernels, special cases of which include the random walk (Gärtner et al., 2003; Borgwardt et al., 2005) and marginalized (Kashima et al., 2003, 2004; Mahét al., 2004) graph kernels. Through reduction to a Sylvester equation we improve the time complexity of kernel computation between unlabeled graphs with n vertices from O(n 6 ) to O(n 3 ). We find a spectral decomposition approach even more efficient when computing entire kernel matrices. For labeled graphs we develop conjugate gradient and fixed-point methods that take O(dn 3 ) time per iteration, where d is the size of the label set. By extending the necessary linear algebra to Reproducing Kernel Hilbert Spaces (RKHS) we obtain the same result for d -dimensional edge kernels, and O(n 4 ) in the infinite-dimensional case; on sparse graphs these algorithms only take O(n 2 ) time per iteration in all cases. Experiments on graphs from bioinformatics and other application domains show that these techniques can speed up computation of the kernel by an order of magnitude or more. We also show that certain rational kernels (Cortes et al., 2002, 2003, 2004) when specialized to graphs reduce to our random walk graph kernel. Finally, we relate our framework to R-convolution kernels (Haussler, 1999) and provide a kernel that is close to the optimal assignment kernel of kernel of Fröhlich et al. (2006) yet provably positive semi-definite. [abs] [ pdf ][ bib ] &copy JMLR 2010. ( edit, beta )

PDF Details

JMLR Journal 2009 Journal Article

Hash Kernels for Structured Data

Qinfeng Shi
James Petterson
Gideon Dror
John Langford
Alex Smola
S.V.N. Vishwanathan

We propose hashing to facilitate efficient kernels. This generalizes previous work using sampling and we show a principled way to compute the kernel matrix for data streams and sparse feature spaces. Moreover, we give deviation bounds from the exact kernel matrix. This has applications to estimation on strings and graphs. [abs] [ pdf ][ bib ] &copy JMLR 2009. ( edit, beta )

PDF Details