\section{An Interior Point Method} \label{sec:IPM} We consider the following convex quadratic programming problem. \begin{eqnarray} {\rm min_{x}}&& \frac{1}{2}x\t Qx - e\t x \nonumber\\ \hspace{-1.3in}(P)\hspace{0.8in}\qquad {\rm s.t.}&&a\t x=0, \nonumber\\ &&0\leq x \leq c,\nonumber \end{eqnarray} where $x\in \R ^n$ is the vector of primal variables, $e$ is the vector of all $1$'s of length $n$ and $a$ is a vector of labels, $1$'s and $-1$'s. $c$ is the penalty parameter associated with the training error. In general it may be desirable to use different penalty parameters for different data points. In this case $c$ should be treated as an $n$-dimensional vector. However, for the sake of simplicity we assume that $c$ is a positive scalar. All our analysis and results extend easily to the more general case. Similarly, one might want to solve a problem with a slightly more general objective function $\frac{1}{2}x\t Qx +q\t x$, where $q$ is some $n$-dimensional vector (e.g., a small scaled optimization problem arising within a chunking-like meta algorithms). Our analysis and results extend easily to this case as well. The dual to the above problem is \begin{eqnarray} {\rm max_{y,s}}&& -\frac{1}{2}x\t Qx - c\sum_{i=1}^n \xi_i \nonumber\\ \hspace{-1.3in}(D)\hspace{0.8in}\qquad {\rm s.t.}&& -Qx+ a y +s-\xi =-e,\nonumber\\ &&s\geq 0,\ \xi \geq 0, \nonumber \end{eqnarray} Here $y$ is the scalar dual variable (it is equal to the negative bias) and $s$ and $\xi$ are the $n$-dimensional vectors of dual variables. Both ($P$) and ($D$) have finite optimal solutions and any optimal primal-dual pair of solutions satisfies the Karush-Kuhn-Tucker (KKT) necessary and sufficient optimality conditions: \begin{eqnarray} &&Xs=0,\nonumber\\ &&(C-X)\xi=0\nonumber\\ &&a\t x=0, \nonumber\\ &&-Qx+ a y +s-\xi =-e,\nonumber\\ &&0\leq x\leq c,\ s\geq 0,\ \xi \geq 0. \nonumber \end{eqnarray} By $X$ ($S$, $C-X$) we denote the diagonal matrix whose diagonal entries are the elements of the vector $x$ ($s$, $c-x$). For optimality conditions of QP and details of applying IPMs to QP \citep[see][]{Wright} and references therein. The perturbed KKT optimality conditions \begin{eqnarray} &&Xs=\sigma \mu e,\nonumber\\ &&(C-X)\xi=\sigma \mu e\nonumber\\ \hspace{-.6in}(CP _\mu)\hspace{.7in}&&a\t x=0, \nonumber\\ && -Qx+ a y +s-\xi=-e,\nonumber\\ &&0\leq x\leq c,\ s\geq 0,\ \xi \geq 0 \nonumber \end{eqnarray} have a unique solution for any positive values of the parameter $\mu$ and $\sigma$. The trajectory of solutions to the above system of equations for all values of $\mu\in (0, \infty)$ with some fixed positive value of $\sigma$ is called the {\sl central path}. The central path converges to an optimal solution. A path-following primal-dual interior point method tries to follow the central path towards the optimal solution by iteratively approximating solutions on the path by applying the Newton method to the above system of nonlinear equations, while reducing the value of parameter $\mu$ on each iteration. Any typical interior point method solves a linearization of the above system of nonlinear equations. We use the so-called Mehrotra predictor-corrector algorithm \citep{Mehrotra}, which is considered to be one of the most efficient in practice, however the ideas presented in Section \ref{sec:Low-rank_updates} on reducing the per-iteration complexity apply to any other interior point method. At every iteration there are two basic steps - the predictor step and the corrector step. The idea behind this algorithm is to start with ``predicting'' the best reduction in the duality gap, by evaluating a step directly towards the optimality. Such step, however, is not taken, since it may ruin the ``centrality'' of the iterates. A corrector step is computed instead. The corrector step enforces the centrality and also takes into account the approximate curvature of the central path predicted by the predictor step. Predictor step is a Newton step towards the solution of the system with $\sigma =0$ (which is the same as the system of the KKT conditions). Then, using this step, a value for $\sigma$ is chosen and a better step (corrector step) towards solution of the above system with this value of $\sigma$ is taken. For the predictor step we compute $(\Delta x, \Delta y, \Delta s, \Delta \xi)$, satisfying $$ \left [ \begin{array}{cccc} -Q &a & I & -I \\ a\t & 0 & 0 & 0\\ S & 0 & X & 0 \\ -\Xi & 0 & 0 & (C-X)\end{array} \right ] \left [ \begin{array}{c} \Delta x \\ \Delta y \\ \Delta s \\ \Delta \xi\end{array} \right ]= \left [ \begin{array}{l} r_c \\ r_b\\ -Xs \\ -(C-X)\xi \end{array} \right ] $$ where $r_b=-a\t x$, $r_c=-e+Qx-a y -s +\xi$. If the current solution is primal and dual feasible, then $r_b$ and $r_c$ are zero (within the numerical accuracy). By eliminating $\Delta s$, $\Delta \xi$ and consequently $\Delta x$ from the system we obtain an expression for $\Delta y$: $a\t(Q+D)^{-1}a\Delta y = r$, where $D=SX^{-1}+\Xi (C-X)^{-1}$ and $r$ is a right hand side that depends on $(Q+D)^{-1}$ and other parameters of the system. Solving for $\Delta y$ we substitute it back to find $\Delta x$, $\Delta s$ and $\Delta \xi$. The maximum possible step length is determined by computing $\alpha\leq 1$ such that $0 \leq x+\alpha \Delta x\leq c$, $0\leq s+\alpha\Delta s$ and $0\leq \xi +\alpha\Delta \xi$. To compute the corrector step, we set $dx=\Delta x$, $ds=\Delta s$ and $d\xi=\Delta \xi$ and $\hat \mu=(x+dx)\t(s+ds)+(c-x-dx)\t (\xi+d\xi)$ (from the predictor step) and compute new $(\Delta x, \Delta y, \Delta s, \Delta \xi)$, satisfying $$ \left [ \begin{array}{cccc} -Q &a & I & -I \\ a\t & 0 & 0 & 0\\ S & 0 & X & 0 \\ -\Xi & 0 & 0 & (C-X)\end{array} \right ] \left [ \begin{array}{c} \Delta x \\ \Delta y \\ \Delta s \\ \Delta \xi\end{array} \right ]= \left [ \begin{array}{l} r_c \\ r_b\\\sigma \mu -dXds -Xs \\ \sigma \mu + dXd\xi-(C-X)\xi \end{array} \right ] $$ where $\sigma$ is defined by $$ \sigma=\left ( \frac{\hat \mu}{\mu}\right ) ^3. $$ We solve this system similarly to the system for the predictor step, compute the largest possible step (but actually take 99$\%$ of that step to avoid hitting the boundaries of the feasible region or else the new solution would not be in the interior), and update the current solution. The stopping criteria is formed by checking the duality gap and the primal and dual feasibility against a predetermined tolerance. If these conditions are still not met, we compute a new value for the parameter $\mu$ and repeat the iteration. This algorithm converges to an optimal solutions from any strictly interior starting point (a point that lies inside all inequality constraints). In theory, it takes $O(n\ln (1/\e))$ iterations to converge, where $\e$ is the relative accuracy. However, in practice, an interior point method rarely takes more than $50$ iterations, regardless of the problem's size. The most time consuming operation on every step is obtaining a vector of the form $u=(Q+D)^{-1}w$ (e.g., during the computation of the predictor step such operation is done twice - once during computation of the right hand side vector $r$ and once during computation of $a\t (Q+D)^{-1}a$). Since $Q+D$ is a dense $n\times n$, symmetric positive definite matrix, then in general obtaining the vector $u$ requires $O(n^3)$ operations. Typically this can be done by either computing the inverse or factorizing\footnote{ Note that since $D$ and $Q$ are the same for both the predictor and the corrector steps, we need to compute the inverse or factorize $D+Q$ only once per every iteration.} $Q+D$. The main point of the next section is to show that if $Q$ can be represented as $Q=VV\t$, where $V$ is $n\times k$ matrix (where $k<