Probability

Random walks and branching random walks: old and new perspectives - Lecture 16

Speaker: 
Perla Sousi
Date: 
Fri, Jul 26, 2024
Location: 
CRM, Montreal
Conference: 
2024 CRM-PIMS Summer School in Probability
Abstract: 

This course will focus on two well-studied models of modern probability: simple symmetric and branching random walks in ℤd. The focus will be on the study of their trace in the regime that this is a small subset of the ambient space.
We will start by reviewing some useful classical (and not) facts about simple random walks. We will introduce the notion of capacity and give many alternative forms for it. Then we will relate it to the covering problem of a domain by a simple random walk. We will review Lawler’s work on non-intersection probabilities and focus on the critical dimension $d=4$. With these tools at hand we will study the tails of the intersection of two infinite random walk ranges in dimensions d≥5.

A branching random walk (or tree indexed random walk) in ℤd is a non-Markovian process whose time index is a random tree. The random tree is either a critical Galton Watson tree or a critical Galton Watson tree conditioned to survive. Each edge of the tree is assigned an independent simple random walk in ℤd increment and the location of every vertex is given by summing all the increments along the geodesic from the root to that vertex. When $d\geq 5$, the branching random walk is transient and we will mainly focus on this regime. We will introduce the notion of branching capacity and show how it appears naturally as a suitably rescaled limit of hitting probabilities of sets. We will then use it to study covering problems analogously to the random walk case.

Class: 

Random matrix theory of high-dimensional optimization - Lecture 16

Speaker: 
Elliot Paquette
Date: 
Fri, Jul 26, 2024
Location: 
CRM, Montreal
Conference: 
2024 CRM-PIMS Summer School in Probability
Abstract: 

Optimization theory seeks to show the performance of algorithms to find the (or a) minimizer x∈ℝd of an objective function. The dimension of the parameter space d has long been known to be a source of difficulty in designing good algorithms and in analyzing the objective function landscape. With the rise of machine learning in recent years, this has been proven that this is a manageable problem, but why? One explanation is that this high dimensionality is simultaneously mollified by three essential types of randomness: the data are random, the optimization algorithms are stochastic gradient methods, and the model parameters are randomly initialized (and much of this randomness remains). The resulting loss surfaces defy low-dimensional intuitions, especially in nonconvex settings.
Random matrix theory and spin glass theory provides a toolkit for theanalysis of these landscapes when the dimension $d$ becomes large. In this course, we will show

how random matrices can be used to describe high-dimensional inference
nonconvex landscape properties
high-dimensional limits of stochastic gradient methods.

Class: 

Condensation phenomena in random trees - Lecture 2

Speaker: 
Igor Kortchemski
Date: 
Thu, Jul 25, 2024
Location: 
CRM, Montreal
Conference: 
2024 CRM-PIMS Summer School in Probability
Abstract: 

Consider a population that undergoes asexual and homogeneous reproduction over time, originating from a single individual and eventually ceasing to exist after producing a total of n individuals. What is the order of magnitude of the maximum number of children of an individual in this population when n tends to infinity? This question is equivalent to studying the largest degree of a large Bienaymé-Galton-Watson random tree. We identify a regime where a condensation phenomenon occurs, in which the second greatest degree is negligible compared to the greatest degree. The use of the "one-big jump principle" of certain random walks is a key tool for studying this phenomenon. Finally, we discuss applications of these results to other combinatorial models.

Class: 

Random matrix theory of high-dimensional optimization - Lecture 15

Speaker: 
Elliot Paquette
Date: 
Thu, Jul 25, 2024
Location: 
CRM, Montreal
Conference: 
2024 CRM-PIMS Summer School in Probability
Abstract: 

