Nonconvex constrained optimization problems can be used to model a number of machine learning problems, such as multi-class Neyman-Pearson classification and constrained Markov decision processes. However, such kinds of problems are challenging because both the objective and constraints are possibly nonconvex, so it is difficult to balance the reduction of the loss value and reduction of constraint violation. Although there are a few methods that solve this class of problems, all of them are double-loop or triple-loop algorithms, and they require oracles to solve some subproblems up to certain accuracy by tuning multiple hyperparameters at each iteration. In this paper, we propose a novel gradient descent and perturbed ascent (GDPA) algorithm to solve a class of smooth nonconvex inequality constrained problems. The GDPA is a primal-dual algorithm, which only exploits the first-order information of both the objective and constraint functions to update the primal and dual variables in an alternating way. The key feature of the proposed algorithm is that it is a single-loop algorithm, where only two step-sizes need to be tuned. We show that under a mild regularity condition GDPA is able to find Karush-Kuhn-Tucker (KKT) points of nonconvex functional constrained problems with convergence rate guarantees. To the best of our knowledge, it is the first single-loop algorithm that can solve the general nonconvex smooth problems with nonconvex inequality constraints. Numerical results also showcase the superiority of GDPA compared with the best-known algorithms (in terms of both stationarity measure and feasibility of the obtained solutions).
翻译:非convex 限制优化问题可以用来模拟一些机器学习问题,例如多级 Neyman-Pearson 分类和限制 Markov 决策程序。 但是,这类问题具有挑战性,因为目标和限制都可能是非convex,所以很难平衡损失价值的减少和限制违规现象的减少。虽然有一些方法可以解决这类问题,但所有这些方法都是双环或三环算法,它们都要求有孔径解,以便通过在每次循环中调整多个超参数来精确地解决某些小问题。在本文件中,我们提出一个新的梯度下移和半弯曲调算法(GDPA ), 以解决平滑的非convex 不平等问题。 GDPA 是一种原始的算法, 它只能利用目标和制约功能函数的一阶信息, 以交替方式更新原始和双重变量。 拟议的算法的关键特征是它是一个单行算算法, 只有两个步序运算法的计算方法, 才能与GDP的两步段级级算法相比。 我们显示一个正常的卡- 水平的算法, 它在正常的状态下, 需要一种正常的状态下, 。