Optimal Anytime Algorithms for Online Convex Optimization with Adversarial Constraints

We propose an anytime online algorithm for learning a sequence of convex cost functions while approximately satisfying a sequence of convex constraints, without prior knowledge of the time horizon. Both the cost and constraint functions may be chosen adversarially over time. While this problem has recently been resolved in the setting where the time horizon is known, extending these guarantees to the anytime setting, without resorting to inefficient doubling tricks, has remained technically challenging. Our main contribution is the introduction of a time-varying yet horizon-oblivious Lyapunov function to track constraint violations. The use of such a time-varying Lyapunov function introduces new technical difficulties, as a key monotonicity property underlying prior analyses no longer holds. By developing a novel analytical technique, we show that our algorithm achieves $O(\sqrt{t})$ regret and $\tilde{O}(\sqrt{t})$ cumulative constraint violation (CCV) for all $t \geq 1$. We further extend our framework to the dynamic regret setting, obtaining bounds that adapt to the unknown path length of the comparator sequence. Finally, we present an adaptive algorithm for the optimistic setting, whose performance scales gracefully with the cumulative prediction error. We validate the practical effectiveness of our approach through numerical experiments on the online shortest path problem.

Many real-world systems must make decisions repeatedly without knowing what will happen next. For example, a routing system may need to choose paths over time while keeping delays, bandwidth usage, or safety constraints under control. This paper studies a mathematical version of this problem, where the costs and constraints can change adversarially and the algorithm does not know in advance how long it will be used. We design new “anytime” algorithms, meaning they work well at every point in time without needing to know the final time horizon beforehand. The main idea is to track constraint violations using a carefully changing potential function, which lets the algorithm balance two goals: keeping total cost close to the best feasible fixed decision in hindsight, and keeping total constraint violation small. Our results show that these two quantities grow at nearly the best possible rate over time. This helps make online optimization methods more practical for settings where decisions must be safe, adaptive, and reliable over an unknown duration.