Online Learning under Adversarial Nonlinear Constraints
This work addresses the challenge of processing non-stationary data streams under adversarial constraints, which is incremental but important for applications like multi-agent systems.
The paper tackles the problem of online learning with adversarial nonlinear constraints by proposing the CVV-Pro algorithm, which achieves √T regret and converges to the feasible set at a rate of 1/√T, as demonstrated empirically on two-player games with shared constraints.
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 $\sqrt{T}$ regret and converges to the feasible set at a rate of $1/\sqrt{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.