论文标题
对在线非convex优化的近端方法的遗憾和长期约束
Regrets of Proximal Method of Multipliers for Online Non-convex Optimization with Long Term Constraints
论文作者
论文摘要
在封闭的凸组中，非凸面损失功能的在线优化问题，再加上一组不平等（可能是非凸）约束，这是一个具有挑战性的在线学习问题。提出了具有二次近似值（称为OPMM）的乘数近端方法，以解决此在线非凸优化的长期约束。 分析了违反OPMM的Karush-Kuhn-Tucker条件来解决在线非凸优化问题的遗憾。 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选择，其中$ t $表示时间段。对于目标是凸二次函数的情况，我们证明，即使可行的集合也是非凸面，也可以确定客观降低的遗憾。对于约束函数是凸的情况，如果通过求解其双重来获得子问题的解决方案，则OPMM被证明是解决在线非convex优化问题的可实现投影方法。
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.
