Kolmogorov meets Turing

*Workshop on probabilistic methods for the analysis of stochastic processes and randomized algorithms*

This year's edition of the Kolmogorov meets Turing Workshop will take place on Thursday, May 23rd 2024, at DIAG https://www.diag.uniroma1.it/, via Ariosto 25, Aula Magna I floor. The purpose of KmT is to bring together researchers from Computer Science, Economics, Mathematics and related fields to present and discuss research on probabilistic methods for the analysis of games, distributed and stochastic processes, dynamic processes and randomized algorithms.

When: Thursday May 23rd, 2024

Where: Dipartimento di Ingegneria Informatica, Automatica e Gestionale “A. Ruberti”, via

Ariosto 25, Roma – Aula Magna, I floor

Schedule

Morning session

11.00 – 12.00. Nicolò Cesa-Bianchi (Università degli Studi di Milano): The mathematics of machine learning: between statistics and game theory

12.00 – 12.30. Xavier Mathieu Raymond Venel (Luiss University): Weighted average-convexity in Cooperative Games

12.30 – 13.00. Guido Schaefer (CWI, Netherlands): To Trust or Not to Trust: Assignment Mechanisms with Predictions

13.00 – 14.30: Lunch break

Afternoon session

14.30 – 15.00. Pietro Caputo (University Roma Tre): Nonlinear Monte Carlo dynamics for the Ising model: some convergence results

15.00 – 15.30. Matteo Quattropani (Sapienza University of Rome): Mixing of the Averaging process on graphs and hypergraphs

15.30 – 16.00. Robin Vacus (Bocconi University): Minority Dynamics: the Short and Winding Road to Consensus

16.00 – 16.30: Coffee break 16.30 – 17.00. Maria Sofia Bucarelli (Sapienza University of Rome): On Generalization

Bounds for Projective Clustering

17.00 – 17.30. Francesco D'Amore (Bocconi University): The Strong Lottery Ticket Hypothesis and the Random Subset Sum Problem

17.30 – 18.00. Federico Fusco (Sapienza University of Rome): The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations

_______________________________________________________

LIST OF ABSTRACTS

Maria Sofia Bucarelli: On Generalization Bounds for Projective Clustering. Given a set of points, clustering consists of finding a partition of a point set into k clusters such that the center to which a point is assigned is as close as possible. Most commonly, centers are points themselves, which leads to the famous k-median and k-means objectives. One may also choose centers to be j dimensional subspaces, which gives rise to subspace clustering. In this paper, we consider learning bounds for these problems. That is, given a set of n samples P drawn independently from some unknown, but fixed distribution D, how quickly does a solution computed on P converge to the optimal clustering of D? We give several near p optimal results. In particular, 1) For center-based objectives, we show a convergence rate of O(√k/n). This matches the known optimal bounds of [Fefferman, Mitter, and Narayanan, Journal of the Mathematical Society 2016] and [Bartlett, Linder, and Lugosi, IEEE Trans. Inf. Theory 1998] for k-means and extends it to other important objectives such as k-median. 2) For subspace clustering with j-dimensional subspaces, we show a convergence rate of O(√kj2/n). These are the first provable bounds for most of these problems. For the specific case of projective clustering, which generalizes k-means, we show a converge rate of Ω(√kj/n) is necessary, thereby proving that the bounds from [Fefferman, Mitter, and Narayanan, Journal of the Mathematical Society 2016] are essentially optimal.

Nicolò Cesa-Bianchi: The mathematics of machine learning: between statistics and game theory. Machine learning is the main driving force behind the current AI revolution. To provide a solid mathematical foundation to learning systems, we must formally characterize what a machine can learn and what is the minimal amount of training data needed to achieve a desired performance. In this talk, I will describe the two main approaches to algorithmic learnability, one rooted in statistics and one in game theory, and explore their connections.

Pietro Caputo: Nonlinear Monte Carlo dynamics for the Ising model: some convergence results. We introduce and analyze a natural class of nonlinear Monte Carlo dynamics for spin systems such as the Ising model. The evolution is based on the framework of mass action kinetics, which models systems undergoing collisions, and captures a number of nonlinear models from various fields, including chemical reaction networks, Boltzmann’s model of an ideal gas, recombination in population genetics and genetic algorithms. In the context of spin systems, it is a nonlinear analog of the familiar Monte Carlo method based on Markov chains, such as Glauber dynamics and block dynamics, which are by now well understood. The nonlinearity makes the dynamics much harder to analyze, and even the most basic convergence issues are far from being settled. We discuss several open problems. The main result is an optimal estimate on the rate of convergence to stationarity in a regime of high temperature. Our analysis combines tools from percolation, branching and fragmentation processes.

Based on joint work with Alistair Sinclair.

Francesco D’Amore: The Strong Lottery Ticket Hypothesis and the Random Subset Sum Problem. 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. (ICML ’20), Pensia et al. (NeurIPS ’20), da Cunha et al. (ICLR ’20), and Burkholz (ICML & ICLR ’22) 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 A. Da Cunha and E. Natale appeared at NeurIPS 2023.

