Research

Presentation

Overall objectives

Broad context

One of the principal objectives of Machine Learning (ML) is to automatically discover using past data some underlying structure behind a data generating process in order either to explain past observations or, perhaps more importantly, to make predictions and/or to optimize decisions made on future instances. The area of ML has exploded over the past decade and has had a tremendous impact in many application domains such as computer vision or bioinformatics.

Most of the current ML literature focuses on the case of a single agent (an algorithm) trying to complete some learning task based on gathered data that follows an exogenous distribution independent of the algorithm. One of the key assumptions is that this data has sufficient “regularity” for classical techniques to work. This classical paradigm of “a single agent learning on nice data”, however, is no longer adequate for many practical and crucial tasks that imply users (who own the gathered data) and/or other (learning) agents that are also trying to optimize their own objectives simultaneously, in a competitive or conflicting way. This is the case, for instance, in most learning tasks related to Internet applications (content recommendation/ranking, ad auctions, fraud detection, etc.). Moreover, as such learning tasks rely on users’ personal data and as their outcome affect users in return, it is no longer sufficient to focus on optimizing prediction performance metrics—it becomes crucial to consider societal and ethical aspects such as fairness or privacy.

The field of single agent ML builds on techniques from domains such as statistics, optimization, or functional analysis. When different agents are involved, a strategic aspect inherent in game theory enters the picture. Indeed, interactions—either positive or negative—between rational entities (firms, single user at home, algorithms, etc.) foster individual strategic behavior such as hiding information, misleading other agents, free-riding, etc. Unfortunately, this selfishness degrades the quality of the data or of the predictions, prevents efficient learning and overall may diminish the social welfare. These strategic aspects, together with the decentralized nature of decision making in a multi-agent environment, also make it harder to build algorithms that meet fairness and privacy constraints.

The overarching objective of FAIRPLAY is to create algorithms that learn for and with users—and techniques to analyze them—, that is to create procedures able to perform classical learning tasks (prediction, decision, explanation) when the data is generated or provided by strategic agents, possibly in the presence of other competing learning agents, while respecting the fairness and privacy of the involved users. To that end, we will naturally rely on multi-agent models where the different agents may be either agents generating or providing data, or agents learning in a way that interacts with other agents; and we will put a special focus on societal and ethical aspects, in particular fairness and privacy. Note that in FAIRPLAY, we focus on the technical challenges inherent to formalizing mathematically and respecting ethical properties such as non-discrimination or privacy, often seen as constraints in the learning procedure. Nevertheless, throughout the team’s life, we will reflect on these mathematical definitions for the particular applications studied, in particular their philosophical roots and legal interpretation, through interactions with HSS researchers and with legal specialists (from Criteo).

Multi-agent systems

Any company developing and implementing ML algorithms is in fact one agent within a large network of users and other firms. Assuming that the data is i.i.d. and can be treated irrespectively of the environment response—as is done in the classical ML paradigm—might be a good first approximation, but should be overcome. Users, clients, suppliers, and competitors are adaptive and change their behavior depending on each other’s interactions. The future of many ML companies—such as Criteo—will consist in creating platforms matching the demand (created by their users) to the offer (proposed by their clients), under the system constraints (imposed by suppliers and competitors). Each of these agents have different, conflicting interests that should be taken into account in the model, which naturally becomes a multi-agent model.

Each agent in a multi-agent system may be modeled as having their own utility function $u_{i}$ that can depend on the action of other agents. Then, there are two main types of objectives: individual or collective 99. If each agent is making their own decision, then they can be modeled as each optimizing their own individual utility (which may include personal benefit as well as other considerations such as altruism where appropriate) unilaterally and in a decentralized way. This is why a mechanism providing correct incentives to agents is often necessary. At the other extreme, social welfare is the collective objective defined as the cumulative sum of utilities of all agents. To optimize it, it is almost always necessary to consider a centralized optimization or learning protocol. A key question in multi-agent systems is to apprehend the “social cost” of letting agents optimize their own utility by choosing unilaterally their decision compared to the one maximizing social welfare; this is often measured by the “price of anarchy”/“price of stability” 108: the ratio of the maximum social welfare to the (worst/best) social welfare when agents optimize individually.

