论文标题
在线牛顿的一种时间变化线性平等约束的方法
An Online Newton's Method for Time-varying Linear Equality Constraints
论文作者
论文摘要
我们考虑与时变线性平等约束的在线优化问题。在此框架中，代理仅使用先验信息做出顺序决策。在每一轮中，代理都会遭受确定的损失，并且必须满足时间变化的约束。损失函数和约束都可以对抗。我们提出了在线预计的等于受限的牛顿方法（OPEN-M）来解决这个问题。在轻度条件下，我们获得了sublinear动态遗憾和违反限制的范围。也就是说，需要最佳的损失函数的平滑度和反向黑森的界限，但不需要凸度。最后，我们在数值网络流程应用程序中显示开放式M的最先进在线约束优化算法。
We consider online optimization problems with time-varying linear equality constraints. In this framework, an agent makes sequential decisions using only prior information. At every round, the agent suffers an environment-determined loss and must satisfy time-varying constraints. Both the loss functions and the constraints can be chosen adversarially. We propose the Online Projected Equality-constrained Newton Method (OPEN-M) to tackle this family of problems. We obtain sublinear dynamic regret and constraint violation bounds for OPEN-M under mild conditions. Namely, smoothness of the loss function and boundedness of the inverse Hessian at the optimum are required, but not convexity. Finally, we show OPEN-M outperforms state-of-the-art online constrained optimization algorithms in a numerical network flow application.
