# Chasing Convex Functions with Long-term Constraints

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 38 references that are in the map.
- First posted on arXiv 21 Feb 2024.

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

- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Carbon-Aware Computing for Datacenters](https://mlsanity.com/paper/2106.11750/) (2021)
- [Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent](https://mlsanity.com/paper/1803.10366/) (2018)
- [Carbon Explorer: A Holistic Approach for Designing Carbon Aware Datacenters](https://mlsanity.com/paper/2201.10036/) (2022)
- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [Chasing Nested Convex Bodies Nearly Optimally](https://mlsanity.com/paper/1811.00999/) (2018)
- [Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems](https://mlsanity.com/paper/2109.01556/) (2021)
- [Chasing Convex Bodies and Functions with Black-Box Advice](https://mlsanity.com/paper/2206.11780/) (2022)
- [Chasing Convex Bodies Optimally](https://mlsanity.com/paper/1905.11968/) (2019)
- [CarbonScaler: Leveraging Cloud Workload Elasticity for Optimizing Carbon-Efficiency](https://mlsanity.com/paper/2302.08681/) (2023)
- [Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging](https://mlsanity.com/paper/2010.00412/) (2020)
- [Let's Wait Awhile: How Temporal Workload Shifting Can Reduce Carbon Emissions in the Cloud](https://mlsanity.com/paper/2110.13234/) (2021)
- [Enabling Sustainable Clouds: The Case for Virtualizing the Energy System](https://mlsanity.com/paper/2106.08872/) (2021)
- [Metrical task systems on trees via mirror descent and unfair gluing](https://mlsanity.com/paper/1807.04404/) (2018)
- [Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms](https://mlsanity.com/paper/2310.20598/) (2023)
- [Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Markets](https://mlsanity.com/paper/2211.06567/) (2022)
- [The Online Pause and Resume Problem: Optimal Algorithms and An Application to Carbon-Aware Load Shifting](https://mlsanity.com/paper/2303.17551/) (2023)
- [Dimension-Free Bounds on Chasing Convex Functions](https://mlsanity.com/paper/2005.14058/) (2020)
- [The Randomized k-Server Conjecture is False!](https://mlsanity.com/paper/2211.05753/) (2022)
- [Carbon-Aware EV Charging](https://mlsanity.com/paper/2209.12373/) (2022)

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

- [Online Convex Optimization with Switching Cost with Only One Single Gradient Evaluation](https://mlsanity.com/paper/2507.04133/) (2025)
- [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)
- [Online Multi-Class Selection with Group Fairness Guarantee](https://mlsanity.com/paper/2510.21055/) (2025)

## Abstract (arXiv)

We introduce and study a family of online metric problems with long-term constraints. In these problems, an online player makes decisions xt in a metric space (X,d) to simultaneously minimize their hitting cost ft(xt) and switching cost as determined by the metric. Over the time horizon T, the player must satisfy a long-term demand constraint sumt c(xt) ≥ 1, where c(xt) denotes the fraction of demand satisfied at time t. Such problems can find a wide array of applications to online resource allocation in sustainable energy/computing systems. We devise optimal competitive and learning-augmented algorithms for the case of bounded hitting cost gradients and weighted ℓ1 metrics, and further show that our proposed algorithms perform well in numerical experiments.