ridge-regression-requires-od-squared-hidden-space

Summary

If a transformer is asked to compute ridge regression by updating a full inverse matrix step by step, it must keep working with d-by-d matrices at every step, so its internal memory scales with the square of the model's dimension. That makes it far more memory-hungry than the simpler alternative of walking through data points one at a time with a gradient update, which only needs space proportional to the number of points plus the dimension. In practice, this means the architectural choice of algorithm directly determines whether a given transformer can fit the task at all as dimensions grow.