Fast Algorithms for Online Stochastic Convex Programming

          @misc{ scivideos_22746,
            doi = {},
            url = {https://old.simons.berkeley.edu/talks/fast-algorithms-online-stochastic-convex-programming},
            author = {},
            keywords = {},
            language = {en},
            title = {Fast Algorithms for Online Stochastic Convex Programming},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2022},
            month = {oct},
            note = {22746 see, \url{https://scivideos.org/simons-institute/22746}}
          }
          

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 the Adwords problem, 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 of 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.