The natural language to model and study multi-agent systems is game theory—see below for a list of tools and techniques on which FAIRPLAY relies, game theory being the first of them. Multi-agent systems have been studied in the past; but not with a focus on learning systems where agents are either learning or providing data, which is our focus in FAIRPLAY and leads to a blend of game theory and learning techniques. We note here again that, wherever appropriate, we shall reflect (in part together with colleagues from HSS) on the soundness of the utility framework for the considered applications.

Societal aspects and ethics

There are several important ethical aspects that must be investigated in multi-agent systems involving users either as data providers or as individuals affected by the ML agent decision (or both).

Fairness and Discrimination

When ML decisions directly affect humans, it is important to ensure that they do not violate fairness principles, be they based on ethical or legal grounds. As ML made its way in many areas of decision making, it was unfortunately repeatedly observed that it can lead to discrimination (regardless of whether or not it is intentional) based on gender, race, age, or other sensitive attributes. This was observed in online targeted advertisement 93, 119, 33, 77, 93, 35, but also in many other applications such as hiring 64, data-driven healthcare 71, or justice 94. Biases also have the unfortunate tendency to reinforce. An operating multi-agent learning system should be able in the long run to get rid by itself of inherent population biases, that is, be fair amongst users irrespective of the improperly constructed dataset.

The mathematical formulation of fairness has been debated in recent works. Although a few initial works proposed a notion of individual fairness, which mandates that “similar individuals” receive “similar outcomes” 66, this notion was quickly found unpractical because it relies on a metric to define closeness that makes the definition somewhat arbitrary. Most of the works then focused on notions of group fairness, which mandate equality of outcome “on average” across different groups defined by sensitive attributes (e.g., race, gender, religious belief, etc.). Most of the works on group fairness focus on the classification problem (e.g., classifying whether a job applicant is good or not for the job) where each data example $(X_{i}, Y_{i})$ contains a set of features $X_{i}$ and a true label $Y_{i} \in {0, 1}$ and the goal is to make a prediction ${\hat{Y}}_{i}$ based on the features $X_{i}$ that has a high probability to be equal to the true label. Assuming that there is a single sensitive attribute $s_{i}$ that can take two values $a$ or $b$ , this defines two groups: those for whom $s_{i} = a$ and those for whom $s_{i} = b$ . There are several different concepts of group fairness that can be considered; we shall especially focus on demographic parity (DP), which prescribes $P ({\hat{Y}}_{i} = 1 | s_{i} = a) = P ({\hat{Y}}_{i} = 1 | s_{i} = b)$ and equal opportunity (EO) 78, which mandates that $P ({\hat{Y}}_{i} = 1 | s_{i} = a, Y_{i} = 1) = P ({\hat{Y}}_{i} = 1 | s_{i} = b, Y_{i} = 1)$ .

The fair classification literature proposed, for each of these fairness notions, ways to train fair classifiers based on three main ideas: pre-processing 127, in-processing 125, 126, 122, and post-processing 78. All of these works, however, focus on idealized situations where a single decision-maker has access to ground truth data with the sensitive features and labels in order to train classifiers that respect fairness constraints. We use similar group fairness definitions and extend them (in particular through causality), but our goal is to go further in terms of algorithms by modeling practical scenarios with multiple decision-makers and incomplete information (in particular lack of ground truth on the labels).

Privacy vs. Incentives

ML algorithms, in particular in Internet applications, often rely on users’ personal information (whether it is directly their personal data or indirectly some hidden “type” – gender, ethnicity, behaviors, etc.). Nevertheless, users may be willing to provide their personal information if it increases their utility. This brings a number of key questions. First, how can we learn while protecting users’ privacy (and how should privacy even be defined)? Second, finding the right balance between those two a-priori incompatible concepts is challenging; how much (and even simply how) should an agent be compensated for providing useful and accurate data?

Differential privacy is the most widely used private learning framework 65, 67, 114 and ensures that the output of an algorithm does not significantly depend on a single element of the whole dataset. These privacy constraints are often too strong for economic applications (as illustrated before, it is sometimes optimal to disclose some private information). $f$ -divergence privacy costs have thus been proposed in recent literature as a promising alternative 57. These $f$ -divergences, such as Kullback-Leibler, are also used by economists to measure the cost of information from a Bayesian perspective, as in the rational inattention literature 118, 101, 96. It was only recently that this approach was considered to measure “privacy losses” in economic mechanisms 68. In this model, the mechanism designer has some prior belief on the unobserved and private information. After observing the player’s action, this belief is updated and the cost of information corresponds to the KL between the prior and posterior distributions of this private information.

