One-Pass Learning via Bridging Orthogonal Gradient Descent and Recursive Least-Squares

Our main contributions can be summarized as follows.

• •

  We develop Orthogonal Recursive Fitting (ORFit), an algorithm for one-pass learning in the overparameterized setting which fits new data on the fly while updating the parameters in a direction that causes the least change to the predictions on previous data. Our algorithm uses memory efficiently by exploiting the structure of the streaming data via incremental principal component analysis (IPCA) to extract the essential information for the update. (§III)

• •

  Through the proposed method, we establish an interesting connection between two different algorithms from adaptive filtering and machine learning, namely, the recursive least-squares (RLS) algorithm and the orthogonal gradient descent (OGD). We further theoretically characterize the behavior of the proposed method in the linear overparameterized setting. (§IV)

• •

  We demonstrate the practicality of our approach and corroborate our theoretical findings through various experiments. (§V)

• •

  We discuss further extensions to overparameterized nonlinear models, relevant for deep learning. (§VI)

One-pass learning shares some similarities with other settings that deal with streaming data such as online learning and incremental learning. While these terms are often inconsistently defined in the literature, one may distinguish them based on whether we learn a single datapoint or a batch of data at a time [14]. Although both of these approaches learn from streaming data, they typically assume that data is arriving from the same distribution. Compared to these settings, one-pass learning requires explicit efforts to not alter the predictions on the previous data while learning new data. Thus, it aims to preserve the predictions even when the new data comes from a different distribution. Another related setting is continual learning where batches of data from different tasks are sequentially learned [6].

Let $f(x;w)\in\mathbb{R}$ be a model that the agent is trying to fit, where $x\in\mathcal{X}\subset\mathbb{R}^{d}$ is the input and $w\in\mathbb{R}^{p}$ is the parameter (weight) vector. Consider a sequentially arriving stream of data $\{(x_{k},y_{k})\}_{k=1}^{K}$ where $x_{k}\in\mathcal{X}$ and $y_{k}\in\mathcal{Y}\subset\mathbb{R}$. In overparameterized models, we have $p\geq K$ (and often $p\gg K$). For a loss function $\ell(\cdot,\cdot)$, let $f_{k}(w)\vcentcolon=f(x_{k};w)$ and $\ell_{k}(w)\vcentcolon=\ell(y_{k},f_{k}(w))$. Then, one-pass learning considers the setting where, given an initial parameter $w_{0}\in\mathbb{R}^{p}$, it updates the parameter $w_{i}\in\mathbb{R}^{p}$ after the new data $(x_{i},y_{i})$ arrived without revisiting previous datapoints $\{(x_{k},y_{k})\}_{k=1}^{i-1}$.

For concreteness, we first focus on a linear overparameterized model $f(x;w)=w^{\top}x$ with $p=d$. We then discuss the extension of the results to nonlinear models (e.g. overparameterized architectures in deep learning) in Section VI.

Before introducing our algorithm and the results, we briefly review two related algorithms capable of one-pass learning, proposed in two different literatures.

First, we briefly review recursive least-squares (RLS) from the control/estimation theory literature (refer to [17] for details). At every step $i$, RLS aims to find a parameter vector that solves the following regularized least-squares problem:

where $\lVert x\rVert_{\Pi}\vcentcolon=\sqrt{x^{\top}\Pi x}$ for a $p\times p$ positive-definite matrix $\Pi$ and $w_{0}$ is an initial parameter estimate. Note that the system is underdetermined/overparameterized, and the regularization term in  (1) is necessary for the solution to be uniquely defined. While there is a closed-form solution for (1) given by $w^{(RLS)}_{i}=(\Pi+X_{i}^{\top}X_{i})^{-1}(X_{i}^{\top}Y_{i}+\Pi w_{0})$ with $X_{i}=[x_{1}\;x_{2}\dots\;x_{i}]^{\top}$ and $Y_{i}=[y_{1}\;y_{2}\dots\;y_{i}]^{\top}$, computing the solution directly requires storing all the previous data as well as recomputing the inverse of the covariance matrix for every new datapoint. RLS bypasses this issue by computing the new solution $w^{(RLS)}_{i}$ of (1) recursively from $w^{(RLS)}_{i-1}$ and $(x_{i},y_{i})$.

We elaborate the algorithm more formally for a general version of RLS called exponentially-weighted recursive least-squares (EW-RLS) [17]. Consider the following problem:

with a forgetting factor $0<\lambda\leq 1$. Note that this reduces to the problem of the vanilla RLS (1) when $\lambda=1$. The exact solution of it is recursively updated as follows:

with $w^{(RLS)}_{0}=w_{0}$ and $P_{0}=\Pi^{-1}$. Here, $P_{i}$ can be alternatively written as $P_{i}=[\Pi+X_{i}^{\top}\Lambda_{i}X_{i}]^{-1}$ where $\Lambda_{i}=\mathrm{diag}(\lambda^{-1},\lambda^{-2},\dots,\lambda^{-i})$.

