Chasing Convex Bodies and Functions with Black-Box Advice

Nicolas Christianson, Tinashe Handina, Adam Wierman
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:867-908, 2022.

Abstract

We consider the problem of convex function chasing with black-box advice, where an online decision-maker aims to minimize the total cost of making and switching between decisions in a normed vector space, aided by black-box advice such as the decisions of a machine-learned algorithm. The decision-maker seeks cost comparable to the advice when it performs well, known as \emph{consistency}, while also ensuring worst-case \emph{robustness} even when the advice is adversarial. We first consider the common paradigm of algorithms that switch between the decisions of the advice and a competitive algorithm, showing that no algorithm in this class can improve upon 3-consistency while staying robust. We then propose two novel algorithms that bypass this limitation by exploiting the problem’s convexity. The first, \textscInterp, achieves (√2+ϵ)-consistency and O(Cϵ2)-robustness for any ϵ>0, where C is the competitive ratio of an algorithm for convex function chasing or a subclass thereof. The second, \textscBdInterp, achieves (1+ϵ)-consistency and O(CDϵ)-robustness when the problem has bounded diameter D. Further, we show that \textscBdInterp achieves near-optimal consistency-robustness trade-off for the special case where cost functions are α-polyhedral.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-christianson22a, title = {Chasing Convex Bodies and Functions with Black-Box Advice}, author = {Christianson, Nicolas and Handina, Tinashe and Wierman, Adam}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {867--908}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/christianson22a/christianson22a.pdf}, url = {https://proceedings.mlr.press/v178/christianson22a.html}, abstract = {We consider the problem of convex function chasing with black-box advice, where an online decision-maker aims to minimize the total cost of making and switching between decisions in a normed vector space, aided by black-box advice such as the decisions of a machine-learned algorithm. The decision-maker seeks cost comparable to the advice when it performs well, known as \emph{consistency}, while also ensuring worst-case \emph{robustness} even when the advice is adversarial. We first consider the common paradigm of algorithms that switch between the decisions of the advice and a competitive algorithm, showing that no algorithm in this class can improve upon 3-consistency while staying robust. We then propose two novel algorithms that bypass this limitation by exploiting the problem’s convexity. The first, $\textsc{Interp}$, achieves $(\sqrt{2}+\epsilon)$-consistency and $\mathcal{O}(\frac{C}{\epsilon^2})$-robustness for any $\epsilon > 0$, where $C$ is the competitive ratio of an algorithm for convex function chasing or a subclass thereof. The second, $\textsc{BdInterp}$, achieves $(1+\epsilon)$-consistency and $\mathcal{O}(\frac{CD}{\epsilon})$-robustness when the problem has bounded diameter $D$. Further, we show that $\textsc{BdInterp}$ achieves near-optimal consistency-robustness trade-off for the special case where cost functions are $\alpha$-polyhedral.} }
Endnote
%0 Conference Paper %T Chasing Convex Bodies and Functions with Black-Box Advice %A Nicolas Christianson %A Tinashe Handina %A Adam Wierman %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-christianson22a %I PMLR %P 867--908 %U https://proceedings.mlr.press/v178/christianson22a.html %V 178 %X We consider the problem of convex function chasing with black-box advice, where an online decision-maker aims to minimize the total cost of making and switching between decisions in a normed vector space, aided by black-box advice such as the decisions of a machine-learned algorithm. The decision-maker seeks cost comparable to the advice when it performs well, known as \emph{consistency}, while also ensuring worst-case \emph{robustness} even when the advice is adversarial. We first consider the common paradigm of algorithms that switch between the decisions of the advice and a competitive algorithm, showing that no algorithm in this class can improve upon 3-consistency while staying robust. We then propose two novel algorithms that bypass this limitation by exploiting the problem’s convexity. The first, $\textsc{Interp}$, achieves $(\sqrt{2}+\epsilon)$-consistency and $\mathcal{O}(\frac{C}{\epsilon^2})$-robustness for any $\epsilon > 0$, where $C$ is the competitive ratio of an algorithm for convex function chasing or a subclass thereof. The second, $\textsc{BdInterp}$, achieves $(1+\epsilon)$-consistency and $\mathcal{O}(\frac{CD}{\epsilon})$-robustness when the problem has bounded diameter $D$. Further, we show that $\textsc{BdInterp}$ achieves near-optimal consistency-robustness trade-off for the special case where cost functions are $\alpha$-polyhedral.
APA
Christianson, N., Handina, T. & Wierman, A.. (2022). Chasing Convex Bodies and Functions with Black-Box Advice. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:867-908 Available from https://proceedings.mlr.press/v178/christianson22a.html.

Related Material