Stochastic Convex Optimization with Multiple Objectives
Mehrdad Mahdavi, Tianbao Yang, Rong Jin · 2013
In this paper, we are interested in the development of efficient algorithms for con-vex optimization problems in the simultaneous presence of multiple objectives and stochasticity in the first-order information. We cast the stochastic multi-ple objective optimization problem into a constrained optimization problem by choosing one function as the objective and try to bound other objectives by appro-priate thresholds. We first examine a two stages exploration-exploitation based algorithm which first approximates the stochastic objectives by sampling and then solves a constrained stochastic optimization problem by projected gradient method. This method attains a suboptimal convergence rate even under strong assumption on the objectives. Our second approach is an efficient primal-dual stochastic algorithm. It leverages on the theory of Lagrangian method in con-strained optimization and attains the optimal convergence rate of O(1= p T) in high probability for general Lipschitz continuous objectives.