Regrets of proximal method of multipliers for online non-convex optimization with long term constraints
Regrets of proximal method of multipliers for online non-convex optimization with long term constraints
复制标题
用于具有长期约束的在线非凸优化的乘法器的近端方法的遗憾
DOI：
10.1007/s10898-022-01196-2
复制
发表时间：
2022-04
影响因子：
1.8
通讯作者：
Xiantao Xiao
中科院分区：
文献类型：
--
作者：
Liwei Zhang;Haoyang Liu;Xiantao Xiao
闭凸集上的非凸损失函数的在线优化问题，加上一组不等式（可能是非凸）约束是一个具有挑战性的在线学习问题。提出了一种二次近似乘法器的近端方法（称为OPMM）来解决这种具有长期约束的在线非凸优化问题。分析了OPMM求解在线非凸优化问题时违反Karush-Kuhn-Tucker条件的遗憾。结果表明，在温和条件下，如果算法中的参数选择得当，该算法会表现出拉格朗日梯度违规遗憾、约束违规遗憾和互补残差遗憾，其中T表示时间段数。对于目标是凸二次函数的情况，我们证明即使可行集是非凸的，也可以建立目标约简的遗憾。对于约束函数为凸的情况，如果通过求解其对偶得到OPMM子问题的解，则证明OPMM是一种可实现的求解在线非凸优化问题的投影方法。
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 exhibitsLagrangian gradient violation regret,constraint violation regret andcomplementarity residual regret if parameters in the algorithm are properly chosen, whereTdenotes 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.
登录
查看更多内容
DOI：
--
发表时间：
2017-08
期刊：
--
影响因子：
--
作者：
Hao Yu;M. Neely;Xiaohan Wei
通讯作者：
Hao Yu;M. Neely;Xiaohan Wei
DOI：
--
发表时间：
2016-04
期刊：
ArXiv
影响因子：
--
作者：
Hao Yu;M. Neely
通讯作者：
Hao Yu;M. Neely
DOI：
10.1109/icccnt56998.2023.10306417
发表时间：
2022-02
期刊：
2023 14th International Conference on Computing Communication and Networking Technologies (ICCCNT)
影响因子：
--
作者：
Gilad Cohen;Raja Giryes
通讯作者：
Gilad Cohen;Raja Giryes
DOI：
--
发表时间：
2019
期刊：
--
影响因子：
--
作者：
Yatin Nandwani;A. Pathak;Mausam;Parag Singla
通讯作者：
Yatin Nandwani;A. Pathak;Mausam;Parag Singla
DOI：
10.1145/1961189.1961200
发表时间：
2011-04
期刊：
ACM Trans. Intell. Syst. Technol.
影响因子：
--
作者：
G. Gasso;A. Pappaioannou;Marina Spivak;L. Bottou
通讯作者：
G. Gasso;A. Pappaioannou;Marina Spivak;L. Bottou