New generations of mobile access networks promise low delay and high-speed throughput data connections paired with in-network processing capabilities. IoT data and local information available to users’ devices will feed AI-based applications executed in proximity on edge servers and service composition will routinely include such applications and their microservice components. PARFAIT tackles new resource allocation problems emerging due to the need of distributed edge orchestration of both computing and communication, in a context where the unknown footprint of AI-based applications requires advanced learning capabilities to permit efficient and reliable edge service orchestration. The PARFAIT project develops theoretical foundations for distributed and scalable resource allocation schemes on edge computing infrastructures tailored for AI-based processing tasks. Algorithmic solutions will be developed based on the theory of constrained, delayed, and distributed Markov decision processes to account for edge service orchestration actions and quantify the effect of orchestration policies. Furthermore, using both game and team formulations, the project will pave the way for a theory of decentralized orchestration, a missing building block necessary to match the application quest for data proximity and the synchronization problems that arise when multiple edge orchestrators cooperate under local or partial system view. Finally, to achieve efficient online edge service orchestration, such solutions will be empowered with reinforcement learning techniques to define a suit of orchestration algorithms able to at once adapt over time to the applications’ load and cope with the uncertain information available from AI-based applications’ footprints. Validation activities will be designed to demonstrate real-world solutions for practical orchestration use cases, using both large scale simulation experiments and research testbeds.

Directed graph (a.k.a. digraph) theory is a lot less developed than (undirected) graph theory and there is a lack of algorithmically meaningful structural theory for digraphs. The objectives of the project is to make some advances on digraph theory in order to get a better understanding of important aspects of digraphs and to have more insight on the differences and the similarities between graphs and digraphs. Our methodology is two-fold. On the one hand, we will consider results on graphs, find their (possibly many) formulations in terms of digraphs and see if and how they can be extended. Studying such extensions has been occasionally done, but the point here is to do it in a kind of systematic way. We will mainly focus on substructures in digraphs (complexity and conditions of existence) and extensions of graph colouring problems to digraphs. On the other hand, we will focus on the tools. We believe that many proof techniques have been too rarely used or adapted to digraphs and can be developed to obtain many more results. This in particular the case of median and cyclic order, the canonical decomposition of digraphs arising from matroids, the different notions of treewidth for digraphs, structural decomposition theorem, entropy compression and VC-deimension. Of course, those two approaches are not mutually exclusive but converge. Our goal is to develop the techniques to make advances in the above mentioned topics.

We aim to explore algorithmic and structural questions related to twin-width, a novel graph and matrix invariant, introduced and developed by the team. Twin-width has already led to progress for questions in algorithmic graph theory (such as the complexity of first-order model checking on hereditary classes of binary structures) and combinatorics (for instance, on the growth of hereditary classes of ordered graphs). Classes with bounded twin-width are rather "orthogonal" to the current organization of graph theory. They include classes excluding a fixed minor but not bounded-degree graphs, unit interval graphs but not all the interval graphs, as well as some expander classes whereas random cubic graphs almost surely have large twin-width. The main questions that we will tackle comprise the existence of an approximation algorithm for twin-width, the generalization of the notion to other mathematical objects, fast computations on matrices with bounded twin-width, and revisiting classical problems in combinatorics through the lens of twin-width.

Solid algorithmic and mathematical foundations are essential to endow AI systems with guaranteed utility, resource-efficiency and trustworthiness. Exploiting massive data streams requires controlling the tradeoffs between performance and computational footprint. For example, sensors for autonomous vehicles generate terabytes of data per day per car. Another constraint is to comply with European regulation (GDPR) e.g. to ensure privacy when captured video streams feature pedestrians or licence plates. Similar constraints arise for AI systems that learn biomarkers from sensitive medical imaging data, with an even stronger emphasis on privacy-preservation, performance guarantees, and robustness in adversarial settings. AllegroAssai will address the fundamental scientific challenge of designing AI techniques endowed not only with solid statistical guarantees (to ensure their performance, fairness, privacy, etc.) but also with provable resource-efficiency (e.g. in terms of bytes and flops, which impact energy consumption and hardware costs), robustness in adversarial conditions for secure performance, and ability to leverage domain-specific models and expert knowledge. The vision of AllegroAssai is that the versatile notion of sparsity, together with sketching techniques using random features, are key in harnessing the fundamental tradeoffs of AI. The first pillar of the project will be to investigate sparsely connected deep networks, to understand the tradeoffs between the approximation capacity of a network architecture (ResNet, U-net, etc.) and its “trainability” with provably-good algorithms. A major endeavor is to design efficient regularizers promoting sparsely connected networks with provable robustness in adversarial settings. The second pillar revolves around the design and analysis of provably-good end-to-end sketching pipelines for versatile and resource-efficient large-scale learning, with controlled complexity driven by the structure of the data and that of the task rather than the dataset size. To achieve its ambitious goals, AllegroAssai will leverage the modern avatars of the concept of sparsity and combine them with advanced high-dimensional function analysis, information geometry, sketching techniques for dimension reduction by distribution embeddings, and nonconvex optimization. This will be performed through a continuous feedback between theoretical investigations and empirical studies on targeted applications. The resulting computing pipelines will be implemented in software and using optical processing wherever possible to reduce the energy footprint, in an agile process. Software packages for distributed aggregation of sketches, sketched learning, and sparse network learning will be developed to ensure a wide dissemination of the results. Thanks to the developed resource-efficient sketching and sparse network approaches, AllegroAssai will contribute to a more ecological, less-energy consuming AI economy favoring the convergence of the ecological transition and the development of AI. Memory-efficiency and privacy-preservation will allow sharing and aggregating of massive data volumes across actors of the transport industry, further opening the door to new ambitious data policies for transport.

Nowadays, who controls the data, controls the world or at least the IT world. Usually Data are managed through a middleware, but in this project, we propose a new data paradigm without any data manager. We want to endow the data with autonomous behaviors and thus create a new entity, so-called Self-managed data. We plan to develop a distributed and autonomous environment, that we call SKYDATA, where the data are regulated by themselves. This change of paradigm represents a huge and truly innovative challenge! This goal must be built on the foundation of a strong theoretical study and knowledge on autonomic computing, since Self-managed data will now have to obtain and compute the services they need in autonomy. We also plan to actually develop a SKYDATA framework prototype and a green-IT use case that focuses data energy coonsumption. SKYDATA will be compliant with GDPR through the targeted datas and some internal process.