\documentclass[twoside,11pt]{article}

\usepackage{jmlr2e}

\newcommand{\comment}[1]{}
\newcommand{\mnote}[1]
{\mbox{}\marginpar{$\bullet$ \scriptsize \it \hspace{0pt}#1}}
\renewcommand{\t}{^{^T}}
\newcommand{\R}{\bf R}
\newcommand{\lt}{\tilde L}
\newcommand{\tl}{L ^{^T}}
\newcommand{\tlt}{\tilde L^{^T}}
\newcommand{\dt}{\tilde \Lambda}
\newcommand{\td}{\tilde \lambda}
\newcommand{\lb}{\bar L}
\newcommand{\bl}{\bar l}
\newcommand{\tlb}{\bar L^{^T}}
\newcommand{\db}{\bar \Lambda}
\newcommand{\dtt}{\tilde {\tilde D}}
\newcommand{\ltt}{\tilde {\tilde L}}
\newcommand{\tltt}{\tilde {\tilde L}\t}
\newcommand{\D}{D^{2}}
\newcommand{\e }{{\epsilon}}
\newcommand{\tQ}{{\tilde Q}}
\newcommand{\dQ}{{\Delta Q}}

% Heading arguments are {volume}{year}{pages}{submitted}{published}{authors}
\jmlrheading{2}{2001}{243-264}{3/01}{12/01}{Shai Fine and Katya Scheinberg}
\ShortHeadings{Efficient SVM Training Using Low-Rank Kernel Representations}{Fine and Scheinberg}
\firstpageno{243}

\begin{document}
\title{Efficient SVM Training Using Low-Rank Kernel Representations}

\author{\name Shai Fine \email fshai@il.ibm.com \\
       \addr Human Language Technologies Department \\
       IBM T. J. Watson Research Center \\	
       P.O. Box  218, Yorktown Heights, NY 10598, USA 
       \AND
       \name Katya Scheinberg \email katyas@watson.ibm.com \\
       \addr Mathematical Science Department \\
       IBM T. J. Watson Research Center \\	
       P.O. Box  218, Yorktown Heights, NY 10598, USA}

\editor{Nello Cristianini, John Shawe-Taylor and Bob Williamson}


\maketitle

\begin{abstract}
SVM training is a convex optimization problem
which scales with the training set size rather than the feature space 
dimension. 
While this is usually considered to be a desired quality, 
in large scale problems it may cause training to be impractical.
The common techniques to handle this difficulty basically build a solution
by solving a sequence of small scale subproblems. 
Our current effort is concentrated on the rank  of the kernel matrix as a
source for further enhancement of the training procedure. We first show that
 for a low rank kernel matrix it is possible to design a better
interior point  method (IPM) in terms of storage requirements
as well as computational complexity. We then  suggest an efficient
use of a known factorization technique to approximate a given kernel matrix
by a low rank matrix, which in turn will be used to feed the optimizer.
Finally, we derive an upper bound on the change in the 
objective function
value based on the approximation error and the number of active constraints
(support vectors). This bound is general in the sense that it holds 
regardless of the approximation method.

\end{abstract}

\begin{keywords}
Support Vector Machine, Interior Point Method, Cholesky Product Form, 
Cholesky Factorization, Approximate Solution
\end{keywords}

%------------------------------------------------------------------------

% Introduction
\input{sec_1.tex}
% An Iterior Point Method
\input{sec_2.tex}
% Low-rank updates
\input{sec_3.tex}
% Approximating the Kernel Matrix
\input{sec_4.tex}
% Experiments
\input{sec_5.tex}
% Concluding Remarks
\input{sec_6.tex}

%\vskip1cm
%\noindent{\large {\bf Acknowledgment:}} 
\acks{The authors wishes to thank Ramesh Gopinath for
pointing out a shorter proof of Theorem \ref{bound},
and to the anonymous referees for their useful comments and suggestions.}

\vskip 0.2in
\bibliography{cholqp_paper}

\end{document}