Session: Randomized algorithms beyond minimization
Chair: Laurent Condat
Cluster: Fixed Points and Variational Inequalities
Talk 1: Splitting the forward-backward algorithm
Speaker: Emanuele Naldi
Abstract: In this talk, we introduce an extension of the forward-backward splitting method, designed to address monotone inclusion problems involving sums of multiple maximal monotone operators, with some of them being cocoercive operators. Our approach builds upon recent developments in splitting methods and offers two significant innovations. First, we generalize the classical forward-backward and Davis-Yin algorithms by incorporating flexible, arbitrary network architectures, making our method well-suited for distributed optimization problems. Second, we relax the common assumption of uniform cocoercivity, allowing the use of larger, more adaptive step sizes based on individual cocoercivity constants, which enables us to accelerate convergence in some instances. We provide a comprehensive convergence rate analysis and demonstrate the practical benefits of this enhanced flexibility through numerical experiments. We investigate and test further the methods introducing also stochasticity in the proposed algorithm.
Talk 2: Solving Hidden Monotone Variational Inequalities with Surrogate Losses
Speaker: Gauthier Gidel
Abstract: Deep learning has proven to be effective in a wide variety of loss minimization problems. However, many applications of interest, like minimizing projected Bellman error and min-max optimization, cannot be modelled as minimizing a scalar loss function but instead correspond to solving a variational inequality (VI) problem. This difference in setting has caused many practical challenges as naive gradient-based approaches from supervised learning tend to diverge and cycle in the VI case. In this talk, I will introduce a principled surrogate-based approach compatible with deep learning to solve VIs. I will show that our surrogate-based approach has three main benefits: (1) under assumptions that are realistic in practice (when hidden monotone structure is present, interpolation, and sufficient optimization of the surrogates), it guarantees convergence, (2) it provides a unifying perspective of existing methods, and (3) is amenable to existing deep learning optimizers like ADAM. I will demonstrate that this surrogate-based approach is effective in min-max optimization and minimizing projected Bellman error. Furthermore, in the deep reinforcement learning case, we propose a novel variant of TD(0) which is more compute and sample efficient.
Talk 3: A Simple Finite-Time Analysis of Temporal Difference Learning with Linear Function Approximation
Speaker: Aritra Mitra
Abstract: We study the finite-time convergence of TD learning with linear function approximation under Markovian sampling. Existing proofs for this setting either assume a projection step in the algorithm to simplify the analysis, or require a fairly intricate argument to ensure stability of the iterates. We ask: Is it possible to retain the simplicity of a projection-based analysis without actually performing a projection step in the algorithm? Our main contribution is to show this is possible via a novel two-step argument. In the first step, we use induction to prove that under a standard choice of a constant step-size α, the iterates generated by TD learning remain uniformly bounded in expectation. In the second step, we establish a recursion that mimics the steady-state dynamics of TD learning up to a bounded perturbation on the order of O(α^2) that captures the effect of Markovian sampling. Combining these pieces leads to an overall approach that considerably simplifies existing proofs. We conjecture that our inductive proof technique will find applications in the analyses of more complex stochastic approximation algorithms, and provide some examples of such applications.
