# Online Learning under Adversarial Nonlinear Constraints

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 36 references that are in the map.
- First posted on arXiv 6 Jun 2023.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [Adaptive Algorithms for Online Convex Optimization with Long-term Constraints](https://mlsanity.com/paper/1512.07422/) (2015)
- [Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/1702.04783/) (2017)
- [Online convex optimization for cumulative constraints](https://mlsanity.com/paper/1802.06472/) (2018)
- [An Online Convex Optimization Approach to Dynamic Network Resource Allocation](https://mlsanity.com/paper/1701.03974/) (2017)
- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (2022)
- [Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints](https://mlsanity.com/paper/2106.05135/) (2021)
- [Efficient Projection-Free Online Convex Optimization with Membership Oracle](https://mlsanity.com/paper/2111.05818/) (2021)
- [New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees](https://mlsanity.com/paper/2202.04721/) (2022)
- [On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems](https://mlsanity.com/paper/2107.08225/) (2021)
- [Projection-free Adaptive Regret with Membership Oracles](https://mlsanity.com/paper/2211.12638/) (2022)
- [Simultaneously Achieving Sublinear Regret and Constraint Violations for Online Convex Optimization with Time-varying Constraints](https://mlsanity.com/paper/2111.07707/) (2021)
- [First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems](https://mlsanity.com/paper/2204.03132/) (2022)
- [Equilibrium Computation of Generalized Nash Games: A New Lagrangian-Based Approach](https://mlsanity.com/paper/2106.00109/) (2021)

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

- [Stochastic Online Optimization for Cyber-Physical and Robotic Systems](https://mlsanity.com/paper/2404.05318/) (2024)
- [Primal Methods for Variational Inequality Problems with Functional Constraints](https://mlsanity.com/paper/2403.12859/) (2024)
- [Optimistic Safety for Online Convex Optimization with Unknown Linear Constraints](https://mlsanity.com/paper/2403.05786/) (2024)
- [Controlling Participation in Federated Learning with Feedback](https://mlsanity.com/paper/2411.19242/) (2024)
- [Safety in the Face of Adversity: Achieving Zero Constraint Violation in Online Learning with Slowly Changing Constraints](https://mlsanity.com/paper/2505.00398/) (2025)
- [An Online Feasible Point Method for Benign Generalized Nash Equilibrium Problems](https://mlsanity.com/paper/2410.02400/) (2024)

## Abstract (arXiv)

In many applications, learning systems are required to process continuous non-stationary data streams. We study this problem in an online learning framework and propose an algorithm that can deal with adversarial time-varying and nonlinear constraints. As we show in our work, the algorithm called Constraint Violation Velocity Projection (CVV-Pro) achieves √T regret and converges to the feasible set at a rate of 1/√T, despite the fact that the feasible set is slowly time-varying and a priori unknown to the learner. CVV-Pro only relies on local sparse linear approximations of the feasible set and therefore avoids optimizing over the entire set at each iteration, which is in sharp contrast to projected gradients or Frank-Wolfe methods. We also empirically evaluate our algorithm on two-player games, where the players are subjected to a shared constraint.