Fast Algorithms for Online Stochastic Convex Programming

Channel:
Microsoft Research
Subscribers:
342,000
Published on ● Video Link: https://www.youtube.com/watch?v=UFkYdVWXSok


Duration: 1:05:14
421 views
2

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



Other Videos By Microsoft Research


2016-06-21Energy-efficient Scheduling in the Non-clairvoyant Model
2016-06-21F# Type Providers: DBpedia and the Combinator Framework
2016-06-21Arithmetic Circuit Complexity
2016-06-21Approximating ATSP by Relaxing Connectivity
2016-06-21Programming languages and biology
2016-06-21Deep clustering: discriminative embeddings for source separation
2016-06-21Social Computing Symposium 2015: Muse: The Brain Sensing Headband
2016-06-21Advances in Quantum Algorithms and Devices: Welcome and Distributed Denstity Matrices
2016-06-21Circle Packing and Its Applications
2016-06-21Advances in Quantum Algorithms & Devices: Quantum Monte Carlo versus Quantum Adiabatic Optimization
2016-06-21Fast Algorithms for Online Stochastic Convex Programming
2016-06-21Research on Concert Hall Acoustics at Aalto University
2016-06-21Fixed-Energy Harmonic Functions
2016-06-21RDFox — A Modern Materialisation-Based RDF System
2016-06-21Competitive erosion is conformally invariant
2016-06-21A Simple O(loglog(rank))-Competitive Algorithm for the Matroid Secretary Problem
2016-06-21Recent Advances in Deep Learning at Microsoft: A Selected Overview
2016-06-21The Interplay of Social Influence and Own Preference in Social Networks
2016-06-21A Fast Distributed Algorithm for α-Fair Packing Problems
2016-06-21Theory Day Session 3
2016-06-21Provable Submodular Minimization via Wolfe’s Algorithm


Tags:
microsoft research
algorithms