Abstract
Topic: Online Learning with Adversaries: A Differential Inclusion View
We consider the measurement model $Y = AX,$ where $X$ and, hence, $Y$ are random variables and $A$ is an a priori known tall matrix. At each time instance, a sample of one of $Y$'s coordinates is available, and the goal is to estimate $\mu := \bE[X]$ via these samples. However, the challenge is that a small but unknown subset of $Y$'s coordinates are controlled by adversaries with infinite power: they can return any real number each time they are queried for a sample. For such an adversarial setting, we propose the first asynchronous online algorithm that converges to $\mu$ almost surely. We prove this result using a novel differential inclusion based two-timescale analysis. Two key highlights of our proof include: (a) the use of a novel Lyapunov function for showing that $\mu$ is the unique global attractor for our algorithm's limiting dynamics, and (b) the use of martingale and stopping time theory to show that our algorithm's iterates are almost surely bounded
Bio
Gugan Thoppe is an Asst. Professor at the Dept. of Computer Science and Automation, Indian Institute of Science (IISc). He is also an Associate Researcher at the Robert Bosh Centre, IIT Madras. His M.S. and Ph.D. are from TIFR Mumbai, India. He has also done two postdocs: one at Technion, Israel, and the other at Duke University, USA. His work has been recognized with the Pratiksha Trust Young Investigator award, the TIFR award for best Ph.D. thesis, and two IBM Ph.D. fellowships. He is also the winner of the IISc award for excellence in teaching. His research interests include stochastic approximation and random topology and their applications to reinforcement learning and data analysis.