Random tensor theory

Random tensors

• Tomioka & Suzuki, 2014: Spectral norm of random tensors (arxiv)
  • A short covering number argument
• Ambainis, Harrow, Hastings, 2009: Random tensor theory: extending random matrix theory to random product states (doi, arxiv)
  • From the quantum information community
  • Generalizes M-P law to sums of random product states (as opposed to random states, which leads to classical Wishart distribution)
  • Does not address tensor decompositions as used in practice

Connections to deep learning

Recent effort to understand saddle-points in high-dimensional non-convex optimization problems (e.g., neural networks)

• Dauphin et al, 2014: Identifying and attacking the saddle point problem in high-dimensional non-convex optimization (arxiv)
• Choromanska et al, 2014: The loss surfaces of multilayer networks (arxiv)
• Sagun etal, 2014: Explorations on high dimensional landscapes (arxiv)
• Chaudhari & Soatto, 2015: The effect of gradient noise on the energy landscape of deep networks (arxiv)

Connections to statistical physics, esp., spin glasses

Many of these are cited in reviews by Bengio and LeCun above.

• Auffinger et al, 2013: Random matrices and complexity of spin glasses (doi, arxiv)
  • Equivalent to eigenvalues of random symmetric tensor
• Auffinger & Ben Arous, 2013: Complexity of random smooth functions on the high-dimensional sphere (doi, arxiv)
  • Extension to more general functions
• Auffinger & Chen, 2014: Free energy and complexity of spherical bipartite models (doi, arxiv)
  • Similar but not quite equivalent to singular values of random tensor
• Bray & Dean, 2007: The statistics of critical points of Gaussian fields on large-dimensional spaces (doi, arxiv)
• Fyodorov & William,s, 2007:Replica symmetry breaking condition exposed by random matrix calculation of landscape complexity (arxiv)
• Fyodorov, 2013, lecture notes: High-dimensional random fields and random matrix theory (arxiv)