2019

Modelling the influence of data structure on learning in neural networks: the hidden manifold model

Goldt, Sebastian, Mézard, Marc, Krzakala, Florent et al.

Understand

Understanding the reasons for the success of deep neural networks trained using stochastic gradient-based methods is a key open problem for the nascent theory of deep learning.

The types of data where these networks are most successful, such as images or sequences of speech, are characterised by intricate correlations.
Yet, most theoretical work on neural networks does not explicitly model training data, or assumes that elements of each data sample are drawn independently from some factorised probability distribution.
These approaches are thus by construction blind to the correlation structure of real-world data sets and their impact on learning in neural networks.

Built on

P. Rotondo, M. Cosentino Lagomarsino, and M. Gherardi, “Counting the learnable functions of structured data,” preprint (2019), arXiv:1903.12021
Original
1903
Earlier work this paper cites.
S. Spigler, M. Geiger, and M. Wyart, “Asymptotic learning curves of kernel methods: empirical data v.s. Teacher-Student paradigm,” prerint (2019), arXiv:1905.10843
Original
1905
Earlier work this paper cites.
S. Mei and A. Montanari, “The generalization error of random features regression: Precise asymptotics and double descent curve,” (2019), arXiv:1908.05355
Original
1908
Earlier work this paper cites.
A. Montanari, F. Ruan, Y. Sohn, and J. Yan, “The generalization error of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime,” (2019), arXiv:1911.01544
Original
1911
Earlier work this paper cites.
T. Karras, S. Laine, M. Aittala, J. Hellsten, J. Lehtinen, and T. Aila, “Analyzing and improving the image quality of stylegan,” (2019), arXiv:1912.04958
Original
1912
Earlier work this paper cites.
I. S Reed, A class of multiple-error-correcting codes and the decoding scheme , Tech. Rep. (Massachusetts Inst of Tech Lexington Lincoln Lab, 1953)
1953
Earlier work this paper cites.
D.E. Muller, “Application of boolean algebra to switching circuit design and to error detection,” Transactions of the IRE professional group on electronic computers 3
1954
Earlier work this paper cites.
F. Rosenblatt, Principles of Neurodynamics (Spartan, 1962)
1962
Earlier work this paper cites.
T.M. Cover, “Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition,” IEEE Transactions on Electronic Computers EC-14
1965
Earlier work this paper cites.
V.A. Marchenko and L.A. Pastur, “Distribution of eigenvalues for some sets of random matrices,” Matematicheskii Sbornik 114
1967
Earlier work this paper cites.
P. Grassberger and I. Procaccia, “Measuring the strangeness of strange attractors,” Physica D: Nonlinear Phenomena 9
1983
Earlier work this paper cites.
F.X. Yu, A.T. Suresh, K.M. Choromanski, D.N. Holtmann-Rice, and S. Kumar, “Orthogonal random features,” in Advances in Neural Information Processing Systems (2016) pp. 1975–1983
1983
Earlier work this paper cites.
B. Derrida, E. Gardner, and A. Zippelius, “An exactly solvable asymmetric neural network model,” EPL (Europhysics Letters) 4
1987
Earlier work this paper cites.
E. Gardner and B. Derrida, “Three unfinished works on the optimal storage capacity of networks,” Journal of Physics A: Mathematical and General 22
1989
Earlier work this paper cites.
W. Kinzel and P. Ruján, “Improving a Network Generalization Ability by Selecting Examples,” EPL (Europhysics Letters) 13
1990
Earlier work this paper cites.
H. S. Seung, H. Sompolinsky, and N. Tishby, “Statistical mechanics of learning from examples,” Physical Review A 45
1992
Earlier work this paper cites.
T.L.H. Watkin, A. Rau, and M. Biehl, “The statistical mechanics of learning a rule,” Reviews of Modern Physics 65
1993
Earlier work this paper cites.
M. Biehl and H. Schwarze, “Learning by on-line gradient descent,” J. Phys. A. Math. Gen. 28
1995
Earlier work this paper cites.
P. Riegler and M. Biehl, “On-line backpropagation in two-layered neural networks,” Journal of Physics A: Mathematical and General 28
1995
Earlier work this paper cites.
M. Biehl, P. Riegler, and C. Wöhler, “Transient dynamics of on-line learning in two-layered neural networks,” Journal of Physics A: Mathematical and General 29
1996
Earlier work this paper cites.
D. Saad and S.A. Solla, “Learning with Noise and Regularizers Multilayer Neural Networks,” in Advances in Neural Information Processing Systems 9 (1997) pp. 260–266
1997
Earlier work this paper cites.
Y. LeCun and C. Cortes, “The MNIST database of handwritten digits,” (1998)
1998
Earlier work this paper cites.
M. Rattray, D. Saad, and S.-I. Amari, “Natural Gradient Descent for On-Line Learning,” Physical Review Letters 81
1998
Earlier work this paper cites.
V. Vapnik, “Statistical learning theory,” New York , 156–160 (1998)
1998
Earlier work this paper cites.
A.C.C. Coolen, D. Saad, and Y.-S. Xiong, “On-line learning from restricted training sets in multilayer neural networks,” EPL (Europhysics Letters) 51
2000
Earlier work this paper cites.
A.C.C. Coolen and D. Saad, “Dynamics of learning with restricted training sets,” Physical Review E 62
2000
Earlier work this paper cites.
A. Engel and C. Van den Broeck, Statistical Mechanics of Learning (Cambridge University Press, 2001)
2001
Earlier work this paper cites.
M.E.A. Seddik, C. Louart, M. Tamaazousti, and R. Couillet, “Random matrix theory proves that deep learning representations of gan-data behave as gaussian mixtures,” (2020), arXiv:2001.08370
Original
2001
Earlier work this paper cites.

