2023Activity reportProject-TeamPOLARIS

2.1 Context

Large distributed infrastructures are rampant in our society. Numerical simulations form the basis of computational sciences and high performance computing infrastructures have become scientific instruments with similar roles as those of test tubes or telescopes. Cloud infrastructures are used by companies in such an intense way that even the shortest outage quickly incurs the loss of several millions of dollars. But every citizen also relies on (and interacts with) such infrastructures via complex wireless mobile embedded devices whose nature is constantly evolving. In this way, the advent of digital miniaturization and interconnection has enabled our homes, power stations, cars and bikes to evolve into smart grids and smart transportation systems that should be optimized to fulfill societal expectations.

Our dependence and intense usage of such gigantic systems obviously leads to very high expectations in terms of performance. Indeed, we strive for low-cost and energy-efficient systems that seamlessly adapt to changing environments that can only be accessed through uncertain measurements. Such digital systems also have to take into account both the users' profile and expectations to efficiently and fairly share resources in an online way. Analyzing, designing and provisioning such systems has thus become a real challenge.

Such systems are characterized by their ever-growing size, intrinsic heterogeneity and distributedness, user-driven requirements, and an unpredictable variability that renders them essentially stochastic. In such contexts, many of the former design and analysis hypotheses (homogeneity, limited hierarchy, omniscient view, optimization carried out by a single entity, open-loop optimization, user outside of the picture) have become obsolete, which calls for radically new approaches. Properly studying such systems requires a drastic rethinking of fundamental aspects regarding the system's observation (measure, trace, methodology, design of experiments), analysis (modeling, simulation, trace analysis and visualization), and optimization (distributed, online, stochastic).

2.2 Objectives

The goal of the POLARIS project is to contribute to the understanding of the performance of very large scale distributed systems by applying ideas from diverse research fields and application domains. We believe that studying all these different aspects at once without restricting to specific systems is the key to push forward our understanding of such challenges and to propose innovative solutions. This is why we intend to investigate problems arising from application domains as varied as large computing systems, wireless networks, smart grids and transportation systems.

The members of the POLARIS project cover a very wide spectrum of expertise in performance evaluation and models, distributed optimization, and analysis of HPC middleware. Specifically, POLARIS' members have worked extensively on:

• Experiment design:
  Experimental methodology, measuring/monitoring/tracing tools, experiment control, design of experiments, and reproducible research, especially in the context of large computing infrastructures (such as computing grids, HPC, volunteer computing and embedded systems).
• Trace Analysis:
  Parallel application visualization (paje, triva/viva, framesoc/ocelotl, ...), characterization of failures in large distributed systems, visualization and analysis for geographical information systems, spatio-temporal analysis of media events in RSS flows from newspapers, and others.
• Modeling and Simulation:
  Emulation, discrete event simulation, perfect sampling, Markov chains, Monte Carlo methods, and others.
• Optimization:
  Stochastic approximation, mean field limits, game theory, discrete and continuous optimization, learning and information theory.

2.3 Contribution to AI/Learning

AI and Learning is everywhere now. Let us clarify how our research activities are positioned with respect to this trend.

A first line of research in POLARIS is devoted to the use of statistical learning techniques (Bayesian inference) to model the expected performance of distributed systems, to build aggregated performance views, to feed simulators of such systems, or to detect anomalous behaviours.

In a distributed context it is also essential to design systems that can seamlessly adapt to the workload and to the evolving behaviour of its components (users, resources, network). Obtaining faithful information on the dynamic of the system can be particularly difficult, which is why it is generally more efficient to design systems that dynamically learn the best actions to play through trial and errors. A key characteristic of the work in the POLARIS project is to leverage regularly game-theoretic modeling to handle situations where the resources or the decision is distributed among several agents or even situations where a centralised decision maker has to adapt to strategic users.

An important research direction in POLARIS is thus centered on reinforcement learning (Multi-armed bandits, Q-learning, online learning) and active learning in environments with one or several of the following features:

• Feedback is limited (e.g., gradient or even stochastic gradients are not available, which requires for example to resort to stochastic approximations);
• Multi-agent setting where each agent learns, possibly not in a synchronised way (i.e., decisions may be taken asynchronously, which raises convergence issues);
• Delayed feedback (avoid oscillations and quantify convergence degradation);
• Non stochastic (e.g., adversarial) or non stationary workloads (e.g., in presence of shocks);
• Systems composed of a very large number of entities, that we study through mean field approximation (mean-field games and mean field control).

As a side effect, many of the gained insights can often be used to dramatically improve the scalability and the performance of the implementation of more standard machine or deep learning techniques over supercomputers.

The POLARIS members are thus particularly interested in the design and analysis of adaptive learning algorithms for multi-agent systems, i.e. agents that seek to progressively improve their performance on a specific task. The resulting algorithms should not only learn an efficient (Nash) equilibrium but they should also be capable of doing so quickly (low regret), even when facing the difficulties associated to a distributed context (lack of coordination, uncertain world, information delay, limited feedback, …)

In the rest of this document, we describe in detail our new results in the above areas.

3.1 Performance Evaluation

Participants: Jonatha Anselmi, Vincent Danjean, Nicolas Gast, Guillaume Huard, Arnaud Legrand, Florence Perronnin, Jean-Marc Vincent.

3.2 Asymptotic Methods

Participants: Jonatha Anselmi, Romain Couillet, Nicolas Gast, Bruno Gaujal, Florence Perronnin, Jean-Marc Vincent.

3.3 Distributed Online Optimization and Learning in Games

Participants: Nicolas Gast, Romain Couillet, Bruno Gaujal, Arnaud Legrand, Patrick Loiseau, Panayotis Mertikopoulos, Bary Pradelski.

3.4 Responsible Computer Science

Participants: Nicolas Gast, Romain Couillet, Bruno Gaujal, Arnaud Legrand, Patrick Loiseau, Panayotis Mertikopoulos, Bary Pradelski.

4.1 Large Computing Infrastructures

Supercomputers typically comprise thousands to millions of multi-core CPUs with GPU accelerators interconnected by complex interconnection networks that are typically structured as an intricate hierarchy of network switches. Capacity planning and management of such systems not only raises challenges in term of computing efficiency but also in term of energy consumption. Most legacy (SPMD) applications struggle to benefit from such infrastructure since the slightest failure or load imbalance immediately causes the whole program to stop or at best to waste resources. To scale and handle the stochastic nature of resources, these applications have to rely on dynamic runtimes that schedule computations and communications in an opportunistic way. Such evolution raises challenges not only in terms of programming but also in terms of observation (complexity and dynamicity prevents experiment reproducibility, intrusiveness hinders large scale data collection, ...) and analysis (dynamic and flexible application structures make classical visualization and simulation techniques totally ineffective and require to build on ad hoc information on the application structure).

4.2 Next-Generation Wireless Networks

