Random walks on random graphs in high dimensions

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