Dimension-Free Bounds for Chasing Convex Functions
Guru Guruganesh, Anupam Gupta, Charles Argue
Subject areas: Online learning, Convex optimization
Presented in: Session 4A, Session 4C
[Zoom link for poster in Session 4A], [Zoom link for poster in Session 4C]
Abstract:
We consider the problem of chasing convex functions, where functions\n arrive over time. The player takes actions after seeing the \n function, and the goal is to achieve a small function cost for these\n actions, as well as a small cost for moving between actions. While\n the general problem requires a polynomial dependence on the \n dimension, we show how to get dimension-independent bounds for \n well-behaved functions. In particular, we consider the case where\n the convex functions are $\kappa$-well-conditioned, and give an\n algorithm that achieves an $O(\sqrt \kappa)$-competitiveness. Moreover,\n when the functions are supported on $k$-dimensional affine\n subspaces---e.g., when the function are the indicators of some\n affine subspaces---we get $O(\min(k, \sqrt{k \log T}))$-competitive \n algorithms for request sequences of length $T$. We also\n show some lower bounds, that well-conditioned functions require \n $\Omega(\kappa^{1/3})$-competitiveness, and $k$-dimensional functions\n require $\Omega(\sqrt{k})$-competitiveness.