This privacy concept can be refined up to a single user level, into the so-called local differential privacy. Informally speaking, the algorithm output can also depend on a single user data that still must be kept private. Estimation are actually sometimes more challenging under this constraint, i.e., estimation rates degrade 115, 52, 53 but is sometimes more adapted to handle user-generated data 73.

Interestingly, we note that the notions of privacy and fairness are somewhat incompatible. This will motivate Theme 2 developed in our research program.

A large variety of tools and techniques

Analyzing multi-agent learning systems with ethical constraints will require us to use, develop, and merge several different theoretical tools and techniques. We describe the main ones here. Note that although FAIRPLAY is motivated by practical use-cases and applications, part of the team’s objectives is to improve those tools as necessary to tackle the problems studied.

Game theory and economics

Game theory 72 is the natural mathematical tool to model multiple interacting decision-makers (called players). A game is defined by a set of players, a set of possible actions for each player, and a payoff function for each player that can depend on the actions of all the players (that is the distinguishing feature of a game compared to an optimization problem). The most standard solution concept is the so-called Nash equilibrium, which is defined as a strategy profile (i.e., a collection of possibly randomized action for each player) such that each player is at best response (i.e., has the maximum payoff given the others’ strategies). It is a “static” (one-shot) solution concept, but there also exist dynamic solution concepts for repeated games 56, 103.

Online and reinforcement learning 49

In online learning (a.k.a. multi-armed bandit 50, 110), data is gathered and treated on the fly. For instance, consider an online binary classification problem. Some unlabelled data $X_{t} \in R^{d}$ is observed, and the agent predicts its label $Y_{t}$ ; let us denote ${\hat{Y}}_{t} \in \pm 1$ the prediction. The agent potentially observes the loss $1 {Y_{t} \neq {\hat{Y}}_{t}}$ and then receives another new unlabeled data example $X_{t + 1}$ . In that specific problem, the typical learning objective is to perform asymptotically as good as the best classifier $f^{*}$ in some given class $ℱ$ , i.e., such that the loss $\sum_{t = 1}^{T} 1 {Y_{t} \neq {\hat{Y}}_{t}}$ is $o (T)$ -close to ${max}_{f \in ℱ} \sum_{t = 1}^{T} 1 {Y_{t} \neq f (X_{t})}$ ; the difference between those terms is called regret. The more general model with an underlying state of the world $S_{t} \in 𝒮$ that evolves at each step following some Markov Decision Process (MDP, i.e., the transition matrix from $S_{t}$ to $S_{t + 1}$ depend on the actions of the agent) and impacts the loss function is called reinforcement learning (RL). RL is an incredibly powerful learning technique, provided enough data are available since learning is usually quite slow. This is why the recent successes involve settings with heavy simulations (like games) or well-understood physical systems (like robots).

These techniques will be central to our approach as we aim to model problems where ground truth data is not available upfront and problems involving sequential decision making. There have been some successful first results in that direction. For instance, there are applications (e.g., cognitive radio) where several agents (users) aim at finding a matching with resources (the different bandwidth). They can do that by “probing” the resources, estimating their preferences and trying to find some stable matchings 47, 95.

Online algorithms 45 and theoretical computer science

Online algorithms are closely related to online learning with a major twist. In online learning, the agent has “0-look ahead”; for instance, in the online binary classification example, the loss at stage $t$ was $1 {Y_{t} \neq {\hat{Y}}_{t}}$ but $Y_{t}$ was not known in advance. The comparison class, on the other hand, was the empirical performance of a given set of classifiers. In online algorithms, the agents have “1-look ahead”; in the classification example, this means that $Y_{t}$ is known before choosing ${\hat{Y}}_{t}$ . But the overall objective is obviously no longer the minimisation of the empirical error, but the minimisation of this error plus the total number of changes (say). The comparison class is then larger, namely a subset of admissible (or the whole set) sequences of prediction ${\pm 1}^{T}$ . The typical and relevant example of online problem relevant for Criteo that will be investigated is the matching problem: agents and resources arrive sequentially and must be, if possible, paired together as fast as possible (and as successfully as possible). Variants of these problems include the optimal stopping time question (when/how make a final decision) such as prophet inequalities and related questions 62,

