13 papers
A Unified Framework for Quantized and Continuous Strong Lottery Tickets
Aakash Kumar, Emanuele Natale
The Strong Lottery Ticket Hypothesis (SLTH) asserts that sufficiently overparameterized, randomly initialized neural networks contain sparse subnetworks that, even without any trai…
Compositional Generalization in Autoregressive Models via Logit Composition
Aakash Kumar, Maria Sofia Bucarelli, Emanuele Natale
Composing autoregressive models remains a core challenge in understanding how large language models can combine behaviors or skills learned across tasks. We introduce a new and pri…
Beyond Fixed Points: Superpolynomial Capacity of Asymmetric Hopfield Networks
Aakash Kumar, Anatoly Khina, Frederik Mallmann-Trenn +1
Classical Hopfield networks are limited to static patterns due to symmetric weights, whereas asymmetric networks can encode temporal sequences via limit-cycle attractors. Achieving…
DejaVu: A Minimalistic Mechanism for Distributed Plurality Consensus
Francesco d'Amore, Niccolò D'Archivio, George Giakkoupis +2
We study the plurality consensus problem in distributed systems where a population of extremely simple agents, each initially holding one of opinions, aims to agree on the init…
Intermittent Cauchy walks enable optimal 3D search across target shapes and sizes
Matteo Stromieri, Emanuele Natale, Amos Korman
Efficiently locating rare targets requires balancing the exploration of novel space with the exploitation of local vicinities. While this tradeoff is well-documented in simplified…
Structured vs. Unstructured Pruning: An Exponential Gap
Davide Ferre', Frédéric Giroire, Frederik Mallmann-Trenn +1
The Strong Lottery Ticket Hypothesis (SLTH) states that large, randomly initialized neural networks contain sparse subnetworks capable of approximating a target function at initial…
Quantization vs Pruning: Insights from the Strong Lottery Ticket Hypothesis
Aakash Kumar, Emanuele Natale
Quantization is an essential technique for making neural networks more efficient, yet our theoretical understanding of it remains limited. Previous works demonstrated that extremel…
Threshold-Driven Streaming Graph: Expansion and Rumor Spreading
Flora Angileri, Andrea Clementi, Emanuele Natale +2
A randomized distributed algorithm called RAES was introduced in [Becchetti et al., SODA 2020] to extract a bounded-degree expander from a dense -vertex expander graph $G = (V,…
On the -majority dynamics with many opinions
Francesco d'Amore, Niccolò D'Archivio, George Giakkoupis +1
We present the first upper bound on the convergence time to consensus of the well-known -majority dynamics with opinions, in the synchronous setting, for and that ar…
Trading-off Accuracy and Communication Cost in Federated Learning
Mattia Jacopo Villani, Emanuele Natale, Frederik Mallmann-Trenn
Leveraging the training-by-pruning paradigm introduced by Zhou et al. and Isik et al. introduced a federated learning protocol that achieves a 34-fold reduction in communication co…
Fast and Robust Information Spreading in the Noisy PULL Model
Niccolò D'Archivio, Amos Korman, Emanuele Natale +1
Efficient information spreading in stochastic multi agent systems is a core challenge when communication is noisy, bandwidth limited, and agents lack global coordination. Yet biolo…
On the Sparsity of the Strong Lottery Ticket Hypothesis
Emanuele Natale, Davide Ferre', Giordano Giambartolomei +2
Considerable research efforts have recently been made to show that a random neural network contains subnetworks capable of accurately approximating any given neural network tha…
Polynomially Over-Parameterized Convolutional Neural Networks Contain Structured Strong Winning Lottery Tickets
Arthur da Cunha, Francesco d'Amore, Emanuele Natale
The Strong Lottery Ticket Hypothesis (SLTH) states that randomly-initialised neural networks likely contain subnetworks that perform well without any training. Although unstructure…