# Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 64 references that are in the map.
- First posted on arXiv 31 Oct 2023.

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

- [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)
- [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)
- [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)
- [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)
- [Smoothed Online Optimization with Unreliable Predictions](https://mlsanity.com/paper/2202.03519/) (2022)
- [The Online Pause and Resume Problem: Optimal Algorithms and An Application to Carbon-Aware Load Shifting](https://mlsanity.com/paper/2303.17551/) (2023)
- [Adaptive Charging Networks: A Framework for Smart Electric Vehicle Charging](https://mlsanity.com/paper/2012.02636/) (2020)
- [The Randomized k-Server Conjecture is False!](https://mlsanity.com/paper/2211.05753/) (2022)
- [Ecovisor: A Virtual Energy System for Carbon-Efficient Applications](https://mlsanity.com/paper/2210.04951/) (2022)
- [Carbon-Aware EV Charging](https://mlsanity.com/paper/2209.12373/) (2022)
- [The War of the Efficiencies: Understanding the Tension between Carbon and Energy Optimization](https://mlsanity.com/paper/2306.16948/) (2023)
- [The Online Knapsack Problem with Departures](https://mlsanity.com/paper/2209.11934/) (2022)

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

- [Chasing Convex Functions with Long-term Constraints](https://mlsanity.com/paper/2402.14012/) (2024)
- [Fast and Reliable N-k Contingency Screening with Input-Convex Neural Networks](https://mlsanity.com/paper/2410.00796/) (2024)
- [LACS: Learning-Augmented Algorithms for Carbon-Aware Resource Scaling with Uncertain Demand](https://mlsanity.com/paper/2404.15211/) (2024)
- [The Secretary Problem with Predictions and a Chosen Order](https://mlsanity.com/paper/2601.07482/) (2026)
- [Learning-Augmented Competitive Algorithms for Spatiotemporal Online Allocation with Deadline Constraints](https://mlsanity.com/paper/2408.07831/) (2024)
- [Online Smoothed Demand Management](https://mlsanity.com/paper/2511.18554/) (2025)
- [Smoothed Online Optimization for Target Tracking: Robust and Learning-Augmented Algorithms](https://mlsanity.com/paper/2509.05930/) (2025)
- [Signal-Aware Workload Shifting Algorithms with Uncertainty-Quantified Predictors](https://mlsanity.com/paper/2509.26511/) (2025)
- [Online Multi-Class Selection with Group Fairness Guarantee](https://mlsanity.com/paper/2510.21055/) (2025)
- [Fairness-Regularized Online Optimization with Switching Costs](https://mlsanity.com/paper/2512.11131/) (2025)

## Abstract (arXiv)

We introduce and study online conversion with switching costs, a family of online problems that capture emerging problems at the intersection of energy and sustainability. In this problem, an online player attempts to purchase (alternatively, sell) fractional shares of an asset during a fixed time horizon with length T. At each time step, a cost function (alternatively, price function) is revealed, and the player must irrevocably decide an amount of asset to convert. The player also incurs a switching cost whenever their decision changes in consecutive time steps, i.e., when they increase or decrease their purchasing amount. We introduce competitive (robust) threshold-based algorithms for both the minimization and maximization variants of this problem, and show they are optimal among deterministic online algorithms. We then propose learning-augmented algorithms that take advantage of untrusted black-box advice (such as predictions from a machine learning model) to achieve significantly better average-case performance without sacrificing worst-case competitive guarantees. Finally, we empirically evaluate our proposed algorithms using a carbon-aware EV charging case study, showing that our algorithms substantially improve on baseline methods for this problem.