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

• URL: http://arxiv.org/abs/2603.16200v1
• Date: Tue, 17 Mar 2026 07:27:43 GMT
• Title: Online Semi-infinite Linear Programming: Efficient Algorithms via Function Approximation
• Abstract summary: We consider the dynamic resource allocation problem where the decision space is finite-dimensional.<n>The solution must satisfy a large or even infinite number of constraints revealed via streaming data or oracle feedback.<n>We employ function approximation to reduce the number of constraints to a constant $q$.
• Score: 5.154847121294575
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Optimal Anytime Algorithms for Online Convex Optimization with Adversarial Constraints [7.798233121583888]
  We propose an anytime online algorithm for the problem of learning a sequence of adversarial convex cost functions.<n>Our proposed algorithm achieves optimal performance bounds without resorting to the standard doubling trick.<n>We show that our algorithm achieves $O(sqrtt)$ regret and $tildeO(sqrtt)$ cumulative constraint violation bounds for any $tgeq 1$.
  arXiv  Detail & Related papers  (2025-10-26T08:35:37Z)
• Infrequent Resolving Algorithm for Online Linear Programming [3.247415064064425]
  Existing online linear programming (OLP) algorithms fall into two categories: LP-based algorithms and LP-free algorithms.<n>We propose a well-performing algorithm, that solves LPs at a few selected time points and conducts first-order computations at other time points.<n>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.
  arXiv  Detail & Related papers  (2024-08-01T11:09:01Z)
• Projection-Free Online Convex Optimization with Time-Varying Constraints [19.993839085310643]
  We consider the setting of online convex optimization with adversarial time-varying constraints. Motivated by scenarios in which the fixed feasible set is difficult to project on, we consider projection-free algorithms that access this set only through a linear optimization oracle (LOO) We present an algorithm that, on a sequence of length $T$ and using overall $T$ calls to the LOO, guarantees $tildeO(T3/4)$ regret w.r.t. the losses and $O(T 7/8)$ constraints violation.
  arXiv  Detail & Related papers  (2024-02-13T21:13:29Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  We consider learning in an adversarial Decision Process (MDP) where the loss functions can change arbitrarily over $K$ episodes. This paper provides two algorithms that improve the regret to $tildemathcal O(K2/3)$ in the same setting.
  arXiv  Detail & Related papers  (2023-01-30T14:37:21Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
  We consider the problem of planning with participation constraints introduced in [Zhang et al., 2022] In this problem, a principal chooses actions in a decision process, resulting in separate utilities for the principal and the agent. We provide the first-time exact algorithm for this problem for finite-horizon settings, where previously only an additive $varepsilon$-approximation was known.
  arXiv  Detail & Related papers  (2022-05-16T15:47:41Z)
• Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints [39.715977181666766]
  We study regret for infinite-horizon average-reward Markov Decision Processes (MDPs) under cost constraints. Our algorithm ensures $widetildeO(sqrtT)$ regret and constant constraint violation for ergodic MDPs. These are the first set of provable algorithms for weakly communicating MDPs with cost constraints.
  arXiv  Detail & Related papers  (2022-01-31T23:52:34Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  We present a meta-algorithm that adapts to the optimal complexity with $tildeO(L5/6 T2/3)$ regret. We also show that the meta-algorithm automatically admits significantly improved instance-dependent regret bounds.
  arXiv  Detail & Related papers  (2020-11-19T10:00:54Z)
• Gradient-Variation Bound for Online Convex Optimization with Constraints [25.002868073267464]
  We study online convex optimization with constraints consisting of multiple functional constraints and a relatively simple constraint set, such as a Euclidean ball. First-order methods achieve an $mathcalO(sqrtT)$ regret and an $mathcalO(1)$ constraint violation, but do not take into account the structural information of the problem. In this paper, we provide an emphinstance-dependent bound for online convex optimization with complex constraints obtained by a novel online primal-dual mirror-prox algorithm.
  arXiv  Detail & Related papers  (2020-06-22T17:38:14Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  A fundamental component of neural network verification is the computation of bounds on the values their outputs can take. We propose a novel approach based on Lagrangian Decomposition. We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
  arXiv  Detail & Related papers  (2020-02-24T17:55:10Z)
• Second-order Conditional Gradient Sliding [70.88478428882871]
  We present the emphSecond-Order Conditional Gradient Sliding (SOCGS) algorithm.<n>The SOCGS algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations.<n>It is useful when the feasible region can only be accessed efficiently through a linear optimization oracle.
  arXiv  Detail & Related papers  (2020-02-20T17:52:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.