Optimal transport 120

Optimal transport is a quite old problem introduced by Monge where an agent aims at moving a pile of sand to fill a hole at the smallest possible price. Formally speaking, given two probability measures $μ$ and $ν$ on some space $𝒳$ , the optimal transport problem consist in finding (if it exists, otherwise the problem can be relaxed) a transport map $T : 𝒳 \to 𝒳$ that minimizes $\int_{𝒳} c (x, T (x)) d μ (x)$ for some cost function $c : 𝒳^{2} \to R$ , under the constraint that $T ♯ μ = ν$ , where $T ♯ μ$ is the push-forward measure of $μ$ by $T$ . Interestingly, when $μ$ and $ν$ are empirical measures, i.e., $μ = \frac{1}{N} \sum_{n = 1} δ_{x_{n}}$ and $ν = \frac{1}{N} \sum_{n = 1} δ_{y_{n}}$ , a transport map is nothing more than a matching between ${x_{n}}$ and ${y_{n}}$ that minimizes the cost $\sum_{n} c (x_{n}, T (x_{n}))$ .

Recently, optimal transport gained a lot of interest in the ML community 109 thanks to its application to images and to new techniques to compute approximate matchings in a tractable way 112. Even more unexpected applications of optimal transport have been discovered: to protect privacy 48, fairness 41, etc. Those connections are promising, but only primitive for the moment. For instance, consider the problem of matching students to schools. The unfairness level of a school can be measured as the Wasserstein distance between the distribution of the students within that school compared to the overall distribution of students. Then the matching algorithms could have a constraint of minimizing the sum of (or its maximum) unfairness levels; alternatively, we could aim at designing mechanisms giving incentives to schools to be fair in their allocation (or at least in their list preferences), typically by paying a higher fee if the unfairness level is high.

General objectives

The overarching objective of FAIRPLAY of to create algorithms to learn for and with users—and techniques to analyze them—, through the study of multi-agent learning systems where the agents can be cooperatively or competitively learning agents, or agents providing or generating data, while guaranteeing that fairness and privacy constraints are satisfied for the involved users. We detail this global objective into a number of more specific ones.

Objective 1: Developing fair and private mechanisms

Our first objective is to incorporate ethical aspects of fairness and privacy in mechanisms used in typical problems occurring in Internet applications, in particular auctions, matching, and recommendation. We will focus on social welfare and consider realistic cases with multiple agents and sequential learning that occur in practice due to sequential decision making. Our objective is both to construct models to analyze the problem, to devise algorithms that respect the constraints at stake, and to evaluate the different trade-offs in standard notions of utility introduced by ethical constraints.

Objective 2: Developing multi-agent statistics and learning

Data is now acquired, treated and/or generated by a whole network of agents interacting with the environment. There are also often multiple agents learning either collaboratively or competitively. Our second objective is to build a new set of tools to perform statistics and learning tasks in such environments. To this end, we aim at modeling these situations as multi-agent systems and at studying the dynamics and equilibrium of these complex game-theoretic situations between multiple learning algorithms and data providers.

Objective 3: Improving the theoretical state of the art

Research must rely on theoretical, proven guarantees. We develop new results for the techniques introduced before, such as prophet inequalities, (online) matchings, bandits and RL, etc.

Objective 4: Proposing practical solutions and enhancing transfer from research to industry

Our last scientific objective is to apply and implement theoretical works and results to practical cases. This will be a crucial component of the project as we focus on transfer within Criteo.

Objective 5: Scientific Publications

We aim at publishing our results in top-tier machine learning conferences (NeurIPS, ICML, COLT, ICLR, etc.) and in top-tier game theory journals (Games and Economic Behavior, Mathematics of OR, etc.). We will also target conferences at the junction of those fields (EC, WINE, WebConf, etc.) as well as conferences specifically on security and privacy (IEEE S&P, NDSS, CSS, PETS, etc.) and on fairness (FAccT, AIES).

All the five objectives are interlaced. For instance, fairness and privacy constraints are important in Objective 2 whereas the multi-agent aspect is also important in Objective 1. Objectives 4 and 5 are transversal and present in all the first three objectives.