Similar

J.A. Costa and A.O. Hero, “Learning intrinsic dimension and intrinsic entropy of high-dimensional datasets,” in 2004 12th European Signal Processing Conference (2004) pp. 369–372
2004
Cited alongside, same era.
E. Levina and P.J. Bickel, “Maximum likelihood estimation of intrinsic dimension,” in Advances in Neural Information Processing Systems 17 (2004)
2004
Cited alongside, same era.
W. Hachem, P. Loubaton, and J. Najim, “Deterministic equivalents for certain functionals of large random matrices,” Ann. Appl. Probab. 17
2007
Cited alongside, same era.
A. Rahimi and B. Recht, “Random features for large-scale kernel machines,” in Advances in neural information processing systems (2008) pp. 1177–1184
2008
Cited alongside, same era.
Alex Krizhevsky, Geoffrey Hinton, et al. , “Learning multiple layers of features from tiny images,” (2009)
2009
Cited alongside, same era.
A. Rahimi and B. Recht, “Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning,” in Advances in neural information processing systems (2009) pp. 1313–1320
2009
Cited alongside, same era.
D. Saad, On-line learning in neural networks , Vol. 17 (Cambridge University Press, 2009)
2009
Cited alongside, same era.
A. Krizhevsky, I. Sutskever, and G.E. Hinton, “Imagenet classification with deep convolutional neural networks,” in Advances in neural information processing systems (2012) pp. 1097–1105
2012
Cited alongside, same era.
M. Mohri, A. Rostamizadeh, and A. Talwalkar, Foundations of Machine Learning (MIT Press, 2012)
2012
Cited alongside, same era.
D. Michelsanti and Z. Tan, “Conditional generative adversarial networks for speech enhancement and noise-robust speaker verification,” in Proc. Interspeech 2017 (2017) pp. 2008–2012
2012
Cited alongside, same era.
V. Vapnik, The nature of statistical learning theory (Springer science & business media, 2013)
2013
Cited alongside, same era.
J. Bruna and S. Mallat, “Invariant scattering convolution networks,” IEEE transactions on pattern analysis and machine intelligence 35
2013
Cited alongside, same era.

Then

