Surfing the Ocean
« Surfing the Ocean » is a seminar organized by Antonio Ocello to foster collaboration and exchange innovative ideas on current projects within the consortium.
Want to stay in the loop? If you’re interested in joining our mailing list or presenting your work in a future session, feel free to reach out.
Future presentations
Past presentations
May 15th, 2025
Minimum Volume Conformal Sets for Multivariate Regression
Sacha Braun
Conformal prediction provides a principled framework for constructing predictive sets with finite-sample validity. While much of the focus has been on univariate response variables, existing multivariate methods either impose rigid geometric assumptions or rely on flexible but computationally expensive approaches that do not explicitly optimize prediction set volume. We propose an optimization-driven framework based on a novel loss function that directly learns minimum-volume covering sets while ensuring valid coverage. This formulation naturally induces a new nonconformity score for conformal prediction, which adapts to the residual distribution and covariates. Our approach optimizes over prediction sets defined by arbitrary norm balls, including single and multi-norm formulations. Additionally, by jointly optimizing both the predictive model and predictive uncertainty, we obtain prediction sets that are tight, informative, and computationally efficient, as demonstrated in our experiments on real-world datasets.
April 30th, 2025
A Bayesian decision-theoretic framework for data privacy
Joshua Bon
The scientific and economic value of data continues to grow alongside technology advances. New hardware and software developments enable, but often require, larger and more complex datasets to function effectively. As the importance of input data to these systems becomes increasingly recognized, so too does the loss of privacy for data providers. In this context, data privacy emerges as a critical issue for fields such as statistics and machine learning, as well as for scientific and industrial endeavours that rely on sensitive data. We propose a framework for measuring privacy from a Bayesian decision-theoretic perspective. This framework enables the creation of new, purpose-driven privacy principles that are rigorously justified, while also allowing for the assessment of existing privacy definitions through decision theory. We pay particular attention to the privacy of deterministic algorithms, which are overlooked by current privacy standards, and to the privacy of N Monte Carlo samples drawn from an invariant distribution as N goes to infinity. We show that Probabilistic Differential Privacy is a special case of our framework and provide some new interpretations for Differential Privacy as a result.
April 10th, 2025
Game Dynamics for Multi-Objective Learning: A Modular Approach to Calibration and Multicalibration
Eric Zhao
Calibration is an important measure of how good one’s predictions are, with statistical, decision-theoretic, and complexity-theoretic interpretations. In this talk, I will describe a multi-objective learning perspective of calibration, and how game dynamics provide a modular toolbox for understanding the growing menagerie of calibration definitions and algorithms. We will use this multi-objective learning lens to rewrite calibration—and its multicalibration extensions—to a learning problem with linear loss functions, allowing us to intuitively and constructively obtain state-of-art calibration guarantees. Importantly, I will describe a simple set of « recipes » (game dynamics) for obtaining these guarantees using only well-known no-regret algorithms, and discuss helpful principles for applying these recipes to new problems. Along the way, I will provide a gentle introduction to multicalibration and touch on some motivating applications in unsupervised learning. This talk is based on the following joint works with Jessica Dai, Nika Haghtalab, and Michael Jordan: https://arxiv.org/abs/2302.10863 and https://arxiv.org/abs/2410.14588.
March 27th, 2025
The Role of the Marketplace Operator in Inducing Competition
Tiffany Ding
The steady rise of e-commerce marketplaces highlights the need to study a market structure that captures the key features of this setting. To this end, we consider a price-quantity Stackelberg duopoly in which the leader is the marketplace operator and the follower is an independent seller. The objective of the marketplace operator is to maximize a weighted sum of profit and a term capturing positive customer experience, whereas the independent seller solely seeks to maximize their own profit. Furthermore, the independent seller is required to share a fraction of their revenue with the marketplace operator for the privilege of selling on the platform. We derive the subgame-perfect Nash equilibrium of this game and find that the equilibrium strategies depend on the assumed rationing rule. We then consider practical implications for marketplace operators. Finally, we show that, under intensity rationing, consumer surplus and total welfare in the duopoly marketplace is always at least as high as under an independent seller monopoly, demonstrating that it is socially beneficial for the operator to join the market as a seller. This is based on joint work with Omer Gottesman, Dominique Perrault-Joncas, Orit Ronen, Dean Foster, Dirk Bergemann, and Michael Jordan. Paper available at https://arxiv.org/abs/2503.06582.
March 13th, 2025
A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games
Francisca Vasconcelos
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 zero-sum 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 this work, 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^2)$ 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.
February 27th, 2025
Equitable Pricing in Auctions
Mathieu Molina
How does auction design affect the division of surplus among buyers? We propose a parsimonious measure for equity and apply it to multi-unit auctions, in which unit demand buyers with private-common values pay mixtures of uniform and pay-as-bid pricing. We show that uniform pricing is equity-optimal if and only if buyers have a pure common value. Surprisingly, however, with pure private values, pay-as-bid pricing may not be optimal, and uniform pricing can achieve higher surplus equity. For the class of log-concave signal distributions, we provide prior-free bounds on the equity-optimal pricing rule.
February 20th, 2025
Exploring the Connection Between Fair Classification and Fair Regression
Solène Gaucher
Algorithmic fairness has gained significant attention in recent years as algorithms increasingly shape and influence our daily lives. It is now widely acknowledged that machine learning algorithms can replicate and even amplify societal biases and discrimination. Among the various approaches proposed to address and mitigate algorithmic unfairness, the statistical fairness framework—which will be the focus of this talk—relies on the formalism of supervised learning to enforce fairness constraints on prediction functions. After introducing and motivating the problem, I will present the statistical fairness framework and discuss the different fairness criteria it encompasses. Specifically, I will focus on the criterion of Demographic Parity and examine the relationship between optimal predictions in the contexts of fair classification and fair regression. After reviewing some classical results, I will present new findings that highlight the contrast between scenarios where disparate treatment is either permitted or prohibited.
January 28th, 2025
Towards optimal learning under distribution shift: new algorithms and theory for covariate shift
Lydia Zakynthinou
In this talk, we will discuss the interplay between differential privacy, robustness to data corruptions, sample and computational complexity guarantees of algorithms for statistical estimation. Specifically, we will present recent results that expose trade-offs between the privacy parameters, ε,δ, the fraction of corruptions in the input that the algorithm allows, η, the probability of failure, β, the sample complexity, n, and the running time, T. The talk does not aim to present a single paper, but rather uses the problem of covariance-aware Gaussian mean estimation as a running example to summarize our understanding of these trade-offs that inform our expectations for private statistical estimation more generally. We will finally discuss relaxing the covariance-aware error requirement to retrieve faster algorithms for the problem. The talk relies on works by Hilal Asi, Gavin Brown, Ilias Diakonikolas, Kristian Georgiev, Sam Hopkins, Gautam Kamath, Mahbod Majid, Shyam Narayanan, Ankit Pensia, Stefan Tiegel, Jonathan Ullman, Lydia Zakynthinou.
December 17th, 2024
Towards optimal learning under distribution shift: new algorithms and theory for covariate shift
Reese Pathak
Common machine learning practice implicitly assumes that training data will resemble future data. However, this is often violated, as seen in evolving e-commerce trends, shifting patient populations in healthcare, and changing environments in autonomous driving. Ignoring such distribution shifts can lead to alarming consequences like misguided recommendations, ineffective medical treatments, or risky maneuvers in self-driving cars. In this talk, we describe new advances in learning under a form of distribution shift known as covariate shift. Our main contribution is establishing the (minimax) statistical complexity for prediction and estimation under covariate shift, within the rich framework of reproducing kernel Hilbert spaces (RKHSs). A key tool we develop is a novel, semidefinite programming (SDP)-based complexity measure through which we determine the optimal statistical rate. Our analysis provides concrete recommendations for new, rate-optimal procedures, based on a form of generalized, distribution-dependent shrinkage. Unlike previous results in this area, our work is comparatively fine-grained and assumption-light: we impose essentially no restrictions on covariate distributions and require neither the existence nor boundedness of likelihood ratios. To illustrate the applicability of our theory, we present numerical results demonstrating the state-of-the-art performance of our methods on benchmark covariate shift datasets.
November 19th, 2024
Coarse correlated equilibria in linear quadratic mean field games and application to an emission abatement game
Fanny Cartellier
Coarse correlated equilibria (CCE) are a good alternative to Nash equilibria (NE), as they arise more naturally as outcomes of learning algorithms and they may exhibit higher payoffs than NE. CCEs include a device which allows players’ strategies to be correlated without any cooperation, only through information sent by a mediator. We develop a methodology to concretely compute mean field CCEs in a linear-quadratic mean field game framework. We compare their performance to mean field control solutions and mean field NE (usually named MFG solutions). Our approach is implemented in the mean field version of an emission abatement game between greenhouse gas emitters. In particular, we exhibit a simple and tractable class of mean field CCEs which allows to outperform very significantly the mean field NE payoff and abatement levels, bridging the gap between the mean field NE and the social optimum obtained by mean field control. Joint work with Luciano Campi and Federico Cannerozzi.
November 19th, 2024
Data Markets: From Data Monetization to Platform Architecture
Alireza Fallah
Users share data with platforms in exchange for services, leading to privacy loss when the data is sold to the buyer. We focus on how users, platforms, and the buyer interact, considering factors such as privacy protections, pricing, and competition. Our results show that when the buyer highly values user data, all platforms offer services to users, but when the buyer’s valuation is low, only large platforms with low costs can serve users. We also explore regulatory interventions to enhance user utility, finding that banning data sharing may benefit users only in markets where all platforms are low-cost, while in mixed markets, users prefer noise mandates over sharing bans, especially when applied selectively to high-cost platforms.
October 10th, 2024
Conditioning diffusion models by explicit forward-backward bridging
Adrien Corenflos
Given an unconditional diffusion model $\pi(x,y)$, using it to perform conditional simulation $\pi(x,y)$ is still largely an open question and is typically achieved by learning conditional drifts to the denoising SDE after the fact. In this work, we express conditional simulation as an inference problem on an augmented space corresponding to a partial SDE bridge. This perspective allows us to implement efficient and principled particle Gibbs and pseudo-marginal samplers marginally targeting the conditional distribution $\pi(x,y)$). Contrary to existing methodology, our methods do not introduce any additional approximation to the unconditional diffusion model aside from the Monte Carlo error. We showcase the benefits and drawbacks of our approach on a series of synthetic and real data examples.
October 10th, 2024
Data Taggants: Dataset Ownership Verification via Harmless Targeted Data Poisoning
Wassim Bouaziz
An increasing number of machine learning models are deployed or published with limited transparency regarding their training data, raising concerns about data contamination and the misuse of datasets beyond their intended purpose. Dataset ownership verification, the process of determining if a dataset is used in a model’s training data, can help address these concerns. We introduce data taggants, an approach relying on stealth targeted data poisoning and targets out of distribution samples which act like keys that allow to verify the signature of a message. Through extensive experiments on practical learning settings and a theoretically grounded detection method, we demonstrate our approach is effective and practical for protecting one’s dataset in the wild.
May 14th, 2024
Insufficient Gibbs Sampling
Antoine Luciano
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.
May 14th, 2024
Operationalizing Counterfactual Metrics: Incentives, Ranking, and Information Asymmetry
Serena Wang
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.
April 23rd, 2024
Demonstration-Regularized RL
Daniil Tiapkin
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.
April 23rd, 2024
Data Acquisition via Experimental Design for Decentralized Data Markets
Baihe Huang
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.
March 19th, 2024
Delegating data collection through linear contracting
Nivasini Ananthakrishnan
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.
March 19th, 2024
Unravelling in Collaborative Learning
Aymeric Capitaine
Collaborative learning environments offer a promising avenue for collective intelligence and knowledge sharing. However, the presence of data heterogeneity poses significant challenges to the stability of the learner coalition. In this study, we demonstrate that when data quality is private information, the coalition may undergo a phenomenon known as unraveling, wherein it shrinks up to the point that it becomes empty or made of the worst agent. The adverse effect of unravelling is sizeable and lead to a significant drop in welfare as compared to the full-information case. To address this issue, we propose a novel method inspired by accuracy shaping and probabilistic verification to enforce individual rationality and incentive compatibility. This enables the emergence of the first-best coalition with high probability in spite of information asymmetry, effectively breaking unravelling.
February 27th, 2024
Incentivized Learning In Principal-agent Bandit games
Antoine Scheid
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.
February 27th, 2024
Private Hierarchical Bayesian Model for Federated Learning
Stanislas Du Che
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.
OCEAN 