Learning-Assisted Algorithm Unrolling for Online Optimization with Budget Constraints

• URL: http://arxiv.org/abs/2212.01689v1
• Date: Sat, 3 Dec 2022 20:56:29 GMT
• Title: Learning-Assisted Algorithm Unrolling for Online Optimization with Budget Constraints
• Authors: Jianyi Yang, Shaolei Ren
• Abstract summary: We propose a new machine learning (ML) assisted unrolling approach, called LAAU (Learning-Assisted Algorithm Unrolling) For efficient training via backpropagation, we derive gradients of the decision pipeline over time. We also provide the average cost bounds for two cases when training data is available offline and collected online, respectively.
• Score: 27.84415856657607
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Online optimization with multiple budget constraints is challenging since the online decisions over a short time horizon are coupled together by strict inventory constraints. The existing manually-designed algorithms cannot achieve satisfactory average performance for this setting because they often need a large number of time steps for convergence and/or may violate the inventory constraints. In this paper, we propose a new machine learning (ML) assisted unrolling approach, called LAAU (Learning-Assisted Algorithm Unrolling), which unrolls the online decision pipeline and leverages an ML model for updating the Lagrangian multiplier online. For efficient training via backpropagation, we derive gradients of the decision pipeline over time. We also provide the average cost bounds for two cases when training data is available offline and collected online, respectively. Finally, we present numerical results to highlight that LAAU can outperform the existing baselines.

Related papers

• Online-BLS: An Accurate and Efficient Online Broad Learning System for Data Stream Classification [52.251569042852815]
  We introduce an online broad learning system framework with closed-form solutions for each online update. We design an effective weight estimation algorithm and an efficient online updating strategy. Our framework is naturally extended to data stream scenarios with concept drift and exceeds state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-01-28T13:21:59Z)
• Optimization Proxies using Limited Labeled Data and Training Time -- A Semi-Supervised Bayesian Neural Network Approach [2.943640991628177]
  Constrained optimization problems arise in various engineering system operations such as inventory management electric power grids. This work introduces a learning scheme using Bayesian Networks (BNNs) to solve constrained optimization problems under limited data and restricted model times. We show that the proposed learning method outperforms conventional BNN and deep neural network (DNN) architectures.
  arXiv  Detail & Related papers  (2024-10-04T02:10:20Z)
• Offline Reinforcement Learning for Learning to Dispatch for Job Shop Scheduling [0.9831489366502301]
  Job Shop Scheduling Problem (JSSP) is a complex optimization problem. Online Reinforcement Learning (RL) has shown promise by quickly finding acceptable solutions for JSSP. We introduce Offline Reinforcement Learning for Learning to Dispatch (Offline-LD)
  arXiv  Detail & Related papers  (2024-09-16T15:18:10Z)
• Online Learning of Weakly Coupled MDP Policies for Load Balancing and Auto Scaling [42.6574685545681]
  This paper introduces a novel model and algorithms for tuning load balancers coupled with auto scalers, considering bursty traffic arriving at finite queues. We begin by presenting the problem as a weakly coupled Markov Decision Processes (MDP), solvable via a linear program (LP) We extend it to tackle the problem of online parameter learning and policy optimization using a two-timescale algorithm based on the LP Lagrangian.
  arXiv  Detail & Related papers  (2024-06-20T09:34:24Z)
• Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
  A machine learning (ML) model is trained to emulate a constrained optimization solver. This paper proposes an alternative approach, in which the ML model is trained to predict dual solution estimates directly. It enables an end-to-end training scheme is which the dual objective is as a loss function, and solution estimates toward primal feasibility, emulating a Dual Ascent method.
  arXiv  Detail & Related papers  (2024-03-06T04:43:22Z)
• Action-Quantized Offline Reinforcement Learning for Robotic Skill Learning [68.16998247593209]
  offline reinforcement learning (RL) paradigm provides recipe to convert static behavior datasets into policies that can perform better than the policy that collected the data. In this paper, we propose an adaptive scheme for action quantization. We show that several state-of-the-art offline RL methods such as IQL, CQL, and BRAC improve in performance on benchmarks when combined with our proposed discretization scheme.
  arXiv  Detail & Related papers  (2023-10-18T06:07:10Z)
• Efficient Methods for Non-stationary Online Learning [61.63338724659592]
  We present efficient methods for optimizing dynamic regret and adaptive regret, which reduce the number of projections per round from $mathcalO(log T)$ to $1$. We also study an even strengthened measure, namely the interval dynamic regret'', and reduce the number of projections per round from $mathcalO(log2 T)$ to $1$.
  arXiv  Detail & Related papers  (2023-09-16T07:30:12Z)
• A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical Computation Offloading [62.34538208323411]
  We propose a multi-head ensemble multi-task learning (MEMTL) approach with a shared backbone and multiple prediction heads (PHs) MEMTL outperforms benchmark methods in both the inference accuracy and mean square error without requiring additional training data.
  arXiv  Detail & Related papers  (2023-09-02T11:01:16Z)
• Online Convex Optimization with Long Term Constraints for Predictable Sequences [5.964436882344728]
  We study a specific framework of OCO called it OCO with long term constraints. Long term constraints are introduced as an alternative to reduce the complexity of the projection at every update step in online optimization. We show that, with a predictor that can supply the information of the next function in the sequence, our algorithm can achieve an overall regret and constraint violation rate that is strictly less than the rate that is achievable without prediction.
  arXiv  Detail & Related papers  (2022-10-30T03:50:53Z)
• Augmented Lagrangian Methods for Time-varying Constrained Online Convex Optimization [1.662966122370634]
  We consider online convex optimization (OCO) with time-varying loss and constraint functions. We first develop a class of model-based augmented Lagrangian methods (MALM) for time-varying functional constrained OCO. numerical results for several examples of constrained OCO are presented to demonstrate the efficiency of the proposed algorithms.
  arXiv  Detail & Related papers  (2022-05-19T14:03:25Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

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.