Fast algorithms for online stochastic convex programming

DOI10.1137/1.9781611973730.93zbMATH Open1371.90091OpenAlexW2951097138MaRDI QIDQ5363008FDOQ5363008

Authors 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)

Full work available at URL https://arxiv.org/abs/1410.7596

Mathematics Subject Classification ID

Convex programming (90C25) Online algorithms; streaming algorithms (68W27) Stochastic programming (90C15)

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.

Recommendations

• Near optimal online algorithms and fast approximation algorithms for resource allocation problems
• Online primal-dual algorithms for covering and packing
• Simple and fast algorithm for binary integer and online linear programming
• Algorithms – ESA 2005

Cited in

(24)

• Interior-point-based online stochastic bin packing
• Online allocation and display ads optimization with surplus supply
• Welfare maximization with production costs: a primal dual approach
• Autobidding with constraints
• Maximizing profit with convex costs in the random-order model
• A truthful near-optimal mechanism for online linear packing-covering problem in the random order model
• Attenuate locally, win globally: attenuation-based frameworks for online stochastic matching with timeouts
• Online Convex Optimization With Binary Constraints
• Competitive online algorithms for resource allocation over the positive semidefinite cone
• Fair resource allocation in a volatile marketplace
• Online Semidefinite Programming.
• Simple and fast algorithm for binary integer and online linear programming
• Introduction to Online Convex Optimization
• Configuration balancing for stochastic requests
• Tractable equilibria in sponsored search with endogenous budgets
• Social welfare and profit maximization from revealed preferences
• Primal beats dual on online packing LPs in the random-order model
• Exploiting problem structure in optimization under uncertainty via online convex optimization
• Bandits with global convex constraints and objective
• Approximation algorithms for stochastic combinatorial optimization problems
• An online convex optimization-based framework for convex bilevel optimization
• Fast and strong convergence of online learning algorithms
• Scalable and Jointly Differentially Private Packing
• Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds

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)