Last activity report : 2023

2023 : PDF – HTML
2022 : PDF – HTML

Results

New results

Auctions and mechanism design

In 18, we consider the problem of maximizing the success probability of policy allocations in online bidding systems. The effectiveness of advertising in e-commerce largely depends on the ability of merchants to bid on and win impressions for their targeted users. The bidding procedure is highly complex due to various factors such as market competition, user behavior, and the diverse objectives of advertisers. In this paper we consider the problem at the level of user timelines instead of individual bid requests, manipulating full policies (i.e. pre-defined bidding strategies) and not bid values. In order to optimally allocate policies to users, typical multiple treatments allocation methods solve knapsack-like problems which aim at maximizing an expected value under constraints. In the industrial contexts such as online advertising, we argue that optimizing for the probability of success is a more suited objective than expected value maximization, and we introduce the SuccessProbaMax algorithm that aims at finding the policy allocation which is the most likely to outperform a fixed reference policy. Finally, we conduct comprehensive experiments both on synthetic and real-world data to evaluate its performance. The results demonstrate that our proposed algorithm outperforms conventional expected-value maximization algorithms in terms of success rate.

In 20, we study a mechanism design problem for pool testing. Large-scale testing is crucial in pandemic containment, but resources are often prohibitively constrained. We study the optimal application of pooled testing for populations that are heterogeneous with respect to an individual’s infection probability and utility that materializes if included in a negative test. We show that the welfare gain from overlapping testing over non-overlapping testing is bounded. Moreover, non-overlapping allocations, which are both conceptually and logistically simpler to implement, are empirically near-optimal, and we design a heuristic mechanism for finding these near-optimal test allocations. In numerical experiments, we highlight the efficacy and viability of our heuristic in practice. We also implement and provide experimental evidence on the benefits of utility-weighted pooled testing in a real-world setting. Our pilot study at a higher education research institute in Mexico finds no evidence that performance and mental health outcomes of participants in our testing regime are worse than under the first-best counterfactual of full access for individuals without testing.

In 21, we study substitutes markets with budget constraints. Markets with multiple divisible goods have been studied widely from the perspective of revenue and welfare. In general, it is well known that envy-free revenue-maximal outcomes can result in lower welfare than competitive equilibrium outcomes. We study a market in which buyers have quasilinear utilities with linear substitutes valuations and budget constraints, and the seller must find prices and an envy-free allocation that maximise revenue or welfare. Our setup mirrors markets such as ad auctions and auctions for the exchange of financial assets. We prove that the unique competitive equilibrium prices are also envy-free revenue-maximal. This coincidence of maximal revenue and welfare is surprising and breaks down even when buyers have piecewise-linear valuations. We present a novel characterisation of the set of ‘feasible’ prices at which demand does not exceed supply, show that this set has an elementwise minimal price vector, and demonstrate that these prices maximise revenue and welfare. The proof also implies an algorithm for finding this unique price vector.

Online algorithms and learning

Learning in games

In citefiegel:hal-04416177, we study how to learn $ϵ$ -optimal strategies in zero-sum imperfect information games (IIG) with trajectory feedback. In this setting, players update their policies sequentially based on their observations over a fixed number of episodes, denoted by $T$ . Existing procedures suffer from high variance due to the use of importance sampling over sequences of actions (Steinberger et al., 2020; McAleer et al., 2022). To reduce this variance, we consider a fixed sampling approach, where players still update their policies over time, but with observations obtained through a given fixed sampling policy. Our approach is based on an adaptive Online Mirror Descent (OMD) algorithm that applies OMD locally to each information set, using individually decreasing learning rates and a regularized loss. We show that this approach guarantees a convergence rate of $\tilde{O} (T^{- 1 / 2})$ with high probability and has a near-optimal dependence on the game parameters when applied with the best theoretical choices of learning rates and sampling policies. To achieve these results, we generalize the notion of OMD stabilization, allowing for time-varying regularization with convex increments.

Bandits, control and reinforcement learning

