Online Learning for Approximately-Convex Functions with Long-term Adversarial Constraints
This work addresses online optimization under adversarial constraints for a broad class of non-convex functions, offering improved guarantees for problems like Adversarial Bandits with Knapsacks.
The paper tackles online learning with long-term adversarial constraints by proposing an efficient first-order algorithm that achieves O(√T) α-regret and O(B_T log T) + Õ(√T) resource consumption for α-approximately convex functions, applicable to problems like DR-submodular maximization and Online Vertex Cover.
We study an online learning problem with long-term budget constraints in the adversarial setting. In this problem, at each round $t$, the learner selects an action from a convex decision set, after which the adversary reveals a cost function $f_t$ and a resource consumption function $g_t$. The cost and consumption functions are assumed to be $α$-approximately convex - a broad class that generalizes convexity and encompasses many common non-convex optimization problems, including DR-submodular maximization, Online Vertex Cover, and Regularized Phase Retrieval. The goal is to design an online algorithm that minimizes cumulative cost over a horizon of length $T$ while approximately satisfying a long-term budget constraint of $B_T$. We propose an efficient first-order online algorithm that guarantees $O(\sqrt{T})$ $α$-regret against the optimal fixed feasible benchmark while consuming at most $O(B_T \log T)+ \tilde{O}(\sqrt{T})$ resources in both full-information and bandit feedback settings. In the bandit feedback setting, our approach yields an efficient solution for the $\texttt{Adversarial Bandits with Knapsacks}$ problem with improved guarantees. We also prove matching lower bounds, demonstrating the tightness of our results. Finally, we characterize the class of $α$-approximately convex functions and show that our results apply to a broad family of problems.