Π-ORFit: One-Pass Learning with Bregman Projection

Abstract

This paper delves into the problem of one-pass learning, where the objective is to train a model on each datapoint in a stream while maintaining performance on past data without retraining on them. An existing approach to this problem in the context of overparameterized (underdetermined) models is Orthogonal Recursive Fitting (ORFit), which fits every new data point while maintaining predictions on previous datapoints by ensuring that parameter updates are orthogonal to the directions that are critical for past data (i.e., the direction of gradient of the model output with respect to the parameters, for those data). For overparameterized linear models, when initialized at zero, ORFit obtains the parameter vector that perfectly fits the data and has the minimum ℓ2 -norm, among the infinitely many perfectly fitting parameter vectors. To generalize this and gain control over the selection of desired parameters, in this paper, we introduce Projected Orthogonal Recursive Fitting (Π-ORFit). We begin by characterizing all parameters that can precisely fit data in general vector-output linear models, employing a formalism based on nullspace projector matrices. This framework yields an alternative derivation of ORFit. Building on this, we further extend ORFit to learn a desired parameter by incorporating a Bregman projection into the update rule. Importantly, we show that the resulting parameter minimizes the potential function that defines the Bregman projection at each update step, enabling the selection of a desired parameter among the (infinitely many) candidates consistent with the data. We provide numerical experiments that validate our analytical findings and underscore the practical significance of this generalized approach.