2019

Training Neural Networks for and by Interpolation

Berrada, Leonard, Zisserman, Andrew, Kumar, M. Pawan

Understand

In modern supervised learning, many deep neural networks are able to interpolate the data: the empirical loss can be driven to near zero on all samples simultaneously.

In this work, we explicitly exploit this interpolation property for the design of a new optimization algorithm for deep learning, which we term Adaptive Learning-rates for Interpolation with Gradients (ALI-G).
ALI-G retains the two main advantages of Stochastic Gradient Descent (SGD), which are (i) a low computational cost per iteration and (ii) good generalization performance in practice.
At each iteration, ALI-G exploits the interpolation property to compute an adaptive learning-rate in closed form.

Built on

A stochastic approximation method
Robbins, H. and Monro, S · 1951
Earlier work this paper cites.
An algorithm for quadratic programming
Frank, M. and Wolfe, P · 1956
Earlier work this paper cites.
Minimization of unsmooth functionals
Polyak, B. T · 1969
Earlier work this paper cites.
Minimization methods for non-differentiable functions
Shor, N. Z · 1985
Earlier work this paper cites.
A generalized subgradient method with relaxation step
Brännlund, U · 1995
Earlier work this paper cites.
Adaptive subgradient methods for online learning and stochastic optimization
Duchi, J., Hazan, E., and Singer, Y · 2011
Earlier work this paper cites.
Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude
Tieleman, T. and Hinton, G · 2012
Earlier work this paper cites.
ADADELTA: an adaptive learning rate method
Zeiler, M · 2012
Earlier work this paper cites.
Block-coordinate Frank-Wolfe optimization for structural SVMs
Lacoste-Julien, S. and Jaggi, M · 2013
Earlier work this paper cites.
No more pesky learning rates
Schaul, T., Zhang, S., and LeCun, Y · 2013
Earlier work this paper cites.
Gradient methods for convex minimization: better rates under weaker conditions
Zhang, H. and Yin, W · 2013
Earlier work this paper cites.
TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems , 2015
Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., Corrado, G., Davis, A., Dean, J., Devin, M., Ghemawat, S., Goodfellow, I., Harp, A., Irving, G., Isard, M., Jia, Y., Jozefowicz, R., Kaiser, L., Kudlur, M., Levenberg, J., Man, D., Monga, R., Moore, S., Murray, D., Olah, C., Schuster, M., Shlens, J., Steiner, B., Sutskever, I., Talwar, K., Tucker, P., Vanhoucke, V., Vasudevan, V., Vi, F., Vinyals, O., Warden, P., Wattenberg, M., Wicke, M., Yu, Y., and Zheng, X · 2015
Earlier work this paper cites.
A large annotated corpus for learning natural language inference
Bowman, S. R., Angeli, G., Potts, C., and Manning, C. D · 2015
Earlier work this paper cites.
Convex optimization: Algorithms and complexity
Bubeck, S · 2015
Earlier work this paper cites.
Adam: A method for stochastic optimization
Kingma, D. P. and Ba, J · 2015
Earlier work this paper cites.
Optimizing neural networks with Kronecker-factored approximate curvature
Martens, J. and Grosse, R · 2015
Earlier work this paper cites.
Scale-free algorithms for online linear optimization
Orabona, F. and Pál, D · 2015
Earlier work this paper cites.
Hybrid computing using a neural network with dynamic external memory
Graves, A., Wayne, G., Reynolds, M., Harley, T., Danihelka, I., Grabska-Barwińska, A., Colmenarejo, S. G., Grefenstette, E., Ramalho, T., Agapiou, J., Badia, A. P., Hermann, K. M., Zwols, Y., Ostrovski, G., Cain, A., King, H., Summerfield, C., Blunsom, P., Kavukcuoglu, K., and Hassabis, D · 2016
Earlier work this paper cites.
Deep residual learning for image recognition
He, K., Zhang, X., Ren, S., and Sun, J · 2016
Earlier work this paper cites.

Similar

