Chasing Convex Bodies and Functions with Black-Box Advice
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 consistency, while also ensuring worst-case 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, INTERP, achieves (√2̅ + ϵ)-consistency and 2̅(C/ϵ²)-robustness for any ϵ > 0, where C is the competitive ratio of an algorithm for convex function chasing or a subclass thereof. The second, BDINTERP, achieves (1 + ϵ)-consistency and O(CD/ϵ)-robustness when the problem has bounded diameter D. Further, we show that BDINTERP achieves near-optimal consistency-robustness trade-off for the special case where cost functions are α-polyhedral.
Additional Information
© 2022 N. Christianson, T. Handina & A. Wierman. Attribution 4.0 International (CC BY 4.0) The authors thank Eitan Levin for several helpful discussions. The authors acknowledge support from an NSF Graduate Research Fellowship (DGE-1745301), NSF grants CNS-2146814, CPS-2136197, CNS-2106403, and NGSDI-2105648, and Amazon AWS.Attached Files
Accepted Version - 2206.11780.pdf
Files
Name | Size | Download all |
---|---|---|
md5:80d013503d779a2611e32b63d0ccc3bb
|
672.3 kB | Preview Download |
Additional details
- Eprint ID
- 120094
- Resolver ID
- CaltechAUTHORS:20230316-204004873
- NSF Graduate Research Fellowship
- DGE-1745301
- NSF
- CNS-2146814
- NSF
- ECCS-2136197
- NSF
- CNS-2105648
- Amazon Web Services
- Created
-
2023-03-16Created from EPrint's datestamp field
- Updated
-
2023-03-16Created from EPrint's last_modified field