In 10, we consider the problem of regret minimization in non-parametric stochastic bandits. When the rewards are known to be bounded from above, there exists asymptotically optimal algorithms, with asymptotic regret depending on an infimum of Kullback-Leibler divergences (KL). These algorithms are computationally expensive and require storing all past rewards, thus simpler but non-optimal algorithms are often used instead. We introduce several methods to approximate the infimum KL which reduce drastically the computational and memory costs of existing optimal algorithms, while keeping their regret guaranties. We apply our findings to design new variants of the MED and IMED algorithms, and demonstrate their interest with extensive numerical simulations.

In 17, we introduce Dynamic Contextual Markov Decision Processes (DCMDPs), a novel reinforcement learning framework for history-dependent environments that generalizes the contextual MDP framework to handle non-Markov environments, where contexts change over time. We consider special cases of the model, with a focus on logistic DCMDPs, which break the exponential dependence on history length by leveraging aggregation functions to determine context transitions. This special structure allows us to derive an upper-confidence-bound style algorithm for which we establish regret bounds. Motivated by our theoretical results, we introduce a practical model-based algorithm for logistic DCMDPs that plans in a latent space and uses optimism over history-dependent features. We demonstrate the efficacy of our approach on a recommendation task (using MovieLens data) where user behavior dynamics evolve in response to recommendations.

In 4, we consider the diffusive limit of a typical pure-jump Markovian control problem as the intensity of the driving Poisson process tends to infinity. We show that the convergence speed is provided by the Hölder constant of the Hessian of the limit problem, and explain how correction terms can be constructed. This provides an alternative efficient method for the numerical approximation of the optimal control of a pure-jump problem in situations with very high intensity of jump. We illustrate this approach in the context of a display advertising auction problem.

Online (and offline) algorithms

In 15, we study online algorithms with advice querying under a budget constraint. Several problems have been extensively studied in the learning-augmented setting, where the algorithm has access to some, possibly incorrect, predictions. However, it is assumed in most works that the predictions are provided to the algorithm as input, with no constraint on their size. In this paper, we consider algorithms with access to a limited number of predictions, that they can request at any time during their execution. We study three classical problems in competitive analysis, the ski rental problem, the secretary problem, and the non-clairvoyant job scheduling. We address the question of when to query predictions and how to use them.

In 16, we also study online algorithms with predictions. A popular approach to go beyond the worst-case analysis of online algorithms is to assume the existence of predictions that can be leveraged to improve performances. Those predictions are usually given by some external sources that cannot be fully trusted. Instead, we argue that trustful predictions can be built by algorithms, while they run. We investigate this idea in the illustrative context of static scheduling with exponential job sizes. Indeed, we prove that algorithms agnostic to this structure do not perform better than in the worst case. In contrast, when the expected job sizes are known, we show that the best algorithm using this information, called Follow-The-Perfect-Prediction (FTPP), exhibits much better performances. Then, we introduce two adaptive explore-then-commit types of algorithms: they both first (partially) learn expected job sizes and then follow FTPP once their self-predictions are confident enough. On the one hand, ETCU explores in “series”, by completing jobs sequentially to acquire information. On the other hand, ETCRR, inspired by the optimal worst-case algorithm Round-Robin (RR), explores efficiently in “parallel”. We prove that both of them asymptotically reach the performances of FTPP, with a faster rate for ETCRR. Those findings are empirically evaluated on synthetic data.

In 9, we study scheduling of moldable tasks, in the offline setting. Moldable tasks allow schedulers to determine the number of processors assigned to each task, thus enabling efficient use of large-scale parallel processing systems. We consider the problem of scheduling independent moldable tasks on processors and propose a new perspective of the existing speedup models: as the number p of processors assigned to a task increases, the speedup is linear if $p$ is small and becomes sublinear after $p$ exceeds a threshold. Based on this, we propose an efficient approximation algorithm to minimize the makespan. As a by-product, we also propose an approximation algorithm to maximize the sum of values of tasks completed by a deadline; this scheduling objective is considered for moldable tasks for the first time while similar works have been done for other types of parallel tasks.

Statistical estimation

