Online Learning under Adversarial Nonlinear Constraints

By Pavel Kolev et al

Published on Oct. 13, 2023

Read the original document by opening this link in a new tab.

Table of Contents

Abstract
1 Introduction
1.1 Related Work
1.2 Main Contributions
1.3 Outline
2 Algorithm Description
3 Results and Analysis
Conclusion

Summary

In this paper, the authors present an online learning framework for handling adversarial time-varying and nonlinear constraints. The proposed algorithm, Constraint Violation Velocity Projection (CVV-Pro), is designed to address the challenges of processing continuous non-stationary data streams. The algorithm achieves a regret rate of √ T and converges to the feasible set at a rate of 1/√ T, despite the slowly time-varying nature of the constraints. By relying on local sparse linear approximations of the feasible set, the algorithm avoids the need to optimize over the entire set at each iteration, distinguishing it from traditional methods like projected gradients or Frank-Wolfe methods. Empirical evaluation on two-player games further demonstrates the effectiveness of the algorithm. The paper highlights the importance of online learning in adaptive decision-making and optimization, especially in the presence of real-world constraints imposed by physical, social, or biological systems. The proposed algorithm's performance is compared with existing methods, showcasing its efficiency in handling nonlinear constraints and time-varying environments.