14h00 - Francesco D'Amore (Aalto University, Espoo)
"The Strong Lottery Ticker Hypothesis and the Random Subset Sum Problem”
Abstract: The Strong Lottery Ticket Hypothesis (SLTH) posits that randomly-initialized neural networks contain subnetworks (strong lottery tickets) that achieve competitive accuracy when compared to sufficiently small target networks, even those that have been trained. Empirical evidence for this phenomenon was first observed by Ramanujan et al. in 2020, spurring a line of theoretical research: Malach et al. (2020), Pensia et al. (2020), da Cunha et al. (2022), and Burkholz (2022) have analytically proved formulations of the SLTH in various neural network classes and under different hypotheses.
In this presentation, we provide an overview of the state-of-the-art theoretical research on the SLTH and its connection with the Random Subset Sum (RSS) problem in theoretical computer science. While previous works on the SLTH ensure that the strong lottery ticket can be obtained via unstructured pruning, we demonstrate how recent advances in the multidimensional generalization of the RSS problem can be leveraged to obtain forms of structured pruning. Additionally, we highlight how refining the RSS results would yield tighter formulations of the SLTH.
This presentation is based on a joint work with Arthur da Cunha and Emanuele Natale that will be presented at NeurIPS 2023.
15h00 - Isabella Ziccardi (Bocconi)
"Distributed Self-Stabilizing MIS Algorithms"
Abstract:
I will discuss self-stabilizing distributed algorithms that find a Maximal Independent Set in an n-vertex graph. These algorithms share the feature of utilizing randomization to break symmetry. I will compare them based on the following parameters: the number of states used by each node, the knowledge of the graph required by each node, and their stabilization time. The first three algorithms are obtained by reconsidering some existing algorithms and making them self-stabilizing by introducing additional states. The first algorithm gets along with three states, but each node must have knowledge of ∆, the maximum node degree. In the second algorithm, nodes only need to be aware of their degree, but each node v has O(∆(v)) states, where ∆(v) is the degree of v. The third algorithm also requires O(∆(v)) states for each node v, but it works in the restricted beeping communication model. All three algorithms stabilize in O(log n) rounds with high probability. Lastly, I will talk about two algorithms that aim to create self-stabilizing algorithms with a constant number of states while requiring no knowledge of the underlying graph. The first algorithm is a natural process that, despite its simplicity, has received limited attention in the literature. It stabilizes in O(polylog(n)) rounds for specific graph families but may exhibit slower convergence time on general graphs. The final algorithm is a modification of this simple process, that tries to fix the particular situations that slow down the convergence.
We encourage in-person partecipation. Should you be unable to come, here is the link to the Teams streaming:
https://teams.microsoft.com/l/meetup-join/19%3arfsL73KX-fw86y1YnXq2nk5VnZFwPU-iIPEmqet8NCg1%40thread.tacv2/1697449913833?context={"Tid"%3a"24c5be2a-d764-40c5-9975-82d08ae47d0e"%2c"Oid"%3a"650fc4a8-4cec-4bd2-87bc-90d134074fe6"}
The seminar is part of the Excellence Project MatMod@TOV.