Optimization theory seeks to show the performance of algorithms to find the (or a) minimizer x∈ℝd of an objective function. The dimension of the parameter space d has long been known to be a source of difficulty in designing good algorithms and in analyzing the objective function landscape. With the rise of machine learning in recent years, this has been proven that this is a manageable problem, but why? One explanation is that this high dimensionality is simultaneously mollified by three essential types of randomness: the data are random, the optimization algorithms are stochastic gradient methods, and the model parameters are randomly initialized (and much of this randomness remains). The resulting loss surfaces defy low-dimensional intuitions, especially in nonconvex settings.
Random matrix theory and spin glass theory provides a toolkit for theanalysis of these landscapes when the dimension $d$ becomes large. In this course, we will show

how random matrices can be used to describe high-dimensional inference
nonconvex landscape properties
high-dimensional limits of stochastic gradient methods.

Class: 

Random walks and branching random walks: old and new perspectives - Lecture 15

Speaker: 
Perla Sousi
Date: 
Thu, Jul 25, 2024
Location: 
CRM, Montreal
Conference: 
2024 CRM-PIMS Summer School in Probability
Abstract: 

This course will focus on two well-studied models of modern probability: simple symmetric and branching random walks in ℤd. The focus will be on the study of their trace in the regime that this is a small subset of the ambient space.
We will start by reviewing some useful classical (and not) facts about simple random walks. We will introduce the notion of capacity and give many alternative forms for it. Then we will relate it to the covering problem of a domain by a simple random walk. We will review Lawler’s work on non-intersection probabilities and focus on the critical dimension $d=4$. With these tools at hand we will study the tails of the intersection of two infinite random walk ranges in dimensions d≥5.

A branching random walk (or tree indexed random walk) in ℤd is a non-Markovian process whose time index is a random tree. The random tree is either a critical Galton Watson tree or a critical Galton Watson tree conditioned to survive. Each edge of the tree is assigned an independent simple random walk in ℤd increment and the location of every vertex is given by summing all the increments along the geodesic from the root to that vertex. When $d\geq 5$, the branching random walk is transient and we will mainly focus on this regime. We will introduce the notion of branching capacity and show how it appears naturally as a suitably rescaled limit of hitting probabilities of sets. We will then use it to study covering problems analogously to the random walk case.

Class: 

Condensation phenomena in random trees - Lecture 1

Speaker: 
Igor Kortchemski
Date: 
Tue, Jul 23, 2024
Location: 
CRM, Montreal
Conference: 
2024 CRM-PIMS Summer School in Probability
Abstract: 

Consider a population that undergoes asexual and homogeneous reproduction over time, originating from a single individual and eventually ceasing to exist after producing a total of n individuals. What is the order of magnitude of the maximum number of children of an individual in this population when n tends to infinity? This question is equivalent to studying the largest degree of a large Bienaymé-Galton-Watson random tree. We identify a regime where a condensation phenomenon occurs, in which the second greatest degree is negligible compared to the greatest degree. The use of the "one-big jump principle" of certain random walks is a key tool for studying this phenomenon. Finally, we discuss applications of these results to other combinatorial models.

Class: 

Random walks and branching random walks: old and new perspectives - Lecture 14

Speaker: 
Perla Sousi
Date: 
Tue, Jul 23, 2024
Location: 
CRM, Montreal
Conference: 
2024 CRM-PIMS Summer School in Probability
Abstract: 

This course will focus on two well-studied models of modern probability: simple symmetric and branching random walks in ℤd. The focus will be on the study of their trace in the regime that this is a small subset of the ambient space.
We will start by reviewing some useful classical (and not) facts about simple random walks. We will introduce the notion of capacity and give many alternative forms for it. Then we will relate it to the covering problem of a domain by a simple random walk. We will review Lawler’s work on non-intersection probabilities and focus on the critical dimension $d=4$. With these tools at hand we will study the tails of the intersection of two infinite random walk ranges in dimensions d≥5.

A branching random walk (or tree indexed random walk) in ℤd is a non-Markovian process whose time index is a random tree. The random tree is either a critical Galton Watson tree or a critical Galton Watson tree conditioned to survive. Each edge of the tree is assigned an independent simple random walk in ℤd increment and the location of every vertex is given by summing all the increments along the geodesic from the root to that vertex. When $d\geq 5$, the branching random walk is transient and we will mainly focus on this regime. We will introduce the notion of branching capacity and show how it appears naturally as a suitably rescaled limit of hitting probabilities of sets. We will then use it to study covering problems analogously to the random walk case.

