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

📄 arXiv: 2609.28263v1 📥 PDF

作者: Jiameng Lyu

分类: cs.LG, math.OC

发布日期: 2026-09-23

💡 一句话要点

提出资源自适应随机梯度下降以解决在线线性规划问题

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 在线线性规划 随机梯度下降 资源分配 动态定价 计算效率

📋 核心要点

  1. 现有的在线线性规划方法在处理大规模问题时计算效率低，难以满足实时需求。
  2. 论文提出的RASGD算法通过一次请求更新资源价格，避免了重新求解的复杂性，提升了计算效率。
  3. 实验结果显示，RASGD在遗憾值上与每次到达的线性规划重新求解相当，并优于现有的一阶基线方法。

📝 摘要（中文）

随着大型语言模型推理和搜索服务的增长，在线线性规划问题的规模不断扩大，亟需高效的计算算法。本文提出了一种资源自适应随机梯度下降（RASGD）算法，用于随机在线线性规划。该算法通过一次请求和当前库存更新资源价格，操作复杂度为O(m)，无需重新求解线性规划或样本平均优化。核心思想是通过一阶SGD更新表达重新求解的当前资源定价逻辑，确保算法在每个样本路径上可行，并在标准非退化条件下实现O(log T)的期望遗憾，匹配下界。实验结果表明，RASGD在计算效率上优于传统方法，同时在分配质量上表现出色。

🔬 方法详解

问题定义：本文旨在解决在线线性规划中的计算效率问题，现有方法在面对大规模问题时往往需要频繁重新求解，导致计算开销过大。

核心思路：RASGD算法通过一次请求和当前库存更新资源价格，利用一阶随机梯度下降的思想，避免了复杂的线性规划求解过程。每次到达时更新剩余库存的双重目标，同时调整步长以适应库存变化的速度。

技术框架：该算法的整体流程包括请求处理、资源价格更新和库存调整三个主要模块。首先接收请求，然后根据当前库存和资源价格进行更新，最后调整步长以优化学习过程。

关键创新：RASGD的主要创新在于将资源定价逻辑与一阶SGD更新结合，避免了对最优价格的跟踪，提升了算法的计算效率和适应性。

关键设计：算法在设计上采用了O(m)的操作复杂度，步长设计上初期减小以加快学习，后期增大以匹配库存调整速度，确保在标准非退化条件下的可行性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，RASGD在遗憾值上与每次到达的线性规划重新求解相当，且在多个测试基线中表现出更优的性能。具体而言，RASGD在计算效率上显著提升，遗憾值达到O(log T)，与已知分布的策略相匹配，展现出强大的竞争力。

🎯 应用场景

该研究的潜在应用领域包括在线资源分配、动态定价和实时优化等场景，尤其适用于需要快速响应和高效计算的大规模系统。未来，RASGD有望在智能调度、云计算资源管理等领域发挥重要作用，推动相关技术的发展。

📄 摘要（原文）

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.