A Data Efficient and Feasible Level Set Method for Stochastic Convex Optimization with Expectation Constraints
A Data Efficient and Feasible Level Set Method for Stochastic Convex Optimization with Expectation Constraints
复制标题
DOI：
10.2139/ssrn.3433280
复制
发表时间：
2019-08
期刊：
影响因子：
--
通讯作者：
Qihang Lin;Selvaprabu Nadarajah;Negar Soheili;Tianbao Yang
中科院分区：
文献类型：
--
作者：
Qihang Lin;Selvaprabu Nadarajah;Negar Soheili;Tianbao Yang
带期望约束的随机凸优化问题(SOEC)在统计学、机器学习、商业和工程中经常遇到。在数据丰富的环境中，SOEC目标和约束包含针对大型数据集定义的预期。因此，求解此类SOEC的高效算法需要限制它们使用的数据点的比例，我们称之为算法数据复杂性。最近的随机一阶方法在处理SOEC时表现出较低的数据复杂度，但仅在收敛时才保证近可行性和近最优性。因此，当启发式终止时，这些方法可能返回高度不可行的解，这是经常发生的情况，因为理论收敛标准是高度保守的。这个问题限制了一阶方法在SOEC约束编码实现要求的几个应用中的使用。针对SOEC，我们设计了一种数据复杂度较低、强调收敛前的可行性的随机可行水平集方法。具体地说，我们的水平集方法通过调用一个新的一阶预言来解决寻根问题，该一阶预言通过扩展镜像下降和在线验证技术来计算水平集函数的随机上界。与现有的确定性可行水平集方法和随机次梯度方法相比，SFLS算法在每一次寻根迭代中都保持一个高概率可行解，并且表现出良好的迭代复杂度。在三个不同应用上的数值实验验证了SFLS相对于前一种方法的低数据复杂度，并突出了SFLS如何以较小的最优差距找到可行解的速度显着快于后一种方法。
Stochastic convex optimization problems with expectation constraints (SOECs) are encountered in statistics and machine learning, business, and engineering. In data-rich environments, the SOEC objective and constraints contain expectations defined with respect to large datasets. Therefore, efficient algorithms for solving such SOECs need to limit the fraction of data points that they use, which we refer to as algorithmic data complexity. Recent stochastic first order methods exhibit low data complexity when handling SOECs but guarantee near-feasibility and near-optimality only at convergence. These methods may thus return highly infeasible solutions when heuristically terminated, as is often the case, due to theoretical convergence criteria being highly conservative. This issue limits the use of first order methods in several applications where the SOEC constraints encode implementation requirements. We design a stochastic feasible level set method (SFLS) for SOECs that has low data complexity and emphasizes feasibility before convergence. Specifically, our level-set method solves a root-finding problem by calling a novel first order oracle that computes a stochastic upper bound on the level-set function by extending mirror descent and online validation techniques. We establish that SFLS maintains a high-probability feasible solution at each root-finding iteration and exhibits favorable iteration complexity compared to state-of-the-art deterministic feasible level set and stochastic subgradient methods. Numerical experiments on three diverse applications validate the low data complexity of SFLS relative to the former approach and highlight how SFLS finds feasible solutions with small optimality gaps significantly faster than the latter method.