Can I read To Each Optimizer a Norm, To Each Norm its Generalization on EtoBox?

To Each Optimizer a Norm, To Each Norm its Generalization by Vaswani, Sharan; Babanezhad, Reza; Gallego-Posada, Jose; Mishkin, Aaron; Lacoste-Julien, Simon; Roux, Nicolas Le is a scholarly article available to read on EtoBox.

What is To Each Optimizer a Norm, To Each Norm its Generalization about?

We study the implicit regularization of optimization methods for linear models interpolating the training data in the under-parametrized and over-parametrized regimes. Since it is difficult to determine whether an optimizer converges to solutions that minimize a known norm, we flip the problem and investigate what is the corresponding norm minimized by an interpolating solution. Using this reasoning, we prove that for over-parameterized linear regression, projections onto linear spans can be used to move between different interpolating solutions. For under-parameterized linear classification, we prove that for any linear classifier separating the data, there exists a family of quadratic norms ||.||_P such that the classifier's direction is the same as that of the maximum P-margin solution. For linear classification, we argue that analyzing convergence to the standard maximum l2-margin is arbitrary and show that minimizing the norm induced by the data results in better generalization. Furthermore, for over-parameterized linear classification, projections onto the data-span enable us to use techniques from the under-parameterized setting. On the empirical side, we propose techniques

Author

Vaswani, Sharan; Babanezhad, Reza; Gallego-Posada, Jose; Mishkin, Aaron; Lacoste-Julien, Simon; Roux, Nicolas Le

Published

2020

Language

EN