Search

Considerable research efforts have recently been made to show that a random neural network $N$ contains subnetworks capable of accurately approximating any given neural network that is sufficiently smaller than $N$, without any training. This line of research, known as the Strong Lottery Ticket Hypothesis (SLTH), was originally motivated by the weaker Lottery Ticket Hypothesis, which states that a sufficiently large random neural network $N$ contains \emph{sparse} subnetworks that can be trained efficiently to achieve performance comparable to that of training the entire network $N$. Despite its original motivation, results on the SLTH have so far not provided any guarantee on the size of subnetworks. Such limitation is due to the nature of the main technical tool leveraged by these results, the Random Subset Sum (RSS) Problem. Informally, the RSS Problem asks how large a random i.i.d. sample $\Omega$ should be so that we are able to approximate any number in $[-1,1]$, up to an error of $ \epsilon$, as the sum of a suitable subset of $\Omega$. We provide the first proof of the SLTH in classical settings, such as dense and equivariant networks, with guarantees on the sparsity of the subnetworks. Central to our results, is the proof of an essentially tight bound on the Random Fixed-Size Subset Sum Problem (RFSS), a variant of the RSS Problem in which we only ask for subsets of a given size, which is of independent interest.

We consider 3-Majority, a probabilistic consensus dynamics on a complete graph with $n$ vertices, each vertex starting with one of $k$ initial opinions. At each discrete time step, a vertex $u$ is chosen uniformly at random. The selected vertex $u$ chooses three neighbors $v_1,v_2,v_3$ uniformly at random with replacement and takes the majority opinion held by the three, where ties are broken in favor of the opinion of $v_3$. The main quantity of interest is the consensus time, the number of steps required for all vertices to hold the same opinion. This asynchronous version turns out to be considerably harder to analyze than the synchronous version and so far results have only been obtained for $k=2$. Even in the synchronous version the results for large $k$ are far from tight. In this paper we prove that the consensus time is $\tilde{\Theta}( \min(nk,n^{1.5}) )$ for all $k$. These are the first bounds for all $k$ that are tight up to a polylogarithmic factor., Comment: Symposium on Discrete Algorithms (SODA25)

We investigate the dynamics of opinion formation on social networking platforms, focusing on how individual opinions, influenced by both social connections and platform algorithms, evolve. We model this process using a differential equation, accounting for both peer influence and the platform's content curation based on user preferences. Our primary aim is to analyze how these factors contribute to opinion polarization and identify potential strategies for its mitigation. We explore the conditions under which opinions converge to a consensus or remain polarized, emphasizing the role of the platform's influence function. Our findings in two-agent, complete graphs, and stochastic block model provide insights into the impact of social media algorithms on public discourse and offer a framework for understanding how polarization can be avoided.

Prophet inequalities are a central object of study in optimal stopping theory. In the iid model, a gambler sees values in an online fashion, sampled independently from a given distribution. Upon observing each value, the gambler either accepts it as a reward or irrevocably rejects it and proceeds to observe the next value. The goal of the gambler, who cannot see the future, is maximising the expected value of the reward while competing against the expectation of a prophet (the offline maximum). In other words, one seeks to maximise the gambler-to-prophet ratio of the expectations. This model has been studied with infinite, finite and unknown number of values. When the gambler faces a random number of values, the model is said to have random horizon. We consider the model in which the gambler is given a priori knowledge of the horizon's distribution. Alijani et al. (2020) designed a single-threshold algorithms achieving a ratio of $1/2$ when the random horizon has an increasing hazard rate and is independent of the values. We prove that with a single-threshold, a ratio of $1/2$ is actually achievable for several larger classes of horizon distributions, with the largest being known as the $\mathcal{G}$ class in reliability theory. Moreover, we extend this result to its dual, the $\overline{\mathcal{G}}$ class (which includes the decreasing hazard rate class), and to low-variance horizons. Finally, we construct the first example of a family of horizons, for which multiple thresholds are necessary to achieve a nonzero ratio. We establish that the Secretary Problem optimal stopping rule provides one such algorithm, paving the way towards the study of the model beyond single-threshold algorithms., Comment: 54 pages, 2 figures

