Online Semi-infinite Linear Programming: Efficient Algorithms via Function Approximation

Yiming Zong; Jiashuo Jiang

cs.LGMar 17, 2026

Online Semi-infinite Linear Programming: Efficient Algorithms via Function Approximation

Authors: Yiming Zong, Jiashuo Jiang

Organizations: Department of Industrial Engineering & Decision Analytics, Hong Kong University of Science and Technology

Abstract

We consider the dynamic resource allocation problem where the decision space is finite-dimensional, yet the solution must satisfy a large or even infinite number of constraints revealed via streaming data or oracle feedback. We model this challenge as an Online Semi-infinite Linear Programming (OSILP) problem and develop a novel LP formulation to solve it approximately. Specifically, we employ function approximation to reduce the number of constraints to a constant $q$ . This addresses a key limitation of traditional online LP algorithms, whose regret bounds typically depend on the number of constraints, leading to poor performance in this setting. We propose a dual-based algorithm to solve our new formulation, which offers broad applicability through the selection of appropriate potential functions. We analyze this algorithm under two classical input models-stochastic input and random permutation-establishing regret bounds of $O(q\sqrt{T})$ and $O\left(\left(q+q\log{T})\sqrt{T}\right)\right)$ respectively. Note that both regret bounds are independent of the number of constraints, which demonstrates the potential of our approach to handle a large or infinite number of constraints. Furthermore, we investigate the potential to improve upon the $O(q\sqrt{T})$ regret and propose a two-stage algorithm, achieving $O(q\log{T} + q/ε)$ regret under more stringent assumptions. We also extend our algorithms to the general function setting. A series of experiments validates that our algorithms outperform existing methods when confronted with a large number of constraints.

Figures & tables

Li and Ye (2022)	stochastic input	$O(m^{2}\log{T}\log{\log{T}})$
	Model	Regret
Li et al. (2023)	stochastic input	$O(m\sqrt{T})$
Li et al. (2023)	random permutation	$O((m+\log{T})\sqrt{T})$
Gao et al. (2025)	stochastic input	$O(m\log{T})$
Our work	stochastic input	$O(q\sqrt{T})$ , $O(q\log{T}+\frac{q}{\epsilon})$
Our work	random permutation	$O((q+q\log{T})\sqrt{T})$

Table 1: Comparison of our work to important prior literature

x_{t}=\begin{cases}1,\penalty\ \penalty\ r_{t}>\bm{a_{t}}^{\top}\Phi\bm{w_{t}}\\ 0,\penalty\ \penalty\ r_{t}\leq\bm{a_{t}}^{\top}\Phi\bm{w_{t}}\end{cases}

Algorithm 1 Main algorithm

x_{t}=\begin{cases}1,\penalty\ \penalty\ r_{t}>\bm{a}_{t}^{\top}\Phi\bm{w}_{t}\\ 0,\penalty\ \penalty\ r_{t}\leq\bm{a}_{t}^{\top}\Phi\bm{w}_{t}\end{cases}

Algorithm 2 Mirror-descent-based algorithm

\tilde{x}_{t}=\begin{cases}1,\penalty\ \penalty\ r_{t}>\bm{a_{t}}^{\top}\Phi\bm{w_{t}}\\ 0,\penalty\ \penalty\ r_{t}\leq\bm{a_{t}}^{\top}\Phi\bm{w_{t}}\end{cases}

Algorithm 3 Fast Convergence Algorithm - Accelerate Stochastic Subgradient Method

\tilde{x}_{t}=\begin{cases}1,\penalty\ \penalty\ r_{t}>\bm{a}_{t}^{\top}\Phi\bm{w}_{t}\\ 0,\penalty\ \penalty\ r_{t}\leq\bm{a}_{t}^{\top}\Phi\bm{w}_{t}\end{cases}

Algorithm 4 Refine Algorithm

x_{t}=\arg\max_{x\in\mathcal{X}}\{f(x;\bm{\theta}_{t})-\bm{g}(x;\bm{\theta}_{t})^{\top}\Phi\bm{w}_{t}\}

(15)

Algorithm 6 Mirror-descent-based algorithm under general function setting

\tilde{x}_{t}=\arg\max_{x\in\mathcal{X}}\{f(x;\bm{\theta}_{t})-\bm{g}(x;\bm{\theta}_{t})^{\top}\Phi\bm{w}_{t}\}

(17)

Algorithm 7

\log{T}

regret Algorithm under general function setting

Panel of Figure 1 — Figure 1: Uniform Distribution with $M=2000$

Panel of Figure 2 — Figure 2: Normal Distribution with $M=2000$

Panel of Figure 3 — Figure 3: Cauchy Distribution with $M=2000$

Panel of Figure 4 — Figure 4: Uniform Distribution with $T=5000$

Panel of Figure 5 — Figure 5: Normal Distribution with $T=5000$

Panel of Figure 6 — Figure 6: Cauchy Distribution with $T=5000$

Panel of Figure 7 — Figure 7: Constraint Num = $2000$

Panel of Figure 8 — Figure 8: Time Horizon T = $5000$

Function Approximation

See all 32 papers

Aug 1, 2024

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

School of Data Science, The Chinese University of Hong Kong, Shenzhen, Guangdong, 518172, P.R. China

Sequential Decision Making Regret Minimization Linear Programming Online Resource Allocation

Ask PDF

Sep 23, 2026

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

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.

Jiameng Lyu

Department of Management Science, School of Management, Fudan University, Shanghai 200433, China

Online Convex Optimization Online Resource Allocation Stochastic Gradient Descent

Ask PDF

Mar 15, 2026

A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming

We study nonstationary Online Linear Programming (OLP), where

n

orders arrive sequentially with reward-resource consumption pairs that form a sequence of independent, but not necessarily identically distributed, random vectors. At the beginning of the planning horizon, the decision-maker is provided with a resource endowment that is sufficient to fulfill a significant portion of the requests. The decision-maker seeks to maximize the expected total reward by making immediate and irrevocable acceptance or rejection decisions for each order, subject to this resource endowment. We focus on the challenging single-sample setting, where only one sample from each of the

n

distributions is available at the start of the planning horizon. We propose a novel re-solving algorithm that integrates a dynamic programming perspective with the dual-based frameworks traditionally employed in stationary environments. In the large-resource regime, where the resource endowment scales linearly with the number of orders, we prove that our algorithm achieves

O((\log n)^2)

regret across a broad class of nonstationary distribution sequences. Our results demonstrate that polylogarithmic regret is attainable even under significant environmental shifts and minimal data availability, bridging the gap between stationary OLP and more volatile real-world resource allocation problems.

Haoran Xu, Owen Shen, Peter Glynn +2

Department of Management Science and Engineering, Stanford University · Operations Research Center, Massachusetts Institute of Technology

Online Resource Allocation Linear Programming Dynamic Regret Minimization

Ask PDF

Abstract

Function Approximation

Explore similar work

Infrequent Resolving Algorithm for Online Linear Programming

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

A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming