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

Jiameng Lyu

cs.LGSep 23, 2026

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

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.

Explore similar work

Aug 1, 2024cs.DS

Infrequent Resolving Algorithm for Online Linear Programming

Online linear programming (OLP) has gained significant attention from both researchers and practitioners due to its extensive applications such as online auctions, network revenue management, order fulfillment and advertising. Existing OLP algorithms fall into two categories: LP-based algorithms and LP-free algorithms. The former typically guarantees better performance but requires solving a large number of LPs, which could be computationally expensive. In contrast, LP-free algorithms only require first-order computations but induce a worse performance. In this work, we bridge the gap between these two extremes by proposing a well-performing algorithm that solves LPs at a few selected time points and conducts first-order computations at other time points. Specifically, for the case where the inputs are drawn from an unknown finite-support distribution, the proposed algorithm achieves a constant regret (even for the hard "degenerate" case) while solving LPs only

O(\log\log T)

times over the time horizon

T

. Moreover, when we are allowed to solve LPs only

M

times, we design the corresponding schedule such that the proposed algorithm can guarantee a nearly

O\left(T^{(1/2)^{M-1}}\right)

regret. Our work highlights the value of resolving both at the beginning and the end of the selling horizon, and provides a novel framework to prove the performance guarantee of the proposed policy under different infrequent resolving schedules. Numerical experiments are conducted to demonstrate the efficiency of the proposed algorithms.

Guokai Li, Zizhuo Wang, Jingwei Zhang

Learning-Augmented Algorithms O(T^Β)$ Simultaneous Regret Mixed-Integer Programming

Ask PDF

Jul 4, 2026cs.AI

Online Linear Programming for Multi-Objective Routing in LLM Serving

We study the online routing problem in large language model serving, where requests arrive sequentially and must be dispatched to parallel decode workers under tight batch-size and KV-cache constraints. Unlike widely used routing heuristics that are not tied to explicit service-level objectives (SLOs) and offer limited control over latency-throughput trade-offs, we introduce a multi-objective optimization framework that formulates routing as an online linear programming with interpretable decision rewards. We apply an efficient bid-price control policy based on the online linear programming that admits requests when their SLO-weighted benefit exceeds their shadow prices. To meet millisecond decision requirements, we develop a warm-started, projected first-order updates that track the evolving dual shadow prices online with predictable runtime. We integrate our router into the Vidur simulator and demonstrate substantial improvements over standard baselines across multiple SLO regimes, including end-to-end latency, time-to-first-token, throughput, and tail performance. A big picture from our result: a science-based approach outperforms others based on heuristics.

Zixi Chen, Yinyu Ye, Zijie Zhou

Large Language Model Routing Large Language Model Serving Mixed-Integer Programming Learning-Augmented Algorithms Trade-Off Prices

Ask PDF

Sep 9, 2026cs.LG

Online Inverse Integer Linear Optimization via Small-Gradient Skipping: Constant Regret and Finite Mistakes

In online inverse linear optimization, the learner predicts a weight at each round, observes the optimal action of the agent, and updates its prediction. In the general setting, the gap of

\log T

between the regret upper bound

O(d \log T)

and the lower bound

Ω(d)

is unresolved (here

T

is the total number of rounds and

d

is the dimension). When the action set is M-convex, the regret is known to be bounded by

O(d \log d)

, but the method attaining it computes a center of gravity at every round. This paper therefore proposes Small-Gradient Skipping (SGS), a mechanism that skips the update at rounds without a mistake in the case where the correct action is uniformly separated from the other candidates, and applies it to online gradient descent, the online Newton step, and MetaGrad. The number of mistakes is then bounded, for all three, by a quantity independent of

T

; and for the online Newton step and for MetaGrad with SGS, the dimension dependence of the regret becomes

O(d^2)

when the forward problem is an integer linear program, that is, the factor

\log T

is removed. Moreover, when the action set is M-convex, the regret is bounded efficiently without computing a center of gravity.

Akira Kitaoka

Near-Optimal Regret Guarantees Mixed-Integer Programming Convex Sets Newton Skip Optimal Actions

Ask PDF