We examine sorting algorithms for $n$ elements whose basic operation is comparing $t$ elements simultaneously (a $t$-comparator). We focus on algorithms that use only a single round or two rounds -- comparisons performed in the second round depend on the outcomes of the first round comparators. We design deterministic and randomized algorithms. In the deterministic case, we show an interesting relation to design theory (namely, to 2-Steiner systems), which yields a single-round optimal algorithm for $n=t^{2^k}$ with any $k\ge 1$ and a variety of possible values of $t$. For some values of $t$, however, no algorithm can reach the optimal (information-theoretic) bound on the number of comparators. For this case (and any other $n$ and $t$), we show an algorithm that uses at most three times as many comparators as the theoretical bound. We also design a randomized Las-Vegas two-rounds sorting algorithm for any $n$ and $t$. Our algorithm uses an asymptotically optimal number of $O(\max(\frac{n^{3/2}}{t^2},\frac{n}{t}))$ comparators, with high probability, i.e., with probability at least $1-1/n$. The analysis of this algorithm involves the gradual unveiling of randomness, using a novel technique which we coin the binary tree of deferred randomness.

We introduce the concept of community consensus in the presence of malicious agents using a well-known median-based consensus algorithm. We consider networks that have multiple well-connected regions that we term communities, characterized by specific robustness and minimum degree properties. Prior work derives conditions on properties that are necessary and sufficient for achieving global consensus in a network. This, however, requires the minimum degree of the network graph to be proportional to the number of malicious agents in the network, which is not very practical in large networks. In this work, we present a natural generalization of this previous result. We characterize cases where, although global consensus is not reached, some subsets of agents $V_i$ will still converge to the same values $M_i$ among themselves. To reach this new type of consensus, we define more relaxed requirements in terms of the number of malicious agents in each community, and the number $k$ of edges connecting an agent in a community to agents external to the community.

We continue our study from Lynch and Mallmann-Trenn (Neural Networks, 2021), of how concepts that have hierarchical structure might be represented in brain-like neural networks, how these representations might be used to recognize the concepts, and how these representations might be learned. In Lynch and Mallmann-Trenn (Neural Networks, 2021), we considered simple tree-structured concepts and feed-forward layered networks. Here we extend the model in two ways: we allow limited overlap between children of different concepts, and we allow networks to include feedback edges. For these more general cases, we describe and analyze algorithms for recognition and algorithms for learning.

Prophet inequalities are a central object of study in optimal stopping theory. A gambler is sent values in an online fashion, sampled from an instance of independent distributions, in an adversarial, random or selected order, depending on the model. When observing each value, the gambler either accepts it as a reward or irrevocably rejects it and proceeds to observe the next value. The goal of the gambler, who cannot see the future, is maximising the expected value of the reward while competing against the expectation of a prophet (the offline maximum). In other words, one seeks to maximise the gambler-to-prophet ratio of the expectations. The model, in which the gambler selects the arrival order first, and then observes the values, is known as Order Selection. In this model a ratio of $0.7251$ is attainable for any instance. Recently, this has been improved up to $0.7258$ by Bubna and Chiplunkar (2023). If the gambler chooses the arrival order (uniformly) at random, we obtain the Random Order model. The worst case ratio over all possible instances has been extensively studied for at least $40$ years. In a computer-assisted proof, Bubna and Chiplunkar (2023) also showed that this ratio is at most $0.7254$ for the Random Order model, thus establishing for the first time that carefully choosing the order, instead of simply taking it at random, benefits the gambler. We give an alternative, non-simulation-assisted proof of this fact, by showing mathematically that in the Random Order model, no algorithm can achieve a ratio larger than $0.7235$. This sets a new state-of-the-art hardness for this model, and establishes more formally that there is a real benefit in choosing the order., Comment: 38 pages, 2 figures

