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

By Youngjae Min, Kwangjun Ahn, Navid Azizan. 2022

24 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Hang Su
2. Jun Zhu
3. Liyuan Wang
4. Xingxing Zhang
5. Youngjae Min
6. Hyo-Sang Shin
7. Namhoon Cho
8. Navid Azizan

In Computational Mechanics

1. Youngjae Min
2. Hyo-Sang Shin
3. Namhoon Cho
4. Jun Zhu
5. Navid Azizan
6. Hang Su

In Optimization & Training

1. Youngjae Min
2. Hyo-Sang Shin
3. Namhoon Cho
4. Liyuan Wang
5. Jun Zhu
6. Navid Azizan
7. Hang Su
8. Xingxing Zhang

Citations in the corpus

• A Comprehensive Survey of Continual Learning: Theory, Method and Application (2023, background): “Recent work has shown that the one-pass performance of visual classification can be largely improved by experience replay of hard examples [297] or orthogonal gradient projection [298].”
• Π-ORFit: One-Pass Learning with Bregman Projection (2024, methodology): “Notably, [1] established a link between ORFit and the discrete-time RLS method in the case of linear prediction models.”
• SketchOGD: Memory-Efficient Continual Learning (2023, unknown): “[25] for the special setting of one-pass learning.”