Olga Solodova will present her General Exam on Monday, May 9, 2022 at 11:00 AM in CS 402 and via zoom.

Zoom link: https://princeton.zoom.us/j/6387833692?pwd=a25TVlhkWlFYUE9uQ2dyVUI4eGpDdz09

Committee Members: Ryan Adams (advisor), Adji Bousso Dieng, Szymon Rusinkiewicz

Abstract:

Two projects will be presented in this work. The first uses deep reinforcement learning (RL) to generate optimized assembly code for arithmetic circuits. The second aims to add to methods for graph-based learning.

Arithmetic circuits are ubiquitous in machine learning and scientific computing; computation of polynomial functions, matrix multiplication, and solutions to differential equations are all arithmetic circuits. These algorithms are so central and executed so often that it is imperative that their implementation is optimal (in terms of metrics such as execution speed or energy consumption). In practice, hundreds of human hours are invested in directly writing optimized machine code for such applications. Unfortunately, machine code implementations of these algorithms are difficult to reason about, especially given increasingly sophisticated computer architectures which have complicated performance characteristics. In this work, Monte Carlo tree search together with a policy and value network is used to efficiently search for optimal solutions in the space of assembly programs which compute some arithmetic circuit.

Graph neural networks (GNNs) are neural networks designed to work with graph-structured data such as the arithmetic circuits described above. Specifically, GNNs generate node embeddings by repeatedly aggregating information from the neighborhood around each node in a graph, and use these embeddings to calculate a prediction. The aggregation and prediction functions consist of neural networks with parameters which are learned from data. At a high level, there are two approaches to learning in GNNs. The first is to have the aggregation function converge to a fixed point in the embedding space of the nodes, and employ the Almeida-Pineda algorithm to take gradients at this fixed point. The second is to unroll the aggregation function for a set number of time steps and use back-propagation through time (BBPT). In existing GNNs, employing the first approach requires constraining the aggregation function generating node embeddings to be a contraction map in order to arrive at a fixed point. This restriction limits the propagation of information across long distances in a graph, which diminishes the ability to learn long-range dependencies. However, having node embeddings converge to a fixed point removes the need to ‘unroll’ all the iterations of the fixed point iteration, which is particularly useful in memory-constrained settings when the graph or number of fixed point iterations is large. The second approach using BBPT suffers from different problems, namely that ‘over-smoothing’ in the node embeddings is difficult to mitigate in deep GNNs (i.e. GNNs with many iterations of the aggregation function). This work presents energy-based GNNs, which use the minimization of an energy function as the aggregation function, which by definition arrives at a fixed point in the space of node embeddings. This allows employing the Almeida-Pineda algorithm to take gradients, and may additionally enable more effective node embeddings to be learned with deep GNNs.

Reading List:

https://docs.google.com/document/d/1qnjynlegkn29HEzg6mS6bO-aAodUxNxdA5S4bqUBAV0/edit

Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so.