Oral
Level-Set Methods for Finite-Sum Constrained Convex Optimization
Qihang Lin · Runchao Ma · Tianbao Yang

Fri Jul 13th 04:20 -- 04:30 PM @ A9

We consider the constrained optimization where the objective function and the constraints are defined as summation of finitely many loss functions. 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 new feasible level-set method. To update the level parameter towards the optimality, both methods require an oracle that generates upper and lower bounds as well as an affine-minorant of the level function. To construct the desired oracle, we 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 total complexity of both level-set methods using the proposed oracle are analyzed.

Author Information

Qihang Lin (Univ Iowa)
Runchao Ma (University of Iowa)
Tianbao Yang (The University of Iowa)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors