  While deep neural networks are capable of achieving state-of-the-art
performance in various domains, their training typically requires iterating for
many passes over the dataset. However, due to computational and memory
constraints and potential privacy concerns, storing and accessing all the data
is impractical in many real-world scenarios where the data arrives in a stream.
In this paper, we investigate the problem of one-pass learning, in which a
model is trained on sequentially arriving data without retraining on previous
datapoints. Motivated by the increasing use of overparameterized models, we
develop Orthogonal Recursive Fitting (ORFit), an algorithm for one-pass
learning which seeks to perfectly fit every new datapoint while changing the
parameters in a direction that causes the least change to the predictions on
previous datapoints. By doing so, we bridge two seemingly distinct algorithms
in adaptive filtering and machine learning, namely the recursive least-squares
(RLS) algorithm and orthogonal gradient descent (OGD). Our algorithm uses the
memory efficiently by exploiting the structure of the streaming data via an
incremental principal component analysis (IPCA). Further, we show that, for
overparameterized linear models, the parameter vector obtained by our algorithm
is what stochastic gradient descent (SGD) would converge to in the standard
multi-pass setting. Finally, we generalize the results to the nonlinear setting
for highly overparameterized models, relevant for deep learning. Our
experiments show the effectiveness of the proposed method compared to the
baselines.