Class: 

Random matrix theory of high-dimensional optimization - Lecture 14

Speaker: 
Elliot Paquette
Date: 
Tue, Jul 23, 2024
Location: 
CRM, Montreal
Conference: 
2024 CRM-PIMS Summer School in Probability
Abstract: 

Optimization theory seeks to show the performance of algorithms to find the (or a) minimizer x∈ℝd of an objective function. The dimension of the parameter space d has long been known to be a source of difficulty in designing good algorithms and in analyzing the objective function landscape. With the rise of machine learning in recent years, this has been proven that this is a manageable problem, but why? One explanation is that this high dimensionality is simultaneously mollified by three essential types of randomness: the data are random, the optimization algorithms are stochastic gradient methods, and the model parameters are randomly initialized (and much of this randomness remains). The resulting loss surfaces defy low-dimensional intuitions, especially in nonconvex settings.
Random matrix theory and spin glass theory provides a toolkit for theanalysis of these landscapes when the dimension $d$ becomes large. In this course, we will show

how random matrices can be used to describe high-dimensional inference
nonconvex landscape properties
high-dimensional limits of stochastic gradient methods.

Class: 

Random matrix theory of high-dimensional optimization - Lecture 13

Speaker: 
Elliot Paquette
Date: 
Mon, Jul 22, 2024
Location: 
CRM, Montreal
Conference: 
2024 CRM-PIMS Summer School in Probability
Abstract: 

ptimization theory seeks to show the performance of algorithms to find the (or a) minimizer x∈ℝd of an objective function. The dimension of the parameter space d has long been known to be a source of difficulty in designing good algorithms and in analyzing the objective function landscape. With the rise of machine learning in recent years, this has been proven that this is a manageable problem, but why? One explanation is that this high dimensionality is simultaneously mollified by three essential types of randomness: the data are random, the optimization algorithms are stochastic gradient methods, and the model parameters are randomly initialized (and much of this randomness remains). The resulting loss surfaces defy low-dimensional intuitions, especially in nonconvex settings.
Random matrix theory and spin glass theory provides a toolkit for theanalysis of these landscapes when the dimension $d$ becomes large. In this course, we will show

how random matrices can be used to describe high-dimensional inference
nonconvex landscape properties
high-dimensional limits of stochastic gradient methods.

Class: 

Random walks and branching random walks: old and new perspectives - Lecture 13

Speaker: 
Perla Sousi
Date: 
Mon, Jul 22, 2024
Location: 
CRM, Montreal
Conference: 
2024 CRM-PIMS Summer School in Probability
Abstract: 

This course will focus on two well-studied models of modern probability: simple symmetric and branching random walks in ℤd. The focus will be on the study of their trace in the regime that this is a small subset of the ambient space.
We will start by reviewing some useful classical (and not) facts about simple random walks. We will introduce the notion of capacity and give many alternative forms for it. Then we will relate it to the covering problem of a domain by a simple random walk. We will review Lawler’s work on non-intersection probabilities and focus on the critical dimension $d=4$. With these tools at hand we will study the tails of the intersection of two infinite random walk ranges in dimensions d≥5.

A branching random walk (or tree indexed random walk) in ℤd is a non-Markovian process whose time index is a random tree. The random tree is either a critical Galton Watson tree or a critical Galton Watson tree conditioned to survive. Each edge of the tree is assigned an independent simple random walk in ℤd increment and the location of every vertex is given by summing all the increments along the geodesic from the root to that vertex. When $d\geq 5$, the branching random walk is transient and we will mainly focus on this regime. We will introduce the notion of branching capacity and show how it appears naturally as a suitably rescaled limit of hitting probabilities of sets. We will then use it to study covering problems analogously to the random walk case.

Class: 

Pages