Fast Algorithms for Online Stochastic Convex Programming

  • Nikhil Devanur | Microsoft Research (Redmond)

We introduce the Online Stochastic Convex Programming (CP) problem, a very general version of stochastic online problems which allows arbitrary convex objectives and feasibility constraints. This problem generalizes the well-studied online stochastic packing problem. We present fast algorithms for these problems, which achieve near-optimal guarantees for the i.i.d. and the random permutation models of stochastic inputs. When applied to the special case of online packing, our ideas yield a simpler and faster primal-dual algorithm which achieves the optimal competitive ratio. We make explicit the connection between the primal-dual paradigm, online learning algorithms and the online stochastic packing problem.

Joint work with Shipra Agrawal

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks