Alexandra Carpentier
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Alexandra Carpentier has a total of 46 co-authors. Here are the top co-authors by number of shared publications:
Rémi Munos
4 shared publicationsArlene Kim
Sungshin Womens Univ, Dept Stat, 34Da Gil 2, Seoul 02844, South Korea
2 shared publications- Céline Duval
Laboratoire MAP5 UMR CNRS 8145 Université Paris Descartes France
2 shared publications - Ester Mariucci
Universität Potsdam Germany
2 shared publications - Maureen Clerc
INRIA
2 shared publications R. Munos
2 shared publications
Latest Publications
- 30 March 2026
- Published by Agence Bibliographique de l'Enseignement Supérieur
On optimal sampling in high and low dimension
De l'échantillonage optimal en grande et petite dimension: Pendant ma thèse, j’ai eu la chance d’apprendre et de travailler sous la supervision de mon directeur de thèse Rémi, et ce dans deux domaines qui me sont particulièrement chers. Je veux parler de la Théorie des Bandits et du Compressed Sensing. Je les voie comme intimement liés non par les méthodes mais par leur objectif commun: l’échantillonnage optimal de l’espace. Tous deux sont centrés sur les manières d’échantillonner l’espace efficacement : la Théorie des Bandits en petite dimension et le Compressed Sensing en grande dimension. Dans cette dissertation, je présente la plupart des travaux que mes co-auteurs et moi-même avons écrit durant les trois années qu’a duré ma thèse.
- 30 March 2026
- Published by Agence Bibliographique de l'Enseignement Supérieur
On optimal sampling in high and low dimension
De l'échantillonage optimal en grande et petite dimension: Pendant ma thèse, j’ai eu la chance d’apprendre et de travailler sous la supervision de mon directeur de thèse Rémi, et ce dans deux domaines qui me sont particulièrement chers. Je veux parler de la Théorie des Bandits et du Compressed Sensing. Je les voie comme intimement liés non par les méthodes mais par leur objectif commun: l’échantillonnage optimal de l’espace. Tous deux sont centrés sur les manières d’échantillonner l’espace efficacement : la Théorie des Bandits en petite dimension et le Compressed Sensing en grande dimension. Dans cette dissertation, je présente la plupart des travaux que mes co-auteurs et moi-même avons écrit durant les trois années qu’a duré ma thèse.
- Open Access
- 17 September 2025
- Published by European Mathematical Society - EMS - Publishing House GmbH in Mathematical Statistics and Learning
- Vol. 8 (3) , 165-192
A simple and improved algorithm for noisy, convex, zeroth-order optimisation
In this paper, we study the problem of noisy, convex, zeroth-order optimisation of a function f over a bounded convex set \overline{\mathcal{X}}\subset \mathbb{R}^{d} . Given a budget n of noisy queries to the function f that can be allocated sequentially and adaptively, our aim is to construct an algorithm that returns a point \hat x\in \overline{\mathcal{X}} such that f(\hat x) is as small as possible. We provide a conceptually simple method inspired by the textbook centre of gravity method, but adapted to the noisy and zeroth-order setting. We prove that this method is such that the f(\hat x) - \min_{x\in \overline{\mathcal{X}}}f(x) is of smaller order than d^{2}/\sqrt{n} up to poly-logarithmic terms. We slightly improve upon literature preceding this work, where the best-known rate was in Lattimore (2019) and was of order d^{2.5}/\sqrt{n} , albeit for a more challenging problem – yet in the literature contemporaneous to our work, the remarkable work of Fokkema et al. (2024) attains the faster rate of d^{1.5}/\sqrt{n} under mild conditions on \overline{\mathcal{X}} . Our main contribution is, however, conceptual, as we believe that our algorithm and its analysis bring novel ideas and are significantly simpler than the existing approaches.
- 17 September 2025
- Published by European Mathematical Society - EMS - Publishing House GmbH in Mathematical Statistics and Learning
- Vol. 8 (3) , 165-192
Open AccessA simple and improved algorithm for noisy, convex, zeroth-order optimisation
In this paper, we study the problem of noisy, convex, zeroth-order optimisation of a function f over a bounded convex set \overline{\mathcal{X}}\subset \mathbb{R}^{d} . Given a budget n of noisy queries to the function f that can be allocated sequentially and adaptively, our aim is to construct an algorithm that returns a point \hat x\in \overline{\mathcal{X}} such that f(\hat x) is as small as possible. We provide a conceptually simple method inspired by the textbook centre of gravity method, but adapted to the noisy and zeroth-order setting. We prove that this method is such that the f(\hat x) - \min_{x\in \overline{\mathcal{X}}}f(x) is of smaller order than d^{2}/\sqrt{n} up to poly-logarithmic terms. We slightly improve upon literature preceding this work, where the best-known rate was in Lattimore (2019) and was of order d^{2.5}/\sqrt{n} , albeit for a more challenging problem – yet in the literature contemporaneous to our work, the remarkable work of Fokkema et al. (2024) attains the faster rate of d^{1.5}/\sqrt{n} under mild conditions on \overline{\mathcal{X}} . Our main contribution is, however, conceptual, as we believe that our algorithm and its analysis bring novel ideas and are significantly simpler than the existing approaches.
- Open Access
- 28 October 2022
- Published by European Mathematical Society - EMS - Publishing House GmbH in Mathematical Statistics and Learning
- Vol. 5 (1) , 1-54
Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials
We consider the identity testing problem – or goodness-of-fit testing problem – in multivariate binomial families, multivariate Poisson families and multinomial distributions. Given a known distribution $p$ and $n$ i.i.d. samples drawn from an unknown distribution $q$, we investigate how large $\rho>0$ should be to distinguish, with high probability, the case $p=q$ from the case $d(p,q) \geq \rho$ , where $d$ denotes a specific distance over probability distributions. We answer this question in the case of a family of different distances: $d(p,q) = |p-q|\_t$ for $t \in \[1,2]$, where $|\cdot|\_t$ is the entrywise $\ell\_t$ norm. Besides being locally minimax-optimal – i.e. characterizing the detection threshold in dependence of the known matrix $p$ – our tests have simple expressions and are easily implementable.- 28 October 2022
- Published by European Mathematical Society - EMS - Publishing House GmbH in Mathematical Statistics and Learning
- Vol. 5 (1) , 1-54
Open AccessSharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials
We consider the identity testing problem – or goodness-of-fit testing problem – in multivariate binomial families, multivariate Poisson families and multinomial distributions. Given a known distribution $p$ and $n$ i.i.d. samples drawn from an unknown distribution $q$, we investigate how large $\rho>0$ should be to distinguish, with high probability, the case $p=q$ from the case $d(p,q) \geq \rho$ , where $d$ denotes a specific distance over probability distributions. We answer this question in the case of a family of different distances: $d(p,q) = |p-q|\_t$ for $t \in \[1,2]$, where $|\cdot|\_t$ is the entrywise $\ell\_t$ norm. Besides being locally minimax-optimal – i.e. characterizing the detection threshold in dependence of the known matrix $p$ – our tests have simple expressions and are easily implementable. - Open Access
The price of unfairness in linear bandits with biased feedback
In this paper, we study the problem of fair sequential decision making with biased linear bandit feedback. At each round, a player selects an action described by a covariate and by a sensitive attribute. The perceived reward is a linear combination of the covariates of the chosen action, but the player only observes a biased evaluation of this reward, depending on the sensitive attribute. To characterize the difficulty of this problem, we design a phased elimination algorithm that corrects the unfair evaluations, and establish upper bounds on its regret. We show that the worst-case regret is smaller than $\mathcal{O}(\kappa_*^{1/3}\log(T)^{1/3}T^{2/3})$, where $\kappa_*$ is an explicit geometrical constant characterizing the difficulty of bias estimation. We prove lower bounds on the worst-case regret for some sets of actions showing that this rate is tight up to a possible sub-logarithmic factor. We also derive gap-dependent upper bounds on the regret, and matching lower bounds for some problem instance.Interestingly, these results reveal a transition between a regime where the problem is as difficult as its unbiased counterpart, and a regime where it can be much harder.Open AccessThe price of unfairness in linear bandits with biased feedback
In this paper, we study the problem of fair sequential decision making with biased linear bandit feedback. At each round, a player selects an action described by a covariate and by a sensitive attribute. The perceived reward is a linear combination of the covariates of the chosen action, but the player only observes a biased evaluation of this reward, depending on the sensitive attribute. To characterize the difficulty of this problem, we design a phased elimination algorithm that corrects the unfair evaluations, and establish upper bounds on its regret. We show that the worst-case regret is smaller than $\mathcal{O}(\kappa_*^{1/3}\log(T)^{1/3}T^{2/3})$, where $\kappa_*$ is an explicit geometrical constant characterizing the difficulty of bias estimation. We prove lower bounds on the worst-case regret for some sets of actions showing that this rate is tight up to a possible sub-logarithmic factor. We also derive gap-dependent upper bounds on the regret, and matching lower bounds for some problem instance.Interestingly, these results reveal a transition between a regime where the problem is as difficult as its unbiased counterpart, and a regime where it can be much harder. - Open Access
The Influence of Shape Constraints on the Thresholding Bandit Problem
We investigate the stochastic Thresholding Bandit problem (TBP) under several shape constraints. On top of (i) the vanilla, unstructured TBP, we consider the case where (ii) the sequence of arm's means $(\mu_k)_k$ is monotonically increasing MTBP, (iii) the case where $(\mu_k)_k$ is unimodal UTBP and (iv) the case where $(\mu_k)_k$ is concave CTBP. In the TBP problem the aim is to output, at the end of the sequential game, the set of arms whose means are above a given threshold. The regret is the highest gap between a misclassified arm and the threshold. In the fixed budget setting, we provide problem independent minimax rates for the expected regret in all settings, as well as associated algorithms. We prove that the minimax rates for the regret are (i) $\sqrt{\log(K)K/T}$ for TBP, (ii) $\sqrt{\log(K)/T}$ for MTBP, (iii) $\sqrt{K/T}$ for UTBP and (iv) $\sqrt{\log\log K/T}$ for CTBP, where $K$ is the number of arms and $T$ is the budget. These rates demonstrate that the dependence on $K$ of the minimax regret varies significantly depending on the shape constraint. This highlights the fact that the shape constraints modify fundamentally the nature of the TBP.Open AccessThe Influence of Shape Constraints on the Thresholding Bandit Problem
We investigate the stochastic Thresholding Bandit problem (TBP) under several shape constraints. On top of (i) the vanilla, unstructured TBP, we consider the case where (ii) the sequence of arm's means $(\mu_k)_k$ is monotonically increasing MTBP, (iii) the case where $(\mu_k)_k$ is unimodal UTBP and (iv) the case where $(\mu_k)_k$ is concave CTBP. In the TBP problem the aim is to output, at the end of the sequential game, the set of arms whose means are above a given threshold. The regret is the highest gap between a misclassified arm and the threshold. In the fixed budget setting, we provide problem independent minimax rates for the expected regret in all settings, as well as associated algorithms. We prove that the minimax rates for the regret are (i) $\sqrt{\log(K)K/T}$ for TBP, (ii) $\sqrt{\log(K)/T}$ for MTBP, (iii) $\sqrt{K/T}$ for UTBP and (iv) $\sqrt{\log\log K/T}$ for CTBP, where $K$ is the number of arms and $T$ is the budget. These rates demonstrate that the dependence on $K$ of the minimax regret varies significantly depending on the shape constraint. This highlights the fact that the shape constraints modify fundamentally the nature of the TBP. - 27 November 2019
- Published by Springer Nature
- p. 385-430
Uncertainty Quantification for Matrix Compressed Sensing and Quantum Tomography Problems
- 27 November 2019
- Published by Springer Nature
- p. 385-430
Uncertainty Quantification for Matrix Compressed Sensing and Quantum Tomography Problems
- 16 October 2019
- Published by Pleiades Publishing Ltd in Automation and Remote Control
- Vol. 80 (10) , 1817-1834
Minimax Rate of Testing in Sparse Linear Regression
We consider the problem of testing the hypothesis that the parameter of linear regression model is 0 against an s-sparse alternative separated from 0 in the l2-distance. We show that, in Gaussian...
- 16 October 2019
- Published by Pleiades Publishing Ltd in Automation and Remote Control
- Vol. 80 (10) , 1817-1834
Minimax Rate of Testing in Sparse Linear Regression
We consider the problem of testing the hypothesis that the parameter of linear regression model is 0 against an s-sparse alternative separated from 0 in the l2-distance. We show that, in Gaussian...
- Open Access
Two-sample Hypothesis Testing for Inhomogeneous Random Graphs
The study of networks leads to a wide range of high dimensional inference problems. In many practical applications, one needs to draw inference from one or few large sparse networks. The present paper studies hypothesis testing of graphs in this high-dimensional regime, where the goal is to test between two populations of inhomogeneous random graphs defined on the same set of $n$ vertices. The size of each population $m$ is much smaller than $n$, and can even be a constant as small as 1. The critical question in this context is whether the problem is solvable for small $m$. We answer this question from a minimax testing perspective. Let $P,Q$ be the population adjacencies of two sparse inhomogeneous random graph models, and $d$ be a suitably defined distance function. Given a population of $m$ graphs from each model, we derive minimax separation rates for the problem of testing $P=Q$ against $d(P,Q)>\rho$. We observe that if $m$ is small, then the minimax separation is too large for some popular choices of $d$, including total variation distance between corresponding distributions. This implies that some models that are widely separated in $d$ cannot be distinguished for small $m$, and hence, the testing problem is generally not solvable in these cases. We also show that if $m>1$, then the minimax separation is relatively small if $d$ is the Frobenius norm or operator norm distance between $P$ and $Q$. For $m=1$, only the latter distance provides small minimax separation. Thus, for these distances, the problem is solvable for small $m$. We also present near-optimal two-sample tests in both cases, where tests are adaptive with respect to sparsity level of the graphs.Open AccessTwo-sample Hypothesis Testing for Inhomogeneous Random Graphs
The study of networks leads to a wide range of high dimensional inference problems. In many practical applications, one needs to draw inference from one or few large sparse networks. The present paper studies hypothesis testing of graphs in this high-dimensional regime, where the goal is to test between two populations of inhomogeneous random graphs defined on the same set of $n$ vertices. The size of each population $m$ is much smaller than $n$, and can even be a constant as small as 1. The critical question in this context is whether the problem is solvable for small $m$. We answer this question from a minimax testing perspective. Let $P,Q$ be the population adjacencies of two sparse inhomogeneous random graph models, and $d$ be a suitably defined distance function. Given a population of $m$ graphs from each model, we derive minimax separation rates for the problem of testing $P=Q$ against $d(P,Q)>\rho$. We observe that if $m$ is small, then the minimax separation is too large for some popular choices of $d$, including total variation distance between corresponding distributions. This implies that some models that are widely separated in $d$ cannot be distinguished for small $m$, and hence, the testing problem is generally not solvable in these cases. We also show that if $m>1$, then the minimax separation is relatively small if $d$ is the Frobenius norm or operator norm distance between $P$ and $Q$. For $m=1$, only the latter distance provides small minimax separation. Thus, for these distances, the problem is solvable for small $m$. We also present near-optimal two-sample tests in both cases, where tests are adaptive with respect to sparsity level of the graphs. - Open Access
Restless dependent bandits with fading memory
We study the stochastic multi-armed bandit problem in the case when the arm samples are dependent over time and generated from so-called weak $\cC$-mixing processes. We establish a $\cC-$Mix Improved UCB agorithm and provide both problem-dependent and independent regret analysis in two different scenarios. In the first, so-called fast-mixing scenario, we show that pseudo-regret enjoys the same upper bound (up to a factor) as for i.i.d. observations; whereas in the second, slow mixing scenario, we discover a surprising effect, that the regret upper bound is similar to the independent case, with an incremental {\em additive} term which does not depend on the number of arms. The analysis of slow mixing scenario is supported with a minmax lower bound, which (up to a $\log(T)$ factor) matches the obtained upper bound.Open AccessRestless dependent bandits with fading memory
We study the stochastic multi-armed bandit problem in the case when the arm samples are dependent over time and generated from so-called weak $\cC$-mixing processes. We establish a $\cC-$Mix Improved UCB agorithm and provide both problem-dependent and independent regret analysis in two different scenarios. In the first, so-called fast-mixing scenario, we show that pseudo-regret enjoys the same upper bound (up to a factor) as for i.i.d. observations; whereas in the second, slow mixing scenario, we discover a surprising effect, that the regret upper bound is similar to the independent case, with an incremental {\em additive} term which does not depend on the number of arms. The analysis of slow mixing scenario is supported with a minmax lower bound, which (up to a $\log(T)$ factor) matches the obtained upper bound. - Open Access
Total variation distance for discretely observed Lévy processes: a Gaussian approximation of the small jumps
It is common practice to treat small jumps of L\'evy processes as Wiener noise and thus to approximate its marginals by a Gaussian distribution. However, results that allow to quantify the goodness of this approximation according to a given metric are rare. In this paper, we clarify what happens when the chosen metric is the total variation distance. Such a choice is motivated by its statistical interpretation. If the total variation distance between two statistical models converges to zero, then no tests can be constructed to distinguish the two models which are therefore equivalent, statistically speaking. We elaborate a fine analysis of a Gaussian approximation for the small jumps of L\'evy processes with infinite L\'evy measure in total variation distance. Non asymptotic bounds for the total variation distance between $n$ discrete observations of small jumps of a L\'evy process and the corresponding Gaussian distribution is presented and extensively discussed. As a byproduct, new upper bounds for the total variation distance between discrete observations of L\'evy processes are provided. The theory is illustrated by concrete examples.Open AccessTotal variation distance for discretely observed Lévy processes: a Gaussian approximation of the small jumps
It is common practice to treat small jumps of L\'evy processes as Wiener noise and thus to approximate its marginals by a Gaussian distribution. However, results that allow to quantify the goodness of this approximation according to a given metric are rare. In this paper, we clarify what happens when the chosen metric is the total variation distance. Such a choice is motivated by its statistical interpretation. If the total variation distance between two statistical models converges to zero, then no tests can be constructed to distinguish the two models which are therefore equivalent, statistically speaking. We elaborate a fine analysis of a Gaussian approximation for the small jumps of L\'evy processes with infinite L\'evy measure in total variation distance. Non asymptotic bounds for the total variation distance between $n$ discrete observations of small jumps of a L\'evy process and the corresponding Gaussian distribution is presented and extensively discussed. As a byproduct, new upper bounds for the total variation distance between discrete observations of L\'evy processes are provided. The theory is illustrated by concrete examples.