Analysis of Distributed First and Zeroth-order Mirror Descent Algorithm

  • 31



Name of the Speaker: Anik Kumar Paul (EE18D030)
Guide: Dr. Arun D Mahindrakar and Dr. Rachel K
Venue/Online meeting link: ESB-234 (Malaviya Hall)
Date/Time: 31st March 2023, 3.30pm

In this work, we investigate distributed stochastic mirror descent technique (DSMD). Mirror descent is a generalisation of the standard subgradient method in a more general non-Euclidean or Banach space. The goal of this work is to show almost sure convergence of the DSMD iterates, as opposed to the majority of the literature, which focuses on showing expected error in function value converges to zero. In many applications of reinforcement learning, statistical learning, we only have access to the noisy evaluation of function value at a desired point. As a result, we must approximate the function's subgradient using the noisy measurement of the function value. This is what gives rise to the concept of zeroth-order mirror descent algorithm. We demonstrate an almost sure convergence of function value of the iterates to a neighbourhood of the optimal value. Finally, for a distributed optimization problem, each iteration consists of two steps: agent communication and iterate computation. The cost of computation and communication for each iteration is determined by the application and algorithm. We investigate if it is possible to reduce the number of communications between two neighbouring agents. We examine the event-triggered mirror descent method in an online scenario, where we have designed thresholding error for event-triggered communication to show sublinear regret - the goal of online optimization.