5 citations · 17 across the 23 of their papers we have counts for
24 papers
Bandit PCA with Minimax Optimal Regret
Moïse Blanchard, Dmitrii Ostrovskii, Aadirupa Saha
We study the bandit-feedback version of online principal component analysis (Bandit PCA): in each round , the adversary selects a symmetric gain matrix…
Distribution-Free Sequential Prediction with Abstentions
Jialin Yu, Moïse Blanchard
We study a sequential prediction problem in which an adversary is allowed to inject arbitrarily many adversarial instances in a stream of i.i.d. instances, but at each round, the l…
Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness
Moïse Blanchard, Abhishek Shetty, Alexander Rakhlin
Understanding minimal assumptions that enable learning and generalization is perhaps the central question of learning theory. Several celebrated results in statistical learning the…
Consistency and inconsistency in -means clustering
Moïse Blanchard, Adam Quinn Jaffe, Nikita Zhivotovskiy
A celebrated result of Pollard proves asymptotic consistency for -means clustering when the population distribution has finite variance. In this work, we point out that the popu…
Distributionally-Constrained Adversaries in Online Learning
Moïse Blanchard, Samory Kpotufe
There has been much recent interest in understanding the continuum from adversarial to stochastic settings in online learning, with various frameworks including smoothed settings p…
Non-Monetary Mechanism Design without Priors: Achieving Efficiency via Adaptive Costly Audits
Yan Dai, Moise Blanchard, Patrick Jaillet
We study repeated resource allocation with strategic agents, where monetary transfers are disallowed and the planner has no prior information on agents' utility distributions. Insp…
Agnostic Smoothed Online Learning without Knowledge of the Base Measure
Moïse Blanchard
Classical results in statistical learning typically consider two extreme data-generating models: i.i.d. instances from an unknown distribution, or fully adversarial instances, ofte…
Near-Optimal Mechanisms for Resource Allocation Without Monetary Transfers
Moïse Blanchard, Patrick Jaillet
We study the problem in which a central planner sequentially allocates a single resource to multiple strategic agents using their utility reports at each round, but without using a…
Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
Moise Blanchard
In this paper we provide oracle complexity lower bounds for finding a point in a given set using a memory-constrained algorithm that has access to a separation oracle. We assume th…
Correlated Binomial Process
Moïse Blanchard, Doron Cohen, Aryeh Kontorovich
Cohen and Kontorovich (COLT 2023) initiated the study of what we call here the Binomial Empirical Process: the maximal absolute value of a sequence of inhomogeneous normalized and…
Tight Bounds for Local Glivenko-Cantelli
Moïse Blanchard, Václav Voráček
This paper addresses the statistical problem of estimating the infinite-norm deviation from the empirical mean to the distribution mean for high-dimensional distributions on $\{0,1…
Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes
Moïse Blanchard, Junhui Zhang, Patrick Jaillet
We propose a family of recursive cutting-plane algorithms to solve feasibility problems with constrained memory, which can also be used for first-order convex optimization. Precise…
Adversarial Rewards in Universal Learning for Contextual Bandits
Moise Blanchard, Steve Hanneke, Patrick Jaillet
We study the fundamental limits of learning in contextual bandits, where a learner's rewards depend on their actions and a known context, which extends the canonical multi-armed ba…
Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal
Moïse Blanchard, Junhui Zhang, Patrick Jaillet
We give query complexity lower bounds for convex optimization and the related feasibility problem. We show that quadratic memory is necessary to achieve the optimal oracle complexi…
Contextual Bandits and Optimistically Universal Learning
Moise Blanchard, Steve Hanneke, Patrick Jaillet
We consider the contextual bandit problem on general action and context spaces, where the learner's rewards depend on their selected actions and an observable context. This general…
Fréchet Mean Set Estimation in the Hausdorff Metric, via Relaxation
Moise Blanchard, Adam Quinn Jaffe
This work resolves the following question in non-Euclidean statistics: Is it possible to consistently estimate the Fréchet mean set of an unknown population distribution, with resp…
Additional Results and Extensions for the paper "Probabilistic bounds on the Traveling Salesman Problem and the Traveling Repairman Problem''
Moïse Blanchard, Alexandre Jacquillat, Patrick Jaillet
This technical report provides additional results for the main paper ``Probabilistic bounds on the Traveling Salesman Problem (TSP) and the Traveling Repairman Problem (TRP…
Probabilistic bounds on the Traveling Salesman Problem and the Traveling Repairman Problem
Moïse Blanchard, Alexandre Jacquillat, Patrick Jaillet
The traveling salesman problem (-TSP) seeks a tour of minimal length that visits a subset of points. The traveling repairman problem (TRP) seeks a complete tour wi…
Universal Regression with Adversarial Responses
Moïse Blanchard, Patrick Jaillet
We provide algorithms for regression with adversarial responses under large classes of non-i.i.d. instance sequences, on general separable metric spaces, with provably minimal assu…
Universal Online Learning with Unbounded Losses: Memory Is All You Need
Moise Blanchard, Romain Cosson, Steve Hanneke
We resolve an open problem of Hanneke on the subject of universally consistent online learning with non-i.i.d. processes and unbounded losses. The notion of an optimistically unive…
Universal Online Learning: an Optimistically Universal Learning Rule
Moïse Blanchard
We study the subject of universal online learning with non-i.i.d. processes for bounded losses. The notion of an universally consistent learning was defined by Hanneke in an effort…
Universal Online Learning with Bounded Loss: Reduction to Binary Classification
Moïse Blanchard, Romain Cosson
We study universal consistency of non-i.i.d. processes in the context of online learning. A stochastic process is said to admit universal consistency if there exists a learner that…
The Representation Power of Neural Networks: Breaking the Curse of Dimensionality
Moise Blanchard, M. Amine Bennouna
In this paper, we analyze the number of neurons and training parameters that a neural networks needs to approximate multivariate functions of bounded second mixed derivatives -- Ko…
On the Length of Monotone Paths in Polyhedra
Moïse Blanchard, Jesùs A. De Loera, Quentin Louveaux
Motivated by the problem of bounding the number of iterations of the Simplex algorithm we investigate the possible lengths of monotone paths followed by the Simplex method inside t…