5 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…
The Increasing Gap Dynamics in a General Spatial Matching Model
Andrés Fielbaum, Roberto Cominetti, José Correa
We study a representation of a problem that appears in numerous transport systems: servers distributed over a given space (e.g., cars on an urban network), receive random reque…
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…
When is the Computation of a Feature Attribution Method Tractable?
P. Barceló, R. Cominetti, M. Morgado
Feature attribution methods have become essential for explaining machine learning models. Many popular approaches, such as SHAP and Banzhaf values, are grounded in power indices fr…