An Online Algorithm for Chance Constrained Resource Allocation
- URL: http://arxiv.org/abs/2303.03254v1
- Date: Mon, 6 Mar 2023 16:17:19 GMT
- Title: An Online Algorithm for Chance Constrained Resource Allocation
- Authors: Yuwei Chen, Zengde Deng, Yinzhi Zhou, Zaiyi Chen, Yujie Chen, Haoyuan
Hu
- Abstract summary: This paper studies the online resource allocation problem (RAP) with chance constraints.
To the best of our knowledge, this is the first time chance constraints are introduced in the online RAP problem.
- Score: 10.791923293928987
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies the online stochastic resource allocation problem (RAP)
with chance constraints. The online RAP is a 0-1 integer linear programming
problem where the resource consumption coefficients are revealed column by
column along with the corresponding revenue coefficients. When a column is
revealed, the corresponding decision variables are determined instantaneously
without future information. Moreover, in online applications, the resource
consumption coefficients are often obtained by prediction. To model their
uncertainties, we take the chance constraints into the consideration. To the
best of our knowledge, this is the first time chance constraints are introduced
in the online RAP problem. Assuming that the uncertain variables have known
Gaussian distributions, the stochastic RAP can be transformed into a
deterministic but nonlinear problem with integer second-order cone constraints.
Next, we linearize this nonlinear problem and analyze the performance of
vanilla online primal-dual algorithm for solving the linearized stochastic RAP.
Under mild technical assumptions, the optimality gap and constraint violation
are both on the order of $\sqrt{n}$. Then, to further improve the performance
of the algorithm, several modified online primal-dual algorithms with heuristic
corrections are proposed. Finally, extensive numerical experiments on both
synthetic and real data demonstrate the applicability and effectiveness of our
methods.
Related papers
- Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
We propose a Trust Sequential Quadratic Programming method to find both first and second-order stationary points.
To converge to first-order stationary points, our method computes a gradient step in each iteration defined by minimizing a approximation of the objective subject.
To converge to second-order stationary points, our method additionally computes an eigen step to explore the negative curvature the reduced Hessian matrix.
arXiv Detail & Related papers (2024-09-24T04:39:47Z) - Offline Policy Optimization in RL with Variance Regularizaton [142.87345258222942]
We propose variance regularization for offline RL algorithms, using stationary distribution corrections.
We show that by using Fenchel duality, we can avoid double sampling issues for computing the gradient of the variance regularizer.
The proposed algorithm for offline variance regularization (OVAR) can be used to augment any existing offline policy optimization algorithms.
arXiv Detail & Related papers (2022-12-29T18:25:01Z) - Learning-Augmented Algorithms for Online Linear and Semidefinite
Programming [9.849604820019394]
Semidefinite programming (SDP) is a unifying framework that generalizes both linear and quadratically-constrained programming.
There exist known impossibility results for approxing the optimal solution when constraints for covering SDPs arrive in an online fashion.
We show that if the predictor is accurate, we can efficiently bypass these impossibility results and achieve a constant-factor approximation to the optimal solution.
arXiv Detail & Related papers (2022-09-21T19:16:29Z) - Online Contextual Decision-Making with a Smart Predict-then-Optimize
Method [4.061135251278187]
We study an online contextual decision-making problem with resource constraints.
We propose an algorithm that mixes a prediction step based on the "Smart Predict-then- (SPO)" method with a dual update step based on mirror descent.
We prove regret bounds and demonstrate that the overall convergence rate of our method depends on the $mathcalO(T-1/2)$ convergence of online mirror descent.
arXiv Detail & Related papers (2022-06-15T06:16:13Z) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
We consider online statistical inference of constrained nonlinear optimization problems.
We apply the Sequential Quadratic Programming (StoSQP) method to solve these problems.
arXiv Detail & Related papers (2022-05-27T00:34:03Z) - Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
We provide the first oracle-efficient, no-regret algorithms in this setting.
We show that if a function class is learnable in the classical setting, then there is an oracle-efficient, no-regret algorithm for contextual bandits.
arXiv Detail & Related papers (2022-02-09T19:22:34Z) - Online Allocation with Two-sided Resource Constraints [44.5635910908944]
We consider an online allocation problem subject to lower and upper resource constraints, where the requests arrive sequentially.
We propose a new algorithm that obtains $1-O(fracepsilonalpha-epsilon)$ -competitive ratio for the offline problems that know the entire requests ahead of time.
arXiv Detail & Related papers (2021-12-28T02:21:06Z) - Stochastic Online Linear Regression: the Forward Algorithm to Replace
Ridge [24.880035784304834]
We derive high probability regret bounds for online ridge regression and the forward algorithm.
This enables us to compare online regression algorithms more accurately and eliminate assumptions of bounded observations and predictions.
arXiv Detail & Related papers (2021-11-02T13:57:53Z) - A spectral algorithm for robust regression with subgaussian rates [0.0]
We study a new linear up to quadratic time algorithm for linear regression in the absence of strong assumptions on the underlying distributions of samples.
The goal is to design a procedure which attains the optimal sub-gaussian error bound even though the data have only finite moments.
arXiv Detail & Related papers (2020-07-12T19:33:50Z) - Fast OSCAR and OWL Regression via Safe Screening Rules [97.28167655721766]
Ordered $L_1$ (OWL) regularized regression is a new regression analysis for high-dimensional sparse learning.
Proximal gradient methods are used as standard approaches to solve OWL regression.
We propose the first safe screening rule for OWL regression by exploring the order of the primal solution with the unknown order structure.
arXiv Detail & Related papers (2020-06-29T23:35:53Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
We propose a new randomized algorithm for solving L2-regularized least-squares problems based on sketching.
We consider two of the most popular random embeddings, namely, Gaussian embeddings and the Subsampled Randomized Hadamard Transform (SRHT)
arXiv Detail & Related papers (2020-06-10T15:00:09Z)
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.