# Online Non-convex Optimization with Long-term Non-convex Constraints

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 42 references that are in the map.
- First posted on arXiv 4 Nov 2023.

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

- [Concrete Problems in AI Safety](https://mlsanity.com/paper/1606.06565/) (2016)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [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)
- [Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances](https://mlsanity.com/paper/2006.08141/) (2020)
- [Online Non-Convex Learning: Following the Perturbed Leader is Optimal](https://mlsanity.com/paper/1903.08110/) (2019)
- [Online Primal-Dual Mirror Descent under Stochastic Constraints](https://mlsanity.com/paper/1908.00305/) (2019)
- [Efficient Regret Minimization in Non-Convex Games](https://mlsanity.com/paper/1708.00075/) (2017)
- [Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraints](https://mlsanity.com/paper/1903.04277/) (2019)
- [Learning in Non-convex Games with an Optimization Oracle](https://mlsanity.com/paper/1810.07362/) (2018)
- [Online Label Shift: Optimal Dynamic Regret meets Practical Algorithms](https://mlsanity.com/paper/2305.19570/) (2023)
- [Second-order Online Nonconvex Optimization](https://mlsanity.com/paper/2001.10114/) (2020)
- [The Online Saddle Point Problem and Online Convex Optimization with Knapsacks](https://mlsanity.com/paper/1806.08301/) (2018)
- [Regrets of Proximal Method of Multipliers for Online Non-convex Optimization with Long Term Constraints](https://mlsanity.com/paper/2204.10986/) (2022)
- [Multi-Point Bandit Algorithms for Nonstationary Online Nonconvex Optimization](https://mlsanity.com/paper/1907.13616/) (2019)
- [Online non-convex learning for river pollution source identification](https://mlsanity.com/paper/2005.11065/) (2020)

## Abstract (arXiv)

A novel Follow-the-Perturbed-Leader type algorithm is proposed and analyzed for solving general long-term constrained optimization problems in an online manner, where the target and constraint functions are oblivious adversarially generated and not necessarily convex. The algorithm is based on Lagrangian reformulation and innovatively integrates random perturbations and regularizations in primal and dual directions: 1). exponentially distributed random perturbations in the primal direction to handle non-convexity, and 2). strongly concave logarithmic regularizations in the dual space to handle constraint violations. Based on a proposed expected static cumulative regret, and under mild Lipschitz continuity assumption, the algorithm demonstrates the online learnability, achieving the first sublinear cumulative regret complexity for this class of problems. The proposed algorithm is applied to tackle a long-term (extreme value) constrained river pollutant source identification problem, validate the theoretical results and exhibit superior performance compared to existing methods.