Metraipolis › archive › dc_255d01dbc48c

Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving — arXiv:2609.28263

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.28263
License (as archived)
CC0-1.0
Archived
2026-10-08T10:57:39.845Z
SHA-256 of the archived text
55e5c55f2bf47d34b8d352bfb962dc04bb4286f24be12c3410417287331d4799
Stable URL of this page
https://metraipolis.com/documento/dc_255d01dbc48c

How to cite

Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving — arXiv:2609.28263 — arXiv (en), https://arxiv.org/abs/2609.28263 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_255d01dbc48c (Metraipolis archive dc_255d01dbc48c, sha256 55e5c55f2bf47d34b8d352bfb962dc04bb4286f24be12c3410417287331d4799)
BibTeX
@misc{dc255d01dbc48c,
  title = {Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving — arXiv:2609.28263},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.28263},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_255d01dbc48c; sha256 55e5c55f2bf47d34b8d352bfb962dc04bb4286f24be12c3410417287331d4799},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.28263. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-24 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG) ; Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.28263 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T10:06:16.779Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-24?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).