Ongoing Projects

Neural systems for fast continual learning (PI J. Sacramento, co-PI A. Steger)

Supported by ETH Research Grant (ETH-23 21-1)

The human brain excels at quickly acquiring new skills while keeping old ones. By contrast, current artificial neural networks have become very skilled at learning specific challenging tasks, but they require enormous computation time and large numbers of training data to learn. Furthermore, they do not easily adapt when presented with a new related problem without forgetting the old one. We try to bridge this gap between biological and artificial neural networks by looking into the architecture of the brain. Following an interdisciplinary approach that involves computer science, mathematics and neuroscience, we aim at building computational and mathematical models which incorporate key design elements of cortical networks. In particular, we want to develop modular neural architectures which (i) display functional specialization, comprising multiple distinct systems, (ii) connect modules recurrently, thus forming feedback loops, and (iii) are hybrid discrete-continuous computers, communicating information using an analog neural code while also being capable of performing discrete operations. Our models have the potential to start adapting faster and forgetting less once they have learned many tasks. Furthermore, their modular aspect suggests ways of learning their connections which differ from standard artificial neural network learning procedures.

Probabilistic Combinatorics and Algorithmic Applications (PI A. Steger)

Supported by Swiss National Science Foundation (SNF) grant 197138

A graph is set to resiliently contain some property P, if we may allow an adversary to destroy edges (within limits) without the graph losing this property. There are various ways how to make ‘within limits’ precise. Currently, the most commonly used notion is that of local resilience, which limits the fraction of edges that the adversary may delete at each vertex. As we showed in some preliminary work, this notion of local resilience has its clear limitations when we study more complex properties. Depending on the property P under consideration, one would like to have some stronger restrictions, that we coined H-resilience. A major part of the proposed project is to further understand the nature of resilience. In addition, we will use methods developed in this context to address some fundamental problems within algorithms design. As an example for such an application, consider the mastermind problem with n positions and k = n colors. A straightforward entropy argument provides a lower bound of Ω(n) on the required rounds. The currently best algorithmic solution requires O(n log log n) rounds. We aim at closing this gap.

Dynamic Processes on Geometric Inhomogeneous Random Graphs (PI J. Lengler)

Supported by Swiss National Science Foundation (SNF) grant 192079

Social networks have two particularly important properties:
1) Inhomogeneity: in a pandemic, some people infect very few other people, while other people infect very many.
2) Communities and clusters: in a person's circle of friends, many people know each other.
Epidemics are very well understood in networks that only have the first characteristic. They happen very quickly there. They are also very well understood in networks that only have the second property. There they run rather slowly, because a virus often encounters people who are already infected when it spreads.
Until now, it was not possible to study such processes in networks that combine both properties. There were no suitable network models for this. These have only been developed in recent years. We therefore want to understand how epidemics and other dynamic processes spread in networks that combine both properties. In particular, we want to understand under which circumstances processes spread exponentially, under which circumstances they spread even faster ("double exponential", "explosive") or slower ("polynomial"). We also want to understand which external measures can be used to slow down or stop such spreading processes. The research project was developed before the outbreak of the CoViD-19 pandemic. The aim of this project is to improve the possibilities for predicting future pandemics. However, the results will come too late for the current pandemic.

Temporal Information Integration in Neural Networks (PI A. Steger, co-PI Benjamin Grewe)

Sinergia project by Swiss National Science Foundation (SNF) grant CRSII5_173721

The goal of this project is to gain a fundamental and analytical understanding of (1) how neuronal networks store information over short time periods and (2) how they link information across time to build internal models of complex temporal input data. Our proposal is well timed because recent advances in neuroscience now allow to record and track the activity of large populations of genetically identified neurons deep in the brain of behaving animals during a temporal learning task – this was simply not possible several years ago. To reach the above goal we combine expertise in developing and using cutting edge in vivo calcium imaging techniques to probe neuronal population activity in awake freely behaving animals (group B. Grewe) with expertise in analyzing random networks (group A. Steger). This combination of collaborators allows us to develop network models and hypotheses from observed data that we can subsequently test in vivo.

Probabilistic Auxiliary Networks: Beyond Learning Single Weight Configurations in Deep Networks (PI J. von Oswald)

Swiss Data Science Center (SDSC) Fellowship J.v.O. P18-03

