# Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving

arXiv: https://arxiv.org/abs/2609.28263 · HTML: https://mlsanity.com/paper/2609.28263/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 22 references that are in the map.
- First posted on arXiv 23 Sep 2026.

## Builds on (most cited first, 13 of 13)

- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2002.10421/) (2020)
- [Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds](https://mlsanity.com/paper/1909.05499/) (2019)
- [Simple and Fast Algorithm for Binary Integer and Online Linear Programming](https://mlsanity.com/paper/2003.02513/) (2020)
- [A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management](https://mlsanity.com/paper/1802.06192/) (2018)
- [An Improved Analysis of LP-based Control for Revenue Management](https://mlsanity.com/paper/2101.11092/) (2021)
- [Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions](https://mlsanity.com/paper/2210.07996/) (2022)
- [Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations](https://mlsanity.com/paper/1912.08917/) (2019)
- [Optimal Regularized Online Allocation by Adaptive Re-Solving](https://mlsanity.com/paper/2209.00399/) (2022)
- [Infrequent Resolving Algorithm for Online Linear Programming](https://mlsanity.com/paper/2408.00465/) (2024)
- [Beyond O(√T) Regret: Decoupling Learning and Decision-making in Online Linear Programming](https://mlsanity.com/paper/2501.02761/) (2025)
- [Beyond Non-Degeneracy: Revisiting Certainty Equivalent Heuristic for Online Linear Programming](https://mlsanity.com/paper/2501.01716/) (2025)
- [Online Linear Programming with Replenishment](https://mlsanity.com/paper/2601.14629/) (2026)

## Abstract (arXiv)

The growth of large language model (LLM) inference and search services increases the scale of online linear programming problems, motivating computationally efficient algorithms. We develop resource-adaptive stochastic gradient descent (RASGD) for stochastic online linear programming. The algorithm uses one request and current inventory to update resource prices, requiring O(m) operations for m resources and memory per arrival and no LP or sample-average optimization. The central idea is to express the current-resource pricing logic of re-solving through a first-order SGD update: each arrival refreshes the remaining-inventory allowance in the dual objective, while the stepsize decreases for early learning and increases later to match the speed of inventory adjustment. Under standard non-degeneracy conditions, our algorithm is feasible on every sample path and achieves O(log T) expected regret against the realized fractional hindsight optimum, which matches the lower bound, even for policies that know the distribution and have unrestricted computation. The analysis converts curvature around the fixed reference price into inventory stability without tracking optimal prices at changing resource levels. Numerical experiments show that RASGD achieves regret competitive with per-arrival LP re-solving and improves upon the tested first-order baselines, while retaining the computational efficiency of first-order methods. These results establish RASGD as a computationally efficient approach to achieving high allocation quality in large-scale OLP.