Mirror Descent, Online Learning, and Competitive AnalysisSpeaker: Fred
Title: Mirror Descent, Online Learning, and Competitive Analysis
Date: 25 Mar 2019 5:30pm-7:00pm
Location: Maxwell-Dworkin 221
Audience background: Basic Calculus
Talk style: Casual
Abstract: We will discuss the motivation and basic formulations of the mirror descent method for convex optimization. We focus on its applications to two classes of online problems. In online learning (a.k.a, regret analysis), it can be viewed as a unified scheme for some well-known algorithms, such as randomized weighted majority (Littlestone and Warmuth, 1994) and online gradient descent (Zinkevich, 2003). In online algorithms (a.k.a, competitive analysis), mirror descent enabled several breakthroughs in recent years, particularly on the k-server (Bubeck et. al., 2018 and Lee, 2018) and metric task system (Bubeck et. al., 2018) problem. Time permitting, we will discuss some high-level ideas of these solutions.