6 papers
Krasnosel'skii-Mann iterations beyond asymptotics: a combinatorial analysis
Mario Bravo, Roberto Cominetti
We revisit the classical Krasnosel'skii-Mann fixed point iteration for contractions and nonexpansive maps in general normed spaces. This iteration is ubiquitous across a wide range…
On the occupation measure of evolution models with vanishing mutations
Michel Benaïm, Mario Bravo, Mathieu Faure
We study the almost sure convergence of the occupation measure of evolution models where mutation rates decrease over time. We show that if the mutation parameter vanishes at a con…
Mixing Times and Privacy Analysis for the Projected Langevin Algorithm under a Modulus of Continuity
Mario Bravo, Juan P. Flores-Mella, Cristóbal Guzmán
We study the mixing time of the projected Langevin algorithm (LA) and the privacy curve of noisy Stochastic Gradient Descent (SGD), beyond nonexpansive iterations. Specifically, we…
Minimax-optimal Halpern iterations for Lipschitz maps
Mario Bravo, Roberto Cominetti, Jongmin Lee
This paper investigates the minimax-optimality of Halpern fixed-point iterations for Lipschitz maps in general normed spaces. Starting from an a priori bound on the orbit of iterat…
Near-Optimal Sample Complexity for MDPs via Anchoring
Jongmin Lee, Mario Bravo, Roberto Cominetti
We study a new model-free algorithm to compute -optimal policies for average reward Markov decision processes, in the weakly communicating case. Given a generative mod…
Stochastic Halpern iteration in normed spaces and applications to reinforcement learning
Mario Bravo, Juan Pablo Contreras
We analyze the oracle complexity of the stochastic Halpern iteration with minibatch, where we aim to approximate fixed-points of nonexpansive and contractive operators in a normed…