 In the setting of supervised learning with the square loss function, the intent is to minimize the empirical loss,

Let formula_2 be the formula_28 data matrix and formula_3 is the formula_30 matrix of target values after the arrival of the first formula_31 data points.Assuming that the covariance matrix formula_32 is invertible (otherwise it is preferential to proceed in a similar fashion with Tikhonov regularization), the best solution formula_33 to the linear least squares problem is given by

Now, calculating the covariance matrix formula_35 takes time formula_36, inverting the formula_37 matrix takes time formula_38, while the rest of the multiplication takes time formula_39, giving a total time of formula_40.When there are formula_41 total points in the dataset, to recompute the solution after the arrival of every datapoint formula_42, the naive approach will have a total complexity formula_43.