In 11, we discuss an application of Stochastic Approximation to statistical estimation of highdimensional sparse parameters. The proposed solution reduces to resolving a penalized stochastic optimization problem on each stage of a multistage algorithm; each problem being solved to a prescribed accuracy by the non-Euclidean Composite Stochastic Mirror Descent (CSMD) algorithm. Assuming that the problem objective is smooth and quadratically minorated and stochastic perturbations are sub-Gaussian, our analysis prescribes the method parameters which ensure fast convergence of the estimation error (the radius of a confidence ball of a given norm around the approximate solution). This convergence is linear during the first “preliminary” phase of the routine and is sublinear during the second “asymptotic” phase. We consider an application of the proposed approach to sparse Generalized Linear Regression problem. In this setting, we show that the proposed algorithm attains the optimal convergence of the estimation error under weak assumptions on the regressor distribution. We also present a numerical study illustrating the performance of the algorithm on high-dimensional simulation data.

In 8, we study a change-point detection problem. Given a times series $𝐘$ in $ℝ^{n}$ , with a piece-wise contant mean and independent components, the twin problems of change-point detection and change-point localization respectively amount to detecting the existence of times where the mean varies and estimating the positions of those change-points. In this work, we tightly characterize optimal rates for both problems and uncover the phase transition phenomenon from a global testing problem to a local estimation problem. Introducing a suitable definition of the energy of a change-point, we first establish in the single change-point setting that the optimal detection threshold is $\sqrt{2 l o g l o g (n)}$ . When the energy is just above the detection threshold, then the problem of localizing the change-point becomes purely parametric: it only depends on the difference in means and not on the position of the change-point anymore. Interestingly, for most change-point positions, including all those away from the endpoints of the time series, it is possible to detect and localize them at a much smaller energy level. In the multiple change-point setting, we establish the energy detection threshold and show similarly that the optimal localization error of a specific change-point becomes purely parametric. Along the way, tight optimal rates for Hausdorff and l 1 estimation losses of the vector of all change-points positions are also established. Two procedures achieving these optimal rates are introduced. The first one is a least-squares estimator with a new multiscale penalty that favours well spread change-points. The second one is a two-step multiscale post-processing procedure whose computational complexity can be as low as $O (n l o g (n))$ . Notably, these two procedures accommodate with the presence of possibly many low-energy and therefore undetectable change-points and are still able to detect and localize high-energy change-points even with the presence of those nuisance parameters.

In 6, we study variable selection, monotone likelihood ratio and group sparsity. In the pivotal variable selection problem, we derive the exact non-asymptotic minimax selector over the class of all s-sparse vectors, which is also the Bayes selector with respect to the uniform prior. While this optimal selector is, in general, not realizable in polynomial time, we show that its tractable counterpart (the scan selector) attains the minimax expected Hamming risk to within factor 2, and is also exact minimax with respect to the probability of wrong recovery. As a consequence, we establish explicit lower bounds under the monotone likelihood ratio property and we obtain a tight characterization of the minimax risk in terms of the best separable selector risk. We apply these general results to derive necessary and sufficient conditions of exact and almost full recovery in the location model with light tail distributions and in the problem of group variable selection under Gaussian noise.

Privacy, Fairness, and Transparency

In 14, 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 (\sqrt{T})$ . 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.

In 12, we study the related problem of transparency, in the particular case of targeted advertising. Several targeted advertising platforms offer transparency mechanisms, but researchers and civil societies repeatedly showed that those have major limitations. In this paper, we propose a collaborative ad transparency method to infer, without the cooperation of ad platforms, the targeting parameters used by advertisers to target their ads. Our idea is to ask users to donate data about their attributes and the ads they receive and to use this data to infer the targeting attributes of an ad campaign. We propose a Maximum Likelihood Estimator based on a simplified Bernoulli ad delivery model. We first test our inference method through controlled ad experiments on Facebook. Then, to further investigate the potential and limitations of collaborative ad transparency, we propose a simulation framework that allows varying key parameters. We validate that our framework gives accuracies consistent with real-world observations such that the insights from our simulations are transferable to the real world. We then perform an extensive simulation study for ad campaigns that target a combination of two attributes. Our results show that we can obtain good accuracy whenever at least ten monitored users receive an ad. This usually requires a few thousand monitored users, regardless of population size. Our simulation framework is based on a new method to generate a synthetic population with statistical properties resembling the actual population, which may be of independent interest.

