Pseudo-inverses and SGD

tags: [ mathematics , gradient_descent ]

• The Moore-Penrose pseudo inverse (which is often just called the pseudoinverse) is just a choice of multiple solutions that leads to a minimum norm solution
  • \(\hat{\beta} = X^+ Y\)
  • An obvious consequence, is that ridge regression is not the same as the pseudoinverse solution, even though they’re obviously very similar
  • my feeling is that, for a particular choice of penalty, the solution should be same (since you should be able to reframe the optimization into
    • \(\min ||\beta||_2 \text{ s.t. } ||Y - X \beta ||_2 \leq t\)
  • part of me is a little confused: if you can just define this pseudoinverse, then how come we don’t use this estimator more often? clearly it must not have good properties?
• thanks to this tweet, realize there’s a section in (Zhang et al. ⊕2019Zhang, Chiyuan, Benjamin Recht, Samy Bengio, Moritz Hardt, and Oriol Vinyals. 2019. “Understanding deep learning requires rethinking generalization.” In 5th International Conference on Learning Representations, Iclr 2017 - Conference Track Proceedings. University of California, Berkeley, Berkeley, United States.) [[rethinking-generalization]] that relates to (Bartlett et al. ⊕2020Bartlett, Peter L, Philip M Long, Gábor Lugosi, and Alexander Tsigler. 2020. “Benign overfitting in linear regression.” Proceedings of the National Academy of Sciences of the United States of America vol. 80 (April): 201907378.) [[benign-overfitting-in-linear-regression]], in that they show that the SGD solution is the same as the minimum-norm (pseudo-inverse)
  • the curvature of the minimum (LS) solutions don’t actually tell you anything (they’re the same)
  • “Unfortunately, this notion of minimum norm is not predictive of generalization performance. For example, returning to the MNIST example, the \(l_2\)-norm of the minimum norm solution with no preprocessing is approximately 220. With wavelet preprocessing, the norm jumps to 390. Yet the test error drops by a factor of 2. So while this minimum-norm intuition may provide some guidance to new algorithm design, it is only a very small piece of the generalization story.”
    • but this is changing the data, so I don’t think this comparison really matters – it’s not saying across all kinds of models, we should be minimizing the norm. it’s just saying that we prefer models with minimum norm
    • interesting that this works well for MNIST/CIFAR10
  • there must be something in all of this: on page 29 of slides, they show that SGD converges to min-norm interpolating solution with respect to a certain kernel (so the norm is on the coefficients for each kernel)
    • as pointed out, this is very different to the benign paper, as this result is data-independent (it’s just a feature of SGD)