Center for Advanced Intelligence Project

Title: New deviation inequalities for Markov chains, with applications to stochastic optimization and empirical risk minimization

Abstract:
Many deviation inequalities were recently proven for Markov chains based on martingale techniques. However, such inequalities rely strongly on the assumption that the chain is homogeneous and contractive. Such an assumption is not satisfied in many practical situations, a typical example being the iterates of SGD. In this paper, we extend these techniques to prove deviation inequalities for a class of non-homogeneous Markov chains. I will introduce these inequalities and then focus on two applications: empirical risk minimization for time series, and stochastic optimization.
This is based on a joint work with Xiequan Fan (Tianjin University) and Paul Doukhan (Université de Cergy-Pontoise): https://arxiv.org/abs/2102.08685

Bio:
https://pierrealquier.github.io/