An algorithm called orthogonal gradient descent (OGD) [7] has been recently proposed in the context of machine learning for a different but related problem. More specifically, [7] considers a continual learning setting in which tasks $\{T_{1},T_{2},\dots\}$ arrive sequentially, and each task consists of a set of datapoints. Continual learning can be understood as a “batch” version of one-pass learning. At a high level, when the $i$-th task $T_{i}$ arrives, OGD updates the parameter to fit new samples from $T_{i}$ in a way that causes minimal changes to the predictions for previous tasks $\{T_{k}\}_{k=1}^{i-1}$. The gradient of the model on a datapoint $x_{j}$ with respect to the parameter, $\nabla_{w}f(x_{j};w)$, is the direction in the parameter space that causes the most change to the prediction on that datapoint. Thus, moving orthogonal to this direction, locally, keeps the prediction unchanged, which is the main idea behind OGD. More formally, the update direction is computed via projecting the current gradient $g$ of the loss onto the subspace orthogonal to $\mathcal{G}\vcentcolon=\text{span}\{\bigcup_{k=1}^{i-1}\{\nabla_{w}f(x;w_{k})\}_{(x,y)\in T_{k}}\}$:

where $S$ is an orthogonal basis for $\mathcal{G}$ and $\textup{proj}_{v}(u)\vcentcolon=(u^{\top}v/\lVert v\rVert^{2})v=(vv^{\top}/\lVert v\rVert^{2})u$. The orthogonal basis $S$ is incrementally updated through the Gram-Schmidt procedure.

We start by considering OGD directly applied to the one-pass learning setting. By treating each task $T_{k}$ in the continual learning setting as consisting of a single datapoint, OGD will run multiple gradient descent steps on the single datapoint. While perfect fitting/interpolation is desired in often highly overparameterized models [5, 4], it will take many iterations for OGD to perfectly fit the datapoint. Instead, inspired by the recent trend in meta-learning, we consider a one-step learning scheme that only runs a single gradient step to interpolate the new datapoint. We first begin with the following result that serves as a building block for our algorithm design; see Appendix -A for a proof.

The main takeaway of Lemma 1 is that the predictions for the previous datapoints do not change when we update the model along the direction $\tilde{g}$. Hence, we may choose $\eta$ so that the updated parameter $w^{\prime}$ can perfectly fit the new datapoint, say $(x^{\prime},y^{\prime})$, as $y^{\prime}=w^{\prime\top}x^{\prime}=(w-\eta\tilde{g})^{\top}x^{\prime}$. Following this principle, a straightforward calculation yields the following update rule for $i\geq 1$:

where $S_{0}=\phi$, $w_{0}$ is the initial weight vector, and the optimal step size is chosen as

For intuition, we note that the optimal step size (6) is typically small for highly overparameterized models; there are many parameter vectors in the vicinity of the current solution that perfectly fit the new datapoint [2, 13, 1].

Another distinction between the update rule (5) and OGD lies in the update of the orthogonal basis $S_{i}$: OGD utilizes “fresher” gradient at the updated parameter $w_{i}$ by $S_{i}=S_{i-1}\bigcup\{\nabla f_{i}(w_{i})-\sum_{v\in S_{i-1}}\textup{proj}_{v}(\nabla f_{i}(w_{i}))\}$. Although the two bases actually span the same subspace for linear models, it turns out that ORFit in (5) leads to a natural generalization for nonlinear models; see Section VI for details.

Although the update rule (5) does not access previous datapoints, it still requires storing the orthogonal basis $S_{i}$, whose size grows linearly in the number of visited datapoints. This is not desirable in practice when one needs to train the model on a large dataset. We address this issue next.

In this section, we overcome the aforementioned memory issue by utilizing the structure of the streaming dataset. The main idea is to summarize the orthogonal basis $S$ using an incremental principal component analysis (IPCA) algorithm, known as the sequential Karhunen–Loeve (SKL) algorithm proposed in [12]. IPCA is a memory-efficient variant of PCA that enables sequential update for streaming/large datasets. Let us formally describe how IPCA incrementally summarizes the orthogonal basis.

Consider the orthogonal basis $S=\{v_{1},v_{2},\dots,v_{i}\}$ obtained by (5). Let the singular value decomposition (SVD) of $A=[v_{1}\;v_{2}\,\dots v_{i}]$ be $A=U\Sigma V^{\top}$. Here, the crucial information of the SVD is the left-singular vectors $\mathrm{col}(U)$ that forms an orthonormal basis for $\mathrm{span}(S)$. This information can be used to come up with a rank-$m$ approximation of $A$ by using the components corresponding to the top $m$ singular values.

Now suppose that the orthogonal basis $S$ is augmented with a newly projected gradient $v^{\prime}$ as in (5). We want to efficiently update $U$ for the new basis. Letting $u\vcentcolon=v^{\prime}/\lVert v^{\prime}\rVert$, the new basis matrix can be represented as:

