Regrets of Proximal Method of Multipliers for Online Non-convex Optimization with Long Term Constraints

DOI10.1007/S10898-022-01196-2arXiv2204.10986MaRDI QIDQ6397258FDOQ6397258

Haoyang Liu, Xiantao Xiao, Liwei Zhang

Publication date: 22 April 2022

Abstract: The online optimization problem with non-convex loss functions over a closed convex set, coupled with a set of inequality (possibly non-convex) constraints is a challenging online learning problem. A proximal method of multipliers with quadratic approximations (named as OPMM) is presented to solve this online non-convex optimization with long term constraints. Regrets of the violation of Karush-Kuhn-Tucker conditions of OPMM for solving online non-convex optimization problems are analyzed. Under mild conditions, it is shown that this algorithm exhibits $cO(T^{-1/8})$ Lagrangian gradient violation regret, $cO(T^{-1/8})$ constraint violation regret and $cO(T^{-1/4})$ complementarity residual regret if parameters in the algorithm are properly chosen, where $T$ denotes the number of time periods. For the case that the objective is a convex quadratic function, we demonstrate that the regret of the objective reduction can be established even the feasible set is non-convex. For the case when the constraint functions are convex, if the solution of the subproblem in OPMM is obtained by solving its dual, OPMM is proved to be an implementable projection method for solving the online non-convex optimization problem.

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26)

This page was built for publication: Regrets of Proximal Method of Multipliers for Online Non-convex Optimization with Long Term Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6397258)