## Abstract

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, √klog 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.

Original language | English (US) |
---|---|

Pages (from-to) | 219-241 |

Number of pages | 23 |

Journal | Proceedings of Machine Learning Research |

Volume | 125 |

State | Published - 2020 |

Event | 33rd Conference on Learning Theory, COLT 2020 - Virtual, Online, Austria Duration: Jul 9 2020 → Jul 12 2020 |

## Keywords

- Online decision-making
- Steiner point
- convex body/function chasing
- online optimization
- smooth online convex optimization
- subspace chasing

## ASJC Scopus subject areas

- Artificial Intelligence
- Software
- Control and Systems Engineering
- Statistics and Probability