Learning-Assisted Algorithm Unrolling for Online Optimization with Budget Constraints

Jianyi Yang, Shaolei Ren

Abstract

Online Optimization with Budget Constraints (OOBC) presents significant challenges in scenarios with short decision horizons and strict resource limits. Traditional iterative algorithms often fail to converge quickly enough, while black-box reinforcement learning models struggle with robustness and constraint satisfaction. This paper proposes Learning-Assisted Algorithm Unrolling (LAAU), a hybrid framework that unrolls the optimization process and utilizes machine learning to predict Lagrangian multipliers. By embedding a differentiable optimization layer, LAAU leverages problem structure to achieve near-optimal utility and high robustness. Evaluations on real-world cloud workload data show that LAAU outperforms existing heuristics and traditional dual methods.

Introduction

In many real-world applications, such as cloud resource allocation or power grid management, decisions must be made sequentially under strict total budget constraints. These problems, termed Online Optimization with Budget Constraints (OOBC), are particularly difficult when the decision window is short. In such "short-horizon" settings, standard iterative methods like Dual Mirror Descent may not have sufficient time to converge to an optimal solution. Furthermore, physical constraints in these domains are often "hard," meaning violations are unacceptable.

The LAAU Framework

The core innovation of this work is Learning-Assisted Algorithm Unrolling (LAAU). Rather than treating the entire decision process as a black box, LAAU unrolls the optimization pipeline into a sequence of units, each corresponding to a time step.

Architecture of the LAAU framework showing the unrolling units and the internal components of each unit.

As shown in Figure 1, each unrolling unit consists of three primary components:

  1. ML-based Multiplier Update: A neural network predicts the Lagrangian multiplier ($\lambda_t$), which acts as a "shadow price" for the resource. This allows the model to learn complex temporal patterns and adjust prices based on the remaining budget.
  2. Optimization Layer: This layer takes the predicted price and solves a standard convex optimization problem to determine the optimal action ($x_t$) for the current step.
  3. Budget Update: The framework explicitly tracks and updates the remaining budget, ensuring that the physical constraints of the problem are respected.

To enable end-to-end training via backpropagation, the authors utilize Karush-Kuhn-Tucker (KKT) conditions to derive gradients through the optimization layer, allowing the ML model to learn how its price predictions influence the final utility and budget consumption.

Experimental Evaluation

The researchers evaluated LAAU using the Azure cloud workload dataset, focusing on a resource allocation task aimed at maximizing weighted fairness under strict CPU budget constraints. LAAU was compared against several benchmarks, including heuristics (Equal allocation), traditional methods (DGD, MW), and end-to-end Reinforcement Learning (RL).

Average utility comparison across different algorithms for varying episode lengths N.

The results, summarized in Figure 2, highlight several key findings:

  • Superior Utility: LAAU consistently achieves higher average utility than traditional experts like DGD and MW, especially in short episodes ($N=10$).
  • Near-Oracle Performance: The performance of LAAU closely approaches the "Offline Optimal" (OPT), which represents the theoretical maximum utility achievable with full future knowledge.
  • Robustness to Distribution Shift: LAAU demonstrated significant robustness to distribution shifts. While pure RL models saw performance drops when noise was introduced to the training data, LAAU's reliance on the underlying problem structure allowed it to maintain high utility.

Conclusion

LAAU represents a significant step forward in solving constrained online optimization problems. By combining the predictive power of machine learning with the mathematical rigor of optimization unrolling, it provides a robust and efficient solution for short-horizon resource allocation. Future work will focus on extending this framework to non-convex problems and multi-agent systems.

Summary updated

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.
BibTeX
@inproceedings{yang2023learning,
  author = {Jianyi Yang and Shaolei Ren},
  title = {{Learning-Assisted Algorithm Unrolling for Online Optimization with Budget Constraints}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i9.26278},
}
Figure