论文标题
保守的随机优化和期望约束
Conservative Stochastic Optimization with Expectation Constraints
论文作者
论文摘要
本文考虑了随机凸优化问题，其中目的和约束函数还涉及对数据指数或环境变量的期望，此外还有对变量域的确定性凸约限制。尽管该设置是通用的，并且在不同的机器学习应用中产生，但是在线和有效解决此类问题的方法尚未得到广泛研究。由于基础数据分布尚不清楚，因此通常无法使用封闭形式的解决方案，并且不适用经典的确定性优化范例。最新的方法，例如使用鞍点框架的方法，可以确保最佳差距以及约束违规衰减为$Ø\ left（t^{ - \ frac {1} {2} {2}}} \ right）$，其中$ t $是$ t $，其中$ t $是随机梯度的数量。在每次迭代时，都假定域约束简单并通过投影处理。在这项工作中，我们提出了一种新颖的保守随机优化算法（CSOA），该算法（CSOA）实现零约束违规和$Ø\ left（t^{ - \ frac {1} {2} {2}}}} \ right）$ optimation $ optimation $。 此外，可以通过考虑该算法的条件梯度或Frank-Wolfe（FW）变体，可以避免提出算法中的投影操作（计算投影很昂贵）。 $ t $迭代后，最新的随机FW变体达到了$Ø\ left的最佳差距（t^{ - \ frac {1} {3}} \ right）$，尽管这些算法尚未应用于具有功能期望约束的问题。在这项工作中，我们提出了FW-CSOA算法，该算法不仅不含投影，而且还可以使用$Ø\ left（t^{ - \ frac {1} {1} {4}}} \ right）违反零约束。在两个相关问题上测试了所提出算法的功效：公平分类和结构化矩阵完成。
This paper considers stochastic convex optimization problems where the objective and constraint functions involve expectations with respect to the data indices or environmental variables, in addition to deterministic convex constraints on the domain of the variables. Although the setting is generic and arises in different machine learning applications, online and efficient approaches for solving such problems have not been widely studied. Since the underlying data distribution is unknown a priori, a closed-form solution is generally not available, and classical deterministic optimization paradigms are not applicable. State-of-the-art approaches, such as those using the saddle point framework, can ensure that the optimality gap as well as the constraint violation decay as $Ø\left(T^{-\frac{1}{2}}\right)$ where $T$ is the number of stochastic gradients. The domain constraints are assumed simple and handled via projection at every iteration. In this work, we propose a novel conservative stochastic optimization algorithm (CSOA) that achieves zero constraint violation and $Ø\left(T^{-\frac{1}{2}}\right)$ optimality gap. Further, the projection operation (for scenarios when calculating projection is expensive) in the proposed algorithm can be avoided by considering the conditional gradient or Frank-Wolfe (FW) variant of the algorithm. The state-of-the-art stochastic FW variants achieve an optimality gap of $Ø\left(T^{-\frac{1}{3}}\right)$ after $T$ iterations, though these algorithms have not been applied to problems with functional expectation constraints. In this work, we propose the FW-CSOA algorithm that is not only projection-free but also achieves zero constraint violation with $Ø\left(T^{-\frac{1}{4}}\right)$ decay of the optimality gap. The efficacy of the proposed algorithms is tested on two relevant problems: fair classification and structured matrix completion.