Federico Fusco: The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations. We study the problem of regret minimization for a single bidder in a sequence of first-price auctions where the bidder discovers the item’s value only if the auction is won. Our main contribution is a complete characterization, up to logarithmic factors, of the minimax regret in terms of the auction’s transparency, which controls the amount of information on competing bids disclosed by the auctioneer at the end of each auction. Our results hold under different assumptions (stochastic, adversarial, and their smoothed variants) on the environment generating the bidder’s valuations and competing bids. These minimax rates reveal how the interplay between transparency and the nature of the environment affects how fast one can learn to bid optimally in first-price auctions.

The talk is based on a joint work with Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, and Stefano Leonardi, which will appear at STOC 2024.

Matteo Quattropani: Mixing of the Averaging process on graphs and hypergraphs.

The Averaging process is a mass redistribution process over the vertex set of a graph or, more generally, a hypergraph. Given a (hyper)graph G, the process starts with a non-negative mass associated with each vertex. At each discrete time step, one of the (hyper)edges of G is sampled at random and the total mass associated with the vertices of the chosen (hyper)edge is equally redistributed among its vertices. Clearly, as time grows to infinity, the state of the system will converge to a flat configuration in which all the vertices have the same mass. This very simple process appeared in different literatures under various names, and it was introduced to the probabilistic community by Aldous and Lanoue in 2012. However, until a few years ago, there were no sharp quantitative results on the time needed to reach equilibrium. Indeed, the analysis of this process requires different tools compared to the classical Markov chain framework, and even in the case of seemingly straightforward geometries—such as the complete graph or the cycle—it can be handled only by means of nontrivial probabilistic and functional analytic techniques. During the talk, I’ll give an overview of the problem and its difficulties, present the classes of examples that are currently settled, and mention some possible future directions of investigation.

Based on joint work with Pietro Caputo and Federico Sau.

Guido Schaefer: To Trust or Not to Trust: Assignment Mechanisms with Predictions.

The realm of algorithms with predictions has led to the development of several new algorithms that leverage (potentially erroneous) predictions to enhance their performance guarantees. The challenge here is to devise algorithms that achieve optimal approximation

guarantees as the prediction quality varies from perfect (consistency) to imperfect (robustness). This framework is particularly appealing in mechanism design contexts, where predictions might convey private information about the agents. In this talk, we present our recent results on the design of truthful mechanisms that leverage predictions to achieve improved approximation guarantees for several variants of the generalized assignment problem (GAP). We consider the private graph model introduced by Dughmi and Ghosh (2010), where the set of resources that an agent is compatible with is private information. We investigate GAP in the private graph model augmented with a prediction of the optimal assignment. We give a deterministic group-strategyproof mechanism that is (1 + 1/γ)-consistent and (1 + γ)-robust for the special case of bipartite matching, where γ ≥ 1 is some confidence parameter. We also prove that this is best possible. Remarkably, our mechanism draws inspiration from the renowned Gale-Shapley algorithm, incorporating predictions as a crucial element. For more general GAP variants, we introduce a unified greedy scheme and use randomization to derive universally group-strategyproof mechanisms that achieve improved consistency and robustness guarantees in expectation.

Robin Vacus: Minority Dynamics: the Short and Winding Road to Consensus. The ”minority” rule is a peculiar opinion dynamics, which prompts agents to adopt the opinion least represented in a sample – in contrast to its far more famous and natural counterpart, the majority rule. Yet, as long as the sample size is large enough and communications happen in parallel, it proves to be an efficient way to reach agreement. Moreover, contrary to traditional consensus protocols, it demonstrates extreme sensitivity to even a small number of ”stubborn” individuals, enabling fast information propagation within the group. In this presentation, I will describe an analysis of convergence time, showcase simulation results, and discuss several open problems, shedding light on what is currently understood and what remains to be explored about this fascinating dynamic.

This talk is based on a recent work with Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan and Isabella Ziccardi, that was published in SODA 2024.

Xavier Mathieu Raymond Venel: Weighted average-convexity in Cooperative Games.

It is well known that the Shapley value of a convex game always belongs to the core. Looking for a weaker condition than convexity insuring that the Shapley value of a game lies in the core, Inarra and Usategui (1993) relaxed the convexity assumption by introducing the notion of average convexity. Assuming that weights are associated with the players, we generalize the notion of convexity and average-convexity for cooperative TU games to the notion of weighted average-convexity. We prove that if a game is weighted average-convex, then the corresponding weighted Shapley value is in the core. We then study the relations between weighted average-convexity, core-inclusion, and communication TU-games. We exhibit necessary and sufficient conditions on the underlying graph to preserve weighted average-convexity from any communication game to the associated Myerson restricted game, extending some previous results established in Slikker (1998).

Joint work with Alexandre Skoda.