Stochastic Convex Optimization with Multiple Objectives
In this paper, we are interested in the development of efficient algorithms for convex optimization problems in the simultaneous presence of multiple objectives and stochasticity in the first-order information. We cast the stochastic multiple objective optimization problem into a constrained optimization problem by choosing one function as the objective and try to bound other objectives by appropriate 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 constrained optimization and attains the optimal convergence rate of O(1/ √ T ) in high probability for general Lipschitz continuous objectives.
This paper presents an algorithm for multiple 
      objectives stochastic convex optimization. The issue with multiple 
      objectives is handled by choosing one objective to minimize and by 
      constraining all the others via lower bounds. The stochastic sampling 
      is addressed by averaging the costs on the available samples. The 
      proposed algorithm is then a primal-dual projected gradient descent. 
      The authors show also that 2 naive implementations yield a worse 
      solution error bound than the primal-dual approach. Quality 
      -- The paper seems technically sound. I have checked several steps 
      but not all. The main serious shortcoming is that there are no 
      experiments at all to support any of the claims made in the paper. 
      Overall, this seems an unfinished paper. Although this is mostly a 
      theoretical paper, I'd recommend to add experiments to show advantages 
      and limitations of the proposed strategy (transfer m objectives to 
      constraints). For example, how does one choose the bounds for each 
      objective function? What is the best way to pick the objective to be 
      minimized? Can one draw any connection of Pareto optimal solutions? 
      Clarity -- Overall the paper is clear. The authors 
      should also show some illustrations together with the theory. 
      Typos/unclear line 183: what is \hat f_i ? line 215: to fail 
      for -> fail for Originality -- The originality of 
      this work is difficult to assess. It seems that Algorithm 1 and the 
      formal proofs are new, but I am not an expert in the field and 
      relevant literature could have escaped me. The idea of moving all but 
      one objectives to the set of constraints seems quite simple and 
      with several limitations. Significance -- The use of 
      multiple objectives as well as stochastic sampling is present in a few 
      applications (some shown at the end of the Introduction) and worthy of 
      attention. However, the resulting algorithm is quite a straightforward 
      idea, and has some limitations (optimization is with respect to only 
      one objective function) that are not fully examined in the paper. 
      The full significance of the algorithm is not demonstrated with 
      experiments either. The main contribution then is left to the 
      proof of the error bounds (Theorems 1 and 2).