# Chasing Convex Bodies and Functions with Black-Box Advice

arXiv: https://arxiv.org/abs/2206.11780 · HTML: https://mlsanity.com/paper/2206.11780/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 46 references that are in the map.
- First posted on arXiv 23 Jun 2022.

## Builds on (most cited first, 16 of 16)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Online Computation with Untrusted Advice](https://mlsanity.com/paper/1905.05655/) (2019)
- [Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent](https://mlsanity.com/paper/1803.10366/) (2018)
- [Online Optimization with Predictions and Switching Costs: Fast Algorithms and the Fundamental Limit](https://mlsanity.com/paper/1801.07780/) (2018)
- [Smoothed Online Optimization for Regression and Control](https://mlsanity.com/paper/1810.10132/) (2018)
- [Chasing Nested Convex Bodies Nearly Optimally](https://mlsanity.com/paper/1811.00999/) (2018)
- [Chasing Convex Bodies Optimally](https://mlsanity.com/paper/1905.11968/) (2019)
- [Chasing Convex Bodies with Linear Competitive Ratio](https://mlsanity.com/paper/1905.11877/) (2019)
- [Can Q-Learning be Improved with Advice?](https://mlsanity.com/paper/2110.13052/) (2021)
- [A Nearly-Linear Bound for Chasing Nested Convex Bodies](https://mlsanity.com/paper/1806.08865/) (2018)
- [Dimension-Free Bounds on Chasing Convex Functions](https://mlsanity.com/paper/2005.14058/) (2020)
- [Online Search With a Hint](https://mlsanity.com/paper/2008.13729/) (2020)
- [Optimal Algorithms for Right-Sizing Data Centers- Extended Version](https://mlsanity.com/paper/1807.05112/) (2018)
- [Better Bounds for Online Line Chasing](https://mlsanity.com/paper/1811.09233/) (2018)

## Built on by (most cited first, 19 of 19)

- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)
- [Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms](https://mlsanity.com/paper/2310.20598/) (2023)
- [Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictions](https://mlsanity.com/paper/2307.10524/) (2023)
- [Learning for Edge-Weighted Online Bipartite Matching with Robustness Guarantees](https://mlsanity.com/paper/2306.00172/) (2023)
- [Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems](https://mlsanity.com/paper/2406.18752/) (2024)
- [Robustified Learning for Online Optimization with Memory Costs](https://mlsanity.com/paper/2305.00677/) (2023)
- [Chasing Convex Functions with Long-term Constraints](https://mlsanity.com/paper/2402.14012/) (2024)
- [Robust Learning for Smoothed Online Convex Optimization with Feedback Delay](https://mlsanity.com/paper/2310.20098/) (2023)
- [Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization](https://mlsanity.com/paper/2311.00181/) (2023)
- [On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rental](https://mlsanity.com/paper/2312.02547/) (2023)
- [Efficiently Solving Discounted MDPs with Predictions on Transition Matrices](https://mlsanity.com/paper/2502.15345/) (2025)
- [Learning-Augmented Decentralized Online Convex Optimization in Networks](https://mlsanity.com/paper/2306.10158/) (2023)
- [Out-of-Distribution-Aware Electric Vehicle Charging](https://mlsanity.com/paper/2311.05941/) (2023)
- [Learning-Augmented Competitive Algorithms for Spatiotemporal Online Allocation with Deadline Constraints](https://mlsanity.com/paper/2408.07831/) (2024)
- [Learning-Augmented Online Minimization with Dual Predictions](https://mlsanity.com/paper/2606.05380/) (2026)
- [Capacity Provisioning Motivated Online Non-Convex Optimization Problem with Memory and Switching Cost](https://mlsanity.com/paper/2403.17480/) (2024)
- [Safe Exploitative Play with Untrusted Type Beliefs](https://mlsanity.com/paper/2411.07679/) (2024)
- [Signal-Aware Workload Shifting Algorithms with Uncertainty-Quantified Predictors](https://mlsanity.com/paper/2509.26511/) (2025)
- [Fairness-Regularized Online Optimization with Switching Costs](https://mlsanity.com/paper/2512.11131/) (2025)

## Abstract (arXiv)

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 textitconsistency, while also ensuring worst-case textitrobustness 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 O(fracCε2)-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(fracCDε)-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.