Online Convex Optimization with Switching Cost and Delayed Gradients

Pranab Panda
Varun Ramanathan
Friday, 19 Apr 2024, 16:00 to 17:00
A-201 (STCS Seminar Room)

This paper focuses on Online Convex Optimization (OCO) problem with linear and quadratic switching costs and by the help of an online algorithm OMGD(Online Multiple Gradient Descent) for a class of L smooth and μ strongly convex functions, in limited information setting (where at time t we choose x_t without knowing f_t and our objective is to minimise f(x) + S(x_t-1, x_t) summed over t. S(.,.) is the switching cost), we can achieve a competitive ratio of at most 4(L + 5) + 16(L + 5)/μ for quadratic switching cost.
Online convex optimization captures many crucial real world problems like server management in data centres, etc. We will also try to look at how the performance of online algorithms changes even when the switching cost changes from quadratic to linear.