Timezone: »

 
Spotlight
Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor
Lijun Zhang · Wei Jiang · Jinfeng Yi · Tianbao Yang

Wed Dec 07 05:00 PM -- 07:00 PM (PST) @
in Lightning Talks 4A-2 »

In this paper, we investigate an online prediction strategy named as Discounted-Normal-Predictor [Kapralov and Panigrahy, 2010] for smoothed online convex optimization (SOCO), in which the learner needs to minimize not only the hitting cost but also the switching cost. In the setting of learning with expert advice, Daniely and Mansour [2019] demonstrate that Discounted-Normal-Predictor can be utilized to yield nearly optimal regret bounds over any interval, even in the presence of switching costs. Inspired by their results, we develop a simple algorithm for SOCO: Combining online gradient descent (OGD) with different step sizes sequentially by Discounted-Normal-Predictor. Despite its simplicity, we prove that it is able to minimize the adaptive regret with switching cost, i.e., attaining nearly optimal regret with switching cost on every interval. By exploiting the theoretical guarantee of OGD for dynamic regret, we further show that the proposed algorithm can minimize the dynamic regret with switching cost in every interval.

Keywords: Smoothed Online Convex Optimization · Dynamic regret with switching cost · Discounted-Normal-Predictor · Adaptive regret with switching cost

Author Information

Lijun Zhang (Nanjing University (NJU))
Wei Jiang (Nanjing University)
Jinfeng Yi (JD AI Research)
Tianbao Yang (Texas A&M University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors