@inproceedings{agrawal2015fast, author = {Agrawal, Shipra and Devanur, Nikhil}, title = {Fast algorithms for online stochastic convex programming}, booktitle = {SODA 2015 (ACM-SIAM Symposium on Discrete Algorithms)}, year = {2015}, month = {January}, abstract = {We introduce the online stochastic Convex Programming (CP) problem, a very general version of stochastic online problems which allows arbitrary concave objectives and convex feasibility constraints. Many well-studied problems like online stochastic packing and covering, online stochastic matching with concave returns, etc. form a special case of online stochastic CP. We present fast algorithms for these problems, which achieve near-optimal regret guarantees for both the i.i.d. and the random permutation models of stochastic inputs. When applied to the special case online packing, our ideas yield a simpler and faster primal-dual algorithm for this well studied problem, which achieves the optimal competitive ratio. Our techniques make explicit the connection of primal-dual paradigm and online learning to online stochastic CP.}, publisher = {SIAM - Society for Industrial and Applied Mathematics}, url = {http://approjects.co.za/?big=en-us/research/publication/fast-algorithms-for-online-stochastic-convex-programming/}, edition = {SODA 2015 (ACM-SIAM Symposium on Discrete Algorithms)}, }