Fast Algorithms for Online Stochastic Convex Programming

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

Series:: Microsoft Research Talks
Date:: February 25, 2015
Speakers:: Nikhil Devanur
Affiliation:: Microsoft Research (Redmond)

- Jeff Running

Series: Microsoft Research Talks

Scalable and Efficient AI: From Supercomputers to Smartphones
June 29, 2023
Speakers:

Torsten Hoefler
Human-Centered AI: Ensuring Human Control While Increasing Automation
May 3, 2023
WiDS Career Panel: Gabriela de Queiroz, Juliet Hougland, & Samantha Sifleet
April 5, 2023
Speakers:

Gabriela de Queiroz,

Juliet Hougland,

Samantha Silfleet
Galea: The Bridge Between Mixed Reality and Neurotechnology
February 13, 2023
Speakers:

Eva Esteban,

Conor Russomanno
Current and Future Application of BCIs
February 1, 2023
Speakers:

Christoph Guger
Challenges in Evolving a Successful Database Product (SQL Server) to a Cloud Service (SQL Azure)
October 27, 2022
Speakers:

Hanuma Kodavalla,

Phil Bernstein
Improving text prediction accuracy using neurophysiology
September 30, 2022
Speakers:

Sophia Mehdizadeh
Tongue-Gesture Recognition in Head-Mounted Displays
August 11, 2022
Speakers:

Tan Gemicioglu
DIABLo: a Deep Individual-Agnostic Binaural Localizer
August 12, 2021
Speakers:

Shoken Kaneko
A Tale of Two Cities: Software Developers in Practice During the COVID-19 Pandemic
February 26, 2021
Speakers:

Denae Ford Robinson
Recent Efforts Towards Efficient And Scalable Neural Waveform Coding
September 29, 2020
Speakers:

Kai Zhen
Geometry-constrained Beamforming Network for end-to-end Farfield Sound Source Separation
September 24, 2020
Speakers:

Ali Aroudi
Audio-based Toxic Language Detection
August 13, 2020
Speakers:

Midia Yousefi
What Kind of Computation is Human Cognition? A Brief History of Thought (Episode 2/2)
August 4, 2020
Speakers:

Paul Smolensky,

Sean Andrist
From SqueezeNet to SqueezeBERT: Developing Efficient Deep Neural Networks
July 29, 2020
Speakers:

Sujeeth Bharadwaj
Hope Speech and Help Speech: Surfacing Positivity Amidst Hate
July 29, 2020
Speakers:

Monojit Choudhury
What Kind of Computation is Human Cognition? A Brief History of Thought (Episode 1/2)
July 28, 2020
Speakers:

Paul Smolensky,

Sean Andrist
An Ethical Crisis in Computing?
March 3, 2020
Speakers:

Emre Kiciman,

Eric Horvitz
Towards Mainstream Brain-Computer Interfaces (BCIs)
February 27, 2020
Speakers:

Hannes Gamper
Underestimating the challenge of cognitive disabilities (and digital literacy). Directions to explore for current, next, and next-next generation UIs
November 25, 2019
Speakers:

Gregg Vanderheiden
'F' to 'A' on the N.Y. Regents Science Exams: An Overview of the Aristo Project
November 18, 2019
Speakers:

Peter Clark
Checkpointing the Un-checkpointable: the Split-Process Approach for MPI and Formal Verification
November 15, 2019
Speakers:

Gene Cooperman
Learning Structured Models for Safe Robot Control
September 27, 2019
Speakers:

Ashish Kapoor
Non-linear Invariants for Control-Command Systems
September 6, 2019
Speakers:

Tahina Ramananandro
Distributed Entity Resolution for Computational Social Science
September 6, 2019
Speakers:

Vivek Narasayya