55 citations · 121 across the 18 of their papers we have counts for
19 papers
Adaptive approximation of monotone functions
Pierre Gaillard, Sébastien Gerchinovitz, Étienne de Montbrun
We study the classical problem of approximating a non-decreasing function in norm by sequentially querying its values, for known compact r…
Certified Multi-Fidelity Zeroth-Order Optimization
Étienne de Montbrun, Sébastien Gerchinovitz
We consider the problem of multi-fidelity zeroth-order optimization, where one can evaluate a function at various approximation levels (of varying costs), and the goal is to op…
A general approximation lower bound in norm, with applications to feed-forward neural networks
El Mehdi Achour, Armand Foucault, Sébastien Gerchinovitz +1
We study the fundamental limits to the expressive power of neural networks. Given two sets , of real-valued functions, we first prove a general lower bound on how well funct…
The loss landscape of deep linear neural networks: a second-order analysis
El Mehdi Achour, François Malgouyres, Sébastien Gerchinovitz
We study the optimization landscape of deep linear neural networks with the square loss. It is known that, under weak assumptions, there are no spurious local minima and no local m…
White Paper Machine Learning in Certified Systems
Hervé Delseny, Christophe Gabreau, Adrien Gauffriau +25
Machine Learning (ML) seems to be one of the most promising solution to automate partially or completely some of the complex tasks currently realized by humans, such as driving veh…
Online nonparametric regression with Sobolev kernels
Oleksandr Zadorozhnyi, Pierre Gaillard, Sebastien Gerschinovitz +1
In this work we investigate the variation of the online kernelized ridge regression algorithm in the setting of dimensional adversarial nonparametric regression. We derive the…
Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with Error Certificates
François Bachoc, Tommaso R Cesari, Sébastien Gerchinovitz
We study the problem of zeroth-order (black-box) optimization of a Lipschitz function defined on a compact subset of , with the additional constraint…
The sample complexity of level set approximation
François Bachoc, Tommaso Cesari, Sébastien Gerchinovitz
We study the problem of approximating the level set of an unknown function by sequentially querying its values. We introduce a family of algorithms called Bisect and Approximate th…
Diversity-Preserving K-Armed Bandits, Revisited
Hédi Hadiji, Sébastien Gerchinovitz, Jean-Michel Loubes +1
We consider the bandit-based framework for diversity-preserving recommendations introduced by Celis et al. (2019), who approached it in the case of a polytope mainly by a reduction…
Regret analysis of the Piyavskii-Shubert algorithm for global Lipschitz optimization
Clément Bouttier, Tommaso Cesari, Mélanie Ducoffe +1
We consider the problem of maximizing a non-concave Lipschitz multivariate function over a compact domain by sequentially querying its (possibly perturbed) values. We study a natur…
Optimization of a SSP's Header Bidding Strategy using Thompson Sampling
Grégoire Jauvion, Nicolas Grislain, Pascal Sielenou Dkengne +2
Over the last decade, digital media (web or app publishers) generalized the use of real time ad auctions to sell their ad spaces. Multiple auction platforms, also called Supply-Sid…
Uniform regret bounds over for the sequential linear regression problem with the square loss
Pierre Gaillard, Sébastien Gerchinovitz, Malo Huard +1
We consider the setting of online linear regression for arbitrary deterministic sequences, with the square loss. We are interested in the aim set by Bartlett et al. (2015): obtain…
Optimal functional supervised classification with separation condition
Sébastien Gadat, Sébastien Gerchinovitz, Clément Marteau
We consider the binary supervised classification problem with the Gaussian functional model introduced in [7]. Taking advantage of the Gaussian structure, we design a natural plug-…
Algorithmic Chaining and the Role of Partial Feedback in Online Nonparametric Learning
Nicolò Cesa-Bianchi, Pierre Gaillard, Claudio Gentile +1
We investigate contextual online learning with nonparametric (Lipschitz) comparison classes under different assumptions on losses and feedback information. For full information fee…
Fano's inequality for random variables
Sebastien Gerchinovitz, Pierre Ménard, Gilles Stoltz
We extend Fano's inequality, which controls the average probability of events in terms of the average of some --divergences, to work with arbitrary events (not necessarily formi…
Refined Lower Bounds for Adversarial Bandits
Sébastien Gerchinovitz, Tor Lattimore
We provide new lower bounds on the regret that must be suffered by adversarial bandit algorithms. The new results show that recent upper bounds that either (a) hold with high-proba…
A Chaining Algorithm for Online Nonparametric Regression
Pierre Gaillard, Sébastien Gerchinovitz
We consider the problem of online nonparametric regression with arbitrary deterministic sequences. Using ideas from the chaining technique, we design an algorithm that achieves a D…
Adaptive and optimal online linear regression on -balls
Sébastien Gerchinovitz, Jia Yuan Yu
We consider the problem of online linear regression on individual sequences. The goal in this paper is for the forecaster to output sequential predictions which are, after time…
Sparsity regret bounds for individual sequences in online linear regression
Sébastien Gerchinovitz
We consider the problem of online linear regression on arbitrary deterministic sequences when the ambient dimension d can be much larger than the number of time rounds T. We introd…