J. Pennington and P. Worah, “Nonlinear random matrix theory for deep learning,” in Advances in Neural Information Processing Systems (2017) pp. 2637–2646
2017
Later among the works it cites.
M.S. Advani and A.M. Saxe, “High-dimensional dynamics of generalization error in neural networks,” (2017), arXiv:1710.03667
Original
2017
Later among the works it cites.
R. Ge, J.D. Lee, and T. Ma, “Learning one-hidden-layer neural networks with landscape design,” in ICLR (2017) arXiv:1711.00501
Original
2017
Later among the works it cites.
Y. Li and Y. Y., “Convergence analysis of two-layer neural networks with relu activation,” in Advances in Neural Information Processing Systems (2017) pp. 597–607
2017
Later among the works it cites.
D. Arpit, S. Jastrzębski, M.S. Kanwal, T. Maharaj, A. Fischer, A. Courville, and Y. Bengio, “A Closer Look at Memorization in Deep Networks,” in Proceedings of the 34th International Conference on Machine Learning (2017)
2017
Later among the works it cites.
C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals, “Understanding deep learning requires rethinking generalization,” in ICLR (2017)
2017
Later among the works it cites.
M. Gabrié, A. Manoel, C. Luneau, J. Barbier, N. Macris, F. Krzakala, and L. Zdeborová, “Entropy and mutual information in models of deep neural networks,” in Advances in Neural Information Processing Systems 31 (2018) pp. 1826–1836
2018
Later among the works it cites.
E. Mossel, “Deep learning and hierarchical generative models,” (2018), arXiv:1612.09057
Original
2018
Later among the works it cites.
C. Louart, Z. Liao, and Romain Couillet, “A random matrix approach to neural networks,” The Annals of Applied Probability 28
2018
Later among the works it cites.
B. Aubin, A. Maillard, J. Barbier, F. Krzakala, N. Macris, and L. Zdeborová, “The committee machine: Computational to statistical gaps in learning a two-layers neural network,” in Advances in Neural Information Processing Systems 31 (2018) pp. 3227–3238
2018
Later among the works it cites.
M. Soltanolkotabi, A. Javanmard, and J. D. Lee, “Theoretical insights into the optimization landscape of over-parameterized shallow neural networks,” IEEE Transactions on Information Theory 65
2018
Later among the works it cites.
S. Mei, A. Montanari, and P. Nguyen, “A mean field view of the landscape of two-layer neural networks,” Proceedings of the National Academy of Sciences 115
2018
Later among the works it cites.
G.M. Rotskoff and E. Vanden-Eijnden, “Parameters as interacting particles: long time convergence and asymptotic error scaling of neural networks,” in Advances in Neural Information Processing Systems 31 (2018) pp. 7146–7155
2018
Later among the works it cites.
L. Chizat and F. Bach, “On the global convergence of gradient descent for over-parameterized models using optimal transport,” in Advances in Neural Information Processing Systems 31 (2018) pp. 3040–3050
2018
Later among the works it cites.
F. Farnia, J. Zhang, and D. Tse, “A spectral approach to generalization and optimization in neural networks,” in ICLR (2018)
2018
Later among the works it cites.
Y. Yoshida and M. Okada, “Data-dependence of plateau phenomenon in learning with neural network — statistical mechanical analysis,” in Advances in Neural Information Processing Systems 32 (2019) pp. 1720–1728
2019
Closest in time.
Z. Fan and A. Montanari, “The spectral norm of random inner-product kernel matrices,” Probability Theory and Related Fields 173
2019
Closest in time.
M.E.A. Seddik, M. Tamaazousti, and R. Couillet, “Kernel random matrices of large concentrated data: the example of gan-generated images,” in ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (IEEE, 2019) pp. 7480–7484
2019
Closest in time.
J. Barbier, F. Krzakala, N. Macris, L. Miolane, and L. Zdeborová, “Optimal errors and phase transitions in high-dimensional generalized linear models,” Proceedings of the National Academy of Sciences 116
2019
Closest in time.
S. Goldt, M.S. Advani, A.M. Saxe, F. Krzakala, and L. Zdeborová, “Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setup,” in Advances in Neural Information Processing Systems 32 (2019)
2019
Closest in time.
Y. Yoshida, R. Karakida, M. Okada, and S.-I. Amari, “Statistical mechanical analysis of learning dynamics of two-layer perceptron with multiple output units,” Journal of Physics A: Mathematical and Theoretical 52
2019
Closest in time.
S. Arora, N. Cohen, W. Hu, and Y. Luo, “Implicit Regularization in Deep Matrix Factorization,” in Advances in Neural Information Processing Systems 33 (2019)
2019
Closest in time.
J. Sirignano and K. Spiliopoulos, “Mean field analysis of neural networks: A central limit theorem,” Stochastic Processes and their Applications (2019), 10.1016/j.spa.2019.06.003
2019
Closest in time.
D. Kalimeris, G. Kaplun, P. Nakkiran, B. Edelman, T. Yang, B. Barak, and H. Zhang, “Sgd on neural networks learns functions of increasing complexity,” in Advances in Neural Information Processing Systems 32 (2019) pp. 3496–3506
2019
Closest in time.
N. Rahaman, A. Baratin, D. Arpit, F. Draxler, M. Lin, F. A Hamprecht, Y. Bengio, and A. Courville, “On the spectral bias of neural networks,” in ICML (2019)
2019
Closest in time.
U. Cohen, SY Chung, D.D. Lee, and H. Sompolinsky, “Separability and geometry of object manifolds in deep neural networks,” Nature communications 11
2020
Closest in time.
F. Gerace, B. Loureiro, F. Krzakala, M. Mézard, and L. Zdeborová, “Generalisation error in learning with random features and the hidden manifold model,” in 37th International Conference on Machine Learning (2020)
2020
Closest in time.
F. Mignacco, F. Krzakala, Y. M. Lu, and L. Zdeborová, “The role of regularization in classification of high-dimensional noisy gaussian mixture,” in 37th International Conference on Machine Learning (2020)
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…