Reza Babanezhad Harikandeh

Mark Schmidt

2021-02-18

ArXiv (preprint)

doi.org

An Analysis of the Adaptation Speed of Causal Models

Rémi LE PRIOL

Yoshua Bengio

2021-01-01

AISTATS (published)

proceedings.mlr.press

To Each Optimizer a Norm, To Each Norm its Generalization

Sharan Vaswani

Jose Gallego

Aaron Mishkin

Nicolas Le Roux

We study the implicit regularization of optimization methods for linear models interpolating the training data in the under-parametrized and… (see more) 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 to bias optimizers towards better generalizing solutions, improving their test performance. We validate our theoretical results via synthetic experiments, and use the neural tangent kernel to handle non-linear models.

2020-06-11

ArXiv (preprint)

An Analysis of the Adaptation Speed of Causal Models

Rémi LE PRIOL

Yoshua Bengio

We consider the problem of discovering the causal process that generated a collection of datasets. We assume that all these datasets were ge… (see more)nerated by unknown sparse interventions on a structural causal model (SCM)

2020-05-18

ArXiv (preprint)

Reducing the variance in online optimization by transporting past gradients

Sébastien M. R. Arnold

Pierre-Antoine Manzagol

Ioannis Mitliagkas

Nicolas Le Roux

Most stochastic optimization methods use gradients once before discarding them. While variance reduction methods have shown that reusing pas… (see more)t gradients can be beneficial when there is a finite number of datapoints, they do not easily extend to the online setting. One issue is the staleness due to using past gradients. We propose to correct this staleness using the idea of implicit gradient transport (IGT) which transforms gradients computed at previous iterates into gradients evaluated at the current iterate without using the Hessian explicitly. In addition to reducing the variance and bias of our updates over time, IGT can be used as a drop-in replacement for the gradient estimate in a number of well-understood methods such as heavy ball or Adam. We show experimentally that it achieves state-of-the-art results on a wide range of architectures and benchmarks. Additionally, the IGT gradient estimator yields the optimal asymptotic convergence rate for online stochastic optimization in the restricted setting where the Hessians of all component functions are equal.

Online variance-reducing optimization

Nicolas Le Roux