where $\tilde{U}\tilde{\Sigma}\tilde{V}^{\top}$ is the SVD of $\begin{bmatrix}\Sigma&0\\ 0&u^{\top}v^{\prime}\end{bmatrix}$. Then, (8) is the SVD of the new basis matrix. Hence to update $U$, one can directly use the information from the previous iteration, namely $U$ and $\Sigma$. The important aspect here is that the update can be made without storing $V$ and without having to recompute the SVD of the new basis matrix. Finally, one can store only the top $m$ singular values in $\Sigma$ and their corresponding components in $U$. By repeatedly applying this IPCA algorithm in addition to (5), we obtain orthogonal recursive fitting (ORFit). See Algorithm 1 for the detailed procedure.

The main advantage of ORFit is its computational/memory efficiency. By only storing the top $m$ components, we can reduce the memory size from $O(ip)$ to $O(mp)$. Moverover, the additional computational overhead to perform IPCA as well as the total time complexity of ORFit at each step is $O(m^{2}(p+m))$. Hence, ORFit can reduce both the computation and the memory complexity by appropriately choosing $m$.

It turns out ORFit corresponds to an extreme case of the well-known RLS method, as formally described in the following result; see Appendix -B for a proof.

One notable aspect of ORFit is that it bridges the two seemingly distinct algorithms OGD and RLS through Proposition 2. The connection provides us new insights into understanding the behavior of our proposed method, as we discuss next.

Before presenting our main result, we first provide some intuitions. To understand the behavior of ORFit, let us first recall that the EW-RLS update rule (3) is the solution to the optimization problem (2). In light of Proposition 2, one might be tempted to claim that ORFit in (5) solves (2) with $\lambda=0$ and $\Pi=I$. However, (2) is not well-defined for $\lambda=0$.

Nevertheless, intuitively one can regard ORFit as solving (2) in the limit of $\lambda\to 0^{+}$. Then, for sufficiently small $\lambda>0$, the first term in the objective of (2) outweighs the second term, which suggests that, in the overparameterized case, the solution should enforce $y_{k}\approx w^{\top}x_{k}$ for all $k=1,2,\dots,i$, while minimizing $\lVert w-w_{0}\rVert^{2}$. In the following theorem, we formalize this intuition and characterize the solution of ORFit; see Appendix -C for a proof.

It is known that, for a linear overparameterized model, in the standard multi-pass learning setting over the dataset $\{(x_{k},y_{k})\}_{k=1}^{i}$, as the number of iterations goes to infinity, the iterates of stochastic gradient descent (SGD) initialized at $w_{0}$ with a sufficiently small step size converge to the solution of problem (9) (see, e.g., Proposition 1 in [3]). Thus, ORFit with just an epoch of training finds the solution that SGD in the limit of infinite number of iterations converges to.

In this experiment, we demonstrate the effectiveness of our proposed method in the memory-restricted setting, in which 100 datapoints are sequentially learned while we are only allowed to store up to $10$ basis vectors. For comparison, we consider the following baselines: (1) Greedy scheme: outputs only the label of the most recently learned datapoint, regardless of the input, as an extreme case of forgetting. (2) One-Step SGD: employs the one-step learning scheme with the step size in (6) but with empty orthogonal basis. (3) ORFit-random: ORFit that keeps $10$ randomly chosen basis vectors after each iteration instead of performing IPCA. (4) ORFit-latest: ORFit that keeps the latest $10$ basis vectors after each iteration instead of performing IPCA.

We first compared the test errors of the proposed method and the baselines. The test errors are measured with the test dataset that consists of $1032$ images of digit ‘$2$’ in the MNIST test set of which each is rotated with a random angle in $[0,\pi]$. As shown in Fig. 2(a), ORFit outperforms other baselines after a sufficient number of training steps. Notably, ORFit results in lower variances over the $10$ independent runs with different initialization.

Next, we compared the degrees of forgetting for the proposed method and the baselines by keeping track of the prediction errors of a training datapoint throughout the training. As shown in Fig. 2(b), ORFit successfully keeps the prediction error low throughout the training. This is in stark contrast with other methods for which the prediction error quickly increases as other datapoints are learned.

In this experiment, we follow the setup in Section V-A except that this time, we do not impose any memory restrictions. For comparison, we run vanilla SGD with a fixed step size $10^{-5}$. Vanilla SGD makes multiple passes over the entire dataset for $1000$ epochs.

Reported in Fig. 3(a) are the training and test errors of vanilla SGD, One-Step SGD, and ORFit. Note that both SGD and ORFit learn the training dataset perfectly with almost zero training error. Moreover, after the training is finished, SGD and ORFit achieve similar test errors, corroborating Theorem 3.

In addition, Fig. 3(b) shows the prediction error of the $11$-th training datapoint throughout the training (analogous to Fig. 2(b)). Note that ORFit perfectly preserves the prediction error of the sample, while One-Step SGD quickly deteriorates it. This result demonstrates the effectiveness of the orthogonal update in ORFit for one-pass learning.