Dimension-Free Bounds for Chasing Convex Functions

C.J. Argue, Anupam Gupta, Guru Guruganesh
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:219-241, 2020.

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-competitive algorithms for request sequences of length T. We also show some lower bounds, that well-conditioned functions require \Omega(\kappa^{1/3})-competitiveness, and k-dimensional functions require \Omega(\sqrt{k})-competitiveness.

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-argue20a, title = {Dimension-Free Bounds for Chasing Convex Functions}, author = {Argue, C.J. and Gupta, Anupam and Guruganesh, Guru}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {219--241}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/argue20a/argue20a.pdf}, url = {https://proceedings.mlr.press/v125/argue20a.html}, 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 $\kappa$-well-conditioned, and give an algorithm that achieves an $O(\sqrt \kappa)$-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, \sqrt{k \log T}))$-competitive algorithms for request sequences of length $T$. We also show some lower bounds, that well-conditioned functions require $\Omega(\kappa^{1/3})$-competitiveness, and $k$-dimensional functions require $\Omega(\sqrt{k})$-competitiveness.} }
Endnote
%0 Conference Paper %T Dimension-Free Bounds for Chasing Convex Functions %A C.J. Argue %A Anupam Gupta %A Guru Guruganesh %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-argue20a %I PMLR %P 219--241 %U https://proceedings.mlr.press/v125/argue20a.html %V 125 %X 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 $\kappa$-well-conditioned, and give an algorithm that achieves an $O(\sqrt \kappa)$-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, \sqrt{k \log T}))$-competitive algorithms for request sequences of length $T$. We also show some lower bounds, that well-conditioned functions require $\Omega(\kappa^{1/3})$-competitiveness, and $k$-dimensional functions require $\Omega(\sqrt{k})$-competitiveness.
APA
Argue, C., Gupta, A. & Guruganesh, G.. (2020). Dimension-Free Bounds for Chasing Convex Functions. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:219-241 Available from https://proceedings.mlr.press/v125/argue20a.html.

Related Material