Grant: Discovery Grants Program - Individual
Université de Montréal
$48,000.00
Random walks on random graphs in high dimensions
EF 2024-25
Résumé
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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2020-05024
Name nom
Fribergh, Alexander
Department département
Mathématiques et de statistique - Mathématiques et de statistique
Organization id
63
Institution établissement
Université de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2020
Award amount
48000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
3006
Research subject group en
Statistics and probability
Research subject group fr
Statistique et probabilité
Research subject en
Probability theory
Research subject fr
Théorie de la probabilité
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Random walks on random graphs in high dimensions
Keywords
random walk; percolation; lace expansion; spin glasses; heavy tailed random variables; super brownian motion
Application summary
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.