Random walks on random graphs in high dimensions

人们可能会想，蚂蚁、半导体中的粒子和人工智能中使用的某些算法有什么共同之处。事实证明，它们都受到诱捕的影响。更准确地说：-在最近的一项工作[33]中，作者进行了一组蚂蚁必须一起把一个大物体带回它们的巢穴的实验。研究小组正在通过将立方体放在回家的路上来测量会发生什么。不出所料，人们观察到这些小块让蚂蚁减慢了速度，但也有人透露，在经过一定数量的障碍后，这种减速变得戏剧性的，最终蚂蚁改变了策略，开始将物体从小块上方抬起，而不是停留在地面上。-物理学家在[11]中观察到，在含有杂质的环境中，被磁场推动的带电粒子在磁场变得太强时开始运动得更慢。这是由于杂质造成的“死胡同”产生了一种捕获机制，这种机制随着磁场的增加而变得更强。-机器学习的核心问题之一是最小化非常高维空间中的函数。一个广泛观察到的现象是，正在使用的算法，如梯度下降或随机梯度，能够显著接近最小值，但最终却卡在真正的最优解之上。尽管存在差异，但所有的模型都有共同的行为。这被称为普适性，是概率论的核心。我的研究重点是随机环境中的随机行走(RWRE)，它是类似于上面描述的例子的数学模型。我的目标是为RWRE发现新的普适性类，了解它们的特征并确定为什么某些模型属于某个普适性类。我的兴趣可以分解成三个大轴。-具有本地陷阱的RWRE的普遍性。我已经开发了一些技术，用于将某些类型的RWRE与物理学家引入的被称为Bouchaud陷阱模型的玩具模型进行比较。我想扩展这些技术的分支，并将它们应用到新的模型中。-临界图上随机游动的普适性。RWRE最著名的模型之一是迷宫中的蚂蚁，即在临界渗流团簇上的简单随机游动。最近的一项工作[30]在高维模型中证明了著名的Alexander-Orbach猜想。这一猜想表明，漫步的光谱维度等于4/3，与d无关(这在低维被认为是错误的)。我的目标是证明在这个万能指数的背后是一个与超布朗运动上的布朗运动有关的普适标度极限。-我还在努力开发工具，用于研究超高维系统的动力学，如自旋玻璃。在这一点上，这是一项非常雄心勃勃的任务，但它是我研究的自然延续，这一研究的动机也是在机器学习中观察到的有趣现象。

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.