Séminaire du Pôle Statistiques
Cette page est consacrée à trois types de séminaires organisés par l'équipe de statistiques :
- le SGM (SIMPAS Group Meeting), où les membres de l'équipe SIMPAS présentent leurs derniers résultats ;
- le séminaire de statistiques, où des membres extérieurs au CMAP présentent leurs travaux ;
- Surfing the OCEAN, le séminaire de l'ERC OCEAN soutenu par l'École Polytechnique.
Les organisateurs : Marylou Gabrié, El Mahdi El Mhamdi, & Antonio Ocello
(à contacter à l'alias seminaire-pole-stat "at" meslistes.polytechnique.fr)
Prochaines séances
Avril 2024
Mardi 23 avril, 17h-19h (Surfing the OCEAN)
Lieu : Ce séminaire se déroule dans un format hybride : à PariSanté Campus, Auditorium et sur Zoom https://ecolepolytechnique.zoom.us/j/8214124180 (meeting ID 821 412 4180)
Baihe Huang (UC Berkeley)
Data Acquisition via Experimental Design for Decentralized Data Markets
Acquiring high-quality training data is essential for current machine learning models. Data markets provide a way to increase the supply of data, particularly in data-scarce domains such as healthcare, by incentivizing potential data sellers to join the market. A major challenge for a data buyer in such a market is selecting the most valuable data points from a data seller. Unlike prior work in data valuation, which assumes centralized data access, we propose a federated approach to the data selection problem that is inspired by linear experimental design. Our proposed data selection method achieves lower prediction error without requiring labeled validation data and can be optimized in a fast and federated procedure. The key insight of our work is that a method that directly estimates the benefit of acquiring data for test set prediction is particularly compatible with a decentralized market setting.
Daniil Tiapkin (Ecole Polytechnique)
Demonstration-Regularized RL
Incorporating expert demonstrations has empirically helped to improve the sample efficiency of reinforcement learning (RL). This paper quantifies theoretically to what extent this extra information reduces RL's sample complexity. In particular, we study the demonstration-regularized reinforcement learning framework that leverages the expert demonstrations by KL-regularization for a policy learned by behavior cloning. Our findings reveal that using N^E expert demonstrations enables the identification of an optimal policy at a sample complexity of order O(Poly(S,A,H)/(\eps^2 N^E) in finite and O(Poly(d,H)/(\eps^2 N^E) in linear Markov decision processes, where \eps is the target precision, H the horizon, A the number of action, S the number of states in the finite case and d the dimension of the feature space in the linear case. As a by-product, we provide tight convergence guarantees for the behavior cloning procedure under general assumptions on the policy classes. Additionally, we establish that demonstration-regularized methods are provably efficient for reinforcement learning from human feedback (RLHF). In this respect, we provide theoretical evidence showing the benefits of KL-regularization for RLHF in tabular and linear MDPs. Interestingly, we avoid pessimism injection by employing computationally feasible regularization to handle reward estimation uncertainty, thus setting our approach apart from the prior works.
Mai 2024
Mardi 14 mai, 17h-19h (Surfing the OCEAN)
Lieu : Ce séminaire se déroule dans un format hybride : à PariSanté Campus, Salle 07 et sur Zoom https://ecolepolytechnique.zoom.us/j/8214124180 (meeting ID 821 412 4180)
Serena Wang (UC Berkeley)
Operationalizing Counterfactual Metrics: Incentives, Ranking, and Information Asymmetry
From the social sciences to machine learning, it has been well documented that metrics to be optimized are not always aligned with social welfare. In healthcare, Dranove et al. (2003) showed that publishing surgery mortality metrics actually harmed the welfare of sicker patients by increasing provider selection behavior. We analyze the incentive misalignments that arise from such average treated outcome metrics, and show that the incentives driving treatment decisions would align with maximizing total patient welfare if the metrics (i) accounted for counterfactual untreated outcomes and (ii) considered total welfare instead of averaging over treated patients. Operationalizing this, we show how counterfactual metrics can be modified to behave reasonably in patient-facing ranking systems. Extending to realistic settings when providers observe more about patients than the regulatory agencies do, we bound the decay in performance by the degree of information asymmetry between principal and agent. In doing so, our model connects principal-agent information asymmetry with unobserved heterogeneity in causal inference.
Antoine Luciano (Ceremade, Université Paris Dauphine-PSL)
Insufficient Gibbs Sampling
In some applied scenarios, the availability of complete data is restricted, often due to privacy concerns; only aggregated, robust and inefficient statistics derived from the data are made accessible. These robust statistics are not sufficient, but they demonstrate reduced sensitivity to outliers and offer enhanced data protection due to their higher breakdown point. We consider a parametric framework and propose a method to sample from the posterior distribution of parameters conditioned on various robust and inefficient statistics: specifically, the pairs (median, MAD) or (median, IQR), or a collection of quantiles. Our approach leverages a Gibbs sampler and simulates latent augmented data, which facilitates simulation from the posterior distribution of parameters belonging to specific families of distributions. A by-product of these samples from the joint posterior distribution of parameters and data given the observed statistics is that we can estimate Bayes factors based on observed statistics via bridge sampling. We validate and outline the limitations of the proposed methods through toy examples and an application to real-world income data.
Mardi 28 mai, 11h30-12h30 (SGM)
Lieu : Salle Jean Lascoux
Théo Gnassounou (CMAP, Ecole Polytechnique)
Convolutional Monge Mapping Normalization for learning on sleep data
In many machine learning applications on signals and biomedical data, especially electroencephalogram (EEG), one major challenge is the variability of the data across subjects, sessions, and hardware devices. In this work, we propose a new method called Convolutional Monge Mapping Normalization (CMMN), which consists in filtering the signals in order to adapt their power spectrum density (PSD) to a Wasserstein barycenter estimated on training data. CMMN relies on novel closed-form solutions for optimal transport mappings and barycenters and provides individual test time adaptation to new data without retraining a prediction model. Numerical experiments on sleep EEG data show that CMMN leads to significant and consistent performance gains independent from the neural network architecture when adapting between subjects, sessions, and even datasets collected with different hardware. Notably, our performance gain is on par with much more numerically intensive Domain Adaptation (DA) methods and can be used in conjunction with those for even better performances.
Paul Krzakala (CMAP, Ecole Polytechnique)
End-to-end Supervised Graph Prediction
We address the problem of Supervised Graph Prediction (SGP), that is any task where the output to predict is a graph. Since the graphs are expected to be of arbitrary sizes the output space has a complex non-euclidean structure. As often in structured prediction problems, most of the existing work relies on surrogate representation of the output space which comes at the price of a computationally expensive decoding step. Our new approach, on the other hand, allows us to tackle those tasks in a fully end-to-end manner through a standard deep learning pipeline. To this end, we introduce a novel framework composed of three key components: a representation suited to graphs of arbitrary sizes, an associated neural network architecture and an optimal transport loss that is both differentiable, scalable and permutation invariant.
Séances passées
Mars 2024
Lundi 25 mars, 14h-15h
Ce séminaire est organisé par : Jaouad MOURTADA (CREST), Anna KORBA (CREST), Karim LOUNICI (CMAP)
Lieu : Salle 3001
Vincent DIVOL (Université Paris Dauphine)
Entropic estimation of optimal transport maps in the semi-discrete case
We study the question of estimating the optimal transport map T between two distributions P and Q, based on i.i.d. samples from the two distributions. This problem has gained a lot of traction since J-C. Hütter and P. Rigollet first proposed an estimator in 2021, based on wavelet decompositions. However, all analyses so far crucially rely on the smoothness of the map T, whereas optimal transport maps T are known to be discontinuous in many practical cases (e.g. when P has a connected support and Q has a disconnected support). As a first step towards developing estimation procedures for discontinuous maps, we consider the important special case where the data distribution Q is a discrete measure supported on a finite number of points. We study a computationally efficient estimator of T based on entropic smoothing, and show that it attains optimal, dimension-free rates of convergence. As a byproduct of our analysis, we give a new stability result for the entropic transport map.
Mardi 19 mars, 17h-19h (Surfing the OCEAN)
Lieu : Ce séminaire se déroule dans un format hybride : à PariSanté Campus, Auditorium et sur Zoom https://ecolepolytechnique.zoom.us/j/8214124180 (meeting ID 821 412 4180)
Nivasini Ananthakrishnan (UC Berkeley)
Delegating data collection through linear contracting
We introduce a model of contract design for a principal delegating data collection for machine learning to an agent. We demonstrate the efficacy of linear contracts in dealing with challenges from two forms of uncertainty and information asymmetry between the principal and the agent. The first is the hidden action (moral hazard) challenge due to the principal’s uncertainty about the quality of the data collected. The second is the hidden state (hidden action) challenge due to the principal’s uncertainty about the accuracy level to target. We also demonstrate the efficacy of repeated linear contracting in a multi-round setting where the agent has uncertainty about the learning task and uses payments from each round as feedback to learn more about the task.
Aymeric Capitaine (CMAP, Ecole Polytechnique)
Unravelling in collaborative learning
Collaborative learning environments offer a promising avenue for collective intelligence and knowledge sharing. However, the presence of data heterogeneity poses significant challenges to the size and quality of the resulting learner coalition. In this study, we demonstrate that in scenarios where data quality is private information, the coalition may undergo a well-studied economic phenomenon known as « unravelling ». In this setting, the coalition diminishes in size and becomes dominated by participants possessing the lowest quality data, which may lead to a sizeable drop in total welfare as compared to the full-information case. We propose a novel mechanism inspired by accuracy shaping and probabilistic verification techniques to address this issue, and show that we can recover with high-probability a full-size collaboration in spite of information asymmetry.
Mardi 5 mars, 11h30-12h30 (SGM)
Lieu : PC 44
Baptiste Goujaud (CMAP, Ecole Polytechnique)
Provable non-accelerations of the heavy-ball method
The Heavy-ball ($\HB$) method stands as a cornerstone in the foundations of computational mathematical optimization. In this work, we show that the latter provably does not reach an accelerated convergence rate on smooth strongly convex problems. More specifically, we show that for any condition number and any choice of algorithmic parameters, either the worst-case convergence rate of $\HB$ on the class of $L$-smooth and $\mu$-strongly convex \textit{quadratic} functions is not accelerated (that is, slower than $1 - \mathcal{O}(\kappa)$), or there exists an $L$-smooth $\mu$-strongly convex function and an initialization such that the method does not converge.
To the best of our knowledge, this result closes a simple yet open question on one of the most used and iconic first-order optimization techniques.Our approach builds on finding functions for which $\HB$ fails to converge and instead cycles over finitely many iterates. We analytically describe all the parametrizations of $\HB$ that exhibit this cycling behavior on a particular cycle shape, whose choice is supported by a systematic and constructive approach to the study of cycling behaviors of first-order methods. We show the robustness of our results to perturbations of the cycle and extend them to classes of functions that also satisfy higher-order regularity conditions.
Février 2024
Mardi 27 février, 17h-19h (Surfing the OCEAN)
Lieu : Ce séminaire se déroule dans un format hybride : à PariSanté Campus, Salle 07 et sur Zoom https://ecolepolytechnique.zoom.us/j/8214124180 (meeting ID 821 412 4180)
Antoine Scheid (CMAP, Ecole Polytechnique)
Incentivized Learning in Principal-Agent Bandit Games
This work considers a repeated principal-agent bandit game, where the principal can only interact with her environment through the agent. The principal and the agent have misaligned objectives and the choice of action is only left to the agent. However, the principal can influence the agent’s decisions by offering incentives which add up to his rewards. The principal aims to iteratively learn an incentive policy to maximize her own total utility. This framework extends usual bandit problems and is motivated by several practical applications, such as healthcare or ecological taxation, where traditionally used mechanism design theories often overlook the learning aspect of the problem. We present nearly optimal (with respect to a horizon T) learning algorithms for the principal’s regret in both multi-armed and linear contextual settings. Finally, we support our theoretical guarantees through numerical experiments.
Stanislas du Che (Université Paris Dauphine, PSL)
Private Bayesian Hierarchical Model for Federated Learning
In privacy concerned federated learning, agents share information about common parameters while protecting the privacy of their data. Within a Bayesian perspective, this setting translates into returning privacy-protected conditional posterior distributions to a central server and it also qualifies as a hierarchical Bayes model, which is a category of models for which the original Gibbs sampler was devised. Instead of the common randomization attached to differential privacy, we argue in this work for a substitution of observations at random by locally generated substitutes. Convergence and bias bounds are to be derived to ensure method coherence.
Lundi 19 février, 15h-16h (session spéciale)
Lieu : nouvelle salle de conférence du CMAP (salle 3005, dernier étage, aile 05 - soit le long couloir perpendiculaire à l’aile 0)
Tim Johnston (University of Edinburgh)
The Performance of the Euler Scheme for SDEs with Discontinuous Drift
In recent years there has been a flurry of research addressing the performance of the Euler scheme for SDEs with non-standard coefficients. In this talk we focus on SDEs with discontinuous drift, where a multitude of results have been obtained under very weak conditions. In particular, we show how recent work has connected this line of research with the study of stochastic algorithms (on an unbounded time domain).
Lien : on Zoom https://ecolepolytechnique.zoom.us/j/8214124180 (meeting ID 821 412 4180)