Dimension-Free Bounds on Chasing Convex Functions
share
We consider the problem of chasing convex functions, where functions arrive over time. The player takes actions after seeing the function, and the goal is to achieve a small function cost for these actions, as well as a small cost for moving between actions. While the general problem requires a polynomial dependence on the dimension, we show how to get dimension-independent bounds for well-behaved functions. In particular, we consider the case where the convex functions are κ-well-conditioned, and give an algorithm that achieves an O(√(κ))-competitiveness. Moreover, when the functions are supported on k-dimensional affine subspaces–e.g., when the function are the indicators of some affine subspaces–we get O(min(k, √(k log T)))-competitive algorithms for request sequences of length T. We also show some lower bounds, that well-conditioned functions require Ω(κ^1/3)-competitiveness, and k-dimensional functions require Ω(√(k))-competitiveness.
READ FULL TEXT