The goal of this fellowship is to support the PhD student in developing tools around a particular neural network called HyperNetworks. These are neural networks itself that produce the weights of another target neural networks. Through this system of networks, the student aims to model rich distributions over target network weights to improve generalization and compression but also tackle multi-task or continual learning problems.

Previous Projects

Saturation Games and Robust Random Structures (PI A. Steger)

Supported by Swiss National Science Foundation (SNF) grant 169242

The goal of this project is to further enhance the understanding and methodical foundations of the interplay between games on graphs and the understanding of random structures. In particular, we aim at attacking two of the most intriguing open problems from both areas. The first one is the so-called saturation game for triangles. Saturation games are particularly hard to analyze as the two players follow different goals (one wants to maximize the number of edges, the other aims at minimizing them). Consequently, only very weak bounds are known so far. The other problem is that of studying the resilience of random graphs with respect to the containment of spanning or almost spanning subgraphs.

Games on Random Graphs

Supported by Swiss National Science Foundation (SNF) grant 143338 (PI A. Steger)

An intriguing observations in the study of combinatorial games is the so-called random graph intuition which says that for many two-player games the outcome of two optimal strategies playing against each other (`clever' vs `clever') is identical to the outcome of two players who just choose their moves randomly (`random' vs `random'). Indeed, there is a strong connection between games on graphs and games on random structures. The goal of this project is to enhance the methodical foundations for dealing with such probabilistic games. In particular, we aim at attacking some of the most interesting and challenging problems within the area of Games on Random Graphs. More precisely, we will study (i) Maker-Breaker games, (ii) Ramsey, and (iii) Achlioptas. Here, her goal can also be to avoid certain substructures or e.g. to avoid or create large connected components. Research around all three topics is very active and has lead to many beautiful and surprising results in the last decades.

Adaptive Relational Networks: A Detailed Model for Effective Cortical Computation

Supported by Swiss National Science Foundation (SNF) grant 143337; (PI A. Steger, together with Matthew Cook)

How do our brains memorize, recall, reason, and interact with their environment? There are two lines of research approaching this question: one from the side of biological knowledge of the anatomy and physiology of neural populations in the cortex, and one from the side of theoretical neural networks that can exhibit the desired emergent behavior. Finding points of contact between these two directions is one of the major current challenges in theoretical neuroscience. In this project we aims at developing a connection between biologically faithful neural network simulations and learning and reasoning abilities that we know that our brain has. By taking a sequence of slow and steady steps, our work plan directly targets the expansion of our understanding of how to construct neurally realistic simulations which exhibit the learning and reasoning characteristics necessary for eventually scaling up to larger scale inference systems.

Biological Information in Cortical Communication

Supported by Swiss National Science Foundation (SNF) grant 143947; (PI A. Steger, together with Matthew Cook)

The aim of this project is to develop in silico simulations of possible dynamic interplays among areas of the visual pathway. Cortical processing of visual input is known to use a distributed representation, with different areas encoding different aspects of the visual interpretation. In this project we will test the general applicability of such type of models to visual processing tasks (like depth perception, three-dimensional information processing, and incorporation of other sensory inputs) and thereby develop a set of principles of inter-areal communication which can be used not only in systems of our own design, but also to allow quantitative predictions regarding the mammalian visual system's structure and dynamics.

Random Processes on Graphs

Supported by Luxembourg Fonds National de la Recherche (FNR) grant 6910960 (PI A. Steger)

Stochastic processes play an increasingly important role in modern graph theory, appearing in many seemingly diverse settings, for example (i) games in which one or more players try to build graphs with specific properties, usually with a random component; (ii) bootstrap percolation phenomena that model the spread of ‘infection’ in certain networks; (iii) (pseudo)-random algorithmic constructions. In many such settings there is a strong interplay between determinism and randomness, and the goal of this project is to explore this connection by focusing on selected problems in probabilistic and extremal graph theory.

Dynamism in Networks and Distributed Computations

Supported by by Swiss National Science Foundation (SNF) grant 200021_120284 (PI A. Steger)

Large and complex networks such as e.g. the Internet, the world wide web, peer-to-peer sys- tems, wireless networks, or different kinds of social networks have become increasingly important over the last years. Most of these networks are organized in a completely decentralized way. As a result such networks are inherently dynamic, nodes appear and disappear, communication links are established or removed, and nodes might even be mobile and move as in wireless ad hoc networks. In addition to understanding the static structural properties of large and complex networks and to know the complexity of distributed computations in large, decentralized networks, it is therefore important to also understand the dynamic nature of such networks. The aim of this project is to develop novel models, tools, and methods to better understand fundamental aspects of the dynamism of networks and distributed computations. In particular, we want to study dynamic network models that are both realistic and tractable. Apart from considering the effects of network dynamism from a standard worst-case perspective, we will develop dynamic network models based on random graphs that allow to analyze average-case scenarios. In addition to (and also based on) the study of models for network dynamism, we will explore the possibilities and complexity of distributed algorithms that run on dynamic networks and constantly have to adapt to network changes. Techniques developed to understand dynamic networks and computations on such networks will also help to more generally understand the dynamic nature of distributed computations in networks.

Synthesis of Cortical Fields and Factor Graphs

Supported by ETH Research Grant ETH-23 08-1 (PI A. Steger)

Our brains have an amazing ability to interpret and react to the world around them. Many models have been proposed in an attempt to reproduce some aspect of the brain's abilities. We can categorize existing models into two broad classes: top-down, and bottom-up. Top-down models aim to reproduce high-level behaviors, without worrying about whether the model matches the implementation in the brain. Bottom-up models, on the other hand, focus on using elements and architectures that are directly taken from neurophysiological and neuroanatomical knowledge, without worrying about reproducing high-level behaviors. So far, no model has been able to successfully bridge this gap between top-down and bottom-up.
The project focuses on merging the impressive computational abilities of top-down approaches with the biological plausibility of bottom-up approaches. Specifically, the project tries to form a connection between factor graphs, a powerful top-down model, and cortical fields, a potent class of bottom-up models. The idea for this project arose from the observation that the low-level operations being performed by factor graphs are in many ways quite similar to low-level operations performed in cortical field models. Here we see for the first time a high level system whose computational primitives seem to correspond to traditional neural network primitives found in bottom-up networks.

The KLR-conjecture and Szemerédi's regularity in the sparse setting

Supported by Swiss National Science Foundation (SNF) grants 200021-108158 and 200020-119918 (PI A. Steger)

One of the most celebrated results in modern graph theory is Szemerédi's regularity lemma which states, roughly speaking, that every sufficiently large graph contains a large subgraph with a certain regular structure. In this project we are concerned with a version of Szemerédis regularity lemma, which applies to graphs on n vertices and o(n^2) edges and which again guarantees a large regular substructure. Our specific interest is in whether a given fixed graph is contained in (almost all) substructures guaranteed by the regularity lemma. A 1997 conjecture to this effect by Kohayakawa, Luczak and Rödl has known implications for extremal properties of random graphs, and in the book 'Random graphs' by Janson, Luczak and Rucinski this conjecture is called"the main probabilistic problem concerning extremal properties of random graphs (and we believe, one of the most important open questions in the theory of random graphs)" (Conjecture 8.35, p.232). We are also interested in algorithmic aspects of the sparse version of the regularity lemma. In the dense case it is well known that there exists a polynomial time algorithm that finds a partition guaranteed by Szemerédi's regularity lemma, and for example approximation algorithms for the MAX-CUT problem are based on this algorithm. In the sparse case nothing is known: neither that there exists a polynomial-time algorithm that finds a regular structure guaranteed by the sparse regularity lemma, nor, for example, that this problem is NP-hard.

Average Case Analysis of Algorithms

Supported by grant 464/4-1 of Deutsche Forschungsgemeinschaft and by Swiss National Science Foundation (SNF) grant 20021-107880/1 (PI A. Steger)

One of the central questions in theoretical computer science is the analysis of algorithms. Here one distinguishes between worst case analysis, which allows statements about the behaviour of the algorithm for the worst possible input, and average case analysis, which considers the average behaviour of the algorithm. From a practical point of view the latter is in particular important if the worst case analysis does not provide good bounds: it is possible that the algorithm provides empirically good results, even though it has a bad worst case behaviour. The sorting algorithm QuickSort is a well known example for this phenomenon. While its running time is quadratic in the worst case, its average case behaviour is much better. Unfortunately, this algorithm is also one of the few examples where such a phenomenon has been strictly analysed so far. The aim of this project is therefore to develop new models and analysis methods for the average case analysis of algorithms.