Loss functions for top-k error: Analysis and insights
Lapin, M., Hein, M., and Schiele, B · 2016
Cited alongside, same era.
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
Shalev-Shwartz, S. and Zhang, T · 2016
Cited alongside, same era.
Barzilai-borwein step size for stochastic gradient descent
Tan, C., Ma, S., Dai, Y.-H., and Qian, Y · 2016
Cited alongside, same era.
Wide residual networks
Zagoruyko, S. and Komodakis, N · 2016
Cited alongside, same era.
Supervised learning of universal sentence representations from natural language inference data
Conneau, A., Kiela, D., Schwenk, H., Barrault, L., and Bordes, A · 2017
Cited alongside, same era.
Adabatch: Efficient gradient aggregation rules for sequential and parallel stochastic gradient methods
Défossez, A. and Bach, F · 2017
Cited alongside, same era.
Densely connected convolutional networks
Huang, G., Liu, Z., Weinberger, K. Q., and van der Maaten, L · 2017
Cited alongside, same era.
Online to offline conversions, universality and adaptive minibatch sizes
Levy, K · 2017
Cited alongside, same era.
A unified optimization view on generalized matching pursuit and frank-wolfe
Locatello, F., Khanna, R., Tschannen, M., and Jaggi, M · 2017
Cited alongside, same era.
Variants of rmsprop and adagrad with logarithmic regret bounds
Mukkamala, M. C. and Hein, M · 2017
Cited alongside, same era.
Automatic differentiation in pytorch
Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., DeVito, Z., Lin, Z., Desmaison, A., Antiga, L., and Lerer, A · 2017
Cited alongside, same era.
The marginal value of adaptive gradient methods in machine learning
Wilson, A. C., Roelofs, R., Stern, M., Srebro, N., and Recht, B · 2017
Cited alongside, same era.

Then

L4: Practical loss-based stepsize adaptation for deep learning
Rolinek, M. and Martius, G · 2018
Later among the works it cites.
Adafactor: Adaptive learning rates with sublinear memory cost
Shazeer, N. and Stern, M · 2018
Later among the works it cites.
WNGrad: Learn the learning rate in gradient descent
Wu, X., Ward, R., and Bottou, L · 2018
Later among the works it cites.
Adaptive methods for nonconvex optimization
Zaheer, M., Reddi, S., Sachan, D., Kale, S., and Kumar, S · 2018
Later among the works it cites.
Stochastic (approximate) proximal point methods: Convergence, optimality, and adaptivity
Asi, H. and Duchi, J. C · 2019
Closest in time.
Deep Frank-Wolfe for neural network optimization
Berrada, L., Zisserman, A., and Kumar, M. P · 2019
Closest in time.
On the convergence of a class of adam-type algorithms for non-convex optimization
Chen, X., Liu, S., Sun, R., and Hong, M · 2019
Closest in time.
Revisiting the polyak step size
Hazan, E. and Kakade, S · 2019
Closest in time.
Small steps and giant leaps: Minimal newton solvers for deep learning
Henriques, J. F., Ehrhardt, S., Albanie, S., and Vedaldi, A · 2019
Closest in time.
On the convergence of stochastic gradient descent with adaptive stepsizes
Li, X. and Orabona, F · 2019
Closest in time.
Accelerating sgd with momentum for over-parameterized learning
Liu, C. and Belkin, M · 2019
Closest in time.
On the variance of the adaptive learning rate and beyond
Liu, L., Jiang, H., He, P., Chen, W., Liu, X., Gao, J., and Han, J · 2019
Closest in time.
Fixing weight decay regularization in adam
Loshchilov, I. and Hutter, F · 2019
Closest in time.
Adaptive gradient methods with dynamic bound of learning rate
Luo, L., Xiong, Y., Liu, Y., and Sun, X · 2019
Closest in time.
Stochastic gradient descent with polyak’s learning rate
Oberman, A. M. and Prazeres, M · 2019
Closest in time.
DeepOBS: A deep learning optimizer benchmark suite
Schneider, F., Balles, L., and Hennig, P · 2019
Closest in time.
Sgd converges to global minimum in deep learning via star-convex path
Zhou, Y., Yang, J., Zhang, H., Liang, Y., and Tarokh, V · 2019
Closest in time.
Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence
Loizou, N., Vaswani, S., Laradji, I., and Lacoste-Julien, S · 2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…