Coordination in a large number of networked robots is a challenging task, especially when robots are constantly moving around the environment and there are malicious attacks within the network. Various approaches in the literature exist for detecting malicious robots, such as message sampling or suspicious behavior analysis. However, these approaches require every robot to sample every other robot in the network, leading to a slow detection process that degrades team performance. This paper introduces a method that significantly decreases the detection time for legitimate robots to identify malicious robots in a scenario where legitimate robots are randomly moving around the environment. Our method leverages the concept of ``Dynamic Crowd Vetting" by utilizing observations from random encounters and trusted neighboring robots' opinions to quickly improve the accuracy of detecting malicious robots. The key intuition is that as long as each legitimate robot accurately estimates the legitimacy of at least some fixed subset of the team, the second-hand information they receive from trusted neighbors is enough to correct any misclassifications and provide accurate trust estimations of the rest of the team. We show that the size of this fixed subset can be characterized as a function of fundamental graph and random walk properties. Furthermore, we formally show that as the number of robots in the team increases the detection time remains constant. We develop a closed form expression for the critical number of time-steps required for our algorithm to successfully identify the true legitimacy of each robot to within a specified failure probability. Our theoretical results are validated through simulations demonstrating significant reductions in detection time when compared to previous works that do not leverage trusted neighbor information., Comment: 9 pages, 5 figures, extended version of paper submitted to the IEEE Conference on Decision and Control (CDC 2023)

We consider two simple asynchronous opinion dynamics on arbitrary graphs where every node $u$ has an initial value $\xi_u(0)$. In the first process, the NodeModel, at each time step $t\ge 0$, a random node $u$ and a random sample of $k$ of its neighbours $v_1,v_2,\cdots,v_k$ are selected. Then, $u$ updates its current value $\xi_u(t)$ to $\xi_u(t+1) = \alpha \xi_u(t) + \frac{(1-\alpha)}{k} \sum_{i=1}^k \xi_{v_i}(t)$, where $\alpha \in (0,1)$ and $k\ge 1$ are parameters of the process. In the second process, the EdgeModel, at each step a random pair of adjacent nodes $(u,v)$ is selected, and then node $u$ updates its value equivalently to the NodeModel with $k=1$ and $v$ as the selected neighbour. For both processes, the values of all nodes converge to $F$, a random variable depending on the random choices made in each step. For the NodeModel and regular graphs, and for the EdgeModel and arbitrary graphs, the expectation of $F$ is the average of the initial values $\frac{1}{n}\sum_{u\in V} \xi_u(0)$. For the NodeModel and non-regular graphs, the expectation of $F$ is the degree-weighted average of the initial values. Our results are two-fold. We consider the concentration of $F$ and show tight bounds on the variance of $F$ for regular graphs. We show that, when the initial values do not depend on the number of nodes, then the variance is negligible, hence the nodes are able to estimate the initial average of the node values. Interestingly, this variance does not depend on the graph structure. For the proof we introduce a duality between our processes and a process of two correlated random walks. We also analyse the convergence time for both models and for arbitrary graphs, showing bounds on the time $T_\varepsilon$ required to make all node values `$\varepsilon$-close' to each other. Our bounds are asymptotically tight under assumptions on the distribution of the initial values., Comment: 21 pages, 6 figures

Among the various aspects of algorithmic fairness studied in recent years, the tension between satisfying both \textit{sufficiency} and \textit{separation} -- e.g. the ratios of positive or negative predictive values, and false positive or false negative rates across groups -- has received much attention. Following a debate sparked by COMPAS, a criminal justice predictive system, the academic community has responded by laying out important theoretical understanding, showing that one cannot achieve both with an imperfect predictor when there is no equal distribution of labels across the groups. In this paper, we shed more light on what might be still possible beyond the impossibility -- the existence of a trade-off means we should aim to find a good balance within it. After refining the existing theoretical result, we propose an objective that aims to balance \textit{sufficiency} and \textit{separation} measures, while maintaining similar accuracy levels. We show the use of such an objective in two empirical case studies, one involving a multi-objective framework, and the other fine-tuning of a model pre-trained for accuracy. We show promising results, where better trade-offs are achieved compared to existing alternatives.