Noticias en español
Deterministic and stochastic fixed-point iterations in normed spaces.
Abstract: In this talk, we present a survey of techniques and results on error bounds and convergence rates for both deterministic and stochastic fixed-point iterations, with a focus on methods such as the Krasnoselskii-Mann and Halpern iterations. Our primary emphasis is on general normed spaces, where we employ tools from optimal transport to derive tight error bounds. For spaces with additional structure, such as Hilbert spaces, we also discuss existing techniques and the sharp results established in the literature. Finally, we highlight applications of these findings in reinforcement...
Read MoreSome dynamical invariants under strong orbit equivalence.
Abstract: A dynamical system is usually made up of a state space and a rule (a map acting on the space) that tells us how the system evolves over time. One of the central questions in studying these systems is figuring out when two of them are essentially the same, or conjugate, as we usually say. There are several known features, called invariants, that stay the same under conjugacy, but so far, no single invariant can completely characterize when two systems are conjugate. Because of that, it is natural to look at a slightly weaker idea of equivalence, called strong orbit equivalence. All...
Read MoreStochastic Halpern iteration in normed spaces and applications to reinforcement learning.
In this seminar, I will present recent results on the oracle complexity of the stochastic Halpern iteration with minibatching, a method designed to approximate fixed points of nonexpansive and contractive operators in finite-dimensional normed spaces. Under the assumption of uniformly bounded variance from the stochastic oracle, we show that the method achieves an oracle complexity of $\tilde{O}(\varepsilon^{-5})$ to obtain an $\varepsilon$-accurate expected fixed-point residual for nonexpansive operators. This improves upon previously known rates for the stochastic Krasnoselskii-Mann...
Read MoreDeterministic Impartial Selection with Weights.
Abstract: In the impartial selection problem, a subset of agents up to a fixed size k among a group of n is to be chosen based on votes cast by the agents themselves. A selection mechanism is impartial if no agent can influence its own chance of being selected by changing its vote. It is \alpha-optimal if, for every instance, the ratio between the votes received by the selected subset is at least a fraction of \alpha of the votes received by the subset of size k with the highest number of votes. We study deterministic impartial mechanisms in a more general setting with arbitrarily weighted...
Read MoreDecidability of the isomorphism problem between constant-shape substitutions.
Abstract: An important question in dynamical systems is the classification, i.e., to be able to distinguish two isomorphic dynamical systems. In this work, we focus on the family of multidimensional substitutive subshifts. Constant-shape substitutions are a multidimensional generalization of constant-length substitutions, where any letter is assigned a pattern with the same shape. We prove that in this class of substitutive subshifts, under the hypothesis of having the same structure, it is decidable whether there exists a factor map between two aperiodic minimal substitutive subshifts. The...
Read MoreShortest Odd path on undirected graphs with conservative weights.
Abstract: We consider the Shortest Odd Path (SOP) problem, where given an undirected graph $G$, a weight function on its edges, and two vertices $s$ and $t$ in $G$, the aim is to find an $(s,t)$-path with odd length and, among all such paths, of minimum weight. For the case when the weight function is conservative, i.e., when every cycle has non-negative total weight, the complexity of the SOP problem had been open for 20 years, and was recently shown to be NP-hard. I’ll present a polynomial-time algorithm for the special case when the weight function is conservative and the set of...
Read More