Abstract

We consider the constrained optimization where the objective function and the constraints are de fined as summation of finitely many loss function This model has applications in machine learning such as Neyman-Pearson classification. We consider two level-set methods to solve this class of problems, an existing inexact Newton method and a feasible level-set method. To update the level parameter towards the optimality, both meth ods require an oracle that generates upper and lower bounds as well as an affine-minorant of the level function. To construct the desired oracle, reformulate the level function as the value of a saddle-point problem using the conjugate and perspective of the loss functions. Then a stochastic variance-reduced gradient method with a special Bregman divergence is proposed as the oracle for solving that saddle-point problem. The special divergence ensures the proximal mapping in each iteration can be solved in a closed form. The tot complexity of both level-set methods using the proposed oracle are analyzed.