Optimal regret rates for nonconvex “Follow the Perturbed Leader”

Department of Computer Science and Automation
Department Seminar

Speaker : Dr. Praneeth Netrapalli
Researcher
Microsoft Research India
Bengaluru

Title : Optimal regret rates for nonconvex “Follow the Perturbed Leader”

Date : Friday, March 29, 2019

Time : 1:00 PM

Venue : CSA Seminar Hall (Room No. 254, First Floor)

Abstract

Consider the online sequential decision making problem, where we are required to output a decision at each time step and then a loss function is revealed to us. The loss function may be adversarial, with the knowledge of our decision. The (cumulative) loss we suffer is (the sum over all times of) the loss function evaluated on our decision. We wish to minimize the regret of our cumulative loss with respect to the best fixed decision in hindsight. Follow the perturbed leader (FTPL) (Kalai and Vempala 2005) is a well known algorithm for obtaining optimal regret rates of O(T^{1/2}) for convex loss functions in this setting, where T is the number of time steps. Recently, (Agarwal et al. 2019) extended this result for nonconvex losses obtaining regret rates of O(T^{2/3}). We improve over this result to obtain the optimal O(T^{1/2}) regret rates for FTPL in the nonconvex setting. The talk will be accessible and will include all necessary background.

Joint work with Arun Sai Suggala (CMU).

Host Faculty : Dr. Anand Louis

ALL ARE WELCOME