Resource-adaptive gradient method improves online allocation efficiency
Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving
Machine Learning
Summary
Managing resources efficiently in real-time is challenging when problems grow very large. The authors created an algorithm called RASGD that updates resource prices quickly using simple calculations without solving complex problems each time. It adjusts how much it learns over time to balance new information and inventory changes. Their method is both practical and mathematically reliable, performing nearly as well as methods that use more computing power. This can help large services handle requests faster while managing resources well.
What this means in practice
- •For cloud service operators: Optimize resource allocation in large-scale online request handling without heavy computation overhead each time a request arrives.
- •For network schedulers: Improve dynamic bandwidth or resource pricing by adapting quickly to demand changes using computationally lightweight updates.
Authors
Jiameng Lyu
Abstract
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.