Random walks on random graphs in high dimensions

人们可能想知道蚂蚁、半导体中的粒子和人工智能中使用的某些算法有什么共同之处。事实证明，它们都受到诱捕的影响。更准确地说：在最近的一项工作中，作者进行了一项实验，一群蚂蚁必须把一个大物体一起搬回它们的巢穴。研究小组通过在它们回家的路上放置立方体来测量会发生什么。不出所料，观察到立方体减慢了蚂蚁的速度，但也揭示了，经过一定数量的障碍后，这种减速变得非常明显，最终蚂蚁改变了策略，开始将物体举到立方体上方，而不是停留在地面上。物理学家在b[11]中观察到，当磁场太强时，一个带电粒子在有杂质的环境中受到磁场的推动，移动速度就会变慢。这是由于杂质造成的“死角”造成的捕获机制随着磁场的增加而变得更强。机器学习的核心问题之一是最小化非常高维空间中的函数。一个广泛观察到的现象是，正在使用的算法，如梯度下降或随机梯度，能够显著接近最小值，但最终卡在真正的最优解之上。尽管存在差异，但所有模型都有共同的行为。这被称为普遍性，是概率论的核心。我研究的重点是随机环境中的随机漫步（RWRE），这是类似于上面描述的例子的数学模型。我的目标是为RWREs发现新的通用性类，了解它们的特征，并确定为什么某些模型属于某个通用性类。我的兴趣可以分成三个大轴。-具有局部陷阱的重水反应堆的普遍性。我已经开发了一种技术，可以将某些类型的rwre与物理学家引入的一个玩具模型进行比较，这个模型被称为布绍陷阱模型。我想扩展这些技术的分支，并将它们应用到新的模型中。临界图上随机游走的普遍性。最著名的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.