论文标题
凸风风险避免分布式优化的最佳方法
Optimal Methods for Convex Risk Averse Distributed Optimization
论文作者
论文摘要
本文研究了网络上凸的风险优化的沟通复杂性。该问题概括了研究良好的风险中立有限和分布式优化问题，其重要性源于在不确定的环境中应对风险的需求。对于文献中的算法，在解决规避风险和风险中性问题的沟通复杂性方面存在差距。我们提出了两种分布式算法，即用滑动（DRAO-S）方法的分布式风险避开风险优化（DRAO）方法和分布式风险优化，以缩小差距。具体而言，DRAO方法通过假设可以在服务器节点中轻松求解特定的鞍点子问题来实现最佳通信复杂性。 DRAO-S方法通过引入一个新颖的鞍点滑动子例程来消除强烈的假设，该子例程仅需要对模棱两可的投影集合$ p $。我们观察到，DRAO-S执行的$ P $ - 项目的数量是最佳的。此外，我们开发了较低的复杂性范围，以显示DRAO和DRAO-S的通信复杂性，以改进。进行数值实验以证明DRAO-S方法的令人鼓舞的经验表现。
This paper studies the communication complexity of convex risk-averse optimization over a network. The problem generalizes the well-studied risk-neutral finite-sum distributed optimization problem and its importance stems from the need to handle risk in an uncertain environment. For algorithms in the literature, there exists a gap in communication complexities for solving risk-averse and risk-neutral problems. We propose two distributed algorithms, namely the distributed risk averse optimization (DRAO) method and the distributed risk averse optimization with sliding (DRAO-S) method, to close the gap. Specifically, the DRAO method achieves the optimal communication complexity by assuming a certain saddle point subproblem can be easily solved in the server node. The DRAO-S method removes the strong assumption by introducing a novel saddle point sliding subroutine which only requires the projection over the ambiguity set $P$. We observe that the number of $P$-projections performed by DRAO-S is optimal. Moreover, we develop matching lower complexity bounds to show the communication complexities of both DRAO and DRAO-S to be improvable. Numerical experiments are conducted to demonstrate the encouraging empirical performance of the DRAO-S method.
