The jury for Prize met on Monday, September 28, 2020. The result of the deliberations is as follows.
Two first prizes were awarded (in alphabetical order) to:
- Denis ANTIPOV, LIX, Institut Polytechnique de Paris, for the article « Fast mutation in crossover-based algorithms ».
Denis ANTIPOV got his bachelor degree in 2014 and his master degree in 2016, both in applied mathematics, and both in ITMO University (St. Petersburg, Russia). In 2020 he got his PhD in computer science after a joint supervision program between Ecole Polytechnique and ITMO University. His is working in the field of theory of evolutionary computation, mostly analysing the population-based evolutionary algorithms.
Most optimization algorithms have one or multiple parameters. Finding parameters’ values which yield the best performance of an optimization algorithm on a particular problem is a challenging task. This task becomes even more difficult when the optimal parameters’ values change during the optimization process.
In our work we consider a genetic algorithm and propose to choose its parameters randomly from a power-law distribution in each iteration of the algorithm. This method of parameters selection has been used before, but it was considered only as a cheap way to relieve an algorithm user from choosing the right parameters. However, it was not clear if it can outperform an algorithm with optimal static parameters which are fixed for the whole run.
The surprising result we observed (both theoretically and empirically) in our work is that the proposed lazy method of choosing parameters gives us the asymptotically best possible performance for the considered class of algorithms on a class of benchmark functions. It is even better than the performance of the same algorithms with fixed parameters. This gives us an almost parameterless algorithm which works out from the box allowing the algorithm user not to worry about how to set the parameters for his particular problem.
- Baptiste BROTO, CEA LIST, Université Paris-Saclay, for the article « Variance reduction for estimation of Shapley effects and adaptation to unknown input distribution ». (video here)
Baptiste BROTO did a thesis at CEA Saclay in mathematics and computer science at the STIC doctoral school and is doing an aggregation validation internship to be a teacher at the Cachan high school.
Les effets de Shapley sont des indices de sensibilité globale: ils permettent de quantifier l’influence de chaque variable d’entrée sur la variable de sortie d’un modèle. Dans ce travail, nous proposons de nouveaux estimateurs de ces indices de sensibilité. Lorsque la loi de probabilité du vecteur d’entrée est connue, nous approfondissons l’étude sur l’algorithme déjà existant défini par Song et al. 2016 et nous proposons un nouvel estimateur avec une variance plus faible. Nous nous inspirons de ces estimateurs pour en proposés de nouveaux lorsque la loi de probabilité du vecteur d’entrée est inconnue. Nous fournissons des propriétés asymptotiques de ces estimateurs. Nous appliquons un de ces estimateurs à des données réelles et nous l’avons intégré au package R “sensitivity”
Four accessits were awarded (in alphabetical order) to:
- Nathan DE LARA et Quentin LUTZ (conjointement), LTCI, Institut Polytechnique de Paris for the software « Scikit-network: Open-source software for graph analysis ».
Quentin LUTZ is a graduate of Télécom Paris (engineer) and of the University de Paris-Saclay. He is pursuing a thesis CIFRE at Télécom Paris and Nokia Bell Labs France.
Nathan DE LARA did a thesis in machine learning at the Institut Polytechnique de Paris and is now sub-prefect of Calvados.
Scikit-network is a Python package inspired by scikit-learn for the analysis of large graphs. Graphs are represented by their adjacency matrix in the sparse CSR format of SciPy. The package provides state-of-the-art algorithms for ranking, clustering, classifying, embedding and visualizing the nodes of a graph. High performance is achieved through a mix of fast matrix-vector products (using SciPy), compiled code (using Cython) and parallel processing. The package is distributed under the BSD license, with dependencies limited to NumPy and SciPy. It is compatible with Python 3.6 and newer. Source code, documentation and installation instructions are available online.
- Ali MAATOUK, L2S, Université Paris-Saclay, for the article « On The Age of Information in a CSMA Environment ».
Ali MAATOUK obtained his master and doctorate in electrical engineering at CentraleSupélec in 2017 and 2020. In 2018, 2019 and 2020, he was a visiting doctoral student at the University of Maryland, College Park. He was the recipient of the Labex Digicosme scholarship for academic excellence in 2016 and also regional and national André Blanc-Lapierre awards for the best master’s student in France in the field of electricity and information and communication technologies. His research interests mainly focus on massive MIMO systems, NOMA, the information age and the new notion of data semantics.
L’âge de l’information est une nouvelle mesure de performance qui a été récemment proposée pour les systèmes de communication sans-fil et qui fait l’objet de recherches importantes ces dernières années. La minimisation de cette mesure est largement considérée comme un moyen de maintenir la fraîcheur des informations, qui est un élément vital pour une variété de nouvelles applications dans les réseaux sans-fil (par exemple, la surveillance à distance, les réseaux de véhicules). Notre article “On the Age of Information in a CSMA Environment” examine cette mesure dans un réseau où les utilisateurs utilisent la technique Carrier-Sense-Multiple-Access. CSMA est considérée comme l’une des méthodes de contrôle d’accès au support dans les réseaux sans-fil les plus populaires (par exemple, CSMA est l’algorithme d’accès au support en Wi-Fi). Notre article est le premier travail qui étudie ce type de réseaux théoriquement et fournit des approches optimales qui minimisent l’âge de l’information. Ces résultats ont un impact pratique. En fait, grâce aux résultats de notre article, la mise en œuvre de méthodes de planification en fonction de l’âge dans les réseaux pratiques (par exemple, Wi-Fi) peut être faite.
- Alessio MANSUTTI, LSV, Université Paris-Saclay, for the article « Internal Calculi for Separation Logics ».
Alessio MANSUTTI est un post-doctorant à l’Université de Oxford (UK), où il travaille dans le project ERC ARiAT (Advanced Reasoning in Arithmetic Theories) de Christoph Haase. Auparavant, il était doctorant à l’ENS Paris-Saclay, dans le laboratoire spécification et vérification (LSV), sous la direction de Stéphane Demri et Etienne Lozes.
Dans le papier “Internal calculi for Separation Logics”, co-écrit avec Stéphane Demri et Etienne Lozes, on définit une méthodologie pour définir systèmes de preuve interne et complet pour les logiques de séparation, des logiques pour la vérification de programmes centrées sur l’allocation dynamique de mémoire. Les logiques de séparation sont appliquées avec succès dans l’industrie (voir par exemple l’outil Infer développé par Facebook), car ils sont capable de vérifier de manière modulaire des programmes avec des millions de lignes de code. Notre méthodologie, appelée core formulae technique, utilise des éléments de la théorie des modèles finis pour produire un calcul modulaire. En utilisant cette technique, on a présenté le premier calcul interne pour la logique de séparation sans quantificateurs du premier ordre, et pour une logique de séparation avec “des quantificateurs sur chemins”. Notre méthodologie est réutilisable: dans le papier “Axiomatising Logics with Separating Conjunction and Modalities”, co-écrit avec Stéphane Demri et Raul Fervari, on a défini des calculs internes pour deux logiques modales enrichies avec le connecteurs sous-structurel ∗ de la logique de séparation.
- Homa NIKBAKTH, LTCI, Institut Polytechnique de Paris, for the article « Multiplexing Gains under Mixed-Delay Constraints on Wyner’s Soft-Handoff Model »
Homa NIKBAKHT obtained is thesis at IP Paris in december 2020 and is now pursuing a Post doctorate at INRIA
This paper analyzes the multiplexing gains (MG) achievable over Wyner’s soft-handoffmodel under mixed-delay constraints, that is, when delay-sensitive and delay-tolerant data are simultaneously transmitted over the network. In the considered model, delay-sensitive data cannot participate or profit in any ways from transmitter or receiver cooperation, but delay-tolerant data can.Cooperation for delay-tolerant data takes place over rate-limited links and is limited to a fixed number of cooperation rounds. For the described setup, inner and outer bounds are derived on the set of MG pairs that are simultaneously achievable for delay-sensitive and delay-tolerant data. The bounds are tight in special cases and allow us to obtain the following conclusions. For large cooperation rates, and when both transmitters and receivers can cooperate, it is possible to simultaneously attain maximum MG for delay-sensitive messages and maximum sum MG for all messages. For comparison, in scheduling schemes (also called time-sharing schemes), the largest achievable sum MG decreases linearly with the MG of delay-sensitive messages.