Online Non-convex Optimization with Long-term Non-convex Constraints
A novel Follow-the-Perturbed-Leader type algorithm is proposed and analyzed for solving general long-term constrained optimization problems in online manner, where the objective and constraints are arbitrarily generated and not necessarily convex. In each period, random linear perturbation and strongly concave perturbation are incorporated in primal and dual directions, respectively, to the offline oracle, and a global minimax point is searched as the solution. Based on a proposed expected static cumulative regret, we derive the first sublinear $O(T^{8/9})$ 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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Adaptive Algorithms for Online Convex Optimization with Long-term Constraints
We present an adaptive online gradient descent algorithm to solve online convex optimization problems with long-term constraints , which are constraints that need to be satisfied when accumulated over a finite number of …
Convex Parameterizations and Fidelity Bounds for Nonlinear Identification and Reduced-Order Modelling
Model instability and poor prediction of long-term behavior are common problems when modeling dynamical systems using nonlinear "black-box" techniques. Direct optimization of the long-term predictions, often called simul…
Online Learning for Approximately-Convex Functions with Long-term Adversarial Constraints
We study an online learning problem with long-term budget constraints in the adversarial setting. In this problem, at each round $t$, the learner selects an action from a convex decision set, after which the adversary re…
Online Convex Optimization with Stochastic Constraints
This paper considers online convex optimization (OCO) with stochastic constraints, which generalizes Zinkevich's OCO over a known simple fixed set by introducing multiple stochastic functional constraints that are i.i.d.…
SchedulingOnline Convex Optimization with Long Term Constraints for Predictable Sequences
In this paper, we investigate the framework of Online Convex Optimization (OCO) for online learning. OCO offers a very powerful online learning framework for many applications. In this context, we study a specific framew…