Considerable interest has arisen from the seminal prediction that the use of multiple-input, multiple-output (MIMO) technologies can lead to substantial gains in information throughput in wireless communications, especially when used at a massive level. In particular, by employing multiple inexpensive service antennas, it is possible to exploit spatial multiplexing in the transmission and reception of radio signals, the only physical limit being the number of antennas that can be deployed on a portable device. As a result, the wireless medium can accommodate greater volumes of data traffic without requiring the reallocation (and subsequent re-regulation) of additional frequency bands. In this context, throughput maximization in the presence of interference by neighboring transmitters leads to games with convex action sets (covariance matrices with trace constraints) and individually concave utility functions (each user's Shannon throughput); developing efficient and distributed optimization protocols for such systems is one of the core objectives of the research theme presented in Section 3.3.

Another major challenge that occurs here is due to the fact that the efficient physical layer optimization of wireless networks relies on perfect (or close to perfect) channel state information (CSI), on both the uplink and the downlink. Due to the vastly increased computational overhead of this feedback – especially in decentralized, small-cell environments – the continued transition to fifth generation (5G) wireless networks is expected to go hand-in-hand with distributed learning and optimization methods that can operate reliably in feedback-starved environments. Accordingly, one of POLARIS' application-driven goals will be to leverage the algorithmic output of Theme 5 into a highly adaptive resource allocation framework for next-géneration wireless systems that can effectively "learn in the dark", without requiring crippling amounts of feedback.

4.3 Energy and Transportation

Smart urban transport systems and smart grids are two examples of collective adaptive systems. They consist of a large number of heterogeneous entities with decentralised control and varying degrees of complex autonomous behaviour. We develop an analysis tool to help to reason about such systems. Our work relies on tools from fluid and mean-field approximation to build decentralized algorithms that solve complex optimization problems. We focus on two problems: decentralized control of electric grids and capacity planning in vehicle-sharing systems to improve load balancing.

4.4 Social Computing Systems

Social computing systems are online digital systems that use personal data of their users at their core to deliver personalized services directly to the users. They are omnipresent and include for instance recommendation systems, social networks, online medias, daily apps, etc. Despite their interest and utility for users, these systems pose critical challenges of privacy, security, transparency, and respect of certain ethical constraints such as fairness. Solving these challenges involves a mix of measurement and/or audit to understand and assess issues, and modeling and optimization to propose and calibrate solutions.

5.1 Footprint of research activities

We try to keep the carbon footprint of the team has low as possible by a stricter laptop renewal policy and by reducing plane travels (e.g., using visioconference or sometimes by avoiding publishing our research in conferences that would take place on the other side of the planet).

Our team does not train heavy ML models requiring important processing power although some of us perform computer science experiments, mostly using the Grid5000 platforms. We keep this usage very reasonable and rely on cheaper alternatives (e.g., simulations) as much as possible.

5.2 Raising awareness on the climate crisis

Romain Couillet has organized several introductory seminars on the Anthropocene, which he has presented to students at the UGA and Grenoble-INP, as well as to associations in Grenoble (FNE, AgirAlternatif). He is also co-responsible of the Digital Transformation DU. He has published several articles on the issue of "usability" of artificial intelligence. He is also co-creator of the sustainable AI transversal axis of the MIAI project in Grenoble. He connects his professionnal activity with public action (Lowtechlab de Grenoble, Université Autogérée, Arche des Innovateurs, etc). Finally, he is a trainer for the "Fresque du Climat" and a member of Adrastia and FNE Isère.

5.3 Impact of research results

Jean-Marc Vincent is heavily engaged since several years in the training of computer science teachers at the elementary/middle/high school levels 33, 2. Among one of his many activities, we can mention his involvement in the design of the Numérique et Sciences Informatiques, NSI : les fondamentaux MOOC. See section 11.2.1 for more details.

6.1 Awards

Victor Boone and Panayotis Mertikopoulos have received a Spotlight at the NIPS conference for theeir article on The equivalence of dynamic and strategic stability under regularized learning in games 13.

7.1 New software

8.1 Performance evaluation of Large Systems

Participants: Sebastian Allmeier, Thomas Barzola, Vincent Danjean, Arnaud Legrand, Nicolas Gast, Guillaume Huard, Lucas Leandro Nesi, Jean-Marc Vincent.

Visualization strategies are a valuable tool in the performance evaluation of HPC applications. Although the traditional Gantt charts are a widespread and enlightening strategy, it presents scalability problems and may misguide the analysis by focusing on resource utilization alone. In 16, we propose an overview strategy to indicate nodes of interest for further investigation with classical visualizations like Gantt charts. For this, it uses a progression metric that captures work done per node inferred from the task-based structure, a time-step clustering of those metrics to decrease redundant information, and a more scalable visualization technique. We demonstrate with six scenarios and two applications that such a strategy can indicate problematic nodes more straightforwardly while using the same visualization space. Also, we provide examples where it correctly captures application work progression, showing application problems earlier and as an easy way to compare nodes. At the same time that traditional methods are misleading.

This work completes our previous work on performance analysis of task-based applications on heterogeneous platforms and is part of the PhD thesis of Lucas Leandro Nesi 27. It will be pursued in the WP5 (Performance analysis and prediction) of the ExaSoft pillar (High Performance Computing software and tools) of the PEPR NumPEx (Numérique Hautes Performances pour l'Exascale). The rest of the thesis of Lucas Leandro Nesi is more related to performance optimization (through algorithmic and reinforcement learning techniques) and evaluation (through predictive simulation and real experiments). A particular effort has been devoted to the reproducibility of the results through the opening of both the data, the code, and the underlying methodology.

Mean field approximation is a powerful technique which has been used in many settings to study large-scale stochastic systems. Some of our latest developments have been transfered in the open source project rmf_tool7.1.6. In the case of two-timescale systems, the approximation is obtained by a combination of scaling arguments and the use of the averaging principle. In 1, we analyze the approximation error of this `average' mean field model for a two-timescale model $(𝐗,𝐘)$, where the slow component $𝐗$ describes a population of interacting particles which is fully coupled with a rapidly changing environment $𝐗$. The model is parametrized by a scaling factor $N$, e.g. the population size, which as $N$ gets large decreases the jump size of the slow component in contrast to the unchanged dynamics of the fast component. We show that under relatively mild conditions, the `average' mean field approximation has a bias of order $O(1/N)$ compared to $𝔼\left[𝐗\right]$. This holds true under any continuous performance metric in the transient regime, as well as for the steady-state if the model is exponentially stable. To go one step further, we derive a bias correction term for the steady-state, from which we define a new approximation called the refined `average' mean field approximation whose bias is of order $O(1/N^2)$. This refined `average' mean field approximation allows computing an accurate approximation even for small scaling factors, i.e., $N\approx$ 10 – 50. We illustrate the developed framework and accuracy results through an application to a random access CSMA model.

Finally, the PhD thesis of Thomas Barzola 22 presents a modular approach to compare optimization methods for bike sharing systems. Bike Sharing Systems (BSSs) are nowadays installed in many cities. In such a system, a user can take any available bike and return it to wherever there is an available parking spot. The Operations Research literature contains many papers that study optimization questions related to BSS, and in particular how to maximize the availability of bikes where and when the users need them. Yet, the optimization methods proposed by these papers are difficult to compare because most papers use their own problem instances and define their own metrics. This thesis aims to fill this gap by building a reproducible research methodology for BSSs. In this work, we divide this methodology in four modules: use of historical data, demand estimation, optimization methods, and performance evaluation. We study each module separately. In each case, we propose a prototype implementation and compare existing solutions when they are available.The first module handles the use of data from real systems. For many systems, two types of data are usually available: trips made by users, and records of the number of bikes available in each station. We observe that in general these data are inconsistent and we propose a method to correct this and detect relocation operations. The second module is the demand estimation one. In optimizing a BSS, it is essential to estimate the demand of the users for whom the system is designed. Most of the optimization works in the literature use historical demand to estimate the demand of the system. We experiment with the few existing methods of the literature along with a newly introduced method to detect censored demand. The third module is bike availability optimization. We implement a published optimization algorithm for this module as an example. We illustrate the challenges of reproducible research by trying to replicate the results. This chapter shows that, although the original authors made the data about their experiments available, we did not get the same quantitative results as the original publication. This difference highlights the need for better publication standards to produce more reproducible results. Finally, our fourth and last module is used to validate the optimization methods implemented in the 3rd module. We advocate that a simulator having all the requirements (user behavior models, demand scenarios, management strategies, etc.) can be a validation model. We use a third-party simulator to illustrate this module.We observe throughout this thesis that making research reproducible is not always handled with due diligence while being fundamental to produce valuable knowledge. In this work, we try our best efforts to specify and provide reproducible tools to ensure that researchers could obtain the same results with the same data. We give links to the data, codes, environments and analyses needed to reproduce the experiments.

8.2 Energy optimization

Participants: Jonatha Anselmi, Bruno Gaujal.

In 4, we optimize the scheduling of Deep Learning training jobs from the perspective of a Cloud Service Provider running a data center, which efficiently selects resources for the execution of each job to minimize the average energy consumption while satisfying time constraints. To model the problem, we first develop a Mixed-Integer Non-Linear Programming formulation. Unfortunately, the computation of an optimal solution is prohibitively expensive, and to overcome this difficulty, we design a heuristic STochastic Scheduler (STS). Exploiting the probability distribution of early termination, STS determines how to adapt the resource assignment during the execution of the jobs to minimize the expected energy cost while meeting the job due dates. The results of an extensive experimental evaluation show that STS guarantees significantly better results than other methods in the literature, effectively avoiding due date violations and yielding a percentage total cost reduction between 32% and 80% on average. We also prove the applicability of our method in real-world scenarios, as obtaining optimal schedules for systems of up to 100 nodes and 400 concurrent jobs requires less than 5 seconds. Finally, we evaluated the effectiveness of GPU sharing, i.e., running multiple jobs in a single GPU. The obtained results demonstrate that depending on the workload and GPU memory, this further reduces the energy cost by 17-29% on average.

8.3 Restless multi-armed bandits

Participants: Nicolas Gast, Bruno Gaujal, Kimang Kuhn, Chen Yan.

Multi-Armed Bandits are a fundamental model for problems in which a decision maker has to iteratively select one of multiple fixed alternatives (i.e. arms or actions) when the reward of each choice is only partially known at the time of decision and is learned as as the decision maker interacts with the bandits. The regret of a strategy is the expectation of the sum of the collected rewards minus the expectation of the optimal reward (the one corresponding to the arm with the larger reward). Markov Decision Processes (MDP) provide a framework for modeling situations where the state of a system (and its associated reward) evolves partly random and partly under the control of the decision maker. The reward depends on the current state of the machine, but good policies can be computed (e.g., using dynamic programming although it can be computationally unreasonable) when the system is fully known upfront. We have considered the intermediate situation of restless and restful bandits where each arm corresponds to an independent Markov chain but where neither the chain nor the associated reward is initially knows. Each time a particular arm is played, the state of that chain advances to a new one, chosen according to the Markov state evolution probabilities. In the restless bandits problem, the states of non-played arms can also evolve over time.

Whittle index is a generalization of Gittins index that provides very efficient allocation rules for restless multi-armed bandits. In 5, we develop an algorithm to test the indexability and compute the Whittle indices of any finite-state restless bandit arm. This algorithm works in the discounted and non-discounted cases, and can compute Gittins index. Our algorithm builds on three tools: (1) a careful characterization of Whittle index that allows one to compute recursively the $k$–th smallest index from the $(k-1)$–th smallest, and to test indexability, (2) the use of the Sherman-Morrison formula to make this recursive computation efficient, and (3) a sporadic use of the fastest matrix inversion and multiplication methods to obtain a subcubic complexity. We show that an efficient use of the Sherman-Morrison formula leads to an algorithm that computes Whittle index in $O(2/3)n^3+o\left(n^3\right)$ arithmetic operations, where $n$ is the number of states of the arm. The careful use of fast matrix multiplication leads to the first subcubic algorithm to compute Whittle or Gittins index: By using the current fastest matrix multiplication, the theoretical complexity of our algorithm is $O\left(n^{2.5286}\right)$. We also develop an efficient implementation of our algorithm that can compute indices of Markov chains with several thousands of states in less than a few seconds.

This work is part of the PhD thesis of Kimang Kuhn 25, where it was shown that no learning algorithms can perform uniformly well over the general class of restless bandits, and where several strategies for restful bandits have also been studied,

In 6, we evaluate the performance of Whittle index policy for restless Markovian bandit. It is shown in Weber and Weiss 110 that if the bandit is indexable and the associated deterministic system has a global attractor fixed point, then the Whittle index policy is asymptotically optimal in the regime where the arm population grows proportionally with the number of activation arms. In this paper, we show that, under the same conditions, this convergence rate is exponential in the arm population, unless the fixed point is singular, which almost never happens in practice. Our result holds for the continuous-time model of Weber and Weiss (1990) and for a discrete-time model in which all bandits make synchronous transitions. Our proof is based on the nature of the deterministic equation governing the stochastic system: We show that it is a piecewise affine continuous dynamical system inside the simplex of the empirical measure of the arms. Using simulations and numerical solvers, we also investigate the singular cases, as well as how the level of singularity influences the (exponential) convergence rate. We illustrate our theorem on a Markovian fading channel model.

In 7, we also provide a framework to analyse control policies for the restless Markovian bandit model, under both finite and infinite time horizon. We show that when the population of arms goes to infinity, the value of the optimal control policy converges to the solution of a linear program (LP). We provide necessary and sufficient conditions for a generic control policy to be: i) asymptotically optimal; ii) asymptotically optimal with square root convergence rate; iii) asymptotically optimal with exponential rate. We then construct the LP-index policy that is asymptotically optimal with square root convergence rate on all models, and with exponential rate if the model is non-degenerate in finite horizon, and satisfies a uniform global attractor property in infinite horizon. We next define the LP-update policy, which is essentially a repeated LP-index policy that solves a new linear program at each decision epoch. We provide numerical experiments to compare the efficiency of LP-based policies. We compare the performance of the LP-index policy and the LP-update policy with other heuristics. Our result demonstrates that the LP-update policy outperforms the LP-index policy in general, and can have a significant advantage when the transition matrices are wrongly estimated.

8.4 Reinforcement Learning and MDP

Participants: Jonatha Anselmi, Victor Boone, Romain Cravic, Nicolas Gast, Bruno Gaujal, Louis-Sébastien Rebuffi.

Although regret is a common objective in Reinforcement Learning, other criteria are relevant and allow to better understand or discriminate algorithms.

The first contribution of 12 is the introduction of a new performance measure of a RL algorithm that is more discriminating than the regret, that we call the regret of exploration that measures the asymptotic cost of exploration. The second contribution is a new performance test (PT) to end episodes in RL optimistic algorithms. This test is based on the performance of the current policy with respect to the best policy over the current confidence set. This is in contrast with all existing RL algorithms whose episode lengths are only based on the number of visits to the states. This modification does not harm the regret and brings an additional property. We show that while all current episodic RL algorithms have a linear regret of exploration, our method has a $O(logT)$ regret of exploration for non-degenerate deterministic MDPs.

In 11, we investigate a new learning problem, the identification of Blackwell optimal policies on deterministic MDPs (DMDPs): A learner has to return a Blackwell optimal policy with fixed confidence using a minimal number of queries. First, we characterize the maximal set of DMDPs for which the identification is possible. Then, we focus on the analysis of algorithms based on product-form confidence regions. We minimize the number of queries by efficiently visiting the state-action pairs with respect to the shape of confidence sets. Furthermore, these confidence sets are themselves optimized to achieve better performance. The performance of our method compares to the lower bound up to a factor $n^2$ in the worst case, where $n$ is the number of states, and constant in certain classes of DMDPs.

In 14, we propose the first model-free algorithm that achieves low regret performance for decentralized learning in two-player zerosum tabular stochastic games with infinite-horizon average-reward objective. In decentralized learning, the learning agent controls only one player and tries to achieve low regret performances against an arbitrary opponent. This contrasts with centralized learning where the agent tries to approximate the Nash equilibrium by controlling both players. In our infinite-horizon undiscounted setting, additional structure assumptions is needed to provide good behaviors of learning processes : here we assume for every strategy of the opponent, the agent has a way to go from any state to any other. This assumption is the analogous to the "communicating" assumption in the MDP setting. We show that our Decentralized Optimistic Nash Q-Learning (DONQ-learning) algorithm achieves both sublinear high probability regret of order 3/4 and sublinear expected regret of order 2/3. Moreover, our algorithm enjoys a low computational complexity and low memory space requirement compared to the previous works in the same setting.

Finally, in 30, we present an efficient reinforcement learning algorithm that learns the optimal admission control policy in a partially observable queueing network. Specifically, only the arrival and departure times from the network are observable, and optimality refers to the average holding/rejection cost in infinite horizon. While reinforcement learning in Partially Observable Markov Decision Processes (POMDP) is prohibitively expensive in general, we show that our algorithm has a regret that only depends sub-linearly on the maximal number of jobs in the network, $𝐒$. In particular, in contrast with existing regret analyses, our regret bound does not depend on the diameter of the underlying Markov Decision Process (MDP), which in most queueing systems is at least exponential in $𝐒$. The novelty of our approach is to leverage Norton's equivalent theorem for closed product-form queueing networks and an efficient reinforcement learning algorithm for MDPs with the structure of birth-and-death processes.

This work is part of the PhD thesis of Louis-Sebastien Rebuffi 29 and allows to propose reinforcement learning algorithms for controlled queueing systems that demonstrate a weak dependence on the state space compared to results obtained in the general case.

8.5 Learning in games

Participants: Victor Boone, Yu-Guan Hsieh, Panayotis Mertikopoulos.

Learning in games naturally occurs in situations where the resources or the decision is distributed among several agents or even in situations where a centralised decision maker has to adapt to strategic users. Yet, it is considerably more difficult than in classical minimization games as the resulting equilibria may be attractive or not and the dynamic often exhibit cyclic behaviors.

A wide array of modern machine learning applications – from adversarial models to multi-agent reinforcement learning – can be formulated as non-cooperative games whose Nash equilibria represent the system's desired operational states. Despite having a highly non-convex loss landscape, many cases of interest possess a latent convex structure that could potentially be leveraged to yield convergence to an equilibrium. Driven by this observation, we propose in 20 a flexible first-order method that successfully exploits such "hidden structures" and achieves convergence under minimal assumptions for the transformation connecting the players' control variables to the game's latent, convex-structured layer. The proposed method – which we call preconditioned hidden gradient descent (PHGD) – hinges on a judiciously chosen gradient preconditioning scheme related to natural gradient methods. Importantly, we make no separability assumptions for the game's hidden structure, and we provide explicit convergence rate guarantees for both deterministic and stochastic environments.

In 13, we show the equivalence of dynamic and strategic stability under regularized learning in games by examining the long-run behavior of regularized, no-regret learning in finite games. A well-known result in the field states that the empirical frequencies of no-regret play converge to the game's set of coarse correlated equilibria; however, our understanding of how the players' actual strategies evolve over time is much more limited - and, in many cases, non-existent. This issue is exacerbated further by a series of recent results showing that only strict Nash equilibria are stable and attracting under regularized learning, thus making the relation between learning and pointwise solution concepts particularly elusive. In lieu of this, we take a more general approach and instead seek to characterize the setwise rationality properties of the players' day-to-day play. To that end, we focus on one of the most stringent criteria of setwise strategic stability, namely that any unilateral deviation from the set in question incurs a cost to the deviator - a property known as closedness under better replies (club). In so doing, we obtain a far-reaching equivalence between strategic and dynamic stability: a product of pure strategies is closed under better replies if and only if its span is stable and attracting under regularized learning. In addition, we estimate the rate of convergence to such sets, and we show that methods based on entropic regularization (like the exponential weights algorithm) converge at a geometric rate, while projection-based methods converge within a finite number of iterations, even with bandit, payoff-based feedback.

In 3, we examine the long-run behavior of multi-agent online learning in games that evolve over time. Specifically, we focus on a wide class of policies based on mirror descent, and we show that the induced sequence of play (a) converges to Nash equilibrium in time-varying games that stabilize in the long run to a strictly monotone limit; and (b) it stays asymptotically close to the evolving equilibrium of the sequence of stage games (assuming they are strongly monotone). Our results apply to both gradient-based and payoff-based feedback – i.e., when players only get to observe the payoffs of their chosen actions.

In 9, we develop a flexible stochastic approximation framework for analyzing the long-run behavior of learning in games (both continuous and finite). The proposed analysis template incorporates a wide array of popular learning algorithms, including gradient-based methods, the exponential / multiplicative weights algorithm for learning in finite games, optimistic and bandit variants of the above, etc. In addition to providing an integrated view of these algorithms, our framework further allows us to obtain several new convergence results, both asymptotic and in finite time, in both continuous and finite games. Specifically, we provide a range of criteria for identifying classes of Nash equilibria and sets of action profiles that are attracting with high probability, and we also introduce the notion of coherence, a game-theoretic property that includes strict and sharp equilibria, and which leads to convergence in finite time. Importantly, our analysis applies to both oracle-based and bandit, payoff-based methods – that is, when players only observe their realized payoffs.

This work is part of the PhD thesis of Yu Guan Hsieh 23 entitled Decision-Making in multi-agent systems: delays, adaptivity, and learning in games, and which has investigated separately two critical aspects of multi-agent systems: the impact of delays and the interactions among agents with non-aligned interests.

8.6 Quantum Games

Participants: Panayotis Mertikopoulos.

Although the games we generally consider for learning have nothing to do with the quantum world, they often involve probabilities (to account for the uncertainty of the agents or of the nature) and semi-definite programming (e.g., when dealing with the optimization of MIMO antennas). Quantum games have thus been a natural target for which we have proposed several contributions.

Recent developments in domains such as non-local games, quantum interactive proofs, and quantum generative adversarial networks have renewed interest in quantum game theory and, specifically, quantum zero-sum games. Central to classical game theory is the efficient algorithmic computation of Nash equilibria, which represent optimal strategies for both players. In 2008, Jain and Watrous proposed the first classical algorithm for computing equilibria in quantum zerosum games using the Matrix Multiplicative Weight Updates (MMWU) method to achieve a convergence rate of $O(d/{\epsilon }^2)$ iterations to $\epsilon$-Nash equilibria in the $4d$-dimensional spectraplex. In 21, we propose a hierarchy of quantum optimization algorithms that generalize MMWU via an extra-gradient mechanism. Notably, within this proposed hierarchy, we introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as $O(d/\epsilon )$ iterations to $\epsilon$-Nash equilibria. This quadratic speed-up relative to Jain and Watrous' original algorithm sets a new benchmark for computing $\epsilon$-Nash equilibria in quantum zero-sum games.

In 17, we study the problem of learning in quantum games and other classes of semidefinite games-with scalar, payoff-based feedback. For concreteness, we focus on the widely used matrix multiplicative weights (MMW) algorithm and, instead of requiring players to have full knowledge of the game (and/or each other's chosen states), we introduce a suite of minimal-information matrix multiplicative weights (3MW) methods tailored to different information frameworks. The main difficulty to attaining convergence in this setting is that, in contrast to classical finite games, quantum games have an infinite continuum of pure states (the quantum equivalent of pure strategies), so standard importance-weighting techniques for estimating payoff vectors cannot be employed. Instead, we borrow ideas from bandit convex optimization and we design a zeroth-order gradient sampler adapted to the semidefinite geometry of the problem at hand. As a first result, we show that the 3MW method with deterministic payoff feedback retains the $O(1/\sqrt{T})$ convergence rate of the vanilla, full information MMW algorithm in quantum min-max games, even though the players only observe a single scalar. Subsequently, we relax the algorithm's information requirements even further and we provide a 3MW method that only requires players to observe a random realization of their payoff observable, and converges to equilibrium at an $O\left(T^{-1/4}\right)$ rate. Finally, going beyond zero-sum games, we show that a regularized variant of the proposed 3MW method guarantees local convergence with high probability to all equilibria that satisfy a certain first-order stability condition.

Finally, in 18, we study the equilibrium convergence and stability properties of the widely used matrix multiplicative weights (MMW) dynamics for learning in general quantum games. A key difficulty in this endeavor is that the induced quantum state dynamics decompose naturally into (i) a classical, commutative component which governs the dynamics of the system's eigenvalues in a way analogous to the evolution of mixed strategies under the classical replicator dynamics; and (ii) a non-commutative component for the system's eigenvectors. This non-commutative component has no classical counterpart and, as a result, requires the introduction of novel notions of (asymptotic) stability to account for the nonlinear geometry of the game's quantum space. In this general context, we show that (i) only pure quantum equilibria can be stable and attracting under the MMW dynamics; and (ii) as a partial converse, pure quantum states that satisfy a certain "variational stability" condition are always attracting. This allows us to fully characterize the structure of quantum Nash equilibria that are stable and attracting under the MMW dynamics, a fact with significant implications for predicting the outcome of a multi-agent quantum learning process.

8.7 Continuous optimization methods

Participants: Yu-Guan Hsieh, Panayotis Mertikopoulos.

Variational inequalities – and, in particular, stochastic variational inequalities – have recently attracted considerable attention in machine learning and learning theory as a flexible paradigm for "optimization beyond minimization", i.e., for problems where finding an optimal solution does not necessarily involve minimizing a loss function.

Many modern machine learning applications – from online principal component analysis to covariance matrix identification and dictionary learning – can be formulated as minimization problems on Riemannian manifolds, and are typically solved with a Riemannian stochastic gradient method (or some variant thereof). However, in many cases of interest, the resulting minimization problem is not geodesically convex, so the convergence of the chosen solver to a desirable solution – i.e., a local minimizer – is by no means guaranteed. In 15, we study precisely this question, that is, whether stochastic Riemannian optimization algorithms are guaranteed to avoid saddle points with probability 1. For generality, we study a family of retraction-based methods which, in addition to having a potentially much lower per-iteration cost relative to Riemannian gradient descent, include other widely used algorithms, such as natural policy gradient methods and mirror descent in ordinary convex spaces. In this general setting, we show that, under mild assumptions for the ambient manifold and the oracle providing gradient information, the policies under study avoid strict saddle points / submanifolds with probability 1, from any initial condition. This result provides an important sanity check for the use of gradient methods on manifolds as it shows that, almost always, the limit state of a stochastic Riemannian algorithm can only be a local minimizer.

In 31, we examine the last-iterate convergence rate of Bregman proximal methods - from mirror descent to mirror-prox and its optimistic variants - as a function of the local geometry induced by the prox-mapping defining the method. For generality, we focus on local solutions of constrained, non-monotone variational inequalities, and we show that the convergence rate of a given method depends sharply on its associated Legendre exponent, a notion that measures the growth rate of the underlying Bregman function (Euclidean, entropic, or other) near a solution. In particular, we show that boundary solutions exhibit a stark separation of regimes between methods with a zero and non-zero Legendre exponent: the former converge at a linear rate, while the latter converge, in general, sublinearly. This dichotomy becomes even more pronounced in linearly constrained problems where methods with entropic regularization achieve a linear convergence rate along sharp directions, compared to convergence in a finite number of steps under Euclidean regularization.

8.8 Random matrix analysis and Machine Learning

Participants: Romain Couillet, Minh-Toan Nguyen.

Random matrix theory has recently proven to be a very effective tool to understand Machine Learning challenges. In particular, concentration results can be used to derive more efficient and frugal algorithms.

The PhD thesis of Minh-Toan Nguyen 28 has provided a nice overview with a deep perspective on replica method and asymptotic equivalence. Replica method is a favorite tool of physicists for studying large disordered systems. Although the method is highly non-rigorous, it can solve difficult problems across various domains: random matrix theory, convex optimization, combinatorial optimization, Bayesian inference, etc. The method has been successfully used to analyze theoretical models in wireless communication and machine learning. The rigorous alternatives for the replica method include the method of deterministic equivalents in random matrix theory, the objective method in combinatorial optimization, and the CGMT (convex Gaussian min-max theorem) in random convex optimization. Although these methods works in different domains, they offer one common insight: the asymptotic equivalence, which tells us that the large system under study is equivalent to a simpler system. As a result, many difficult computations on the original system can be done more easily on the equivalent system. In contrast, with the replica method, the insights come after the calculations. We start by writing down what we want to compute and then proceed to get the answer at the end. After calculating various quantities related to the system, with some observations and a good intuition, we may uncover the equivalent system. In this thesis, we show that the asymptotic equivalent of a disordered system can be obtained directly through the replica formalism by paying attention to the large-deviation computations lurking behind the replica computations. In other words, we develop a version of the replica method that can directly compute the asymptotic equivalent of a disordered system. This version of the replica method, which fits into the same framework of deterministic equivalence as the rigorous methods above, can compute the deterministic equivalents of random matrices, formally derive the CGMT, and solve problems in high-dimensional Bayesian statistics. Moreover, it can derive results on the Sherrington-Kirkpatrick model in a clear and simple manner. In this version of the replica method, each disordered system is associated with an object called “the replica density”. By De Finetti's theorem, a disordered system can be recovered from its replica density. To compute the asymptotic equivalent of a disordered system, we compute the equivalent of its replica density, using a result that we derive from the fundamental Gibbs principle. We thus obtain another replica density, which corresponds to another disordered system. This system is asymptotically equivalent to the original disordered system.

8.9 Fairness and equity in digital (recommendation, advertising, persistent storage) systems

Participants: Rémi Castera, Nicolas Gast, Till Kletti, Simon Jantschgi, Mathieu Molina, Bary Pradelski.

The general deployment of machine-learning systems in many domains ranging from security to recommendation and advertising to guide strategic decisions leads to an interesting line of research from a game theory perspective. In this context, fairness, discrimination, and privacy are particularly important issues.

In 32, we study statistical discrimination in matching, where multiple decision-makers are simultaneously facing selection problems from the same pool of candidates. We propose a model where decision-makers observe different, but correlated estimates of each candidate's quality. The candidate population consists of several groups that represent gender, ethnicity, or other attributes. The correlation differs across groups and may, for example, result from noisy estimates of candidates' latent qualities, a weighting of common and decision-maker specific evaluations, or different admission criteria of each decision maker. We show that lower correlation (e.g., resulting from higher estimation noise) for one of the groups worsens the outcome for all groups, thus leading to efficiency loss. Further, the probability that a candidate is assigned to their first choice is independent of their group. In contrast, the probability that a candidate is assigned at all depends on their group, and — against common intuition — the group that is subjected to lower correlation is better off. The resulting inequality reveals a novel source of statistical discrimination.

In 8, we conducted a large number of controlled continuous double auction experiments to reproduce and stress-test the phenomenon of convergence to competitive equilibrium under private information with decentralized trading feedback. Our main finding is that across a total of 104 markets (involving over 1,700 subjects), convergence occurs after a handful of trading periods. Initially, however, there is an inherent asymmetry that favors buyers, typically resulting in prices below equilibrium levels. Analysis of over 80,000 observations of individual bids and asks helps identify empirical ingredients contributing to the observed phenomena including higher levels of aggressiveness initially among buyers than sellers.

This work is part of the PhD thesis of Simon Jantschgi 24 on market design for double auctions.

Individual behavior such as choice of fashion, adoption of new products, and selection of means of transport is influenced by taking account of others' actions. In 10, we study social influence in a heterogeneous population and analyze the behavior of the dynamic processes. We distinguish between two information regimes: (i) agents are influenced by the adoption ratio, (ii) agents are influenced by the usage history. We identify the stable equilibria and long-run frequencies of the dynamics. We then show that the two processes generate qualitatively different dynamics, leaving characteristic 'footprints'. In particular, (ii) favors more extreme outcomes than (i).

In 19, we consider the problem of online allocation subject to a long-term fairness penalty. Contrary to existing works, however, we do not assume that the decision-maker observes the protected attributes – which is often unrealistic in practice. Instead they can purchase data that help estimate them from sources of different quality; and hence reduce the fairness penalty at some cost. We model this problem as a multi-armed bandit problem where each arm corresponds to the choice of a data source, coupled with the online allocation problem. We propose an algorithm that jointly solves both problems and show that it has a regret bounded by $O\left(\sqrt{T}\right)$. A key difficulty is that the rewards received by selecting a source are correlated by the fairness penalty, which leads to a need for randomization (despite a stochastic setting). Our algorithm takes into account contextual information available before the source selection, and can adapt to many different fairness notions. We also show that in some instances, the estimates used can be learned on the fly.

Finally, fairness has also been studied in the PhD thesis of Till Kletti 26, in the context of multistakeholder recommendation platforms. The object of study of this thesis is the ranking of potentially relevant objects in response to an information request, for example when using a search engine or in the case of online con-tent recommendation. Such a ranking brings together two groups: users searching for relevant information, and content producers, whose goal is to make the produced information visible.For example, when searching for restaurants, the user is interested in seeing good restaurants,while the interest of the restaurant owners is to be seen by many people, in order to attract customers. The objects to be ranked are thus competing with each other and it is in the interest of the platform generating the rankings to ensure that the exposure allocated to the objects is fairly distributed. Obviously there are many possibilities of defining what fair means and none of them will be unanimously agreed upon. Therefore in this thesis the definition of fairness is taken as a parameter represented by a vector of merit, which determines the proportion with which visibility should be distributed amongst the items. This will make our method applicable to a wide range of possible definitions.Two things then become apparent. First, there does not in general exists ranking that is fair in the sense of proportionality of exposure to merit. It is therefore necessary to produce several rankings that compensate each other in order to give, on average, fair exposures to the items.Secondly, these rankings do not generally give maximum utility to the user. Indeed, to guarantee fairness, less relevant objects could potentially be shown to him. These two objectives, fairness and utility, are thus not simultaneously optimizable. The contribution of this thesis is to develop methods to determine Pareto optimal ranking sequences, i.e. such that it is not possible to improve one of the two objectives without deteri-orating the other. The idea is that this would make it possible for a qualified decision maker to make an informed choice about an adequate trade-off between user utility and fairness amongst items.The determination of these optimal sequences is accomplished via the introduction of a geometric object, a polytope named expohedron. This polytope expresses the set of average exposures attainable with ranking sequences and is therefore a good decision space for both fairnessand utility. The expohedron makes it possible to compute these optimal ranking sequences using only mathematically exact geometric constructions inside it, and this in a significantly faster way than previous methods based on linear programming. Moreover, the proposed method is applicable to two large classes of exposure models including Position Based Model (PBM) and Dynamic Bayesian Network (DBN) models to which linear programming is not applicable.

10.1 European initiatives

10.2 National initiatives

Projects indicated with a $☆$ are projects coordinated by members of the POLARIS team.

11.1 Promoting scientific activities

11.2 Teaching - Supervision - Juries

11.3 Popularization

12.1 Publications of the year

12.2 Cited publications

• 34 inproceedingsA.Athanasios Andreou, M.Marcio Silva, F.Fabrício Benevenuto, O.Oana Goga, P.Patrick Loiseau and A.Alan Mislove. Measuring the Facebook Advertising Ecosystem.NDSS 2019 - Proceedings of the Network and Distributed System Security SymposiumSan Diego, United StatesFebruary 2019, 1-15HALDOIback to text
• 35 inproceedingsA.Athanasios Andreou, G.Giridhari Venkatadri, O.Oana Goga, K. P.Krishna P Gummadi, P.Patrick Loiseau and A.Alan Mislove. Investigating Ad Transparency Mechanisms in Social Media: A Case Study of Facebook's Explanations.NDSS 2018 - Network and Distributed System Security SymposiumSan Diego, United StatesFebruary 2018, 1-15HALDOIback to text
• 36 articleJ.Jonatha Anselmi. Combining Size-Based Load Balancing with Round-Robin for Scalable Low Latency.IEEE Transactions on Parallel and Distributed Systems2019, 1-3HALDOIback to textback to text
• 37 articleJ.Jonatha Anselmi and J.Josu Doncel. Asymptotically Optimal Size-Interval Task Assignments.IEEE Transactions on Parallel and Distributed Systems30112019, 2422-2433HALDOIback to textback to text
• 38 articleJ.Jonatha Anselmi and F.François Dufour. Power-of-d-Choices with Memory: Fluid Limit and Optimality.Mathematics of Operations Research4532020, 862-888HALDOIback to textback to text
• 39 inproceedingsR. M.Rosa M. Badia, J.Jesús Labarta, J.Judit Giménez and F.Francesc Escalé. Dimemas: Predicting MPI Applications Behaviour in Grid Environments.Proc. of the Workshop on Grid Applications and Programming Tools2003back to text
• 40 conferenceS.Swen Böhm and C.Christian Engelmann. xSim: The Extreme-Scale Simulator.HPCSIstanbul, Turkey2011back to text
• 41 inproceedingsP.Pedro Bruel, S.Steven Quinito Masnada, B.Brice Videau, A.Arnaud Legrand, J.-M.Jean-Marc Vincent and A.Alfredo Goldman. Autotuning under Tight Budget Constraints: A Transparent Design of Experiments Approach.CCGrid 2019 - International Symposium in Cluster, Cloud, and Grid ComputingLarcana, CyprusIEEEMay 2019, 1-10HALDOIback to text
• 42 incollectionH.Holger Brunst, D.Daniel Hackenberg, G.Guido Juckeland and H.Heide Rohling. Comprehensive Performance Tracking with VAMPIR 7.Tools for High Performance Computing 2009The paper details the latest improvements in the Vampir visualization tool.Springer Berlin Heidelberg2010DOIback to text
• 43 articleP.Pierre COUCHENEY, B.Bruno Gaujal and P.Panayotis Mertikopoulos. Penalty-Regulated Dynamics and Robust Learning Procedures in Games.Mathematics of Operations Research4032015, 611-633HALDOIback to text
• 44 articleG.Giuliano Casale and N.Nicolas Gast. Performance analysis methods for list-based caches with non-uniform access.IEEE/ACM Transactions on NetworkingDecember 2020, 1-18HALDOIback to text
• 45 inproceedingsA.Abhijnan Chakraborty, G. K.Gourab K Patro, N.Niloy Ganguly, K. P.Krishna P Gummadi and P.Patrick Loiseau. Equality of Voice: Towards Fair Representation in Crowdsourced Top-K Recommendations.FAT* 2019 - ACM Conference on Fairness, Accountability, and TransparencyProceedings of the ACM Conference on Fairness, Accountability, and Transparency (FAT*)Atlanta, United StatesACMJanuary 2019, 129-138HALDOIback to text
• 46 inproceedingsT.Tom Cornebize, A.Arnaud Legrand and F. C.Franz C Heinrich. Fast and Faithful Performance Prediction of MPI Applications: the HPL Case Study.2019 IEEE International Conference on Cluster Computing (CLUSTER)Albuquerque, United StatesSeptember 2019HALDOIback to text
• 47 articleT.Tom Cornebize and A.Arnaud Legrand. Simulation-based Optimization and Sensibility Analysis of MPI Applications: Variability Matters.Journal of Parallel and Distributed ComputingApril 2022HALDOIback to text
• 48 articleA.Augustin Degomme, A.Arnaud Legrand, G.Georges Markomanolis, M.Martin Quinson, M. L.Mark Lee Stillwell and F.Frédéric Suter. Simulating MPI applications: the SMPI approach.IEEE Transactions on Parallel and Distributed Systems288August 2017, 14HALDOIback to text
• 49 inproceedingsB.Bruno Donassolo, I.Ilhem Fajjari, A.Arnaud Legrand and P.Panayotis Mertikopoulos. Load Aware Provisioning of IoT Services on Fog Computing Platform.IEEE International Conference on Communications (ICC)Shanghai, ChinaIEEEMay 2019HALDOIback to text
• 50 articleB.Bruno Donassolo, A.Arnaud Legrand, P.Panayotis Mertikopoulos and I.Ilhem Fajjari. Online Reconfiguration of IoT Applications in the Fog: The Information-Coordination Trade-off.IEEE Transactions on Parallel and Distributed Systems3352022, 1156-1172HALDOIback to text
• 51 inproceedings J.Josu Doncel, N.Nicolas Gast and B.Bruno Gaujal. Are mean-field games the limits of finite stochastic games? The 18th Workshop on MAthematical performance Modeling and Analysis Nice, France June 2016 HAL back to text
• 52 articleJ.Josu Doncel, N.Nicolas Gast and B.Bruno Gaujal. Discrete Mean Field Games: Existence of Equilibria and Convergence.Journal of Dynamics and Games632019, 1-19HALDOIback to text
• 53 inproceedingsV.Vitalii Emelianov, G.George Arvanitakis, N.Nicolas Gast, K. P.Krishna P Gummadi and P.Patrick Loiseau. The Price of Local Fairness in Multistage Selection.IJCAI-2019 - Twenty-Eighth International Joint Conference on Artificial IntelligenceMacao, FranceInternational Joint Conferences on Artificial Intelligence OrganizationAugust 2019, 5836-5842HALDOIback to text
• 54 inproceedingsV.Vitalii Emelianov, N.Nicolas Gast, K. P.Krishna P. Gummadi and P.Patrick Loiseau. On Fair Selection in the Presence of Implicit Variance.EC 2020 - Twenty-First ACM Conference on Economics and ComputationBudapest, HungaryACMJuly 2020, 649–675HALDOIback to text
• 55 inproceedingsL.Lampros Flokas, E. V.Emmanouil V Vlatakis-Gkaragkounis, T.Thanasis Lianeas, P.Panayotis Mertikopoulos and G.Georgios Piliouras. No-regret learning and mixed Nash equilibria: They do not mix.NeurIPS 2020 - 34th International Conference on Neural Information Processing SystemsVancouver, CanadaDecember 2020, 1-24HALback to text
• 56 articleV.Vinicius Garcia Pinto, L. M.Lucas Mello Schnorr, L.Luka Stanisic, A.Arnaud Legrand, S.Samuel Thibault and V.Vincent Danjean. A Visual Performance Analysis Framework for Task-based Parallel Applications running on Hybrid Clusters.Concurrency and Computation: Practice and Experience3018April 2018, 1-31HALDOIback to textback to text
• 57 articleN.Nicolas Gast, L.Luca Bortolussi and M.Mirco Tribastone. Size Expansions of Mean Field Approximation: Transient and Steady-State Analysis.Performance Evaluation2018, 1-15HALback to text
• 58 inproceedingsN.Nicolas Gast. Expected Values Estimated via Mean-Field Approximation are $1/N$-Accurate.ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems , SIGMETRICS '171ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems , SIGMETRICS '17Urbana-Champaign, United StatesJune 2017, 26HALDOIback to text
• 59 article N.Nicolas Gast, B.Bruno Gaujal and K.Kimang Khun. Learning algorithms for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism? Transactions on Machine Learning Research Journal November 2022 HAL back to text
• 60 unpublishedN.Nicolas Gast, B.Bruno Gaujal and C.Chen Yan. Exponential Convergence Rate for the Asymptotic Optimality of Whittle Index Policy.December 2020, HALback to textback to text
• 61 inproceedingsN.Nicolas Gast and B. V.Benny Van Houdt. A Refined Mean Field Approximation.ACM SIGMETRICS 2018Irvine, United StatesJune 2018, 1HALback to text
• 62 articleN.Nicolas Gast, S.Stratis Ioannidis, P.Patrick Loiseau and B.Benjamin Roussillon. Linear Regression from Strategic Data Sources.ACM Transactions on Economics and Computation82May 2020, 1-24HALDOIback to text
• 63 inproceedingsN.Nicolas Gast, D.Diego Latella and M.Mieke Massink. A Refined Mean Field Approximation for Synchronous Population Processes.MAMA 2018Workshop on MAthematical performance Modeling and AnalysisIrvine, United StatesJune 2018, 1-3HALback to text
• 64 inproceedingsN.Nicolas Gast and B.Benny Van Houdt. Asymptotically Exact TTL-Approximations of the Cache Replacement Algorithms LRU(m) and h-LRU.28th International Teletraffic Congress (ITC 28)Würzburg, GermanySeptember 2016HALback to text
• 65 articleN.Nicolas Gast and B.Benny Van Houdt. TTL Approximations of the Cache Replacement Algorithms LRU(m) and h-LRU.Performance EvaluationSeptember 2017HALDOIback to text
• 66 inproceedingsB.Bruno Gaujal, J.Josu Doncel and N.Nicolas Gast. Vaccination in a Large Population: Mean Field Equilibrium versus Social Optimum.NETGCOOP 2020 - 10th International Conference on NETwork Games, COntrol and OPtimizationCargèse, FranceSeptember 2021, 1-9HALback to text
• 67 inproceedingsB.Bruno Gaujal, A.Alain Girault and S.Stéphan Plassart. A Linear Time Algorithm for Computing Off-line Speed Schedules Minimizing Energy Consumption.MSR 2019 - 12ème Colloque sur la Modélisation des Systèmes RéactifsAngers, FranceNovember 2019, 1-14HALback to text
• 68 inproceedingsB.Bruno Gaujal, A.Alain Girault and S.Stéphan Plassart. Discrete and Continuous Optimal Control for Energy Minimization in Real-Time Systems.EBCCSP 2020 - 6th International Conference on Event-Based Control, Communication, and Signal ProcessingKrakow, PolandIEEESeptember 2020, 1-8HALDOIback to text
• 69 articleB.Bruno Gaujal, A.Alain Girault and S.Stéphan Plassart. Dynamic Speed Scaling Minimizing Expected Energy Consumption for Real-Time Tasks.Journal of SchedulingJuly 2020, 1-25HALDOIback to text
• 70 techreportB.Bruno Gaujal, A.Alain Girault and S.Stéphan Plassart. Exploiting Job Variability to Minimize Energy Consumption under Real-Time Constraints.RR-9300Inria Grenoble Rhône-Alpes, Université de Grenoble ; Université Grenoble - AlpesNovember 2019, 23HALback to text
• 71 inproceedingsA.Angeliki Giannou, E. V.Emmanouil Vasileios Vlatakis-Gkaragkounis and P.Panayotis Mertikopoulos. Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information.COLT 2021 - 34th Annual Conference on Learning TheoryBoulder, United StatesAugust 2021, 1-30HALback to text
• 72 articleM.MT Heath and J.JA Etheridge. Visualizing the performance of parallel programs.IEEE software85The paper presents Paragraph.1991back to text
• 73 inproceedingsF. C.Franz C. Heinrich, T.Tom Cornebize, A.Augustin Degomme, A.Arnaud Legrand, A.Alexandra Carpen-Amarie, S.Sascha Hunold, A.-C.Anne-Cécile Orgerie and M.Martin Quinson. Predicting the Energy Consumption of MPI Applications at Scale Using a Single Node.Cluster 2017IEEEHawaii, United StatesSeptember 2017HALback to text
• 74 inproceedingsT.Torsten Hoefler, T.Timo Schneider and A.Andrew Lumsdaine. LogGOPSim - Simulating Large-Scale Applications in the LogGOPS Model.ACM Workshop on Large-Scale System and Application Performance2010back to text
• 75 inproceedingsY.-P.Ya-Ping Hsieh, P.Panayotis Mertikopoulos and V.Volkan Cevher. The limits of min-max optimization algorithms: Convergence to spurious non-critical sets.ICML 2021 - 38th International Conference on Machine LearningVienna, AustriaJuly 2021HALback to text
• 76 articleL. V.Laxmikant V. Kalé, G.Gengbin Zheng, C. W.Chee Wai Lee and S.Sameer Kumar. Scaling applications to massively parallel machines using Projections performance analysis tool.Future Generation Comp. Syst.2232006back to text
• 77 inproceedingsR.Rafael Keller Tesser, L.Lucas Mello Schnorr, A.Arnaud Legrand, F.Fabrice Dupros and P. O.Philippe O A Navaux. Using Simulation to Evaluate and Tune the Performance of Dynamic Load Balancing of an Over-decomposed Geophysics Application.Euro-Par 2017: 23rd International European Conference on Parallel and Distributed ComputingSantiago de Compostela, SpainAugust 2017, 15HALback to text
• 78 articleR.Rafael Keller Tesser, L.Lucas Mello Schnorr, A.Arnaud Legrand, C.Christian Heinrich, F.Fabrice Dupros and P. O.Philippe Olivier Alexandre Navaux. Performance Modeling of a Geophysics Application to Accelerate the Tuning of Over-decomposition Parameters through Simulation.Concurrency and Computation: Practice and Experience2018, 1-21HALDOIback to text
• 79 inproceedingsT.-E.Takai-Eddine Kennouche, F.Florent Cadoux, N.Nicolas Gast and B.Benoît Vinot. ASGriDS: Asynchronous Smart-Grids Distributed Simulator.APPEEC 2019 - 11th IEEE PES Asia-Pacific Power and Energy Engineering ConferenceMacao, Macau SAR ChinaIEEEDecember 2019, 1-5HALback to text
• 80 inproceedingsJ. M.Jon M. Kleinberg and M.Manish Raghavan. Selection Problems in the Presence of Implicit Bias.Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS)2018, 33:1--33:17back to text
• 81 inproceedingsA.Arnaud Legrand, D.Denis Trystram and S.Salah Zrigui. Adapting Batch Scheduling to Workload Characteristics: What can we expect From Online Learning?IPDPS 2019 - 33rd IEEE International Parallel & Distributed Processing SymposiumRio de Janeiro, BrazilIEEEMay 2019, 686-695HALDOIback to text
• 82 articleJ. D.Jacob D Leshno and B. S.Bary S R Pradelski. The importance of memory for price discovery in decentralized markets.Games and Economic Behavior125January 2021, 62-78HALDOIback to text
• 83 inproceedingsM.Mouhcine Mendil, N.Nicolas Gast and H.-J.Henry-Joseph Audéoud. Collisions groupées lors du mécanisme d'évitement de collisions de CPL-G3.CoRes 2020 - Rencontres Francophones sur la Conception de Protocoles, l’Évaluation de Performance et l’Expérimentation des Réseaux de CommunicationLyon, FranceSeptember 2020, 1-4HALback to text
• 84 inproceedingsP.Panayotis Mertikopoulos, B.Bruno Lecouat, H.Houssam Zenati, C.-S.Chuan-Sheng Foo, V.Vijay Chandrasekhar and G.Georgios Piliouras. Optimistic Mirror Descent in Saddle-Point Problems: Going the Extra (Gradient) Mile.ICLR 2019 - 7th International Conference on Learning RepresentationsNew Orleans, United StatesMay 2019, 1-23HALback to text
• 85 inproceedingsP.Panayotis Mertikopoulos, H.Heinrich Nax and B.Bary Pradelski. Quick or cheap? Breaking points in dynamic markets.EC 2020 - 21st ACM Conference on Economics and ComputationBudapest, HungaryJuly 2020, 1-32HALback to text
• 86 inproceedingsP.Panayotis Mertikopoulos, C. H.Christos Harilaos Papadimitriou and G.Georgios Piliouras. Cycles in adversarial regularized learning.SODA '18 - Twenty-Ninth Annual ACM-SIAM Symposium on Discrete AlgorithmsNew Orleans, United StatesJanuary 2018, 2703-2717HALback to text
• 87 articleP.Panayotis Mertikopoulos and W. H.William H. Sandholm. Learning in games via reinforcement learning and regularization.Mathematics of Operations Research414November 2016, 1297-1324HALDOIback to textback to text
• 88 articleP.Panayotis Mertikopoulos and W. H.William H. Sandholm. Riemannian game dynamics.Journal of Economic Theory177September 2018, 315-364HALDOIback to text
• 89 articleM. C.Marcelo Cogo Miletto, L. L.Lucas Leandro Nesi, L.Lucas Mello Schnorr and A.Arnaud Legrand. Performance Analysis of Irregular Task-Based Applications on Hybrid Platforms: Structure Matters.Future Generation Computer Systems135October 2022HALback to text
• 90 inproceedingsM.Mohsen Minaei, M.Mainack Mondal, P.Patrick Loiseau, K. P.Krishna P Gummadi and A.Aniket Kate. Forgetting the Forgotten with Lethe: Conceal Content Deletion from Persistent Observers.PETS 2019 - 19th Privacy Enhancing Technologies SymposiumStockholm, SwedenJuly 2019, 1-21HALback to text
• 91 articleW.W.E. Nagel, A.A. Arnold, M.M. Weber, H.H.C. Hoppe and K.K. Solchenbach. VAMPIR: Visualization and Analysis of MPI Resources.Supercomputer1211996back to text
• 92 inproceedingsL. L.Lucas Leandro Nesi, A.Arnaud Legrand and L.Lucas Mello Schnorr. Exploiting system level heterogeneity to improve the performance of a GeoStatistics multi-phase task-based application.ICPP 2021 - 50th International Conference on Parallel ProcessingLemont, United StatesAugust 2021, 1-10HALDOIback to text
• 93 techreportM.Miquel Oliu-Barton and B.Bary Pradelski. A vaccination policy by zones.Think tank Terra NovaOctober 2020HALback to text
• 94 articleM.Miquel Oliu-Barton, B.Bary Pradelski, P.Philippe Aghion, P.Patrick Artus, I.Ilona Kickbusch, J.Jeffrey Lazarus, D.Devi Sridhar and S.Samantha Vanderslott. SARS-CoV-2 elimination, not mitigation, creates best outcomes for health, the economy, and civil liberties.The Lancet39710291June 2021, 2234-2236HALDOIback to text
• 95 inproceedingsM.Miquel Oliu-Barton and B.Bary Pradelski. Green bridges: Reconnecting Europe to avoid economic disaster.Europe in the Time of Covid-192020HALback to text
• 96 inproceedingsV.V. Pillet, J.J. Labarta, T.T. Cortes and S.S. Girona. PARAVER: A tool to visualise and analyze parallel code.Proceedings of Transputer and Occam Developments, WOTUG-18.441995back to text
• 97 articleB. S.Bary S R Pradelski and H. H.Heinrich H Nax. Market sentiments and convergence dynamics in decentralized assignment economies.International Journal of Game Theory491March 2020, 275-298HALDOIback to text
• 98 techreportB.Bary Pradelski and M.Miquel Oliu-Barton. Focus mass testing: How to overcome low test accuracy.Esade Centre for Economic PolicyDecember 2020HALback to text
• 99 articleB.Bary Pradelski and M.Miquel Oliu-Barton. Green zoning: An effective policy tool to tackle the Covid-19 pandemic.Health Policy1258August 2021, 981-986HALDOIback to text
• 100 inproceedingsD.DA Reed, P.PC Roth, R.RA Aydt, K.KA Shields, L.LF Tavera, R.RJ Noe and B.BW Schwartz. Scalable performance analysis: the Pablo performance analysis environment.Scalable Parallel Libraries Conference1993back to text
• 101 thesisP. H.Pedro Henrique Rocha Bruel. Toward transparent and parsimonious methods for automatic performance tuning.UGA (Université Grenoble Alpes); USP (Universidade de São Paulo)July 2021HALback to text
• 102 inproceedingsB.Ben Shneiderman. The eyes have it: A task by data type taxonomy for information visualizations.IEEE Symposium on Visual LanguagesIEEE1996back to text
• 103 inproceedingsD. C.David C. Snowdon, S.Sergio Ruocco and G.Gernot Heiser. Power Management and Dynamic Voltage Scaling: Myths and Facts.Proceedings of the 2005 Workshop on Power Aware Real-time ComputingNew Jersey, USASeptember 2005back to text
• 104 inproceedingsT.Till Speicher, M.Muhammad Ali, G.Giridhari Venkatadri, F.Filipe Ribeiro, G.George Arvanitakis, F.Fabrício Benevenuto, K. P.Krishna P Gummadi, P.Patrick Loiseau and A.Alan Mislove. Potential for Discrimination in Online Targeted Advertising.FAT 2018 - Conference on Fairness, Accountability, and Transparency81New-York, United StatesFebruary 2018, 1-15HALback to text
• 105 inproceedingsM.Mustafa Tikir, M.Michael Laurenzano, L.Laura Carrington and A.Allan Snavely. PSINS: An Open Source Event Tracer and Execution Simulator for MPI Applications.Euro-Par2009back to text
• 106 inproceedingsG.Giridhari Venkatadri, A.Athanasios Andreou, Y.Yabing Liu, A.Alan Mislove, K. P.Krishna P Gummadi, P.Patrick Loiseau and O.Oana Goga. Privacy Risks with Facebook’s PII-based Targeting: Auditing a Data Broker’s Advertising Interface.39th IEEE Symposium on Security and Privacy (S&P)Proceedings of the 39th IEEE Symposium on Security and Privacy (S&P)San Francisco, United States2018HALback to text
• 107 inproceedingsB.Benoıt Vinot, F.Florent Cadoux and N.Nicolas Gast. Congestion Avoidance in Low-Voltage Networks by using the Advanced Metering Infrastructure.ePerf 2018 - IFIP WG PERFORMANCE - 36th International Symposium on Computer Performance, Modeling, Measurements and EvalutionToulouse, FranceDecember 2018, 1-3HALback to text
• 108 inproceedingsB.Benoît Vinot, F.Florent Cadoux and R.Rodolphe Heliot. Decentralized Optimization of Energy Exchanges in an Electricity Microgrid .ACM e-Energy 2016 - 7th ACM International Conference on Future Energy SystemsWaterloo, CanadaJune 2016HALDOIback to text
• 109 inproceedingsB.Benoît Vinot, F.Florent Cadoux and R.Rodolphe Héliot. Decentralized optimization of energy exchanges in an electricity microgrid.2016 IEEE PES Innovative Smart Grid Technologies Conference Europe (ISGT-Europe)Ljubljana, SloveniaIEEEOctober 2016, 1-6HALDOIback to text
• 110 articleR. R.Richard R. Weber and G.Gideon Weiss. On an Index Policy for Restless Bandits.Journal of Applied Probability2731990, 637--648URL: http://www.jstor.org/stable/3214547back to text
• 111 inproceedingsM.Mark Weiser, B.Brent Welch, A.Alan Demers and S.Scott Shenker. Scheduling for Reduced CPU Energy.Proceedings of the 1st USENIX Conference on Operating Systems Design and ImplementationOSDI '94USAMonterey, CaliforniaUSENIX Association1994, 2–esback to text
• 112 inproceedingsJ.Jeremiah Wilke, K.Khachik Sargsyan, J.Joseph Kenny, B.Bert Debusschere, H.Habib Najm and G.Gilbert Hendry. Validation and Uncertainty Assessment of Extreme-Scale HPC Simulation through Bayesian Inference.Euro-Par2013back to text
• 113 articleO.O. Zaki, E.E. Lusk, W.W. Gropp and D.D. Swider. Toward Scalable Performance Visualization with Jumpshot.International Journal of High Performance Computing Applications1331999DOIback to text
• 114 inproceedingsG.Gengbin Zheng, G.Gunavardhan Kakulapati and L.Laxmikant Kalé. BigSim: A Parallel Simulator for Performance Prediction of Extremely Large Parallel Machines.IPDPS2004back to text
• 115 articleS.Salah Zrigui, R. y.Raphael y de Camargo, A.Arnaud Legrand and D.Denis Trystram. Improving the Performance of Batch Schedulers Using Online Job Runtime Classification.Journal of Parallel and Distributed Computing164February 2022, 83-95HALDOIback to text