In 13, we also study a transparency problem related to fairness, but in the context of decentralized systems. In permissionless blockchains, transaction issuers include a fee to incentivize miners to include their transactions. To accurately estimate this prioritization fee for a transaction, transaction issuers (or blockchain participants, more generally) rely on two fundamental notions of transparency, namely contention and prioritization transparency. Contention transparency implies that participants are aware of every pending transaction that will contend with a given transaction for inclusion. Prioritization transparency states that the participants are aware of the transaction or prioritization fees paid by every such contending transaction. Neither of these notions of transparency holds well today. Private relay networks, for instance, allow users to send transactions privately to miners. Besides, users can offer fees to miners via either direct transfers to miners’ wallets or off-chain payments-neither of which are public. In this work, we characterize the lack of contention and prioritization transparency in Bitcoin and Ethereum resulting from such practices. We show that private relay networks are widely used and private transactions are quite prevalent. We show that the lack of transparency facilitates miners to collude and overcharge users who may use these private relay networks despite them offering little to no guarantees on transaction prioritization. The lack of these transparencies in blockchains has crucial implications for transaction issuers as well as the stability of blockchains. Finally, we make our data sets and scripts publicly available.

In 5, we address the problem of variable selection in a high-dimensional but sparse mean model, under the additional constraint that only privatised data are available for inference. The original data are vectors with independent entries having a symmetric, strongly log-concave distribution on $ℝ$ . For this purpose, we adopt a recent generalisation of classical minimax theory to the framework of local $α -$ differential privacy. We provide lower and upper bounds on the rate of convergence for the expected Hamming loss over classes of at most $s$ -sparse vectors whose non-zero coordinates are separated from 0 by a constant $a > 0$ . As corollaries, we derive necessary and sufficient conditions (up to log factors) for exact recovery and for almost full recovery. When we restrict our attention to non-interactive mechanisms that act independently on each coordinate our lower bound shows that, contrary to the non-private setting, both exact and almost full recovery are impossible whatever the value of $a$ in the high-dimensional regime such that $n α^{2} / d^{2} \leq 1$ . However, in the regime $n α^{2} / d^{2} ≫ log (d)$ we can exhibit a critical value $a^{*}$ (up to a logarithmic factor) such that exact and almost full recovery are possible for all $a ≫ a^{*}$ and impossible for $a \leq a^{*}$ . We show that these results can be improved when allowing for all non-interactive (that act globally on all coordinates) locally $α -$ differentially private mechanisms in the sense that phase transitions occur at lower levels.

In 7, we study interactive versus non-interactive locally differentially private estimation for the quadratic functional. Local differential privacy has recently received increasing attention from the statistics community as a valuable tool to protect the privacy of individual data owners without the need of a trusted third party. Similar to the classical notion of randomized response, the idea is that data owners randomize their true information locally and only release the perturbed data. Many different protocols for such local perturbation procedures can be designed. In most estimation problems studied in the literature so far, however, no significant difference in terms of minimax risk between purely non-interactive protocols and protocols that allow for some amount of interaction between individual data providers could be observed. In this paper we show that for estimating the integrated square of a density, sequentially interactive procedures improve substantially over the best possible non-interactive procedure in terms of minimax rate of estimation. In particular, in the non-interactive scenario we identify an elbow in the minimax rate at $s = 3 / 4$ , whereas in the sequentially interactive scenario the elbow is at $s = 1 / 2$ . This is markedly different from both, the case of direct observations, where the elbow is well known to be at $s = 1 / 4$ , as well as from the case where Laplace noise is added to the original data, where an elbow at $s = 9 / 4$ is obtained. We also provide adaptive estimators that achieve the optimal rate up to log-factors, we draw connections to non-parametric goodness-of-fit testing and estimation of more general integral functionals and conduct a series of numerical experiments. The fact that a particular locally differentially private, but interactive, mechanism improves over the simple non-interactive one is also of great importance for practical implementations of local differential privacy.

Research direction 1

…….
Research direction 2

……….
Research direction 3

……….

Presentation

Overall objectives

Broad context

Multi-agent systems

Societal aspects and ethics

Fairness and Discrimination

Privacy vs. Incentives

A large variety of tools and techniques

Game theory and economics

Online and reinforcement learning 49

Online algorithms 45 and theoretical computer science

Optimal transport 120

General objectives

Last activity report : 2023

Results

New results

Auctions and mechanism design

Online algorithms and learning

Learning in games

Bandits, control and reinforcement learning

Online (and offline) algorithms

Statistical estimation

Privacy, Fairness, and Transparency

Research direction 1

Research direction 2

Research direction 3