# Online Optimization with Predictions and Non-convex Losses

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Nov 2019.

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

- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [Smoothed Online Optimization with Unreliable Predictions](https://mlsanity.com/paper/2202.03519/) (2022)
- [Movement Penalized Bayesian Optimization with Application to Wind Energy Systems](https://mlsanity.com/paper/2210.08087/) (2022)
- [Expert-Calibrated Learning for Online Optimization with Switching Costs](https://mlsanity.com/paper/2204.08572/) (2022)
- [Adaptive Composite Online Optimization: Predictions in Static and Dynamic Environments](https://mlsanity.com/paper/2205.00446/) (2022)
- [Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor](https://mlsanity.com/paper/2205.00741/) (2022)
- [Lazy Lagrangians with Predictions for Online Learning](https://mlsanity.com/paper/2201.02890/) (2022)
- [Near-Optimal Adversarial Reinforcement Learning with Switching Costs](https://mlsanity.com/paper/2302.04374/) (2023)
- [Robustified Learning for Online Optimization with Memory Costs](https://mlsanity.com/paper/2305.00677/) (2023)
- [Robust Learning for Smoothed Online Convex Optimization with Feedback Delay](https://mlsanity.com/paper/2310.20098/) (2023)
- [Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach](https://mlsanity.com/paper/2510.18687/) (2025)
- [Fairness-Regularized Online Optimization with Switching Costs](https://mlsanity.com/paper/2512.11131/) (2025)

## Abstract (arXiv)

We study online optimization in a setting where an online learner seeks to optimize a per-round hitting cost, which may be non-convex, while incurring a movement cost when changing actions between rounds. We ask: textitunder what general conditions is it possible for an online learner to leverage predictions of future cost functions in order to achieve near-optimal costs? Prior work has provided near-optimal online algorithms for specific combinations of assumptions about hitting and switching costs, but no general results are known. In this work, we give two general sufficient conditions that specify a relationship between the hitting and movement costs which guarantees that a new algorithm, Synchronized Fixed Horizon Control (SFHC), provides a 1+O(1/w) competitive ratio, where w is the number of predictions available to the learner. Our conditions do not require the cost functions to be convex, and we also derive competitive ratio results for non-convex hitting and movement costs. Our results provide the first constant, dimension-free competitive ratio for online non-convex optimization with movement costs. Further, we give an example of a natural instance, Convex Body Chasing (CBC), where the sufficient conditions are not satisfied and we can prove that no online algorithm can have a competitive ratio that converges to 1.