Playlist: 22 videos
Meet the Fellows Welcome Event Fall 2022
0:15:20
Claire Donnat (University of Chicago)
https://simons.berkeley.edu/talks/understanding-geometry-graph-neural-networks
Meet the Fellows Welcome Event Fall 2022
By recursively summing node features over entire neighborhoods, spatial graph convolution operators have been heralded as key to the success of Graph Neural Networks (GNNs). Yet, despite the multiplication of GNN methods across tasks and applications, the impact of this aggregation operation on their performance still has yet to be extensively analyzed. In fact, while efforts have mostly focused on optimizing the architecture of the neural network, fewer works have attempted to characterize (a) the different classes of spatial convolution operators, (b) how the choice of a particular class relates to properties of the data }, and {\it (c) its impact on the geometry of the embedding space. In this talk, we bring elements of solution to these three questions by dividing existing operators into two main classes (symmetrized vs. row-normalized spatial convolutions), and show how these translate into different implicit biases on the nature of the data. Finally, we show that this aggregation operator is in fact tunable, and explicit regimes in which certain choices of operators --- and therefore, embedding geometries --- might be more appropriate
Visit talk page
https://simons.berkeley.edu/talks/understanding-geometry-graph-neural-networks
Meet the Fellows Welcome Event Fall 2022
By recursively summing node features over entire neighborhoods, spatial graph convolution operators have been heralded as key to the success of Graph Neural Networks (GNNs). Yet, despite the multiplication of GNN methods across tasks and applications, the impact of this aggregation operation on their performance still has yet to be extensively analyzed. In fact, while efforts have mostly focused on optimizing the architecture of the neural network, fewer works have attempted to characterize (a) the different classes of spatial convolution operators, (b) how the choice of a particular class relates to properties of the data }, and {\it (c) its impact on the geometry of the embedding space. In this talk, we bring elements of solution to these three questions by dividing existing operators into two main classes (symmetrized vs. row-normalized spatial convolutions), and show how these translate into different implicit biases on the nature of the data. Finally, we show that this aggregation operator is in fact tunable, and explicit regimes in which certain choices of operators --- and therefore, embedding geometries --- might be more appropriate
0:12:5
Shuang Gao (McGill University)
https://simons.berkeley.edu/talks/transmission-neural-networks-virus-spread-models-neural-networks
Meet the Fellows Welcome Event Fall 2022
This work connects models for virus spread on networks with their equivalent neural network representations. Based on this connection, we propose a new neural network architecture, called Transmission Neural Networks (TransNNs) where activation functions are primarily associated with links and are allowed to have different activation levels. Furthermore, this connection leads to the discovery and the derivation of three new activation functions with tunable or trainable parameters. We prove that TransNNs with a single hidden layer and a fixed non-zero bias term are universal function approximators. Moreover, we present new derivations of continuous time epidemic network models based on TransNNs.
Visit talk page
https://simons.berkeley.edu/talks/transmission-neural-networks-virus-spread-models-neural-networks
Meet the Fellows Welcome Event Fall 2022
This work connects models for virus spread on networks with their equivalent neural network representations. Based on this connection, we propose a new neural network architecture, called Transmission Neural Networks (TransNNs) where activation functions are primarily associated with links and are allowed to have different activation levels. Furthermore, this connection leads to the discovery and the derivation of three new activation functions with tunable or trainable parameters. We prove that TransNNs with a single hidden layer and a fixed non-zero bias term are universal function approximators. Moreover, we present new derivations of continuous time epidemic network models based on TransNNs.
0:13:46
Ana-Andreea Stoica (Columbia University/ MPI Tubingen)
https://simons.berkeley.edu/talks/diversity-and-inequality-social-networks
Meet the Fellows Welcome Event Fall 2022
Online social networks often mirror inequality in real-world networks, from historical prejudice, economic or social factors. Such disparities are often picked up and amplified by algorithms that leverage social data for the purpose of providing recommendations, diffusing information, or forming groups. In this talk, I will present a short overview of my research involving explanations for algorithmic bias in social networks, briefly describing my work in information diffusion, grouping, and general definitions of inequality.
Visit talk page
https://simons.berkeley.edu/talks/diversity-and-inequality-social-networks
Meet the Fellows Welcome Event Fall 2022
Online social networks often mirror inequality in real-world networks, from historical prejudice, economic or social factors. Such disparities are often picked up and amplified by algorithms that leverage social data for the purpose of providing recommendations, diffusing information, or forming groups. In this talk, I will present a short overview of my research involving explanations for algorithmic bias in social networks, briefly describing my work in information diffusion, grouping, and general definitions of inequality.
0:16:30
Chin-Chia Hsu (Microsoft)
https://simons.berkeley.edu/talks/misinformation-persuasion-and-news-media-social-networks
Meet the Fellows Welcome Event Fall 2022
Social media platforms have become a popular source of news and information for a large segment of society. Users can receive information, share digital content, or attend to online publishers for the latest news. However, the recent proliferation of misinformation has affected people’s perception of the veracity of online information and, in turn, their social behavior. In this environment of real and false information, I studied two aspects of user behavior through the lens of persuasion: (1) sharing online news, and (2) consumer choice of news media. In this talk, I will present my game-theoretic models and share theoretical insights into these two user behaviors.
Visit talk page
https://simons.berkeley.edu/talks/misinformation-persuasion-and-news-media-social-networks
Meet the Fellows Welcome Event Fall 2022
Social media platforms have become a popular source of news and information for a large segment of society. Users can receive information, share digital content, or attend to online publishers for the latest news. However, the recent proliferation of misinformation has affected people’s perception of the veracity of online information and, in turn, their social behavior. In this environment of real and false information, I studied two aspects of user behavior through the lens of persuasion: (1) sharing online news, and (2) consumer choice of news media. In this talk, I will present my game-theoretic models and share theoretical insights into these two user behaviors.
0:13:35
Niccolo Lomys (Toulouse School of Economics)
https://simons.berkeley.edu/talks/estimation-games-under-no-regret
Meet the Fellows Welcome Event Fall 2022
We develop a method to estimate a game’s primitives in complex dynamic environments. Because of the environment’s complexity, agents may not know or understand some key features of their interaction. Instead of equilibrium assumptions, we impose an asymptotic ε-regret (ε-AR) condition on the observed play. According to ε-AR, the time average of the counterfactual increase in past payoffs, had each agent changed each past play of a given action with its best replacement in hindsight, becomes small in the long run. We first prove that the time average of play satisfies εAR if and only if it converges to the set of Bayes correlated ε-equilibrium predictions of the stage game. Next, we use the static limiting model to construct a set estimator of the parameters of interest. The estimator’s coverage properties directly arise from the theoretical convergence results. The method applies to panel data as well as to cross-sectional data interpreted as long-run outcomes of learning dynamics. We apply the method to pricing data in an online marketplace. We recover bounds on the distribution of sellers’ marginal costs that are useful to inform policy experiments.
Visit talk page
https://simons.berkeley.edu/talks/estimation-games-under-no-regret
Meet the Fellows Welcome Event Fall 2022
We develop a method to estimate a game’s primitives in complex dynamic environments. Because of the environment’s complexity, agents may not know or understand some key features of their interaction. Instead of equilibrium assumptions, we impose an asymptotic ε-regret (ε-AR) condition on the observed play. According to ε-AR, the time average of the counterfactual increase in past payoffs, had each agent changed each past play of a given action with its best replacement in hindsight, becomes small in the long run. We first prove that the time average of play satisfies εAR if and only if it converges to the set of Bayes correlated ε-equilibrium predictions of the stage game. Next, we use the static limiting model to construct a set estimator of the parameters of interest. The estimator’s coverage properties directly arise from the theoretical convergence results. The method applies to panel data as well as to cross-sectional data interpreted as long-run outcomes of learning dynamics. We apply the method to pricing data in an online marketplace. We recover bounds on the distribution of sellers’ marginal costs that are useful to inform policy experiments.
0:13:16
Alankrita Bhatt (Simons Institute)
https://simons.berkeley.edu/talks/universal-portfolios-continuous-side-information
Meet the Fellows Welcome Event Fall 2022
In this talk, I will revisit the problem of universal portfolio selection first proposed by Cover in 1991. This is a basic problem in information theory with several operational interpretations and connections to, among others, data compression and universal prediction. I will talk about recent work on a new portfolio selection strategy that adapts to a continuous side-information sequence, with a universal wealth guarantee against a class of state-constant rebalanced portfolios with respect to an unknown state function that maps each side-information symbol to a finite set of states.
Visit talk page
https://simons.berkeley.edu/talks/universal-portfolios-continuous-side-information
Meet the Fellows Welcome Event Fall 2022
In this talk, I will revisit the problem of universal portfolio selection first proposed by Cover in 1991. This is a basic problem in information theory with several operational interpretations and connections to, among others, data compression and universal prediction. I will talk about recent work on a new portfolio selection strategy that adapts to a continuous side-information sequence, with a universal wealth guarantee against a class of state-constant rebalanced portfolios with respect to an unknown state function that maps each side-information symbol to a finite set of states.
0:15:36
Jackie Baek (MIT / NYU)
https://simons.berkeley.edu/talks/exploration-algorithmic-fairness
Meet the Fellows Welcome Event Fall 2022
Disparate impact of machine learning algorithms is often caused by imbalanced datasets, in particular, the scarcity of data from certain subpopulations. One obvious solution to this problem is to collect more data - and one natural way to do this is to continue collecting data after an algorithm is deployed. In this sense, the use of exploration in an online learning framework is a natural way to "collect more data" over time to address this problem. I will talk about some recent work on fairness in exploration, as well as some open directions in this setting.
Visit talk page
https://simons.berkeley.edu/talks/exploration-algorithmic-fairness
Meet the Fellows Welcome Event Fall 2022
Disparate impact of machine learning algorithms is often caused by imbalanced datasets, in particular, the scarcity of data from certain subpopulations. One obvious solution to this problem is to collect more data - and one natural way to do this is to continue collecting data after an algorithm is deployed. In this sense, the use of exploration in an online learning framework is a natural way to "collect more data" over time to address this problem. I will talk about some recent work on fairness in exploration, as well as some open directions in this setting.
0:9:31
Kangning Wang (Simons Institute, UC Berkeley)
https://simons.berkeley.edu/talks/approximately-efficient-bilateral-trade
Meet the Fellows Welcome Event Fall 2022
I will showcase a recent work in this talk. We study the following classical bilateral trade model: A seller with a private cost is selling one item to a buyer with a private value, where the cost and the value are drawn from publicly known independent distributions. The celebrated result of Myerson and Satterthwaite in 1983 states that in general, no incentive-compatible, individually rational and weakly budget balanced mechanism can be socially efficient. Given this, a natural question is whether there exists a mechanism with these properties that guarantees a constant fraction of the first-best gains-from-trade, a natural benchmark measuring the level of maximum possible efficiency when the agents are not strategic. We positively resolve this long-standing open question using a simple mechanism. This is based on joint work with Yuan Deng, Jieming Mao and Balasubramanian Sivan from Google Research.
Visit talk page
https://simons.berkeley.edu/talks/approximately-efficient-bilateral-trade
Meet the Fellows Welcome Event Fall 2022
I will showcase a recent work in this talk. We study the following classical bilateral trade model: A seller with a private cost is selling one item to a buyer with a private value, where the cost and the value are drawn from publicly known independent distributions. The celebrated result of Myerson and Satterthwaite in 1983 states that in general, no incentive-compatible, individually rational and weakly budget balanced mechanism can be socially efficient. Given this, a natural question is whether there exists a mechanism with these properties that guarantees a constant fraction of the first-best gains-from-trade, a natural benchmark measuring the level of maximum possible efficiency when the agents are not strategic. We positively resolve this long-standing open question using a simple mechanism. This is based on joint work with Yuan Deng, Jieming Mao and Balasubramanian Sivan from Google Research.
0:14:16
Souvik Dhara (University of California, Berkeley)
https://simons.berkeley.edu/talks/power-two-matrices-spectral-algorithms
Meet the Fellows Welcome Event Fall 2022
Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a single matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms have been quite successful for graph partitioning problems among other applications. In this talk, I will present a scenario for graph partitioning with censored edges where spectral algorithms with a single encoding matrix is suboptimal. However, if we use multiple encoding matrices instead of one, that achieves optimality and leads to a much powerful and flexible class of algorithms. This is joint work with Julia Gaudio, Elchanan Mossel, Colin Sandon
Visit talk page
https://simons.berkeley.edu/talks/power-two-matrices-spectral-algorithms
Meet the Fellows Welcome Event Fall 2022
Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a single matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms have been quite successful for graph partitioning problems among other applications. In this talk, I will present a scenario for graph partitioning with censored edges where spectral algorithms with a single encoding matrix is suboptimal. However, if we use multiple encoding matrices instead of one, that achieves optimality and leads to a much powerful and flexible class of algorithms. This is joint work with Julia Gaudio, Elchanan Mossel, Colin Sandon
0:15:25
Jason Li (Simons Institute)
https://simons.berkeley.edu/talks/recent-trends-minimum-cut-algorithms
Meet the Fellows Welcome Event Fall 2022
Minimum cut problems are among the most basic questions in algorithm design. In the last few years, there has been a resurgence in new results in this domain, resulting in the first improvements in many decades for many of these problems. In this talk, I will survey some of these results, focusing on the broad themes and techniques that have driven this progress.
Visit talk page
https://simons.berkeley.edu/talks/recent-trends-minimum-cut-algorithms
Meet the Fellows Welcome Event Fall 2022
Minimum cut problems are among the most basic questions in algorithm design. In the last few years, there has been a resurgence in new results in this domain, resulting in the first improvements in many decades for many of these problems. In this talk, I will survey some of these results, focusing on the broad themes and techniques that have driven this progress.