Online Non-convex Optimization with Long-term Non-convex Constraints
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918151805992960 |
|---|---|
| author | Pan, Shijie Xu, Jianyu Huang, Wenjie |
| author_facet | Pan, Shijie Xu, Jianyu Huang, Wenjie |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_02426 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Online Non-convex Optimization with Long-term Non-convex Constraints Pan, Shijie Xu, Jianyu Huang, Wenjie Optimization and Control Machine Learning 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. |
| title | Online Non-convex Optimization with Long-term Non-convex Constraints |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2311.02426 |