mlsanityData to 14 Oct 2026

Fast Algorithms for Online Stochastic Convex Programming

arXiv 1410.7596 ↗First posted 28 Oct 2014cs.LG cs.DS math.OCcited by 36

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 36 papers in the map (data through 14 Oct 2026). First posted on arXiv 28 Oct 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 5; 2022: 12; 2023: 7; 2024: 2; 2025: 8; 2026: 2.

36 papers.

Sort:

By area:

  1. 2021Reward is enough for convex MDPscited by 84
  2. 2022Online Bidding Algorithms for Return-on-Spend Constrained Advertiserscited by 17
  3. 2024Towards Better Statistical Understanding of Watermarking LLMscited by 16
  4. 2022Online Contextual Decision-Making with a Smart Predict-then-Optimize Methodcited by 12
  5. 2022Optimal Contextual Bandits with Knapsacks under Realizability via Regression Oraclescited by 12
  6. 2022Online Resource Allocation under Horizon Uncertaintycited by 9
  7. 2022Optimal Regularized Online Allocation by Adaptive Re-Solvingcited by 8
  8. 2025Revisiting Projection-Free Online Learning with Time-Varying Constraintscited by 5
  9. 2025No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!cited by 5
  10. 2023Robust Budget Pacing with a Single Samplecited by 4
  11. 2025Single-Sample and Robust Online Resource Allocationcited by 3
  12. 2021Improved Regret Bounds for Online Submodular Maximizationcited by 2
24 more
  1. 2022Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancementscited by 2
  2. 2022Dynamic Budget Throttling in Repeated Second-Price Auctionscited by 2
  3. 2023Improved Algorithms for Multi-period Multi-class Packing Problems with Bandit Feedbackcited by 2
  4. 2023Trading-off price for data quality to achieve fair online allocationcited by 2
  5. 2025Online Bidding under RoS Constraints without Knowing the Valuecited by 2
  6. 2026Cross-Epoch Adaptive Rollout Optimization for RL Post-Trainingcited by 2
  7. 2021Robust Allocations with Diversity Constraintscited by 1
  8. 2022Online Allocation and Learning in the Presence of Strategic Agentscited by 1
  9. 2022Learning-Assisted Algorithm Unrolling for Online Optimization with Budget Constraintscited by 1
  10. 2023Online Learning for Equilibrium Pricing in Markets under Incomplete Informationcited by 1
  11. 2023Online Resource Allocation in Episodic Markov Decision Processescited by 1
  12. 2024Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictionscited by 1
  13. 2025Online Learning for Approximately-Convex Functions with Long-term Adversarial Constraintscited by 1
  14. 2025A Theoretical Framework for Auxiliary-Loss-Free Load Balancing of Sparse Mixture-of-Experts in Large-Scale AI Modelscited by 1
  15. 2021Optimization-friendly generic mechanisms without moneycited by 0
  16. 2021A General Traffic Shaping Protocol in E-Commercecited by 0
  17. 2022Online Regenerative Learningcited by 0
  18. 2022Optimal Efficiency-Envy Trade-Off via Optimal Transportcited by 0
  19. 2022Stochastic Direct Search Method for Blind Resource Allocationcited by 0
  20. 2023Constrained Online Two-stage Stochastic Optimization: Near Optimal Algorithms via Adversarial Learningcited by 0
  21. 2023Near-Optimal Experimental Design Under the Budget Constraint in Online Platformscited by 0
  22. 2025Online Bidding Algorithms with Strict Return on Spend (ROS) Constraintcited by 0
  23. 2025Fairness-Regularized Online Optimization with Switching Costscited by 0
  24. 2026Fair Online Resource Allocationcited by 0