Fast algorithms for online stochastic convex programming
From MaRDI portal
Publication:5363008
DOI10.1137/1.9781611973730.93zbMATH Open1371.90091arXiv1410.7596OpenAlexW2951097138MaRDI QIDQ5363008FDOQ5363008
Shipra Agrawal, Nikhil R. Devanur
Publication date: 5 October 2017
Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1410.7596
Recommendations
Convex programming (90C25) Online algorithms; streaming algorithms (68W27) Stochastic programming (90C15)
Cited In (25)
- Online Semidefinite Programming.
- Scalable and Jointly Differentially Private Packing
- Fast and strong convergence of online learning algorithms
- Simple and fast algorithm for binary integer and online linear programming
- Approximation algorithms for stochastic combinatorial optimization problems
- Attenuate locally, win globally: attenuation-based frameworks for online stochastic matching with timeouts
- Tractable Equilibria in Sponsored Search with Endogenous Budgets
- Bandits with Global Convex Constraints and Objective
- Online allocation and display ads optimization with surplus supply
- Competitive online algorithms for resource allocation over the positive semidefinite cone
- Title not available (Why is that?)
- Welfare maximization with production costs: a primal dual approach
- Introduction to Online Convex Optimization
- Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds
- Configuration balancing for stochastic requests
- Autobidding with constraints
- Social welfare and profit maximization from revealed preferences
- An online convex optimization-based framework for convex bilevel optimization
- How the experts algorithm can help solve LPs online
- Primal Beats Dual on Online Packing LPs in the Random-Order Model
- Interior-Point-Based Online Stochastic Bin Packing
- Fair Resource Allocation in a Volatile Marketplace
- A truthful near-optimal mechanism for online linear packing-covering problem in the random order model
- Exploiting problem structure in optimization under uncertainty via online convex optimization
- Online Convex Optimization With Binary Constraints
This page was built for publication: Fast algorithms for online stochastic convex programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363008)
