Dimension-Free Bounds for Chasing Convex Functions

C. J. Argue, Anupam Gupta, Guru Guruganesh

Research output: Contribution to journalConference articlepeer-review


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 languageEnglish (US)
Pages (from-to)219-241
Number of pages23
JournalProceedings of Machine Learning Research
StatePublished - 2020
Event33rd Conference on Learning Theory, COLT 2020 - Virtual, Online, Austria
Duration: Jul 9 2020Jul 12 2020


  • 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


Dive into the research topics of 'Dimension-Free Bounds for Chasing Convex Functions'. Together they form a unique fingerprint.

Cite this