Random walks on random graphs in high dimensions

人们可能想知道蚂蚁、半导体中的粒子和人工智能中使用的某些算法有什么共同之处。事实证明，它们都受到诱捕的影响。更准确地说应该是:

One may wonder what an ant, a particle in a semi-conductor and certain algorithms used in artificial intelligence would have in common. It turns out they are all affected by trapping. More precisely: -in a recent work [33], the authors performed experiments where a group of ants had to carry together a large object back to their nest. The team was measuring what would happen by putting cubes on their path home. Unsurprisingly, it was observed that the cubes slowed down the ants, but it was also revealed that past a certain number of obstacles this slowdown became dramatic and eventually the ants switched strategy and started to lift the object above the cubes instead of staying on the ground. -Physicists observed in [11] that a charged particle pushed by a magnetic field in an environment with impurities starts moving slower when the magnetic field gets too strong. This is due to "dead-ends" caused by impurities creating a trapping mechanism which gets stronger as the magnetic field is increased. -One of the central problems in machine learning is minimizing a function in very high-dimensional space. A widely observed phenomenon is that the algorithms being used, such as gradient descent or stochastic gradient, are able to approach significantly the minimal value but end up getting stuck above the true optimal solution. Despite their differences all the models share common behaviours. This is called universality and is the heart of probability theory. The key focus of my research has been on random walks in random environments (RWRE) which are mathematical models similar to the examples described above. My goal is to discover new universality classes for RWREs, understand their characteristics and determine why certain models belong to a certain universality class. My interests can be decomposed in three large axes. -Universality for RWREs with local traps. I have developed techniques for comparing certain types of RWREs with a toy model introduced by physicists known as the Bouchaud trap model. I want to extend the ramification of those techniques and apply them to new models. -Universality for random walks on critical graphs. One of the most famous models of RWRE is the ant in the labyrinth i.e. the simple random walk on critical percolation clusters. A recent work [30] proved the famous Alexander-Orbach conjecture in this model in high dimensions. This conjecture states that the spectral dimension of the walk is equal to 4/3 independently of d (this is now believed to be false in low dimensions). My goal is to show that behind this universal exponent lies a universal scaling limit related to the Brownian motion on the Super-Brownian motion. -I am also working to develop tools for studying dynamics in very-high dimensional systems such as spin glasses. This is a very ambitious task at this point but it is a natural continuation of my research which is also motivated by the interesting phenomena that have been observed in machine learning.